Necessary optimality conditions for a special class of bilevel programming problems with unique lower level solution

We consider a bilevel programming problem in Banach spaces whose lower level solution is unique for any choice of the upper level variable. A condition is presented which ensures that the lower level solution mapping is directionally differentiable, and a formula is constructed which can be used to compute this directional derivative. Afterwards, we apply these results in order to obtain first-order necessary optimality conditions for the bilevel programming problem. It is shown that these optimality conditions imply that a certain mathematical program with complementarity constraints in Banach spaces has the optimal solution zero. We state the weak and strong stationarity conditions of this problem as well as corresponding constraint qualifications in order to derive applicable necessary optimality conditions for the original bilevel programming problem. Finally, we use the theory to state new necessary optimality conditions for certain classes of semidefinite bilevel programming problems and present an example in terms of bilevel optimal control.     

非线性二层规划问题的全局优化方法

对于下层为线性规划问题的一类非线性二层规划问题,利用线性规划的对偶理论,将其转化为一个单层优化问题,同时取下层问题的对偶间隙作为惩罚项,构造了一个相应的罚问题,然后提出了一个求解该类二层规划问题的全局优化方法。最后,数值结果表明,所提出的方法是可行的。     

Optimality conditions for mixed discrete bilevel optimization problems

In this article, we consider bilevel optimization problems with discrete lower level and continuous upper level problems. Taking into account both approaches (optimistic and pessimistic) which have been developed in the literature to deal with this type of problem, we derive some conditions for the existence of solutions. In the case where the lower level is a parametric linear problem, the bilevel problem is transformed into a continuous one. After that, we are able to discuss local optimality conditions using tools of variational analysis for each of the different approaches. Finally, we consider a simple application of our results namely the bilevel programming problem with the minimum spanning tree problem in the lower level.     

Designing robust coverage networks to hedge against worst-case facility losses

In order to design a coverage-type service network that is robust to the worst instances of long-term facility loss, we develop a facility location–interdiction model that maximizes a combination of initial coverage by p facilities and the minimum coverage level following the loss of the most critical r facilities. The problem is formulated both as a mixed-integer program and as a bilevel mixed-integer program. To solve the bilevel program optimally, a decomposition algorithm is presented, whereby the original bilevel program is decoupled into an upper level master problem and a lower level subproblem. After sequentially solving these problems, supervalid inequalities can be generated and appended to the upper level master in an attempt to force it away from clearly dominated solutions. Computational results show that when solved to optimality, the bilevel decomposition algorithm is up to several orders of magnitude faster than performing branch and bound on the mixed-integer program.     

Weak and strong stationarity in generalized bilevel programming and bilevel optimal control

In this article, we consider a general bilevel programming problem in reflexive Banach spaces with a convex lower level problem. In order to derive necessary optimality conditions for the bilevel problem, it is transferred to a mathematical program with complementarity constraints (MPCC). We introduce a notion of weak stationarity and exploit the concept of strong stationarity for MPCCs in reflexive Banach spaces, recently developed by the second author, and we apply these concepts to the reformulated bilevel programming problem. Constraint qualifications are presented, which ensure that local optimal solutions satisfy the weak and strong stationarity conditions. Finally, we discuss a certain bilevel optimal control problem by means of the developed theory. Its weak and strong stationarity conditions of Pontryagin-type and some controllability assumptions ensuring strong stationarity of any local optimal solution are presented.     

On solving simple bilevel programs with a nonconvex lower level program

In this paper, we consider a simple bilevel program where the lower level program is a nonconvex minimization problem with a convex set constraint and the upper level program has a convex set constraint. By using the value function of the lower level program, we reformulate the bilevel program as a single level optimization problem with a nonsmooth inequality constraint and a convex set constraint. To deal with such a nonsmooth and nonconvex optimization problem, we design a smoothing projected gradient algorithm for a general optimization problem with a nonsmooth inequality constraint and a convex set constraint. We show that, if the sequence of penalty parameters is bounded then any accumulation point is a stationary point of the nonsmooth optimization problem and, if the generated sequence is convergent and the extended Mangasarian-Fromovitz constraint qualification holds at the limit then the limit point is a stationary point of the nonsmooth optimization problem. We apply the smoothing projected gradient algorithm to the bilevel program if a calmness condition holds and to an approximate bilevel program otherwise. Preliminary numerical experiments show that the algorithm is efficient for solving the simple bilevel program.     

非线性-线性二层规划问题的罚函数方法

利用下层问题的K-T最优性条件将下层为线性规划的一类非线性二层规划转化成相应的单层规划,同时取下层问题的互补条件为罚项,构造了该类非线性二层规划的罚问题.通过对相应罚问题性质的分析,得到了该类非线性二层规划问题的最优性条件,同时设计了该类二层规划问题的求解方法.数值结果表明该方法是可行、有效的.     

A penalty function method for solving inverse optimal value problem

