On the convergence properties of modified augmented Lagrangian methods for mathematical programming with complementarity constraints

In this paper, we present new convergence results of augmented Lagrangian methods for mathematical programs with complementarity constraints (MPCC). Modified augmented Lagrangian methods based on four different algorithmic strategies are considered for the constrained nonconvex optimization reformulation of MPCC. We show that the convergence to a global optimal solution of the problem can be ensured without requiring the boundedness condition of the multipliers.     

Convergence Properties of Modified and Partially-Augmented Lagrangian Methods for Mathematical Programs with Complementarity Constraints

We present new convergence properties of partially augmented Lagrangian methods for mathematical programs with complementarity constraints (MPCC). Four modified partially augmented Lagrangian methods for MPCC based on different algorithmic strategies are proposed and analyzed. We show that the convergence of the proposed methods to a B-stationary point of MPCC can be ensured without requiring the boundedness of the multipliers.     

An exponential penalty method for nondifferentiable minimax problems with general constraints

A well-known approach to constrained minimization is via a sequence of unconstrained optimization computations applied to a penalty function. This paper shows how it is possible to generalize Murphy's penalty method for differentiable problems of mathematical programming (Ref. 1) to solve nondifferentiable problems of finding saddle points with constraints. As in mathematical programming, it is shown that the method has the advantages of both Fiacco and McCormick exterior and interior penalty methods (Ref. 2). Under mild assumptions, the method has the desirable property that all trial solutions become feasible after a finite number of iterations. The rate of convergence is also presented. It should be noted that the results presented here have been obtained without making any use of differentiability assumptions.     

群零模正则化问题的等价Lipschitz优化模型

针对群零模正则化问题, 从零模函数的变分刻画入手, 将其等价地表示为带有 互补约束的数学规划问题(简称MPCC问题), 然后证明将互补约束直接罚到MPCC的目标函数而得到的罚问题是MPCC问题的全局精确罚. 此精确罚问题的目标函数不仅在可行集上全局Lipschitz连续而且还具有满意的双线性结构, 为设计群零模正则化问题的序列凸松弛算法提供了满意的等价Lipschitz优化模型.     

On the convergence rate for a penalty function method of exponential type

Recently, Kort and Bertsekas (Ref. 1) and Hartman (Ref. 2) presented independently a new penalty function algorithm of exponential type for solving inequality-constrained minimization problems. The main purpose of this work is to give a proof on the rate of convergence of a modification of the exponential penalty method proposed by these authors. We show that the sequence of points generated by the modified algorithm converges to the solution of the original nonconvex problem linearly and that the sequence of estimates of the optimal Lagrange multiplier converges to this multiplier superlinearly. The question of convergence of the modified method is discussed. The present paper hinges on ideas of Mangasarian (Ref. 3), but the case considered here is not covered by Mangasarian's theory.     

Optimization problems with equilibrium constraints and their numerical solution

We consider a class of optimization problems with a generalized equation among the constraints. This class covers several problem types like MPEC (Mathematical Programs with Equilibrium Constraints) and MPCC (Mathematical Programs with Complementarity Constraints). We briefly review techniques used for numerical solution of these problems: penalty methods, nonlinear programming (NLP) techniques and Implicit Programming approach (ImP). We further present a new theoretical framework for the ImP technique that is particularly useful in case of difficult equilibria. Finally, three numerical examples are presented: an MPEC that can be solved by ImP but can hardly be formulated as a nonlinear program, an MPCC that cannot be solved by ImP and finally an MPEC solvable by both, ImP and NLP techniques. In the last example we compare the efficiency of the two approaches.On leave from the Academy of Sciences of the Czech Republic.Mathematics Subject Classification (2000):49J40, 49J52, 90C30, 90C33     

Enlarging the region of convergence of Newton's method for constrained optimization

In this paper, we consider Newton's method for solving the system of necessary optimality conditions of optimization problems with equality and inequality constraints. The principal drawbacks of the method are the need for a good starting point, the inability to distinguish between local maxima and local minima, and, when inequality constraints are present, the necessity to solve a quadratic programming problem at each iteration. We show that all these drawbacks can be overcome to a great extent without sacrificing the superlinear convergence rate by making use of exact differentiable penalty functions introduced by Di Pillo and Grippo (Ref. 1). We also show that there is a close relationship between the class of penalty functions of Di Pillo and Grippo and the class of Fletcher (Ref. 2), and that the region of convergence of a variation of Newton's method can be enlarged by making use of one of Fletcher's penalty functions.This work was supported by the National Science Foundation, Grant No. ENG-79-06332.     

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.     

Penalty methods for mathematical programming inE nwith general constraint sets

This paper extends the principal supporting results and the general convergence theorems for penalty methods, obtained by Fiacco and McCormick (Ref. 1) for the continuous mathematical programming problem, to the problem of minimizing a mildly regulated objective function over any nonempty subset ofE ⁿ.The constraint set need not be defined through a collection of inequalities. A general auxiliary function is defined, and the desired minimizing sequence is shown to exist, without additional assumptions (i.e., assumptions other than those invoked in the principal convergence theorem of Ref. 1). A particularly interesting consequence is the fact that a discrete (e.g., integer) programming problem can be solved by asingle unconstrained minimization of the auxiliary function.     

Inexact Implicit Method with Variable Parameter for Mixed Monotone Variational Inequalities

