共查询到17条相似文献,搜索用时 328 毫秒
1.
用罚函数求解线性双层规划的全局优化方法 总被引:5,自引:0,他引:5
用罚函数法将线性双层规划转化为带罚函数子项的双线性规划问题,由于其全局最优解可在约束域的极点上找到,利用对偶理论给出了一种求解该双线性规划的方法,并证明当罚因子大于某一正数时,双线性规划的解就是原线性双层规划的全局最优解。 相似文献
2.
研究了线性半向量二层规划问题的全局优化方法. 利用下层问题的对偶间隙构造了线性半向量二层规划问题的罚问题, 通过分析原问题的最优解与罚问题可行域顶点之间的关系, 将线性半向量二层规划问题转化为有限个线性规划问题, 从而得到线性半向量二层规划问题的全局最优解. 数值结果表明所设计的全局优化方法对线性半向量二层规划问题是可行的. 相似文献
3.
本文对带有不定二次约束且目标函数为非凸二次函数的最优化问题提出了一类新的确定型全局优化算法,通过对目标函数和约束函数的线性下界估计,建立了原规划的松弛线性规划,通过对松弛线性规划可行域的细分以及一系列松弛线性规划的求解过程,得到原问题的全局最优解.我们从理论上证明了算法能收敛到原问题的全局最优解. 相似文献
4.
对许多工程设计中常用的广义几何规划问题(GGP)提出一种确定性全局优化算法,该算法利用目标和约束函数的线性下界估计,建立GGP的松弛线性规划(RLP),从而将原来非凸问题(GGP)的求解过程转化为求解一系列线性规划问题(RLP).通过可行域的连续细分以及一系列线性规划的解,提出的分枝定界算法收敛到GGP的全局最优解,且数值例子表明了算法的可行性. 相似文献
5.
6.
为求线性比试和问题的全局最优解,本文给出了一个分支定界算法.通过一个等价问题和一个新的线性化松弛技巧,初始的非凸规划问题归结为一系列线性规划问题的求解.借助于这一系列线性规划问题的解,算法可收敛于初始非凸规划问题的最优解.算法的计算量主要是一些线性规划问题的求解.数值算例表明算法是切实可行的. 相似文献
7.
8.
通过分析双层线性规划可行域的结构特征和全局最优解在约束域的极点上达到这一特性,对单纯形方法中进基变量的选取法则进行适当修改后,给出了一个求解双层线性规划局部最优解方法,然后引进上层目标函数对应的一种割平面约束来修正当前局部最优解,直到求得双层线性规划的全局最优解.提出的算法具有全局收敛性,并通过算例说明了算法的求解过程. 相似文献
9.
10.
本文对一类新的分式规划问题(FP)提出了一个有效的全局优化方法.首先将问题(FP)转化为其等价问题(EFP),然后利用线性化技术建立了(EFP)的松弛线性规划问题(RLP),通过对其可行域的细分和求解一系列的线性规划,得到问题(EFP)的全局最优值的上下界.理论证明和数值试验的结果都表明该算法能有效求解问题(FP),推广了线性比式和的情形. 相似文献
11.
This paper studies a bilevel polynomial program involving box data uncertainties in both its linear constraint set and its lower-level optimization problem. We show that the robust global optimal value of the uncertain bilevel polynomial program is the limit of a sequence of values of Lasserre-type hierarchy of semidefinite linear programming relaxations. This is done by first transforming the uncertain bilevel polynomial program into a single-level non-convex polynomial program using a dual characterization of the solution of the lower-level program and then employing the powerful Putinar’s Positivstellensatz of semi-algebraic geometry. We provide a numerical example to show how the robust global optimal value of the uncertain bilevel polynomial program can be calculated by solving a semidefinite programming problem using the MATLAB toolbox YALMIP. 相似文献
12.
Deriving the Properties of Linear Bilevel Programming via a Penalty Function Approach 总被引:7,自引:0,他引:7
Z. K. Xu 《Journal of Optimization Theory and Applications》1999,103(2):441-456
For the linear bilevel programming problem, we propose an assumption weaker than existing assumptions, while achieving similar results via a penalty function approach. The results include: equivalence between (i) existence of a solution to the problem, (ii) existence of an exact penalty function approach for solving the problem, and (iii) achievement of the optimal value of the equivalent form of the problem at some vertex of a certain polyhedral convex set. We prove that the assumption is both necessary and sufficient for the linear bilevel programming problem to admit an exact penalty function formulation, provided that the equivalent form of the problem has a feasible solution. A method is given for computing the minimal penalty function parameter value. This method can be executed by solving a set of linear programming problems. Lagrangian duality is also presented. 相似文献
13.
The penalty function method, presented many years ago, is an important numerical method for the mathematical programming problems. In this article, we propose a dual-relax penalty function approach, which is significantly different from penalty function approach existing for solving the bilevel programming, to solve the nonlinear bilevel programming with linear lower level problem. Our algorithm will redound to the error analysis for computing an approximate solution to the bilevel programming. The error estimate is obtained among the optimal objective function value of the dual-relax penalty problem and of the original bilevel programming problem. An example is illustrated to show the feasibility of the proposed approach. 相似文献
14.
Zhiqing Meng Chuangyin Dang Rui Shen Ming Jiang 《Journal of Optimization Theory and Applications》2012,153(2):377-387
Penalty methods are very efficient in finding an optimal solution to constrained optimization problems. In this paper, we
present an objective penalty function with two penalty parameters for inequality constrained bilevel programming under the
convexity assumption to the lower level problem. Under some conditions, an optimal solution to a bilevel programming defined
by the objective penalty function is proved to be an optimal solution to the original bilevel programming. Moreover, based
on the objective penalty function, an algorithm is developed to obtain an optimal solution to the original bilevel programming,
with its convergence proved under some conditions. 相似文献
15.
16.
In this paper we propose an optimal method for solving the linear bilevel programming problem with no upper-level constraint. The main idea of this method is that the initial point which is in the feasible region goes forward along the optimal direction firstly. When the iterative point reaches the boundary of the feasible region, it can continue to go forward along the suboptimal direction. The iteration is terminated until the iterative point cannot go forward along the suboptimal direction and effective direction, and the new iterative point is the solution of the lower-level programming. An algorithm which bases on the main idea above is presented and the solution obtained via this algorithm is proved to be optimal solution to the bilevel programming problem. This optimal method is effective for solving the linear bilevel programming problem. 相似文献
17.
《European Journal of Operational Research》1999,114(1):188-197
Bilevel programming involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. In this paper we consider the bilevel linear/linear fractional programming problem in which the objective function of the first level is linear, the objective function of the second level is linear fractional and the feasible region is a polyhedron. For this problem we prove that an optimal solution can be found which is an extreme point of the polyhedron. Moreover, taking into account the relationship between feasible solutions to the problem and bases of the technological coefficient submatrix associated to variables of the second level, an enumerative algorithm is proposed that finds a global optimum to the problem. 相似文献