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.     

A log-exponential smoothing method for mathematical programs with complementarity constraints

In this paper a log-exponential smoothing method for mathematical programs with complementarity constraints (MPCC) is analyzed, with some new interesting properties and convergence results provided. It is shown that the stationary points of the resulting smoothed problem converge to the strongly stationary point of MPCC, under the linear independence constraint qualification (LICQ), the weak second-order necessary condition (WSONC), and some reasonable assumption. Moreover, the limit point satisfies the weak second-order necessary condition for MPCC. A notable fact is that the proposed convergence results do not restrict the complementarity constraint functions approach to zero at the same order of magnitude.     

A new smoothing scheme for mathematical programs with complementarity constraints

In this paper, we consider a mathematical program with complementarity constraints (MPCC). We present a new smoothing scheme for this problem, which makes the primal structure of the complementarity part unchanged mostly. For the new smoothing problem, we show that the linear independence constraint qualification (LICQ) holds under some conditions. We also analyze the convergence behavior of the smoothing problem, and get some sufficient conditions such that an accumulation point of stationary points of the smoothing problems is C (M, B)-stationarity respectively. Based on the smoothing problem, we establish an algorithm to solve the primal MPCC problem. Some numerical experiments are given in the paper.     

Active set algorithm for mathematical programs with linear complementarity constraints

In the paper, an incomplete active set algorithm is given for mathematical programs with linear complementarity constraints (MPLCC). At each iteration, a finite number of inner-iterations are contained for approximately solving the relaxed nonlinear optimization problem. If the feasible region of the MPLCC is bounded, under the uniform linear independence constraint qualification (LICQ), any cluster point of the sequence generated from the algorithm is a B-stationary point of the MPLCC. Preliminary numerical tests show that the algorithm is promising.     

Strongly stable C-stationary points for mathematical programs with complementarity constraints

In this paper we consider the class of mathematical programs with complementarity constraints (MPCC). Under an appropriate constraint qualification of Mangasarian–Fromovitz type we present a topological and an equivalent algebraic characterization of a strongly stable C-stationary point for MPCC. Strong stability refers to the local uniqueness, existence and continuous dependence of a solution for each sufficiently small perturbed problem where perturbations up to second order are allowed. This concept of strong stability was originally introduced by Kojima for standard nonlinear optimization; here, its generalization to MPCC demands a sophisticated technique which takes the disjunctive properties of the solution set of MPCC into account.

     

非线性互补约束规划问题的一个新的QP-free算法

本文研究了非线性互补约束均衡问题.利用互补函数以及光滑近似法,把非线性互补约束均衡问题转化为一个光滑非线性规划问题,得到了超线性收敛速度,数值实验结果表明本文提出的算法是可行的.     

求解互补约束优化问题的乘子松弛法

利用互补问题的Lagrange函数, 给出了互补约束优化问题\,(MPCC)\,的一种新松弛问题. 在较弱的条件下, 新松弛问题满足线性独立约束规范. 在此基础上, 提出了求解互补约束优化问题的乘子松弛法. 在MPCC-LICQ条件下, 松弛问题稳定点的任何聚点都是MPCC的M-稳定点. 无需二阶必要条件, 只在ULSC条件下, 就可保证聚点是MPCC的B-稳定点. 另外, 给出了算法收敛于B-稳定点的新条件.     

First order optimality conditions for mathematical programs with semidefinite cone complementarity constraints

In this paper we consider a mathematical program with semidefinite cone complementarity constraints (SDCMPCC). Such a problem is a matrix analogue of the mathematical program with (vector) complementarity constraints (MPCC) and includes MPCC as a special case. We first derive explicit formulas for the proximal and limiting normal cone of the graph of the normal cone to the positive semidefinite cone. Using these formulas and classical nonsmooth first order necessary optimality conditions we derive explicit expressions for the strong-, Mordukhovich- and Clarke- (S-, M- and C-)stationary conditions. Moreover we give constraint qualifications under which a local solution of SDCMPCC is a S-, M- and C-stationary point. Moreover we show that applying these results to MPCC produces new and weaker necessary optimality conditions.     

