Optimality Conditions for Disjunctive Programs with Application to Mathematical Programs with Equilibrium Constraints

We consider optimization problems with a disjunctive structure of the feasible set. Using Guignard-type constraint qualifications for these optimization problems and exploiting some results for the limiting normal cone by Mordukhovich, we derive different optimality conditions. Furthermore, we specialize these results to mathematical programs with equilibrium constraints. In particular, we show that a new constraint qualification, weaker than any other constraint qualification used in the literature, is enough in order to show that a local minimum results in a so-called M-stationary point. Additional assumptions are also discussed which guarantee that such an M-stationary point is in fact a strongly stationary point.      

On finite termination of an iterative method for linear complementarity problems

Based on a well-known reformulation of the linear complementarity problem (LCP) as a nondifferentiable system of nonlinear equations, a Newton-type method will be described for the solution of LCPs. Under certain assumptions, it will be shown that this method has a finite termination property, i.e., if an iterate is sufficiently close to a solution of LCP, the method finds this solution in one step. This result will be applied to a recently proposed algorithm by Harker and Pang in order to prove that their algorithm also has the finite termination property.     

A New Class of Semismooth Newton-Type Methods for Nonlinear Complementarity Problems

We introduce a new, one-parametric class of NCP-functions. This class subsumes the Fischer function and reduces to the minimum function in a limiting case of the parameter. This new class of NCP-functions is used in order to reformulate the nonlinear complementarity problem as a nonsmooth system of equations. We present a detailed investigation of the properties of the equation operator, of the corresponding merit function as well as of a suitable semismooth Newton-type method. Finally, numerical results are presented for this method being applied to a number of test problems.     

Generalized Nash equilibrium problems

The Generalized Nash equilibrium problem is an important model that has its roots in the economic sciences but is being fruitfully used in many different fields. In this survey paper we aim at discussing its main properties and solution algorithms, pointing out what could be useful topics for future research in the field. The work of Christain Kanzow has been partially supported by the program “Identification, Optimization and Control with Applications in Modern Technologies” of the Elite Network of Bavaria, Germany.     

Strictly feasible equation-based methods for mixed complementarity problems

Summary.   We introduce a new algorithm for the solution of the mixed complementarity problem (MCP) which has stronger properties than most existing methods. In fact, typical solution methods for the MCP either generate feasible iterates but have to solve relatively complicated subproblems (like quadratic programs or linear complementarity problems), or they have relatively simple subproblems (like linear systems of equations) but generate not necessarily feasible iterates. The method to be presented here combines the nice features of these two classes of methods: It has to solve only one linear system of equations (of reduced dimension) at each iteration, and it generates feasible (more precisely: strictly feasible) iterates. The new method has some nice global and local convergence properties. Some preliminary numerical results will also be given. Received August 26, 1999 / Revised version recived April 11, 2000 / Published online February 5, 2001     

On a Smooth Dual Gap Function for a Class of Quasi-Variational Inequalities

A well-known technique for the solution of quasi-variational inequalities (QVIs) consists in the reformulation of this problem as a constrained or unconstrained optimization problem by means of so-called gap functions. In contrast to standard variational inequalities, however, these gap functions turn out to be nonsmooth in general. Here, it is shown that one can obtain an unconstrained optimization reformulation of a class of QVIs with affine operator by using a continuously differentiable dual gap function. This extends an idea from Dietrich (J. Math. Anal. Appl. 235:380–393 [24]). Some numerical results illustrate the practical behavior of this dual gap function approach.     

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.     

Sequential optimality conditions for cardinality-constrained optimization problems with applications

Computational Optimization and Applications - Recently, a new approach to tackle cardinality-constrained optimization problems based on a continuous reformulation of the problem was proposed....     

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     

New NCP-Functions and Their Properties

Recently, Luo and Tseng proposed a class of merit functions for the nonlinear complementarity problem (NCP) and showed that it enjoys several interesting properties under some assumptions. In this paper, adopting a similar idea to that of Luo and Tseng, we present new merit functions for the NCP, which can be decomposed into component functions. We show that these merit functions not only share many properties with the one proposed by Luo and Tseng but also enjoy additional favorable properties owing to their decomposable structure. In particular, we present fairly mild conditions under which these merit functions have bounded level sets.