The exact penalty map for nonsmooth and nonconvex optimization

Augmented Lagrangian duality provides zero duality gap and saddle point properties for nonconvex optimization. On the basis of this duality, subgradient-like methods can be applied to the (convex) dual of the original problem. These methods usually recover the optimal value of the problem, but may fail to provide a primal solution. We prove that the recovery of a primal solution by such methods can be characterized in terms of (i) the differentiability properties of the dual function and (ii) the exact penalty properties of the primal-dual pair. We also connect the property of finite termination with exact penalty properties of the dual pair. In order to establish these facts, we associate the primal-dual pair to a penalty map. This map, which we introduce here, is a convex and globally Lipschitz function and its epigraph encapsulates information on both primal and dual solution sets.     

Exact penalty functions in proximal bundle methods for constrained convex nondifferentiable minimization

This paper presents new versions of proximal bundle methods for solving convex constrained nondifferentiable minimization problems. The methods employ ₁ or exact penalty functions with new penalty updates that limit unnecessary penalty growth. In contrast to other methods, some of them are insensitive to problem function scaling. Global convergence of the methods is established, as well as finite termination for polyhedral problems. Some encouraging numerical experience is reported. The ideas presented may also be used in variable metric methods for smooth nonlinear programming.This research was supported by the Polish Academy of Sciences.     

Regularized gap function as penalty term for constrained minimization problems

By using the regularized gap function for variational inequalities, Li and Peng introduced a new penalty function Pα(x) for the problem of minimizing a twice continuously differentiable function in closed convex subset of the n-dimensional space Rn. Under certain assumptions, they proved that the original constrained minimization problem is equivalent to unconstrained minimization of Pα(x). The main purpose of this paper is to give an in-depth study of those properties of the objective function that can be extended from the feasible set to the whole Rn by Pα(x). For example, it is proved that the objective function has bounded level sets (or is strongly coercive) on the feasible set if and only if Pα(x) has bounded level sets (or is strongly coercive) on Rn. However, the convexity of the objective function does not imply the convexity of Pα(x) when the objective function is not quadratic, no matter how small α is. Instead, the convexity of the objective function on the feasible set only implies the invexity of Pα(x) on Rn. Moreover, a characterization for the invexity of Pα(x) is also given.     

A Lagrange penalty reformulation method for constrained optimization

In this paper a constrained optimization problem is transformed into an equivalent one in terms of an auxiliary penalty function. A Lagrange function method is then applied to this transformed problem. Zero duality gap and exact penalty results are obtained without any coercivity assumption on either the objective function or constraint functions. The work of the authors was supported by the Australian Research Council (grant DP0343998), the Research Grants Council of Hong Kong (PolyU 5145/02E) and NNSF (10571174) of China, respectively.     

A two-parameter exact penalty function for nonlinear programming

A sequential quadratic programming algorithm for nonlinear programs using anl -exact penalty function is described. Numerical results are also presented. These results show that the algorithm is competitive with other exact penalty function based algorithms and that the inclusion of the second penalty parameter can be advantageous.     

An RQP algorithm using a differentiable exact penalty function for inequality constrained problems

In this paper we propose a recursive quadratic programming algorithm for nonlinear programming problems with inequality constraints that uses as merit function a differentiable exact penalty function. The algorithm incorporates an automatic adjustment rule for the selection of the penalty parameter and makes use of an Armijo-type line search procedure that avoids the need to evaluate second order derivatives of the problem functions. We prove that the algorithm possesses global and superlinear convergence properties. Numerical results are reported.     

非线性约束优化的光滑化平方根罚函数

介绍一种非线性约束优化的不可微平方根罚函数,为这种非光滑罚函数提出了一个新的光滑化函数和对应的罚优化问题,获得了原问题与光滑化罚优化问题目标之间的误差估计. 基于这种罚函数,提出了一个算法和收敛性证明,数值例子表明算法对解决非线性约束优化具有有效性.     

Nonmonotone bundle-type scheme for convex nonsmooth minimization

In this paper, we present a general scheme for bundle-type algorithms which includes a nonmonotone line search procedure and for which global convergence can be proved. Some numerical examples are reported, showing that the nonmonotonicity can be beneficial from a computational point of view.This work was partially supported by the National Research Program on Metodi di ottimizzazione per le decisioni, Ministero dell' Universitá e della Ricerca Scientifica e Tecnologica and by ASI: Agenzia Spaziale Italiana.     

A combination of penalty function and multiplier methods for solving optimal control problems

The properties of combined multiplier and penalty function methods are investigated using a second-order expansion and results known for the Riccati equation. It is shown that the lower bound of the values of the penalty constant necessary to obtain a minimum is given by a certain Riccati equation. The convergence rate of a common updating rule for the multipliers is shown to be linear.This work has been supported by the Swedish Institute of Applied Mathematics.     

On the convergence of quasi-newton methods for nonsmooth problems