A note on sensitivity of value functions of mathematical programs with complementarity constraints

Using standard nonlinear programming (NLP) theory, we establish formulas for first and second order directional derivatives of optimal value functions of parametric mathematical programs with complementarity constraints (MPCCs). The main point is that under a linear independence condition on the active constraint gradients, optimal value sensitivity of MPCCs is essentially the same as for nonlinear programs, in spite of the combinatorial nature of the MPCC feasible set. Unlike NLP however, second order directional derivatives of the MPCC optimal value function show combinatorial structure. Received: October 31, 2000 / Accepted: March 8, 2002?Published online June 25, 2002     

Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints

Mathematical programs with equilibrium constraints (MPECs) are difficult optimization problems whose feasible sets do not satisfy most of the standard constraint qualifications. Hence MPECs cause difficulties both from a theoretical and a numerical point of view. As a consequence, a number of MPEC-tailored solution methods have been suggested during the last decade which are known to converge under suitable assumptions. Among these MPEC-tailored solution schemes, the relaxation methods are certainly one of the most prominent class of solution methods. Several different relaxation schemes are available in the meantime, and the aim of this paper is to provide a theoretical and numerical comparison of these schemes. More precisely, in the theoretical part, we improve the convergence theorems of several existing relaxation methods. There, we also take a closer look at the properties of the feasible sets of the relaxed problems and show which standard constraint qualifications are satisfied for these relaxed problems. Finally, the numerical comparison is based on the MacMPEC test problem collection.     

Stochastic mathematical programs with probabilistic complementarity constraints: SAA and distributionally robust approaches

Computational Optimization and Applications - In this paper, a class of stochastic mathematical programs with probabilistic complementarity constraints is considered. We first investigate...     

A note on stability of stationary points in mathematical programs with generalized complementarity constraints

We consider parameter-dependent mathematical programs with constraints governed by the generalized non-linear complementarity problem and with additional non-equilibrial constraints. We study a local behaviour of stationarity maps that assign the respective C- or M-stationarity points of the problem to the parameter. Using generalized differential calculus rules, we provide criteria for the isolated calmness and the Aubin properties of stationarity maps considered. To this end, we derive and apply formulas of some particular objects of the third-order variational analysis.     

Convergence properties of the inexact Lin-Fukushima relaxation method for mathematical programs with complementarity constraints

Mathematical programs with equilibrium (or complementarity) constraints, MPECs for short, form a difficult class of optimization problems. The feasible set of MPECs is described by standard equality and inequality constraints as well as additional complementarity constraints that are used to model equilibrium conditions in different applications. But these complementarity constraints imply that MPECs violate most of the standard constraint qualifications. Therefore, more specialized algorithms are typically applied to MPECs that take into account the particular structure of the complementarity constraints. One popular class of these specialized algorithms are the relaxation (or regularization) methods. They replace the MPEC by a sequence of nonlinear programs NLP(t) depending on a parameter t, then compute a KKT-point of each NLP(t), and try to get a suitable stationary point of the original MPEC in the limit t→0. For most relaxation methods, one can show that a C-stationary point is obtained in this way, a few others even get M-stationary points, which is a stronger property. So far, however, these results have been obtained under the assumption that one is able to compute exact KKT-points of each NLP(t). But this assumption is not implementable, hence a natural question is: What kind of stationarity do we get if we only compute approximate KKT-points? It turns out that most relaxation methods only get a weakly stationary point under this assumption, while in this paper, we show that the smooth relaxation method by Lin and Fukushima (Ann. Oper. Res. 133:63–84, 2005) still yields a C-stationary point, i.e. the inexact version of this relaxation scheme has the same convergence properties as the exact counterpart.     

Global optimization of mathematical programs with complementarity constraints and application to clean energy deployment

We study the problem of clean energy introduction under emission regulations using the generation expansion models developed by He et al. (Comput Ind Eng 63:708–716, 2012). A game theoretic approach was used to model capacity investments and new technology introduction in response to carbon emission regulations. We report algorithmic advancements that were made to enhance the performance of BARON (Tawarmalani and Sahinidis, Math Progr 103:225–249, 2005) on this and other mathematical programs with complementarity constraints.     