In order to consider the inverse optimal value problem under more general conditions, we transform the inverse optimal value problem into a corresponding nonlinear bilevel programming problem equivalently. Using the Kuhn–Tucker optimality condition of the lower level problem, we transform the nonlinear bilevel programming into a normal nonlinear programming. The complementary and slackness condition of the lower level problem is appended to the upper level objective with a penalty. Then we give via an exact penalty method an existence theorem of solutions and propose an algorithm for the inverse optimal value problem, also analysis the convergence of the proposed algorithm. The numerical result shows that the algorithm can solve a wider class of inverse optimal value problem.     

二(双)层规划综述

二(双)层规划是研究二层决策的递阶优化问题.其理论、方法和应用在过去的30多年取得了很大的发展.本文对二层规划问题的基本概念、性质和算法作了综述,并且对下层规划问题的解不唯一的情况也作了介绍,最后还给出了几种常见的二层规划模型.     

一种求解线性二层规划的割平面方法

以下层问题的K-T最优性条件代替下层问题,将线性二层规划转化为相应的单层规划问题,通过分析单层规划可行解集合的结构特征,设计了一种求解线性二层规划全局最优解的割平面算法.数值结果表明所设计的割平面算法是可行、有效的.     

关于二层规划的逼近问题

下层问题以上层决策变量作为参数,而上层是以下层问题的最优值作为响应 的一类最优化问题——二层规划问题。我们给出了由一系列此类二层规划去逼近原二层规划的逼近法,得到了这种逼近的一些有趣的结果.     

Bilevel programming problems with simple convex lower level

This article is dedicated to the study of bilevel optimal control problems equipped with a fully convex lower level of special structure. In order to construct necessary optimality conditions, we consider a general bilevel programming problem in Banach spaces possessing operator constraints, which is a generalization of the original bilevel optimal control problem. We derive necessary optimality conditions for the latter problem using the lower level optimal value function, ideas from DC-programming and partial penalization. Afterwards, we apply our results to the original optimal control problem to obtain necessary optimality conditions of Pontryagin-type. Along the way, we derive a handy formula, which might be used to compute the subdifferential of the optimal value function which corresponds to the lower level parametric optimal control problem.     

An exact penalty on bilevel programs with linear vector optimization lower level

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.     

A Bridge Between Bilevel Programs and Nash Games

We study connections between optimistic bilevel programming problems and generalized Nash equilibrium problems. We remark that, with respect to bilevel problems, we consider the general case in which the lower level program is not assumed to have a unique solution. Inspired by the optimal value approach, we propose a Nash game that, transforming the so-called implicit value function constraint into an explicitly defined constraint function, incorporates some taste of hierarchy and turns out to be related to the bilevel programming problem. We provide a complete theoretical analysis of the relationship between the vertical bilevel problem and our “uneven” horizontal model: in particular, we define classes of problems for which solutions of the bilevel program can be computed by finding equilibria of our game. Furthermore, by referring to some applications in economics, we show that our “uneven” horizontal model, in some sense, lies between the vertical bilevel model and a “pure” horizontal game.     

A trust region algorithm for solving bilevel programming problems

In this paper, we present a new trust region algorithm for a nonlinear bilevel programming problem by solving a series of its linear or quadratic approximation subproblems. For the nonlinear bilevel programming problem in which the lower level programming problem is a strongly convex programming problem with linear constraints, we show that each accumulation point of the iterative sequence produced by this algorithm is a stationary point of the bilevel programming problem.     

Parametric global optimisation for bilevel programming

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.     

A dual-relax penalty function approach for solving nonlinear bilevel programming with linear lower level problem

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.     

A New Semidefinite Programming Bound for Indefinite Quadratic Forms Over a Simplex

The paper describes a method for computing a lower bound of the global minimum of an indefinite quadratic form over a simplex. The bound is derived by computing an underestimator of the convex envelope by solving a semidefinite program (SDP). This results in a convex quadratic program (QP). It is shown that the optimal value of the QP is a lower bound of the optimal value of the original problem. Since there exist fast (polynomial time) algorithms for solving SDP's and QP's the bound can be computed in reasonable time. Numerical experiments indicate that the relative error of the bound is about 10 percent for problems up to 20 variables, which is much better than a known SDP bound.     

Solution of bilevel optimization problems using the KKT approach

ABSTRACT

Using the Karush–Kuhn–Tucker conditions for the convex lower level problem, the bilevel optimization problem is transformed into a single-level optimization problem (a mathematical program with complementarity constraints). A regularization approach for the latter problem is formulated which can be used to solve the bilevel optimization problem. This is verified if global or local optimal solutions of the auxiliary problems are computed. Stationary solutions of the auxiliary problems converge to C-stationary solutions of the mathematical program with complementarity constraints.     

一种非增值型凸二次双层规划的有效算法

主要研究了非增值型凸二次双层规划的一种有效求解算法。首先利用数学规划的对偶理论,将所求双层规划转化为一个下层只有一个无约束凸二次子规划的双层规划问题.然后根据两个双层规划的最优解和最优目标值之间的关系,提出一种简单有效的算法来解决非增值型凸二次双层规划问题.并通过数值算例的计算结果说明了该算法的可行性和有效性。