Combining the regularization strategy and the SQP to solve MPCC — A MATLAB implementation

Mathematical Program with Complementarity Constraints (MPCC) plays a very important role in many fields such as engineering design, economic equilibrium, multilevel games, and mathematical programming theory itself. In theory its constraints fail to satisfy a standard constraint qualification such as the linear independence constraint qualification (LICQ) or the Mangasarian-Fromovitz constraint qualification (MFCQ) at any feasible point. As a result, the developed nonlinear programming theory may not be applied to MPCC class directly. Nowadays, a natural and popular approach is trying to find some suitable approximations of an MPCC so that it can be solved by solving a sequence of nonlinear programs.This work aims to solve the MPCC using nonlinear programming techniques, namely the SQP and the regularization scheme. Some algorithms with two iterative processes, the inner and the external, were developed. A set of AMPL problems from MacMPEC database (Leyffer, 2000) [8] were tested. The comparative analysis regarding performance of algorithms was carried out.     

Superlinear Convergence of a Smooth Approximation Method for Mathematical Programs with Nonlinear Complementarity Constraints

<正>Mathematical programs with complementarity constraints(MPCC) is an important subclass of MPEC.It is a natural way to solve MPCC by constructing a suitable approximation of the primal problem.In this paper,we propose a new smoothing method for MPCC by using the aggregation technique.A new SQP algorithm for solving the MPCC problem is presented.At each iteration,the master direction is computed by solving a quadratic program,and the revised direction for avoiding the Maratos effect is generated by an explicit formula.As the non-degeneracy condition holds and the smoothing parameter tends to zero,the proposed SQP algorithm converges globally to an S-stationary point of the MPEC problem,its convergence rate is superlinear.Some preliminary numerical results are reported.     

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.     

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     

Generalized stationary points and an interior-point method for mathematical programs with equilibrium constraints

Generalized stationary points of the mathematical program with equilibrium constraints (MPEC) are studied to better describe the limit points produced by interior point methods for MPEC. A primal-dual interior-point method is then proposed, which solves a sequence of relaxed barrier problems derived from MPEC. Global convergence results are deduced under fairly general conditions other than strict complementarity or the linear independence constraint qualification for MPEC (MPEC-LICQ). It is shown that every limit point of the generated sequence is a strong stationary point of MPEC if the penalty parameter of the merit function is bounded. Otherwise, a point with certain stationarity can be obtained. Preliminary numerical results are reported, which include a case analyzed by Leyffer for which the penalty interior-point algorithm failed to find a stationary point.Mathematics Subject Classification (1991):90C30, 90C33, 90C55, 49M37, 65K10     

An MPCC approach for stochastic Stackelberg–Nash–Cournot equilibrium

In this article, we investigate a Stochastic Stackelberg–Nash–Cournot Equilibrium problem by reformulating it as a Mathematical Program with Complementarity Constraints (MPCC). The complementarity constraints are further reformulated as a system of nonsmooth equations. We characterize the followers’ Nash–Cournot equilibria by studying the implicit solution of a system of equations. We outline numerical methods for the solution of a stochastic Stackelberg–Nash–Cournot Equilibrium problem with finite distribution of market demand scenarios and propose a discretization approach based on implicit numerical integration to deal with stochastic Stackelberg–Nash–Cournot Equilibrium problem with continuous distribution of demand scenarios. Finally, we discuss the two-leader Stochastic Stackelberg–Nash–Cournot Equilibrium problem.     

Identification of some nonsmooth evolution systems with illustration on adhesive contacts at small strains

A class of evolution quasi-static systems which leads, after a suitable time discretization, to recursive non-linear programs, is considered and optimal control or identification problems governed by such systems are investigated. The resulting problem is an evolutionary Mathematical Programs with Equilibrium Constraints. A subgradient information of the (in general nonsmooth) composite objective function is evaluated and the problem is solved by the implicit programming approach. The abstract theory is illustrated on an identification problem governed by delamination of a unilateral adhesive contact of elastic bodies discretized by finite-element method in space and a semiimplicit formula in time. Being motivated by practical tasks, an identification problem of the fracture toughness and of the elasticity moduli of the adhesive is computationally implemented and tested numerically on a two-dimensional example. Other applications including frictional contacts or bulk damage, plasticity or phase transformations are outlined.     

Integrating SQP and Branch-and-Bound for Mixed Integer Nonlinear Programming

