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

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

Dynamic feedback Stackelberg games with non-unique solutions

Stackelberg games, which was originally introduced by Stackelberg, are widely applied in such fields as economics, management, politics and behavioral sciences. Stackelberg games can be modelled as a bi-level optimization problem. There exists an extensive literature about static bi-level optimization problems. However, the studies on dynamic bi-level optimization problems are fairly scarce in spite of the importance in explaining and predicting some phenomena rationally. In this paper, we consider discrete time dynamic Stackelberg games with feedback information. In general, the lower-level strategies are non-unique in practice. For a unique solution, dynamic programming algorithms have been presented with multiple players. We revisit dynamic programming for feedback information dynamic Stackelberg games with non-unique lower-level solution. First, we define some kind of solutions related to the decisions styles. Then, we analyze them, respectively. Moreover, dynamic programming algorithm is successful in solving solve feedback information dynamic Stackelberg games with non-unique lower-level solutions.     

Necessary optimality conditions for Stackelberg problems

First-order necessary optimality conditions are derived for a class of two-level Stackelberg problems in which the followers' lower-level problems are convex programs with unique solutions. To this purpose, generalized Jacobians of the marginal maps corresponding to followers' problems are estimated. As illustrative examples, two discretized optimum design problems with elliptic variational inequalities are investigated. The theoretical results may be used also for the numerical solution of the Stackelberg problems considered by nondifferentiable optimization methods.Communicated by M. Simaan     

一类二层凸规划的对偶二层规划

本文讨论上层目标函数以下层子系统目标函数的最优值作为反馈的一类二层凸规划的对偶规划问题 ,在构成函数满足凸连续可微等条件的假设下 ,建立了二层凸规划的 Lagrange对偶二层规划 ,并证明了基本对偶定理 .     

Exact Penalty Functions for Convex Bilevel Programming Problems

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.     

On Optimality Conditions for Generalized Semi-Infinite Programming Problems

Generalized semi-infinite optimization problems (GSIP) are considered. We generalize the well-known optimality conditions for minimizers of order one in standard semi-infinite programming to the GSIP case. We give necessary and sufficient conditions for local minimizers of order one without the assumption of local reduction. The necessary conditions are derived along the same lines as the first-order necessary conditions for GSIP in a recent paper of Jongen, Rückmann, and Stein (Ref. 1) by assuming the so-called extended Mangasarian–Fromovitz constraint qualification. Using the ideas of a recent paper of Rückmann and Shapiro, we give short proofs of necessary and sufficient optimality conditions for minimizers of order one under the additional assumption of the Mangasarian–Fromovitz constraint qualification at all local minimizers of the so-called lower-level problem.     

二层凸规划的基本性质

本文研究了一类抛述二层决策问题的二层数学规划模型，在一定条件下讨论了下层极值函数和上层复合目标函数的凸性和连续性，给出了二层决策问题优决策的存在条件。     

双层规划的递阶交互决策有效化方法

本文讨论了协调集上双层规划问题解的性质,所得结论表明上层将所得利益全部让给下层,或下层将所得利益全部让给上层.当决策者不满足此种有效化方式时,必须寻找体现递阶结构的有效化方法.本文给出了一种保持递阶结构的递阶交互决策有效化方法.该方法适用于下层有多个平行子问题的双层线性规划.     

First Order Optimality Conditions for Generalized Semi-Infinite Programming Problems

We study first-order optimality conditions for the class of generalized semi-infinite programming problems (GSIPs). We extend various well-known constraint qualifications for finite programming problems to GSIPs and analyze the extent to which a corresponding Karush-Kuhn-Tucker (KKT) condition depends on these extensions. It is shown that in general the KKT condition for GSIPs takes a weaker form unless a certain constraint qualification is satisfied. In the completely convex case where the objective of the lower-level problem is concave and the constraint functions are quasiconvex, we show that the KKT condition takes a sharper form. The authors thank the anonymous referees for careful reading of the paper and helpful suggestions. The research of the first author was partially supported by NSERC.     

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.     

二层广义凸规划及其性质

