共查询到20条相似文献,搜索用时 78 毫秒
1.
We are interested in a class of linear bilevel programs where the upper level is a linear scalar optimization problem and the lower level is a linear multi-objective optimization problem. We approach this problem via an exact penalty method. Then, we propose an algorithm illustrated by numerical examples. 相似文献
2.
Descent approaches for quadratic bilevel programming 总被引:7,自引:0,他引:7
The bilevel programming problem involves two optimization problems where the data of the first one is implicitly determined by the solution of the second. In this paper, we introduce two descent methods for a special instance of bilevel programs where the inner problem is strictly convex quadratic. The first algorithm is based on pivot steps and may not guarantee local optimality. A modified steepest descent algorithm is presented to overcome this drawback. New rules for computing exact stepsizes are introduced and a hybrid approach that combines both strategies is discussed. It is proved that checking local optimality in bilevel programming is a NP-hard problem.Support of this work has been provided by INIC (Portugal) under Contract 89/EXA/5, by FCAR (Québec), and by NSERC and DND-ARP (Canada). 相似文献
3.
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. 相似文献
4.
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. 相似文献
5.
We consider a hierarchical system where a leader incorporates into its strategy the reaction of the follower to its decision.
The follower's reaction is quite generally represented as the solution set to a monotone variational inequality. For the solution
of this nonconvex mathematical program a penalty approach is proposed, based on the formulation of the lower level variational
inequality as a mathematical program. Under natural regularity conditions, we prove the exactness of a certain penalty function,
and give strong necessary optimality conditions for a class of generalized bilevel programs. 相似文献
6.
Weak linear bilevel programming problems: existence of solutions via a penalty method 总被引:1,自引:0,他引:1
Abdelmalek Aboussoror Abdelatif Mansouri 《Journal of Mathematical Analysis and Applications》2005,304(1):399-408
We are concerned with a class of weak linear bilevel programs with nonunique lower level solutions. For such problems, we give via an exact penalty method an existence theorem of solutions. Then, we propose an algorithm. 相似文献
7.
J. Glackin J. G. Ecker M. Kupferschmid 《Journal of Optimization Theory and Applications》2009,140(2):197-212
We present an algorithm for solving bilevel linear programs that uses simplex pivots on an expanded tableau. The algorithm
uses the relationship between multiple objective linear programs and bilevel linear programs along with results for minimizing
a linear objective over the efficient set for a multiple objective problem. Results in multiple objective programming needed
are presented. We report computational experience demonstrating that this approach is more effective than a standard branch-and-bound
algorithm when the number of leader variables is small. 相似文献
8.
Le Thi Hoai An Pham Dinh Tao Nam Nguyen Canh Nguyen Van Thoai 《Journal of Global Optimization》2009,44(3):313-337
We propose a method for finding a global solution of a class of nonlinear bilevel programs, in which the objective function
in the first level is a DC function, and the second level consists of finding a Karush-Kuhn-Tucker point of a quadratic programming
problem. This method is a combination of the local algorithm DCA in DC programming with a branch and bound scheme well known
in discrete and global optimization. Computational results on a class of quadratic bilevel programs are reported. 相似文献
9.
双层规划在经济、交通、生态、工程等领域有着广泛而重要的应用.目前对双层规划的研究主要是基于强双层规划和弱双层规划.然而,针对弱双层规划的求解方法却鲜有研究.研究求解弱线性双层规划问题的一种全局优化方法,首先给出弱线性双层规划问题与其松弛问题在最优解上的关系,然后利用线性规划的对偶理论和罚函数方法,讨论该松弛问题和它的罚问题之间的关系.进一步设计了一种求解弱线性双层规划问题的全局优化方法,该方法的优势在于它仅仅需要求解若干个线性规划问题就可以获得原问题的全局最优解.最后,用一个简单算例说明了所提出的方法是可行的. 相似文献
10.
Linear mixed 0–1 integer programming problems may be reformulated as equivalent continuous bilevel linear programming (BLP)
problems. We exploit these equivalences to transpose the concept of mixed 0–1 Gomory cuts to BLP. The first phase of our new
algorithm generates Gomory-like cuts. The second phase consists of a branch-and-bound procedure to ensure finite termination
with a global optimal solution. Different features of the algorithm, in particular, the cut selection and branching criteria
are studied in details. We propose also a set of algorithmic tests and procedures to improve the method. Finally, we illustrate
the performance through numerical experiments. Our algorithm outperforms pure branch-and-bound when tested on a series of
randomly generated problems.
Work of the authors was partially supported by FCAR, MITACS and NSERC grants. 相似文献
11.
Bilevel programming: A survey 总被引:15,自引:0,他引:15
Benoít Colson Patrice Marcotte Gilles Savard 《4OR: A Quarterly Journal of Operations Research》2005,3(2):87-107
This paper provides an introductory survey of a class of optimization problems known as bilevel programming. We motivate this class through a simple application, and then proceed with the general formulation of bilevel programs. We consider various cases (linear, linear-quadratic, nonlinear), describe their main properties and give an overview of solution approaches.Received: April 2005, Revised: May 2005, AMS classification:
90C05, 90C11, 90C20, 90C27, 90C3D, 65K05 相似文献
12.
' 1 IntroductionWe collsider the fOllowi11g bilevel programndng problen1:max f(x, y),(BP) s.t.x E X = {z E RnIAx = b,x 2 0}, (1)y e Y(x).whereY(x) = {argmaxdTyIDx Gy 5 g, y 2 0}, (2)and b E R", d, y E Rr, g E Rs, A, D.and G are m x n1 s x n aild 8 x r matrices respectively. If itis not very difficult to eva1uate f(and/or Vf) at all iteration points, there are many algorithmeavailable fOr solving problem (BP) (see [1,2,3etc1). However, in some problems (see [4]), f(x, y)is too com… 相似文献
13.
Parametric global optimisation for bilevel programming 总被引:2,自引:2,他引:0
Nuno P. Faísca Vivek Dua Berç Rustem Pedro M. Saraiva Efstratios N. Pistikopoulos 《Journal of Global Optimization》2007,38(4):609-623
We propose a global optimisation approach for the solution of various classes of bilevel programming problems (BLPP) based
on recently developed parametric programming algorithms. We first describe how we can recast and solve the inner (follower’s)
problem of the bilevel formulation as a multi-parametric programming problem, with parameters being the (unknown) variables
of the outer (leader’s) problem. By inserting the obtained rational reaction sets in the upper level problem the overall problem
is transformed into a set of independent quadratic, linear or mixed integer linear programming problems, which can be solved
to global optimality. In particular, we solve bilevel quadratic and bilevel mixed integer linear problems, with or without
right-hand-side uncertainty. A number of examples are presented to illustrate the steps and details of the proposed global
optimisation strategy. 相似文献
14.
Khosrow Moshirvaziri Mahyar A. Amouzegar Stephen E. Jacobsen 《Journal of Global Optimization》1996,8(3):235-243
A method of constructing test problems for linear bilevel programming problems is presented. The method selects a vertex of the feasible region, far away from the solution of the relaxed linear programming problem, as the global solution of the bilevel problem. A predetermined number of constraints are systematically selected to be assigned to the lower problem. The proposed method requires only local vertex search and solutions to linear programs. 相似文献
15.
《Operations Research Letters》2023,51(1):84-91
In this paper, we study the bilevel programming problem with discrete polynomial lower level problem. We start by transforming the problem into a bilevel problem comprising a semidefinite program (SDP for short) in the lower level problem. Then, we are able to deduce some conditions of existence of solutions for the original problem. After that, we again change the bilevel problem with SDP in the lower level problem into a semi-infinite program. With the aid of the exchange technique, for simple bilevel programs, an algorithm for computing a global optimal solution is suggested, the convergence is shown, and a numerical example is given. 相似文献
16.
A Trust-Region Method for Nonlinear Bilevel Programming: Algorithm and Computational Experience 总被引:7,自引:0,他引:7
We consider the approximation of nonlinear bilevel mathematical programs by solvable programs of the same type, i.e., bilevel programs involving linear approximations of the upper-level objective and all constraint-defining functions, as well as a quadratic approximation of the lower-level objective. We describe the main features of the algorithm and the resulting software. Numerical experiments tend to confirm the promising behavior of the method. 相似文献
17.
18.
19.
This paper focuses on bilevel programs with a convex lower-level problem violating Slater’s constraint qualification. We relax the constrained domain of the lower-level problem. Then, an approximate solution of the original bilevel program can be obtained by solving this perturbed bilevel program. As the lower-level problem of the perturbed bilevel program satisfies Slater’s constraint qualification, it can be reformulated as a mathematical program with complementarity constraints which can be solved by standard algorithms. The lower convergence properties of the constraint set mapping and the solution set mapping of the lower-level problem of the perturbed bilevel program are expanded. We show that the solutions of a sequence of the perturbed bilevel programs are convergent to that of the original bilevel program under some appropriate conditions. And this convergence result is applied to simple trilevel programs. 相似文献
20.
Exact Penalty Functions for Convex Bilevel Programming Problems 总被引:2,自引:0,他引:2
Liu G. S. Han J. Y. Zhang J. Z. 《Journal of Optimization Theory and Applications》2001,110(3):621-643
In this paper, we propose a new constraint qualification for convex bilevel programming problems. Under this constraint qualification, a locally and globally exact penalty function of order 1 for a single-level reformulation of convex bilevel programming problems is given without requiring the linear independence condition and the strict complementarity condition to hold in the lower-level problem. Based on these results, locally and globally exact penalty functions for two other single-level reformulations of convex bilevel programming problems can be obtained. Furthermore, sufficient conditions for partial calmness to hold in some single-level reformulations of convex bilevel programming problems can be given. 相似文献