Solving Ill-posed Bilevel Programs

This paper deals with ill-posed bilevel programs, i.e., problems admitting multiple lower-level solutions for some upper-level parameters. Many publications have been devoted to the standard optimistic case of this problem, where the difficulty is essentially moved from the objective function to the feasible set. This new problem is simpler but there is no guaranty to obtain local optimal solutions for the original optimistic problem by this process. Considering the intrinsic non-convexity of bilevel programs, computing local optimal solutions is the best one can hope to get in most cases. To achieve this goal, we start by establishing an equivalence between the original optimistic problem and a certain set-valued optimization problem. Next, we develop optimality conditions for the latter problem and show that they generalize all the results currently known in the literature on optimistic bilevel optimization. Our approach is then extended to multiobjective bilevel optimization, and completely new results are derived for problems with vector-valued upper- and lower-level objective functions. Numerical implementations of the results of this paper are provided on some examples, in order to demonstrate how the original optimistic problem can be solved in practice, by means of a special set-valued optimization problem.     

On Bilevel Programs with a Convex Lower-Level Problem Violating Slater’s Constraint Qualification

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.     

Multicriteria Approach to Bilevel Optimization

In this paper, we study the relationship between bilevel optimization and multicriteria optimization. Given a bilevel optimization problem, we introduce an order relation such that the optimal solutions of the bilevel problem are the nondominated points with respect to the order relation. In the case where the lower-level problem of the bilevel optimization problem is convex and continuously differentiable in the lower-level variables, this order relation is equivalent to a second, more tractable order relation. Then, we show how to construct a (nonconvex) cone for which we can prove that the nondominated points with respect to the order relation induced by the cone are also nondominated points with respect to any of the two order relations mentioned before. We comment also on the practical and computational implications of our approach.     

二层多目标最优化问题解集的连通性

研究了二层多目标最优化模型(BLMOP)解集的连通性问题,其中(BLMOP)的上层集值目标函数由下层问题的有效点确定.把(BLMOP)看作成单层的集值函数优化问题,借助集值函数优化问题各种有效解集的连通性的结论,得到了(BLMOP)相应的有效解集连通性的结论.     

Finding Robust Global Optimal Values of Bilevel Polynomial Programs with Uncertain Linear Constraints

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.     

Global solution of nonlinear mixed-integer bilevel programs

An algorithm for the global optimization of nonlinear bilevel mixed-integer programs is presented, based on a recent proposal for continuous bilevel programs by Mitsos et al. (J Glob Optim 42(4):475–513, 2008). The algorithm relies on a convergent lower bound and an optional upper bound. No branching is required or performed. The lower bound is obtained by solving a mixed-integer nonlinear program, containing the constraints of the lower-level and upper-level programs; its convergence is achieved by also including a parametric upper bound to the optimal solution function of the lower-level program. This lower-level parametric upper bound is based on Slater-points of the lower-level program and subsets of the upper-level host sets for which this point remains lower-level feasible. Under suitable assumptions the KKT necessary conditions of the lower-level program can be used to tighten the lower bounding problem. The optional upper bound to the optimal solution of the bilevel program is obtained by solving an augmented upper-level problem for fixed upper-level variables. A convergence proof is given along with illustrative examples. An implementation is described and applied to a test set comprising original and literature problems. The main complication relative to the continuous case is the construction of the parametric upper bound to the lower-level optimal objective value, in particular due to the presence of upper-level integer variables. This challenge is resolved by performing interval analysis over the convex hull of the upper-level integer variables.     

Is bilevel programming a special case of a mathematical program with complementarity constraints?

