Modified relaxation method for mathematical programs with complementarity constraints

In this paper, we suggest a new relaxation method for solving mathematical programs with complementarity constraints. This method can be regarded as a modification of a method proposed in a recent paper (J. Opt. Theory Appl. 2003; 118 :81–116). We show that the main results remain true for the modified method and particularly, some conditions assumed in the previous paper can be removed. Copyright © 2007 John Wiley & Sons, Ltd.     

Simultaneously optimizing link tolls and signal settings in a road network

The problem of determining link tolls to reduce traffic congestion is often referred as a toll design problem. In this paper, optimal tolls are determined for signal-controlled junctions in urban traffic road networks where the rerouting traffic is properly taken into account. This problem can be formulated as a mathematical program with equilibrium constraints (MPEC) where the user equilibrium is expressed as a variational inequality problem. Due to the non-differentiability of the equilibrium problem, an efficient convergent solution scheme is established. Numerical calculations are conducted on a variety of example road networks and comparisons are made with earlier methods.     

An SQP algorithm for mathematical programs with nonlinear complementarity constraints

In this paper, we describe a successive approximation and smooth sequential quadratic programming （SQP） method for mathematical programs with nonlinear complementarity constraints （MPCC）. We introduce a class of smooth programs to approximate the MPCC. Using an 11 penalty function, the line search assures global convergence, while the superlinear convergence rate is shown under the strictly complementary and second-order sufficient conditions. Moreover, we prove that the current iterated point is an exact stationary point of the mathematical programs with equilibrium constraints （MPEC） when the algorithm terminates finitely.     

A $$ \mathcal{U}\mathcal{V} $$-decomposed method for solving an MPEC problem

uv-decomposition method for solving a mathematical program with equilibrium constraints （MPEC） problem with linear complementarity constraints is presented. The problem is first converted into a nonlinear programming one. The structure of subdifferential a corresponding penalty function and results of its uv-decomposition are given. A conceptual algorithm for solving this problem with a superUnear convergence rate is then constructed in terms of the obtained results.     

均衡约束数学规划问题的一类广义Mond-Weir型对偶理论

针对均衡约束数学规划模型难以满足约束规范及难于求解的问题,基于Mond和Weir提出的标准非线性规划的对偶形式,利用其S稳定性,建立了均衡约束数学规划问题的一类广义Mond-Weir型对偶,从而为求解均衡约束优化问题提供了一种新的方法.在Hanson-Mond广义凸性条件下,利用次线性函数,分别提出了弱对偶性、强对偶性和严格逆对偶性定理,并给出了相应证明.该对偶化方法的推广为研究均衡约束数学规划问题的解提供了理论依据.     

双渠道闭环供应链的三种回收模式的建模分析

针对生产商负责网上直销、零售商负责网下零售、且具有回收再制造功能的双渠道闭环供应链,首先分析了生产商负责产品回收和零售商负责产品回收下生产商和零售商之间的博弈行为,建立了刻画两种回收模式的两层规划模型;进而假定生产商委托第三方企业负责回收,分析了生产商、零售商和第三方回收企业之间的博弈行为,建立了对应此一主两从博弈结构的带均衡约束的两层规划模型.对所得模型进行了模型求解,得到了三种回收模式下双渠道闭环分散式供应链的最优直销价、零售价和回收再制造率决策.通过数值算例对上述三种回收模式进行了比较分析,并对刻画网上直销吸引力的相关参数进行了灵敏度分析.研究发现,生产商负责回收时的回收再制造率最高;网上直销具有激发潜在需求(正效应)和吸引零售市场需求发生转移(负效应)的双重效应等.     

Mathematical programs with vanishing constraints: constraint qualifications,their applications,and a new regularization method

ABSTRACT

We propose a new family of relaxation schemes for mathematical programs with vanishing constraints that extend the relaxation of Hoheisel, Kanzow & Schwartz from 2012. We discuss the properties of the sequence of relaxed non-linear programs as well as stationary properties of limiting points. Our relaxation schemes have the desired property of converging to an M-stationary point. A main advantage of this new method is to converge to an S-stationary point satisfying MPVC-LICQ for a large class of problem. We also study MPVC constraint qualification connected to this study and prove convergence of the method under the new MPVC-CRSC. Additionally, we obtain the new MPVC-wGCQ and prove that it is the weakest MPVC constraint qualification.     

Multiplier convergence in trust-region methods with application to convergence of decomposition methods for MPECs

We study piecewise decomposition methods for mathematical programs with equilibrium constraints (MPECs) for which all constraint functions are linear. At each iteration of a decomposition method, one step of a nonlinear programming scheme is applied to one piece of the MPEC to obtain the next iterate. Our goal is to understand global convergence to B-stationary points of these methods when the embedded nonlinear programming solver is a trust-region scheme, and the selection of pieces is determined using multipliers generated by solving the trust-region subproblem. To this end we study global convergence of a linear trust-region scheme for linearly-constrained NLPs that we call a trust-search method. The trust-search has two features that are critical to global convergence of decomposition methods for MPECs: a robustness property with respect to switching pieces, and a multiplier convergence result that appears to be quite new for trust-region methods. These combine to clarify and strengthen global convergence of decomposition methods without resorting either to additional conditions such as eventual inactivity of the trust-region constraint, or more complex methods that require a separate subproblem for multiplier estimation.      

Global solution of bilevel programs with a nonconvex inner program

A bounding algorithm for the global solution of nonlinear bilevel programs involving nonconvex functions in both the inner and outer programs is presented. The algorithm is rigorous and terminates finitely to a point that satisfies ε-optimality in the inner and outer programs. For the lower bounding problem, a relaxed program, containing the constraints of the inner and outer programs augmented by a parametric upper bound to the parametric optimal solution function of the inner program, is solved to global optimality. The optional upper bounding problem is based on probing the solution obtained by the lower bounding procedure. For the case that the inner program satisfies a constraint qualification, an algorithmic heuristic for tighter lower bounds is presented based on the KKT necessary conditions of the inner program. The algorithm is extended to include branching, which is not required for convergence but has potential advantages. Two branching heuristics are described and analyzed. Convergence proofs are provided and numerical results for original test problems and for literature examples are presented.     

Leader-Follower Equilibria for Electric Power and NO x Allowances Markets

This paper investigates the ability of the largest producer in an electricity market to manipulate both the electricity and emission allowances markets to its advantage. A Stackelberg game to analyze this situation is constructed in which the largest firm plays the role of the leader, while the medium-sized firms are treated as Cournot followers with price-taking fringes that behave competitively in both markets. Since there is no explicit representation of the best-reply function for each follower, this Stackelberg game is formulated as a large-scale mathematical program with equilibrium constraints. The best-reply functions are implicitly represented by a set of nonlinear complementarity conditions. Analysis of the computed solution for the Pennsylvania–New Jersey–Maryland electricity market shows that the leader can gain substantial profits by withholding allowances and driving up NO _x allowance costs for rival producers. The allowances price is higher than the corresponding price in the Nash–Cournot case, although the electricity prices are essentially the same.We are grateful to two anonymous referees for their insightful comments that helped us improve the paper. This work is partially supported by NSF grants CS 0080577 and 0224817, by USEPA STAR grant R82873101-0, and by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, Office of Science, U.S. Department of Energy, under Contract W-31-109-Eng-38. Any opinions or errors are the responsibility of the authors and not the sponsoring agencies.