We develop a theory of quasi-New ton and least-change update methods for solving systems of nonlinear equations F(x) = 0. In this theory, no differentiability conditions are necessary. Instead, we assume that Fcan be approximated, in a weak sense, by an affine function in a neighborhood of a solution. Using this assumption, we prove local and ideal convergence. Our theory can be applied to B-differentiable functions and to partially differentiable functions.     

Exact penalty function algorithm with simple updating of the penalty parameter

A new globally convergent algorithm for minimizing an objective function subject to equality and inequality constraints is presented. The algorithm determines a search direction by solving a quadratic programming subproblem, which always has an optimal solution, and uses an exact penalty function to compute the steplength along this direction through an Armijo-type scheme. The special structure of the quadratic subproblem is exploited to construct a new and simple method for updating the penalty parameter. This method may increase or reduce the value of the penalty parameter depending on some easily performed tests. A new method for updating the Hessian of the Lagrangian is presented, and a Q-superlinear rate of convergence is established.This work was supported in part by the British Council and the Conselho Nacional de Desenvolvimento Cientifico & Tecnologico/CNPq, Rio de Janeiro, Brazil.The authors are very grateful to Mr. Lam Yeung for his invaluable assistance in computing the results and to a reviewer for constructive advice.     

A computational study on different penalty approaches for solving constrained global optimization problems with the electromagnetism-like method

In this article, the application of the electromagnetism-like method (EM) for solving constrained optimization problems is investigated. A number of penalty functions have been tested with EM in this investigation, and their merits and demerits have been discussed. We have also provided motivations for such an investigation. Finally, we have compared EM with two recent global optimization algorithms from the literature. We have shown that EM is a suitable alternative to these methods and that it has a role to play in solving constrained global optimization problems.     

An exact penalty function method with global convergence properties for nonlinear programming problems

In this paper a new continuously differentiable exact penalty function is introduced for the solution of nonlinear programming problems with compact feasible set. A distinguishing feature of the penalty function is that it is defined on a suitable bounded open set containing the feasible region and that it goes to infinity on the boundary of this set. This allows the construction of an implementable unconstrained minimization algorithm, whose global convergence towards Kuhn-Tucker points of the constrained problem can be established.     

Globally convergent algorithm for nonlinearly constrained optimization problems

A new globally convergent algorithm for minimizing an objective function subject to equality and inequality constraints is presented. The algorithm determines a search direction by first solving a linear program and using the information gained thereby to define a quadratic approximation, with a guaranteed solution, to the original problem; the solution of the quadratic problem is the desired search direction. The algorithm incorporates a new method for choosing the penalty parameter. Numerical results illustrate the performance of the algorithm.The author wishes to thank Professor D. Q. Mayne and Dr. F. A. Pantoja for critically reviewing the first draft of this paper, for their suggestions, criticism, and contributions to some of the proofs. Support of the UK Science Research and Engineering Council is gratefully acknowledged.     

Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems

In this paper, some Newton and quasi-Newton algorithms for the solution of inequality constrained minimization problems are considered. All the algorithms described produce sequences {x _k } convergingq-superlinearly to the solution. Furthermore, under mild assumptions, aq-quadratic convergence rate inx is also attained. Other features of these algorithms are that only the solution of linear systems of equations is required at each iteration and that the strict complementarity assumption is never invoked. First, the superlinear or quadratic convergence rate of a Newton-like algorithm is proved. Then, a simpler version of this algorithm is studied, and it is shown that it is superlinearly convergent. Finally, quasi-Newton versions of the previous algorithms are considered and, provided the sequence defined by the algorithms converges, a characterization of superlinear convergence extending the result of Boggs, Tolle, and Wang is given.This research was supported by the National Research Program Metodi di Ottimizzazione per la Decisioni, MURST, Roma, Italy.     

On superlinear convergence in univariate nonsmooth minimization

This note demonstrates a new result on superlinear convergence in nonsmooth univariate minimization. It also gives other concepts of rapid convergence for minimization of functions that may have discontinuous derivatives.Research sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Numbers AFOSR-83-0210 and AFOSR-88-0180.     

A trust region algorithm for equality constrained optimization

A trust region algorithm for equality constrained optimization is proposed that employs a differentiable exact penalty function. Under certain conditions global convergence and local superlinear convergence results are proved.     

A note on solving nonlinear minimax problems via a differentiable penalty function

The note demonstrates that modeling a nonlinear minimax problem as a nonlinear programming problem and applying a classical differentiable penalty function to attempt to solve the problem can lead to convergence to a stationary point of the penalty function which is not a feasible point of the nonlinear programming problem. This occurred naturally in an application from statistical reliability theory. The note resolves the problem through modification of both the problem formulation and the iterative penalty function method.     

A recursive quadratic programming algorithm that uses differentiable exact penalty functions

In this paper, a recursive quadratic programming algorithm for solving equality constrained optimization problems is proposed and studied. The line search functions used are approximations to Fletcher's differentiable exact penalty function. Global convergence and local superlinear convergence results are proved, and some numerical results are given.