Bilevel programming problems are often reformulated using the Karush–Kuhn–Tucker conditions for the lower level problem resulting in a mathematical program with complementarity constraints(MPCC). Clearly, both problems are closely related. But the answer to the question posed is “No” even in the case when the lower level programming problem is a parametric convex optimization problem. This is not obvious and concerns local optimal solutions. We show that global optimal solutions of the MPCC correspond to global optimal solutions of the bilevel problem provided the lower-level problem satisfies the Slater’s constraint qualification. We also show by examples that this correspondence can fail if the Slater’s constraint qualification fails to hold at lower-level. When we consider the local solutions, the relationship between the bilevel problem and its corresponding MPCC is more complicated. We also demonstrate the issues relating to a local minimum through examples.     

Necessary Optimality Conditions and a New Approach to Multiobjective Bilevel Optimization Problems

Multiobjective optimization problems typically have conflicting objectives, and a gain in one objective very often is an expense in another. Using the concept of Pareto optimality, we investigate a multiobjective bilevel optimization problem (say, P). Our approach consists of proving that P is locally equivalent to a single level optimization problem, where the nonsmooth Mangasarian–Fromovitz constraint qualification may hold at any feasible solution. With the help of a special scalarization function introduced in optimization by Hiriart–Urruty, we convert our single level optimization problem into another problem and give necessary optimality conditions for the initial multiobjective bilevel optimization problem P.     

Connections Between Single-Level and Bilevel Multiobjective Optimization

The relationship between bilevel optimization and multiobjective optimization has been studied by several authors, and there have been repeated attempts to establish a link between the two. We unify the results from the literature and generalize them for bilevel multiobjective optimization. We formulate sufficient conditions for an arbitrary binary relation to guarantee equality between the efficient set produced by the relation and the set of optimal solutions to a bilevel problem. In addition, we present specially structured bilevel multiobjective optimization problems motivated by real-life applications and an accompanying binary relation permitting their reduction to single-level multiobjective optimization problems.     

Multiobjective bilevel optimization

In this work nonlinear non-convex multiobjective bilevel optimization problems are discussed using an optimistic approach. It is shown that the set of feasible points of the upper level function, the so-called induced set, can be expressed as the set of minimal solutions of a multiobjective optimization problem. This artificial problem is solved by using a scalarization approach by Pascoletti and Serafini combined with an adaptive parameter control based on sensitivity results for this problem. The bilevel optimization problem is then solved by an iterative process using again sensitivity theorems for exploring the induced set and the whole efficient set is approximated. For the case of bicriteria optimization problems on both levels and for a one dimensional upper level variable, an algorithm is presented for the first time and applied to two problems: a theoretical example and a problem arising in applications.     

New optimality conditions and a scalarization approach for a nonconvex semi-vectorial bilevel optimization problem

In this paper, we are concerned with the optimistic formulation of a semivectorial bilevel optimization problem. Introducing a new scalarization technique for multiobjective programs, we transform our problem into a scalar-objective optimization problem by means of the optimal value reformulation and establish its theoretical properties. Detailed necessary conditions, to characterize local optimal solutions of the problem, were then provided, while using the weak basic CQ together with the generalized differentiation calculus of Mordukhovich. Our approach is applicable to nonconvex problems and is different from the classical scalarization techniques previously used in the literature and the conditions obtained are new.

     

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.     

Bilevel Decision with Generalized Semi-infinite Optimization for Fuzzy Mappings as Lower Level Problems

In this paper, we introduce the bilevel decision problems with parametric generalized semi-infinite optimization for fuzzy mappings as the lower-level problem, and its corresponding MPEC problems. For these problems, we establish two models which are different in the feasible region setting of lower-level problems. Some new existence results are obtained in rather weak conditions.     

Generating equidistant representations in biobjective programming

In recent years, emphasis has been placed on generating quality representations of the nondominated set of multiobjective optimization problems. This paper presents two methods for generating discrete representations with equidistant points for biobjective problems with solution sets determined by convex, polyhedral cones. The Constraint Controlled-Spacing method is based on the epsilon-constraint method with an additional constraint to control the spacing of generated points. The Bilevel Controlled-Spacing method has a bilevel structure with the lower-level generating the nondominated points and the upper-level controlling the spacing, and is extended to multiobjective problems. Both methods are proven to produce (weakly) nondominated points and are demonstrated on a variety of test problems.     

