1,935 research outputs found
KKT reformulation and necessary conditions for optimality in nonsmooth bilevel optimization
No full textFor a long time, the bilevel programming problem has essentially been considered as a special case of mathematical programs with equilibrium constraints (MPECs), in particular when the so-called KKT reformulation is in question. Recently though, this widespread believe was shown to be false in general. In this paper, other aspects of the difference between both problems are revealed as we consider the KKT approach for the nonsmooth bilevel program. It turns out that the new inclusion (constraint) which appears as a consequence of the partial subdifferential of the lower-level Lagrangian (PSLLL) places the KKT reformulation of the nonsmooth bilevel program in a new class of mathematical program with both set-valued and complementarity constraints. While highlighting some new features of this problem, we attempt here to establish close links with the standard optimistic bilevel program. Moreover, we discuss possible natural extensions for C-, M-, and S-stationarity concepts. Most of the results rely on a coderivative estimate for the PSLLL that we also provide in this paper
The generalized Mangasarian-Fromowitz constraint qualification and optimality conditions for bilevel programs
No full textWe consider the optimal value reformulation of the bilevel programming problem. It is shown that the Mangasarian-Fromowitz constraint qualification in terms of the basic generalized differentiation constructions of Mordukhovich, which is weaker than the one in terms of Clarke’s nonsmooth tools, fails without any restrictive assumption. Some weakened forms of this constraint qualification are then suggested, in order to derive Karush-Kuhn-Tucker type optimality conditions for the aforementioned problem. Considering the partial calmness, a new characterization is suggested and the link with the previous constraint qualifications is analyzed
On the Karush–Kuhn–Tucker reformulation of the bilevel optimization problem
No full textThis paper is mainly concerned with the classical KKT reformulation and the primal KKT reformulation (also known as an optimization problem with generalized equation constraint (OPEC)) of the optimistic bilevel optimization problem. A generalization of the MFCQ to an optimization problem with operator constraint is applied to each of these reformulations, hence leading to new constraint qualifications (CQs) for the bilevel optimization problem. M- and S-type stationarity conditions tailored for the problem are derived as well. Considering the close link between the aforementioned reformulations, similarities and relationships between the corresponding CQs and optimality conditions are highlighted. In this paper, a concept of partial calmness known for the optimal value reformulation is also introduced for the primal KKT reformulation and used to recover the M-stationarity conditions
The bilevel programming problem: reformulations, constraint qualifications and optimality conditions
No full textWe consider the bilevel programming problem and its optimal value and KKT one level reformulations. The two reformulations are studied in a unified manner and compared in terms of optimal solutions, constraint qualifications and optimality conditions. We also show that any bilevel programming problem where the lower level problem is linear with respect to the lower level variable, is partially calm without any restrictive assumption. Finally, we consider the bilevel demand adjustment problem in transportation, and show how KKT type optimality conditions can be obtained under the partial calmness, using the differential calculus of Mordukhovich
Bilevel road pricing: theoretical analysis and optimality conditions
No full textWe consider the bilevel road pricing problem. In contrary to the Karush-Kuhn-Tucker (one level) reformulation, the optimal value reformulation is globally and locally equivalent to the initial problem. Moreover, in the process of deriving optimality conditions, the optimal value reformulation helps to preserve some essential data involved in the traffic assignment problem that may disappear with the Karush-Kuhn-Tucker (KKT) one. Hence, we consider in this work the optimal value reformulation of the bilevel road pricing problem; using some recent developments in nonsmooth analysis, we derive implementable KKT type optimality conditions for the problem containing all the necessary information. The issue of estimating the (fixed) demand required for the road pricing problem is a quite difficult problem which has been also addressed in recent years using bilevel programming. We also show how the ideas used in designing KKT type optimality conditions for the road pricing problem can be applied to derive optimality conditions for the origin-destination (O-D) matrix estimation problem. Many other theoretical aspects of the bilevel road pricing and O-D matrix estimation problems are also studied in this paper
New optimality conditions for the semivectorial bilevel optimization problem
No full textThe paper is concerned with the optimistic formulation of a bilevel optimization problem with multiobjective lower-level problem. Considering the scalarization approach for the multiobjective program, we transform our problem into a scalar-objective optimization problem with inequality constraints by means of the well-known optimal value reformulation. Completely detailed first-order necessary optimality conditions are then derived in the smooth and nonsmooth settings while using the generalized differentiation calculus of Mordukhovich. Our approach is different from the one previously used in the literature and the conditions obtained are new. Furthermore, they reduce to those of a usual bilevel program, if the lower-level objective function becomes single-valued
On the effects of combining objectives in multi-objective optimization
No full textIn multi-objective optimization, one considers optimization problems with more than one objective function, and in general these objectives conflict each other. As the solution set of a multiobjective problem is often rather large and contains points of no interest to the decision-maker, strategies are sought that reduce the size of the solution set. One such strategy is to combine several objectives with each other, i.e. by summing them up, before employing tools to solve the resulting multiobjective optimization problem. This approach can be used to reduce the dimensionality of the solution set as well as to discard certain unwanted solutions, especially the ’extreme’ ones found by minimizing just one of the objectives given in the classical sense while disregarding all others. In this paper, we discuss in detail how the strategy of combining objectives linearly influences the set of optimal, i.e. efficient solutions
Two level value function approach to nonsmooth optimistic and pessimistic bilevel programs
No full textThe authors' paper in Optimization 63 (2014), 505533, see Ref. [5], was the rstone to provide detailed optimality conditions for pessimistic bilevel optimization. The results there were based on the concept of the two-level optimal value function introduced and analyzed in SIAM J. Optim. 22 (2012), 13091343; see Ref. [4], for the case of optimistic bilevel programs. One of the basic assumptions in both of these papers is that the functionsinvolved in the problems are at least continuously differentiable. Motivated by the fact that many real-world applications of optimization involve functions that are nondifferentiable at some points of their domain, the main goal of the current paper is extending the two-level value function approach to deriving new necessary optimality conditions for both optimistic and pessimistic versions in bilevel programming with nonsmooth data
Sensitivity analysis for two-level value functions with applications to bilevel programming
No full textThis paper contributes to a deeper understanding of the link between a now conventional framework in hierarchical optimization called the optimistic bilevel problem and its initial more difficult formulation that we call here the original optimistic bilevel optimization problem. It follows from this research that although the process of deriving necessary optimality conditions for the latter problem is more involved, the conditions themselves do not - to a large extent - differ from those known for the conventional problem. It has already been well recognized in the literature that for optimality conditions of the usual optimistic bilevel program appropriate coderivative constructions for the set-valued solution map of the lower-level problem could be used, while it is shown in this paper that for the original optimistic formulation we have to go a step further to require and justify a certain Lipschitz-like property of this map. This is related to the local Lipschitz continuity of the optimal value function of an optimization problem constrained by solutions to another optimization problem; this function is labeled here as the two-level value function. More generally, we conduct a detailed sensitivity analysis for value functions of mathematical programs with extended complementarity constraints. The results obtained in this vein are applied to the two-level value function and then to the original optimistic formulation of the bilevel optimization problem, for which we derive verifiable stationarity conditions of various types entirely in terms of the initial data
Necessary optimality conditions in pessimistic bilevel programming
No full textThis article is devoted to the so-called pessimistic version of bilevel programming programs. Minimization problems of this type are challenging to handle partly because the corresponding value functions are often merely upper (while not lower) semicontinuous. Employing advanced tools of variational analysis and generalized differentiation, we provide rather general frameworks ensuring the Lipschitz continuity of the corresponding value functions. Several types of lower subdifferential necessary optimality conditions are then derived by using the lower-level value function approach and the Karush–Kuhn–Tucker representation of lower-level optimal solution maps. We also derive upper subdifferential necessary optimality conditions of a new type, which can be essentially stronger than the lower ones in some particular settings. Finally, certain links are established between the obtained necessary optimality conditions for the pessimistic and optimistic versions in bilevel programming
- …