On linear programs with linear complementarity constraints

The paper is a manifestation of the fundamental importance of the linear program with linear complementarity constraints (LPCC) in disjunctive and hierarchical programming as well as in some novel paradigms of mathematical programming. In addition to providing a unified framework for bilevel and inverse linear optimization, nonconvex piecewise linear programming, indefinite quadratic programs, quantile minimization, and ℓ ₀ minimization, the LPCC provides a gateway to a mathematical program with equilibrium constraints, which itself is an important class of constrained optimization problems that has broad applications. We describe several approaches for the global resolution of the LPCC, including a logical Benders approach that can be applied to problems that may be infeasible or unbounded.     

A globally convergent approximately active search algorithm for solving mathematical programs with linear complementarity constraints

Summary. In this paper, we propose a new algorithm for solving mathematical programs with linear complementarity constraints. The algorithm uses a method of approximately active search and introduces the idea of acceptable descent face. The main advantage of the new algorithm is that it is globally convergent without requiring strong assumptions such as nondegeneracy or linear independence condition. Numerical results are presented to show the effectiveness of the algorithm.Mathematics Subject Classification (2000): 90C30, 90C33, 65K05This research is partially supported by City University of Hong Kong under its Strategic Research Grant #7001339 and the National Natural Science Foundation of China grant # 10171108 and # 70271014     

A note on the sample average approximation method for stochastic mathematical programs with complementarity constraints

Meng and Xu (2006) [3] proposed a sample average approximation (SAA) method for solving a class of stochastic mathematical programs with complementarity constraints (SMPCCs). After showing that under some moderate conditions, a sequence of weak stationary points of SAA problems converge to a weak stationary point of the original SMPCC with probability approaching one at exponential rate as the sample size tends to infinity, the authors proposed an open question, that is, whether similar results can be obtained under some relatively weaker conditions. In this paper, we try to answer the open question. Based on the reformulation of stationary condition of MPCCs and new stability results on generalized equations, we present a similar convergence theory without any information of second order derivative and strict complementarity conditions. Moreover, we carry out convergence analysis of the regularized SAA method proposed by Meng and Xu (2006) [3] where the convergence results have not been considered.     

互补约束问题的一种新松弛规划及其收敛性

在G.H.Lin与M.Fukushima思想的启发下,针对一般形式的互补约束问题,本文构造了一种新的松弛规划.通过修正和简化G.H.Lin与M.Fukushima的证明方法,在比其更弱的假设条件下获得了该松弛规划的收敛性质.     

On the convergence of general regularization and smoothing schemes for mathematical programs with complementarity constraints

We extend the convergence analysis of a smoothing method [M. Fukushima and J.-S. Pang (2000). Convergence of a smoothing continuation method for mathematical programs with complementarity constraints. In: M. Théra and R. Tichatschke (Eds.), Ill-posed Variational Problems and Regularization Techniques, pp. 99–110. Springer, Berlin/Heidelberg.] to a general class of smoothing functions and show that a weak second-order necessary optimality condition holds at the limit point of a sequence of stationary points found by the smoothing method. We also show that convergence and stability results in [S. Scholtes (2001). Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim., 11, 918–936.] hold for a relaxation problem suggested by Scholtes [S. Scholtes (2003). Private communications.] using a class of smoothing functions. In addition, the relationship between two technical, yet critical, concepts in [M. Fukushima and J.-S. Pang (2000). Convergence of a smoothing continuation method for mathematical programs with complementarity constraints. In: M. Théra and R. Tichatschke (Eds.), Ill-posed Variational Problems and Regularization Techniques, pp. 99–110. Springer, Berlin/Heidelberg; S. Scholtes (2001). Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim., 11, 918–936.] for the convergence analysis of the smoothing and regularization methods is discussed and a counter-example is provided to show that the stability result in [S. Scholtes (2001). Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim., 11, 918–936.] cannot be extended to a weaker regularization.