...equivalence between original constrained problem and the unconstrained minimization of an exact augmented Lagrangian function and the use of a curvilinear line search technique that exploits information on the nonconvexity of the augmented Lagrangian function.

Key words: nonlinear programming; primal-dual algorithm; augmented Lagrangian function; second-order stationary point

MSC2000 subject classification: Primary: 90C30; secondary: 65K05

OR/MS subject classification: Primary: Nonlinear programming theory; secondary: nonlinear programming algorithms

History: Received May 6, 2002; revised May 5, 2003, March 15, 2004, and September 29, 2004.

1. Introduction. We consider the smooth constrained optimization problem

min f(x)

g(x) [less than or equal to] 0, (1)

where x [member of] [[??].sup.n] and f: [[??].sup.n] [right arrow] [??], g: [[??].sup.n] [right arrow] [[??].sup.m] are three times continuously differentiable functions.

A Karush-Kuhn-Tucker (KKT) pair for Problem (1) is a pair ([bar.x], [bar.[lambda]]) [member of] [[??].sup.n+m] such that

[[nabla].sub.x]L([bar.x], [bar.[lambda]]) = 0, [bar.[lambda]]'g([bar.x]) = 0, g([bar.x]) [less than or equal to] 0, [bar.[lambda]] [less than or equal to] 0, (2)

where L(x, [lambda]) = f(x) + [lambda]'g(x) is the Lagrangian function for Problem (1) and [lambda] [member of] [[??].sup.m] is the KKT multiplier. The strict complementarity condition holds at ([bar.x], [bar.[lambda]]) if [[bar.[lambda]].sub.j] > for all j such that [g.sub.j]([bar.x]) = 0.

If the linear independence constraints qualification (LICQ) holds at [bar.x], namely, if the gradients [nabla][g.sub.j]([bar.x]) with j: [g.sub.j]([bar.x]) = are linearly independent, then (2) are first-order necessary optimality conditions for Problem (1). The second-order necessary optimality conditions (SONC) are satisfied in a KKT pair ([bar.x], [bar.[lambda]]) if

y'[[nabla].sup.2.sub.x]L([bar.x], [bar.[lambda]])y [greater than or equal to] [for all] y: [nabla][g.sub.j]([bar.x])'y = with j: [g.sub.j]([bar.x]) = 0. (3)

Standard algorithms for constrained minimization usually generate sequences converging to KKT pairs. In this paper, we define a primal-dual algorithm model, having the potential for application to large-scale problems, that generates a sequence {([x.sup.k], [[lambda].sup.k])} converging to pairs satisfying also the second-order necessary conditions for optimality. Of course, convergence to second-order stationary points allows us to better select among the points candidate to be solutions of Problem(1).

The basis for the definition of the algorithm model is to recast the constrained problem as an unconstrained one and to adapt the techniques used in the unconstrained case.

In the unconstrained case, the necessary conditions boil down to [nabla]f([bar.x])= and [[nabla].sup.2]f([bar.x]) [??] 0. Convergence to second-order stationary points was established for trust-region algorithms in More and Sorensen [28], and Sorensen [31], and this constitutes one of the main reasons for the popularity of this class of methods. In an Armijo-type line search procedure, it is possible, by using directions of negative curvature, to guarantee convergence to second-order stationary points (Ferris et al. [17], Lucidi et al. [23], McCormick [24, 25], and More and Sorensen [27]). From a practical point of view, the use of negative curvature directions turned out to be very helpful in problems with strongly nonconvex regions (see Ferris et al. [17] and Lucidi et al. [23]).

The extension to the constrained case of techniques for the unconstrained case is not easy and requires theoretical investigation, in addition to technicalities.

For constrained problems, trust-region algorithms convergent to second-order stationary points have been developed for equality constrained and box constrained problems (Byrd et al. [3], Coleman et al. [5], Dennis and Vicente [7], Dennis et al. [8], El-Alem [13], More and Sorensen [28], and Sorensen [31]). In Conn et al. [6], an interior point primal-dual trust-region method for problems with general inequality constraints and linear equality constraints was proposed. In Tseng [32] an infeasible interior point method based on a trust region strategy was proposed that used a log-barrier function for the slack variables. Line search algorithms were proposed at the beginning for the linear inequality constrained case (Forsgren and Murray [18] and McCormick [25]) and then also for the more complex nonlinear inequality constrained Problem (1). In particular, in Mukai and Polak [29] the inequality constrained problem is reduced, by the introduction of slack variables, to an equality constrained one which is then dealt with by means of an exact penalty function. In Auslender [1], a negative curvature Armijo type line search approach is used in connection with a sequential penalty approach. In Facchinei and Lucidi [15], a curvilinear line search approach was proposed in connection with an exact penalty function. Recently, in Moguerza and Prieto [26] an interior point method with a curvilinear line search was proposed which used negative curvature directions in connection with an augmented Lagrangian function with the additional restriction on the infeasibility of the current iterate. Some interesting numerical experiments have been reported.

