140 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
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
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
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
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
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
Regularization and Approximation Methods in Stackelberg Games and Bilevel Optimization
No full textIn a two-stage Stackelberg game, depending on the leader’s information about the choice of the follower among his optimal responses, one can associate different types of mathematical problems. We present formulations and solution concepts for such problems, together with their possible roles in bilevel optimization, and we illustrate the crucial issues concerning these solution concepts. Then, we discuss which of these issues can be positively or negatively answered and how managing the latter ones by means of two widely used approaches: regularizing the set of optimal responses of the follower, via different types of approximate solutions, or regularizing the follower’s payoff function, via the Tikhonov or the proximal regularizations. The first approach allows to define different kinds of regularized problems whose solutions exist and are stable under perturbations assuming sufficiently general conditions. Moreover, when the original problem has no solutions, we consider suitable regularizations of the second-stage problem, called inner regularizations, which enable to construct a surrogate solution, called viscosity solution, to the original problem. The second approach permits to overcome the non-uniqueness of the follower’s optimal response, by constructing sequences of Stackelberg games with a unique second-stage solution which approximate in some sense the original game, and to select among the solutions by using appropriate constructive methods
Synergistic up-regulation of MCP-2/CCL8 activity is counteracted by chemokine cleavage, limiting its inflammatory and anti-tumoral effects
No full textChemokines mediate the inflammatory response by attracting various leukocyte types. MCP-2/CC chemokine ligand 8 (CCL8) was induced at only suboptimal levels in fibroblasts and endothelial cells by IL-1β or IFN-γ, unless these cytokineswere combined. IFN-γ also synergized with the TLR ligands peptidoglycan (TLR2), dsRNA (TLR3) or LPS (TLR4). Under these conditions, intact MCP-2/CCL8(1-76) produced by fibroblasts was found to be processed into MCP-2/CCL8(6-75), which lacked chemotactic activity for monocytic cells. Furthermore, the capacity of MCP-2/CCL8(6-75) to increase intracellular calcium levels through CCR1, CCR2, CCR3 and CCR5 was severely reduced. However, the truncated isoform still blocked these receptors for other ligands. MCP-2/ CCL8(6-75) induced internalization of CCR2, inhibited MCP-1/CCL2 and MCP-2/CCL8 ERK signaling and antagonized the chemotactic activity of several CCR2 ligands (MCP-1/CCL2, MCP-2/CCL8, MCP-3/CCL7). In contrast to MCP-3/CCL7, parvoviral delivery of MCP-2/CCL8 into B78/H1 melanoma failed to inhibit tumor growth, partially due to proteolytic cleavage into inactive MCP-2/CCL8 missing five NH2-terminal residues. However, in an alternative tumor model, using HeLa cells, MCP-2/CCL8 retarded tumor development. These data indicate that optimal induction and delivery of MCP-2/CCL8 is counteracted by converting this chemokine into a receptor antagonist, thereby losing its antitumoral potential
Comment to “interactive fuzzy goal programming approach for bilevel programming problem” by S.R. Arora and R. Gupta
No full text
- …
