优化方法解决无上层约束的线性双层规划问题

In this paper we propose an optimal method for solving the linear bilevel programming problem with no upper-level constraint. The main idea of this method is that the initial point which is in the feasible region goes forward along the optimal direction firstly. When the iterative point reaches the boundary of the feasible region, it can continue to go forward along the suboptimal direction. The iteration is terminated until the iterative point cannot go forward along the suboptimal direction and effective direction, and the new iterative point is the solution of the lower-level programming. An algorithm which bases on the main idea above is presented and the solution obtained via this algorithm is proved to be optimal solution to the bilevel programming problem. This optimal method is effective for solving the linear bilevel programming problem.     

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.     

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

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

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

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

基于凹性割的线性双层规划全局优化算法

通过对线性双层规划下层问题对偶间隙的讨论,定义了一种凹性割,利用该凹性割的性质,给出了一个求解线性双层规划的割平面算法。由于线性双层规划全局最优解可在其约束域的极点上达到,提出的算法能求得问题的全局最优解,并通过一个算例说明了算法的有效性。     

Solving linear fractional bilevel programs

In this paper, we prove that an optimal solution to the linear fractional bilevel programming problem occurs at a boundary feasible extreme point. Hence, the Kth-best algorithm can be proposed to solve the problem. This property also applies to quasiconcave bilevel problems provided that the first level objective function is explicitly quasimonotonic.     

A new approach for solving linear bilevel problems using genetic algorithms

Bilevel programming involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. This paper develops a genetic algorithm for the linear bilevel problem in which both objective functions are linear and the common constraint region is a polyhedron. Taking into account the existence of an extreme point of the polyhedron which solves the problem, the algorithm aims to combine classical extreme point enumeration techniques with genetic search methods by associating chromosomes with extreme points of the polyhedron. The numerical results show the efficiency of the proposed algorithm. In addition, this genetic algorithm can also be used for solving quasiconcave bilevel problems provided that the second level objective function is linear.     

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.     

The bilevel linear/linear fractional programming problem

Bilevel programming involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. In this paper we consider the bilevel linear/linear fractional programming problem in which the objective function of the first level is linear, the objective function of the second level is linear fractional and the feasible region is a polyhedron. For this problem we prove that an optimal solution can be found which is an extreme point of the polyhedron. Moreover, taking into account the relationship between feasible solutions to the problem and bases of the technological coefficient submatrix associated to variables of the second level, an enumerative algorithm is proposed that finds a global optimum to the problem.     

求解二层规划问题的遗传算法

本文求解二层规划问题的遗传算法，给出了算法基本框架并对算法实现进行了研究．算法适用于各类线性和非线性二层规划问题．数值计算结果显示，该方法是可行和有效的．     

Links Between Linear Bilevel and Mixed 0–1 Programming Problems

We study links between the linear bilevel and linear mixed 0–1 programming problems. A new reformulation of the linear mixed 0–1 programming problem into a linear bilevel programming one, which does not require the introduction of a large finite constant, is presented. We show that solving a linear mixed 0–1 problem by a classical branch-and-bound algorithm is equivalent in a strong sense to solving its bilevel reformulation by a bilevel branch-and-bound algorithm. The mixed 0–1 algorithm is embedded in the bilevel algorithm through the aforementioned reformulation; i.e., when applied to any mixed 0–1 instance and its bilevel reformulation, they generate sequences of subproblems which are identical via the reformulation.     

An extended branch and bound algorithm for linear bilevel programming

For linear bilevel programming, the branch and bound algorithm is the most successful algorithm to deal with the complementary constraints arising from Kuhn–Tucker conditions. However, one principle challenge is that it could not well handle a linear bilevel programming problem when the constraint functions at the upper-level are of arbitrary linear form. This paper proposes an extended branch and bound algorithm to solve this problem. The results have demonstrated that the extended branch and bound algorithm can solve a wider class of linear bilevel problems can than current capabilities permit.     

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

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

Strong-Weak Nonlinear Bilevel Problems: Existence of Solutions in a Sequential Setting

The paper deals with a strong-weak nonlinear bilevel problem which generalizes the well-known weak and strong ones. In general, the study of the existence of solutions to such a problem is a difficult task. So that, for a strong-weak nonlinear bilevel problem, we first give a regularization based on the use of strict ??-solutions of the lower level problem. Then, via this regularization and under sufficient conditions, we show that the problem admits at least one solution. The obtained result is an extension and an improvement of some recent results appeared recently in the literature for both weak nonlinear bilevel programming problems and linear finite dimensional case.     

Solving nonlinear principal-agent problems using bilevel programming