Of course, the definition of algorithms converging to second-order points needs the use of second-order information of the constrained problem that requires additional computational burden with respect to first-order convergent algorithms. This paper aims to perform a step in the direction of defining algorithms with a limited additional computational burden, drawing inspiration from second-order convergent unconstrained approaches for large-scale problems (such as Lucidi et al. [23]). Indeed, our algorithm scheme belongs to the class of line search methods and it is based on the unconstrained reformulation of the constrained problem by means of an exact augmented Lagrangian function. Our approach can be seen as a nontrivial modification of the method proposed in Facchinei and Lucidi [15], where a line search algorithm using negative curvature directions of an exact penalty function was proposed. However, the method proposed in Facchinei and Lucidi [15] is not suitable for problems with a large number of constraints. In fact, the exact continuously differentiable penalty function employed in Facchinei and Lucidi [15] incorporates a multiplier function (see (6) in [section] 2), so that every penalty function evaluation requires the exact solution of an m x m linear system.

In this paper, we follow the same basic ideas, namely, the use of an exact merit function and the use of an algorithm able to escape from the region of nonconvexity of the merit function. The merit function allows us to find a solution of the constrained problem by using unconstrained minimization techniques. Hence, taking inspiration from algorithms in the unconstrained case, we define a negative curvature algorithm that exploits information on the nonconvexity of the merit function obtainable by a suitable approximation of its generalized Hessian. The main differences with the algorithm proposed in Facchinei and Lucidi [15] are the following:

* the use of an exact augmented Lagrangian as a merit function, which avoids the solution of the m x m linear system needed for the evaluation of the exact penalty function; this makes the Lagrangian approach more suitable when the number of constraints is large.

* the definition of a new class of suitable negative curvature directions; these can be obtained efficiently during the calculation of the direction that enforces global convergence and superlinear rate of convergence as discussed at the end of [section] 5.

We prove convergence to second-order stationary points without requiring strict complementarity.

This paper is organized as follows. In [section] 2 we describe the exact augmented Lagrangian function [L.sub.a] employed in this paper. In particular, we use the exact augmented Lagrangian function [L.sub.a] studied in Di Pillo and Lucidi [11], where it is shown that the original constrained Problem (1) is equivalent to the unconstrained minimization of [L.sub.a] for sufficiently small values of a penalty parameter [??]. We report the main exactness results that we need in this paper. Furthermore, we perform a second-order analysis that plays a key role in the definition of the algorithm. Namely, we show that points satisfying the SONC for Problem (1) correspond to points satisfying some kind of second-order optimality condition for the unconstrained problem (which is not twice continuously differentiable).

Section 3 is dedicated to the definition of a curvilinear line search technique (CLS) for the minimization of [L.sub.a] for a fixed value of the penalty parameter [??]. In [section] 4 we introduce the overall algorithm (SOLA) converging to points satisfying the SONC. Updating rules for e that guarantee that it eventually stays fixed and that exactness properties are met are defined here.

In the definition of both CLS and SOLA, we make use of directions [d.sup.k], [s.sup.k] and matrices [Q.sup.k] satisfying some conditions for ensuring convergence to second-order stationary points. Section 5 is dedicated to the practical realization of the overall algorithm SOLA and CLS, namely, we describe how...

NOTE: All illustrations and photos have been removed from this article.



More articles from Mathematics of Operations Research
Efficient algorithms for separated continuous linear programs: the mul..., November 01, 2005
Boundedness theorems for the relaxation method., November 01, 2005
Characterizations of the strong basic constraint qualifications., November 01, 2005
Convergence of a hybrid projection-proximal point algorithm coupled wi..., November 01, 2005
Some P-properties for nonlinear transformations on Euclidean Jordan al..., November 01, 2005

Looking for additional articles?
Search our database of over 3 million articles.

Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication name or publication date.

About Goliath
Whether you're looking for sales prospects, competitive information, company analysis or best practices in managing your organization, Goliath can help you meet your business needs.

Our extensive business information databases empower business professionals with both the breadth and depth of credible, authoritative information they need to support their business goals. Whether it be strategic planning, sales prospecting, company research or defining management best practices - Goliath is your leading source for accurate information.