讨论了二层规划的性质 ,在一些凸性和广义凸性假设下 ,讨论了下层极值函数和上层目标函数的凸性、拟凸性和连续性性质 ,获得了五个定理 ,并予以证明 .     

基于粒子群算法的非线性二层规划问题的求解算法

粒子群算法（Particle Swarm Optimization，PSO）是一种新兴的优化技术，其思想来源于人工生命和演化计算理论。PSO通过粒子追随自己找到的最好解和整个群的最好解来完成优化。该算法简单易实现，可调参数少，已得到了广泛研究和应用。本文根据该算法能够有效的求出非凸数学规划全局最优解的特点，对非线性二层规划的上下层问题求解，并根据二层规划的特点，给出了求解非线性二层规划问题全局最优解的有效算法。数值计算结果表明该算法有效。     

Top-Down Fuzzy Decision Making with Partial Preference Information

This paper proposes a multi-stage decision procedure to cope with a hierarchical multiple objective decision environment in which the upper-level DM only provides partial preference information and the lower-level DM is fuzzy about the tradeoff questions such that to achieve substantially more than or equal to some values is delivered to maximize the objectives. Therefore, the procedure consists of two levels, a upper-level and a lower-level. The main idea is that after the upper-level provides partial preference information to the lower-level as a guideline of decision, the lower-level DM determines a satisfactory solution from the reduced non-dominated set in the framework of multi-objective fuzzy programs.     

Derivative evaluation and computational experience with large bilevel mathematical programs

A bilevel program is a mathematical program involving functions defined implicitly as solutions to another mathematical program. We discuss a method for extracting derivative information on the implicit function, which is especially efficient when the lower-level problem has simple bounds on the variables and/or many inactive constraints. Computational experience on problems with up to 230 variables and 30 constraints is presented.Computational support from Robert Bivins and Myron Stein is gratefully acknowledged. We have also appreciated comments from Jon Bard and an anonymous referee. This work was supported in part by the US Department of Energy through the Los Alamos National Laboratory.     

一个带产品定价约束的竞争选址双层规划模型及其求解算法

以大型连锁卖场的选址为研究背景,提出了一个在竞争环境下使获利最大的竞争选址定价双层规划模型,其中上层模型做出选址决策,下层模型确定产品的纳什均衡价格.将设施效用引入到模型中,用指数效用函数来刻画顾客的购物行为偏好,首次证明了不合作状态下双方价格均衡解的存在性和唯一性,并给出了求解最优设施点设置方案和价格均衡解的算法思想及数值算例.     

On bilevel programming,Part I: General nonlinear cases

This paper is concerned with general nonlinear nonconvex bilevel programming problems (BLPP). We derive necessary and sufficient conditions at a local solution and investigate the stability and sensitivity analysis at a local solution in the BLPP. We then explore an approach in which a bundle method is used in the upper-level problem with subgradient information from the lower-level problem. Two algorithms are proposed to solve the general nonlinear BLPP and are shown to converge to regular points of the BLPP under appropriate conditions. The theoretical analysis conducted in this paper seems to indicate that a sensitivity-based approach is rather promising for solving general nonlinear BLPP.This research is sponsored by the Office of Naval Research under contract N00014-89-J-1537.     

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.     

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.     

A Trust-Region Method for Nonlinear Bilevel Programming: Algorithm and Computational Experience

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.     

On Constraint Qualifications in Nonsmooth Optimization

We introduce extensions of the Mangasarian-Fromovitz and Abadie constraint qualifications to nonsmooth optimization problems with feasibility given by means of lower-level sets. We do not assume directional differentiability, but only upper semicontinuity of the defining functions. By deriving and reviewing primal first-order optimality conditions for nonsmooth problems, we motivate the formulations of the constraint qualifications. Then, we study their interrelation, and we show how they are related to the Slater condition for nonsmooth convex problems, to nonsmooth reverse-convex problems, to the stability of parametric feasible set mappings, and to alternative theorems for the derivation of dual first-order optimality conditions.In the literature on general semi-infinite programming problems, a number of formally different extensions of the Mangasarian-Fromovitz constraint qualification have been introduced recently under different structural assumptions. We show that all these extensions are unified by the constraint qualification presented here.