In this paper, we focus on a useful modification of the implicit method by Noor (Ref. 1) for mixed variational inequalities. Experience on applications has shown that the number of iterations of the original method depends significantly on the penalty parameter. One of the contributions of the proposed method is that we allow the penalty parameter to be variable. By introducing a self-adaptive rule, we find that our method is more flexible and efficient than the original one. Another contribution is that we require only an inexact solution of the nonlinear equations at each iteration. A detailed convergence analysis of our method is also included.     

A Sequential Smooth Penalization Approach to Mathematical Programs with Complementarity Constraints

In this paper, a mathematical program with complementarity constraints (MPCC) is reformulated as a nonsmooth constrained mathematical program via the Fischer–Burmeister function. Smooth penalty functions are used to treat this nonsmooth constrained program. Under linear independence constraint qualification, and upper level strict complementarity condition, together with some other mild conditions, we prove that the limit point of stationary points satisfying second-order necessary conditions of unconstrained penalized problems is a strongly stationary point, hence a B-stationary point of the original MPCC. Furthermore, this limit point also satisfies a second-order necessary condition of the original MPCC. Numerical results are presented to test the performance of this method.     

Decomposition Method with a Variable Parameter for a Class of Monotone Variational Inequality Problems

In this paper, we focus on a useful modification of the decomposition method by He et al. (Ref. 1). Experience on applications has shown that the number of iterations of the original method depends significantly on the penalty parameter. The main contribution of our method is that we allow the penalty parameter to vary automatically according to some self-adaptive rules. As our numerical simulations indicate, the modified method is more flexible and efficient in practice. A detailed convergence analysis of our method is also included.     

Image space approach to penalty methods

In this paper, we introduce a unified framework for the study of penalty concepts by means of the separation functions in the image space (see Ref. 1). Moreover, we establish new results concerning a correspondence between the solutions of the constrained problem and the limit points of the unconstrained minima. Finally, we analyze some known classes of penalty functions and some known classical results about penalization, and we show that they can be derived from our results directly.     

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.     

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 geometric framework for nonconvex optimization duality using augmented lagrangian functions

We provide a unifying geometric framework for the analysis of general classes of duality schemes and penalty methods for nonconvex constrained optimization problems. We present a separation result for nonconvex sets via general concave surfaces. We use this separation result to provide necessary and sufficient conditions for establishing strong duality between geometric primal and dual problems. Using the primal function of a constrained optimization problem, we apply our results both in the analysis of duality schemes constructed using augmented Lagrangian functions, and in establishing necessary and sufficient conditions for the convergence of penalty methods.     

Planar Conjugate Gradient Algorithm for Large-Scale Unconstrained Optimization,Part 1: Theory

In this paper, we present a new conjugate gradient (CG) based algorithm in the class of planar conjugate gradient methods. These methods aim at solving systems of linear equations whose coefficient matrix is indefinite and nonsingular. This is the case where the application of the standard CG algorithm by Hestenes and Stiefel (Ref. 1) may fail, due to a possible division by zero. We give a complete proof of global convergence for a new planar method endowed with a general structure; furthermore, we describe some important features of our planar algorithm, which will be used within the optimization framework of the companion paper (Part 2, Ref. 2). Here, preliminary numerical results are reported.This work was supported by MIUR, FIRB Research Program on Large-Scale Nonlinear Optimization, Rome, ItalyThe author acknowledges Luigi Grippo and Stefano Lucidi, who contributed considerably to the elaboration of this paper. The exchange of experiences with Massimo Roma was a constant help in the investigation. The author expresses his gratitude to the Associate Editor and the referees for suggestions and corrections.     

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.     

Partial Augmented Lagrangian Method and Mathematical Programs with Complementarity Constraints

In this paper, we apply a partial augmented Lagrangian method to mathematical programs with complementarity constraints (MPCC). Specifically, only the complementarity constraints are incorporated into the objective function of the augmented Lagrangian problem while the other constraints of the original MPCC are retained as constraints in the augmented Lagrangian problem. We show that the limit point of a sequence of points that satisfy second-order necessary conditions of the partial augmented Lagrangian problems is a strongly stationary point (hence a B-stationary point) of the original MPCC if the limit point is feasible to MPCC, the linear independence constraint qualification for MPCC and the upper level strict complementarity condition hold at the limit point. Furthermore, this limit point also satisfies a second-order necessary optimality condition of MPCC. Numerical experiments are done to test the computational performances of several methods for MPCC proposed in the literature. This research was partially supported by the Research Grants Council (BQ654) of Hong Kong and the Postdoctoral Fellowship of The Hong Kong Polytechnic University. Dedicated to Alex Rubinov on the occassion of his 65th birthday.     

Convergence analysis of power penalty method for American bond option pricing

This paper is concerned with the convergence analysis of power penalty method to pricing American options on discount bond, where the single factor Cox–Ingrosll–Ross model is adopted for the short interest rate. The valuation of American bond option is usually formulated as a partial differential complementarity problem. We first develop a power penalty method to solve this partial differential complementarity problem, which produces a nonlinear degenerated parabolic PDE. Within the framework of variational inequalities, the solvability and convergence properties of this penalty approach are explored in a proper infinite dimensional space. Moreover, a sharp rate of convergence of the power penalty method is obtained. Finally, we show that the power penalty approach is monotonically convergent with the penalty parameter.