Optimality Conditions for Bilevel Vector Optimization Problems with a Variable Ordering Structure

The article is concerned with the optimistic formulation of a multiobjective bilevel optimization problem with locally Lipschitz continuous inclusion constraints. Using a variable ordering structure defined by a Bishop–Phelps cone, we investigate necessary optimality conditions for locally weakly nondominated solutions. Reducing the problem into a one-level nonlinear and nonsmooth program, we use the extremal principle by Mordukhovich to get fuzzy optimality conditions. More explicit conditions with the initial data are obtained using both the Ekeland’s variational principle and the support function. Fortunately, the Lipschitz property of a set-valued mapping is conserved for its support function. An appropriate regularity condition is given to help us discern the Lagrange-Kuhn-Tucker multipliers.     

Optimality conditions for a class of inverse optimal control problems with partial differential equations

ABSTRACT

We consider bilevel optimization problems which can be interpreted as inverse optimal control problems. The lower-level problem is an optimal control problem with a parametrized objective function. The upper-level problem is used to identify the parameters of the lower-level problem. Our main focus is the derivation of first-order necessary optimality conditions. We prove C-stationarity of local solutions of the inverse optimal control problem and give a counterexample to show that strong stationarity might be violated at a local minimizer.     

一类不定性多人两层多目标协调决策模型的初探

考虑到组织决策中分权的普遍存在和高低管理层间依靠信息沟通所发生的控制和协调行为以及组织环境和内部条件的真实特征-不定性，本文将一类特殊的多人两层多目标协调决策模型置于组织不定性环境中予以研究，提出了不定性多人两层多目标协调决策模型．并通过模型的不断转化和K—T条件的应用，最终转化为确定的一般目标规划模型．同时，考虑到上层决策单元对下层决策行为的信息反馈进行处理时的及时性和交互性要求，一个具有快速反应能力的双层人机交互决策模式在问题求解中被设计出来以适应组织对适时目标管理的信息处理需要．     

A general MPCC model and its solution algorithm for continuous network design problem

This paper formulates the continuous network design problem as a mathematical program with complementarity constraints (MPCC), with the upper level a nonlinear programming problem and the lower level a nonlinear complementarity problem. Unlike in most previous studies, the proposed framework is more general, in which both symmetric and asymmetric user equilibria can be captured. By applying the complementarity slackness condition of the lower-level problem, the original bilevel formulation can be converted into a single-level and smooth nonlinear programming problem. In order to solve the problem, a relaxation scheme is applied by progressively restricting the complementarity condition, which has been proven to be a rigorous approach under certain conditions. The model and solution algorithm are tested for well-known network design problems and promising results are shown.     

A single-level reformulation of mixed integer bilevel programming problems

This paper focuses on the single-level reformulation of mixed integer bilevel programming problems (MIBLPP). Due to the existence of lower-level integer variables, the popular approaches in the literature such as the first-order approach are not applicable to the MIBLPP. In this paper, we reformulate the MIBLPP as a mixed integer mathematical program with complementarity constraints (MIMPCC) by separating the lower-level continuous and integer variables. In particular, we show that global and local minimizers of the MIBLPP correspond to those of the MIMPCC respectively under suitable conditions.     

Semivectorial Bilevel Optimization Problem: Penalty Approach

We consider a bilevel optimization problem where the upper level is a scalar optimization problem and the lower level is a vector optimization problem. For the lower level, we deal with weakly efficient solutions. We approach our problem using a suitable penalty function which vanishes over the weakly efficient solutions of the lower-level vector optimization problem and which is nonnegative over its feasible set. Then, we use an exterior penalty method.Communicated by H. P. Benson(Formerly Serban Bolintinéanu) Professor, University of New Caledonia, ERIM, Nouméa, New Caledonia. This author thanks the University of Naples Federico II for its support and the Department of Mathematics and Statistics for its hospitality.