This paper considers the solution of Mixed Integer Nonlinear Programming (MINLP) problems. Classical methods for the solution of MINLP problems decompose the problem by separating the nonlinear part from the integer part. This approach is largely due to the existence of packaged software for solving Nonlinear Programming (NLP) and Mixed Integer Linear Programming problems.In contrast, an integrated approach to solving MINLP problems is considered here. This new algorithm is based on branch-and-bound, but does not require the NLP problem at each node to be solved to optimality. Instead, branching is allowed after each iteration of the NLP solver. In this way, the nonlinear part of the MINLP problem is solved whilst searching the tree. The nonlinear solver that is considered in this paper is a Sequential Quadratic Programming solver.A numerical comparison of the new method with nonlinear branch-and-bound is presented and a factor of up to 3 improvement over branch-and-bound is observed.     

Inexact solution of NLP subproblems in MINLP

In the context of convex mixed integer nonlinear programming (MINLP), we investigate how the outer approximation method and the generalized Benders decomposition method are affected when the respective nonlinear programming (NLP) subproblems are solved inexactly. We show that the cuts in the corresponding master problems can be changed to incorporate the inexact residuals, still rendering equivalence and finiteness in the limit case. Some numerical results will be presented to illustrate the behavior of the methods under NLP subproblem inexactness.     

Parameter estimation in metabolic flux balance models for batch fermentation—Formulation & Solution using Differential Variational Inequalities (DVIs)

Recent years have witnessed a surge in research in cellular biology. There has been particular interest in the interaction between cellular metabolism and its environment. In this work we present a framework for fitting fermentation models that include this interaction. Differential equations describe the evolution of extracellular metabolites, while a Linear Program (LP) models cell metabolism, and piecewise smooth functions model the links between cell metabolism and its environment. We show that the fermentation dynamics can be described using Differential Variational Inequalities (DVIs). Discretization of the system and reformulation of the VIs using optimality conditions converts the DVI to a Mathematical Program with Complementarity Constraints (MPCC). We briefly describe an interior point algorithm for solving MPCCs. Encouraging numerical results are presented in estimating model parameters to fit model prediction and data obtained from fermentation, using cultures of Saccharomyces cerevisiae reported in the literature.     

A likelihood-MPEC approach to target classification

In this paper we develop a method for classifying an unknown data vector as belonging to one of several classes. This method is based on the statistical methods of maximum likehood and borrowed strength estimation. We develop an MPEC procedure (for Mathematical Program with Equilibrium Constraints) for the classification of a multi-dimensional observation, using a finite set of observed training data as the inputs to a bilevel optimization problem. We present a penalty interior point method for solving the resulting MPEC and report numerical results for a multispectral minefield classification application. Related approaches based on conventional maximum likehood estimation and a bivariate normal mixture model, as well as alternative surrogate classification objective functions, are described. Received: October 26, 1998 / Accepted: June 11, 2001?Published online March 24, 2003 RID="***" ID="***"The authors of this work were all partially supported by the Wright Patterson Air Force Base via Veda Contract F33615-94-D-1400. The first and third author were also supported by the National Science Foundation under grant DMS-9705220. RID="*" ID="*"The work of this author was based on research supported by the U.S. National Science Foundation under grant CCR-9624018. RID="**" ID="**"The work of this author was supported by the Office of Naval Research under grant N00014-95-1-0777.     

Optimal cycle for a signalized intersection using Global Optimization and Complementarity

A queueing system resulting from a signalised intersection regulated by pre-timed control in an urban traffic network is considered in this paper. Subsequently, we analyse the manner in which Global Optimisation and Complementarity may be used to determine the optimal cycle length and green split allocation for an isolated signalised intersection. The model in question has been formulated as a Mathematical Program with Equilibrium (or Complementarity) Constraints (MPEC). A?sequential complementarity algorithm for computing a global minimum for the MPEC is also subject to analysis in this paper. Furthermore, computational experience is included to demonstrate the efficiency of this method as an effective solution for the problem in question.     

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.     

Approximating infinite horizon stochastic optimal control in discrete time with constraints

Traditional approaches to solving stochastic optimal control problems involve dynamic programming, and solving certain optimality equations. When recast as stochastic programming problems, structural aspects such as convexity are retained, and numerical solution procedures based on decomposition and duality may be exploited. This paper explores a class of stationary, infinite-horizon stochastic optimization problems with discounted cost criterion. Constraints on both states and controls are permitted, and modeled in the objective function by allowing it to take infinite values. Approximating techniques are developed using variational analysis, and intuitive lower bounds are obtained via averaging the future. These bounds could be used in a finite-time horizon stochastic programming setting to find solutions numerically. Research supported in part by a grant of the National Science Foundation. AMS Classification 46N10, 49N15, 65K10, 90C15, 90C46     