While significant progress has been made, analytic research on principal-agent problems that seek closed-form solutions faces limitations due to tractability issues that arise because of the mathematical complexity of the problem. The principal must maximize expected utility subject to the agent’s participation and incentive compatibility constraints. Linearity of performance measures is often assumed and the Linear, Exponential, Normal (LEN) model is often used to deal with this complexity. These assumptions may be too restrictive for researchers to explore the variety of relationships between compensation contracts offered by the principal and the effort of the agent. In this paper we show how to numerically solve principal-agent problems with nonlinear contracts. In our procedure, we deal directly with the agent’s incentive compatibility constraint. We illustrate our solution procedure with numerical examples and use optimization methods to make the problem tractable without using the simplifying assumptions of a LEN model. We also show that using linear contracts to approximate nonlinear contracts leads to solutions that are far from the optimal solutions obtained using nonlinear contracts. A principal-agent problem is a special instance of a bilevel nonlinear programming problem. We show how to solve principal-agent problems by solving bilevel programming problems using the ellipsoid algorithm. The approach we present can give researchers new insights into the relationships between nonlinear compensation schemes and employee effort.     

DC programming techniques for solving a class of nonlinear bilevel programs

We propose a method for finding a global solution of a class of nonlinear bilevel programs, in which the objective function in the first level is a DC function, and the second level consists of finding a Karush-Kuhn-Tucker point of a quadratic programming problem. This method is a combination of the local algorithm DCA in DC programming with a branch and bound scheme well known in discrete and global optimization. Computational results on a class of quadratic bilevel programs are reported.     

THE CONVERGENCE OF APPROACH PENALTY FUNCTION METHOD FOR APPROXIMATE BILEVEL PROGRAMMING PROBLEM

' 1 IntroductionWe collsider the fOllowi11g bilevel programndng problen1:max f(x, y),(BP) s.t.x E X = {z E RnIAx = b,x 2 0}, (1)y e Y(x).whereY(x) = {argmaxdTyIDx Gy 5 g, y 2 0}, (2)and b E R", d, y E Rr, g E Rs, A, D.and G are m x n1 s x n aild 8 x r matrices respectively. If itis not very difficult to eva1uate f(and/or Vf) at all iteration points, there are many algorithmeavailable fOr solving problem (BP) (see [1,2,3etc1). However, in some problems (see [4]), f(x, y)is too com…     

Nonlinear robust optimization via sequential convex bilevel programming

In this paper, we present a novel sequential convex bilevel programming algorithm for the numerical solution of structured nonlinear min–max problems which arise in the context of semi-infinite programming. Here, our main motivation are nonlinear inequality constrained robust optimization problems. In the first part of the paper, we propose a conservative approximation strategy for such nonlinear and non-convex robust optimization problems: under the assumption that an upper bound for the curvature of the inequality constraints with respect to the uncertainty is given, we show how to formulate a lower-level concave min–max problem which approximates the robust counterpart in a conservative way. This approximation turns out to be exact in some relevant special cases and can be proven to be less conservative than existing approximation techniques that are based on linearization with respect to the uncertainties. In the second part of the paper, we review existing theory on optimality conditions for nonlinear lower-level concave min–max problems which arise in the context of semi-infinite programming. Regarding the optimality conditions for the concave lower level maximization problems as a constraint of the upper level minimization problem, we end up with a structured mathematical program with complementarity constraints (MPCC). The special hierarchical structure of this MPCC can be exploited in a novel sequential convex bilevel programming algorithm. We discuss the surprisingly strong global and locally quadratic convergence properties of this method, which can in this form neither be obtained with existing SQP methods nor with interior point relaxation techniques for general MPCCs. Finally, we discuss the application fields and implementation details of the new method and demonstrate the performance with a numerical example.     

求解弱线性双层规划问题的一种全局优化方法

双层规划在经济、交通、生态、工程等领域有着广泛而重要的应用.目前对双层规划的研究主要是基于强双层规划和弱双层规划.然而,针对弱双层规划的求解方法却鲜有研究.研究求解弱线性双层规划问题的一种全局优化方法,首先给出弱线性双层规划问题与其松弛问题在最优解上的关系,然后利用线性规划的对偶理论和罚函数方法,讨论该松弛问题和它的罚问题之间的关系.进一步设计了一种求解弱线性双层规划问题的全局优化方法,该方法的优势在于它仅仅需要求解若干个线性规划问题就可以获得原问题的全局最优解.最后,用一个简单算例说明了所提出的方法是可行的.     

一种基于进化算法的非线性两层规划的快速全局优化方法

由于非线性两层规划具有非凸性、NP-难等计算困难，高效的算法并不多见。本文设计了一种新的进化算法，基于此进化算法提出了求解带有一重或多重下层的非线性两层规划的高效算法。该算法充分利用两层规划的结构特点。最后，给出了六个不同类型的算例，数值结果表明，本算法是快速和有效的。