Parametric Sensitivity Analysis of Perturbed PDE Optimal Control Problems with State and Control Constraints

We study parametric optimal control problems governed by a system of time-dependent partial differential equations (PDE) and subject to additional control and state constraints. An approach is presented to compute the optimal control functions and the so-called sensitivity differentials of the optimal solution with respect to perturbations. This information plays an important role in the analysis of optimal solutions as well as in real-time optimal control.The method of lines is used to transform the perturbed PDE system into a large system of ordinary differential equations. A subsequent discretization then transcribes parametric ODE optimal control problems into perturbed nonlinear programming problems (NLP), which can be solved efficiently by SQP methods.Second-order sufficient conditions can be checked numerically and we propose to apply an NLP-based approach for the robust computation of the sensitivity differentials of the optimal solutions with respect to the perturbation parameters. The numerical method is illustrated by the optimal control and sensitivity analysis of the Burgers equation.Communicated by H. J. Pesch     

Arc-Length Method for Frictional Contact Problems Using Mathematical Programming with Complementarity Constraints

A new formulation as well as a new solution technique is proposed for an equilibrium path-following method in two-dimensional quasistatic frictional contact problems. We consider the Coulomb friction law as well as a geometrical nonlinearity explicitly. Based on a criterion of maximum dissipation of energy, we propose a formulation as a mathematical program with complementarity constraints (MPEC) in order to avoid unloading solutions in which most contact candidate nodes become stuck. A regularization scheme for the MPEC is proposed, which can be solved by using a conventional nonlinear programming approach. The equilibrium paths of various structures are computed in cases such that there exist some limit points and/or infinite number of successive bifurcation points.     

Hybrid Approach with Active Set Identification for Mathematical Programs with Complementarity Constraints

We consider a mathematical program with complementarity constraints (MPCC). Our purpose is to develop methods that enable us to compute a solution or a point with some kind of stationarity to MPCC by solving a finite number of nonlinear programs. We apply an active set identification technique to a smoothing continuation method (Ref. 1) and propose a hybrid algorithm for solving MPCC. We develop also two modifications: one makes use of an index addition strategy; the other adopts an index subtraction strategy. We show that, under reasonable assumptions, all the proposed algorithms possess a finite termination property. Further discussions and numerical experience are given as well This work was supported in part by the Scientific Research Grant-in-Aid from the Ministry of Education, Science, Sports, and Culture of Japan. The authors are grateful to Professor Paul Tseng for helpful suggestions on an earlier version of the paper.     

Evaluating the strategic behavior of cement producers: An equilibrium problem with equilibrium constraints

This paper investigates the equilibria reached by a number of strategic producers in the cement sector through a technological representation of the market. We present a bilevel model for each producer that characterizes its profit maximizing behavior. In the bilevel model, the upper-level problem of each producer is constrained by a lower-level market clearing problem representing cement trading and whose objective function corresponds to social welfare. Replacing the lower level problem by its optimality condition yields a Mathematical Program with Equilibrium Constraints (MPEC). Then, all strategic producers are jointly considered. Representing their interaction requires solving jointly the interrelated MPECs of all producers, which results in an Equilibrium Problem with Equilibrium Constraints (EPEC).A parametric analysis concerning cost, capacity and demand fluctuations has been conducted. Our analysis shows that the European cement sector is mature and has lost its competitiveness; African cement market can assume a prominent role in international markets in the coming future if investments in new and efficient capacity are carried out. Finally, the Far East will remain the reference exporter of cement at worldwide level.     

Abadie-Type Constraint Qualification for Mathematical Programs with Equilibrium Constraints

Mathematical programs with equilibrium constraints (MPEC) are nonlinear programs which do not satisfy any of the common constraint qualifications (CQ). In order to obtain first-order optimality conditions, constraint qualifications tailored to the MPECs have been developed and researched in the past. In this paper, we introduce a new Abadie-type constraint qualification for MPECs. We investigate sufficient conditions for this new CQ, discuss its relationship to several existing MPEC constraint qualifications, and introduce a new Slater-type constraint qualifications. Finally, we prove a new stationarity concept to be a necessary optimality condition under our new Abadie-type CQ.Communicated by Z. Q. Luo