A primal-dual algorithm for nonlinear programming exploiting negative curvature directions

Gianni Di Pillo; Giampaolo  Liuzzi; Stefano  Lucidi

doi:10.3934/naco.2011.1.509

Article Contents

2011, Volume 1, Issue 3: 509-528. Doi: 10.3934/naco.2011.1.509

This issue Previous Article A unified nonlinear augmented Lagrangian approach for nonconvex vector optimization Next Article A smoothing Broyden-like method for polyhedral cone constrained eigenvalue problem

A primal-dual algorithm for nonlinear programming exploiting negative curvature directions

1.
Sapienza University of Rome, Department of Computer and System Sciences ``A. Ruberti'', Via Ariosto 25, 00185 Roma
2.
Italian National Research Council, Institute for Systems Analysis and Computer Science ``A. Ruberti'', Viale Manzoni 30, 00185 Roma

Received: April 2011

Revised: August 2011

Published: September 2011

Abstract / Introduction Related Papers Cited by

Abstract

In this paper we propose a primal-dual algorithm for the solution of inequality constrained optimization problems. The distinguishing feature of the proposed algorithm is that of exploiting as much as possible the local non-convexity of the problem to the aim of producing a sequence of points converging to second order stationary points. In the unconstrained case this task is accomplished by computing a suitable negative curvature direction of the objective function. In the constrained case it is possible to gain analogous information by exploiting the non-convexity of a particular exact merit function. The algorithm hinges on the idea of comparing, at every iteration, the relative effects of two directions and then selecting the more promising one. The first direction conveys first order information on the problem and can be used to define a sequence of points converging toward a KKT pair of the problem. Whereas, the second direction conveys information on the local non-convexity of the problem and can be used to drive the algorithm away from regions of non-convexity. We propose a proper selection rule for these two directions which, under suitable assumptions, is able to generate a sequence of points that is globally convergent to KKT pairs that satisfy the second order necessary optimality conditions, with superlinear convergence rate if the KKT pair satisfies also the strong second order sufficiency optimality conditions.

Keywords:

Mathematics Subject Classification: Primary: 90C30; Secondary: 65K05.

Citation:

Related Papers

Cited by

References

[1]	A. Auslender, Penalty methods for computing points that satisfy second order necessary conditions, Mathematical Programming, 17 (1979), 229-238.doi: 10.1007/BF01588245.
[2]	R. H. Byrd, R. B. Schnabel and G. A. Shultz, A trust region algorithm for nonlinearly constrained optimization, SIAM Journal on Numerical Analysis, 24 (1987), 1152-1170.doi: 10.1137/0724076.
[3]	F. H. Clarke, "Optimization and Nonsmooth Analysis," John Wiley & Sons, New York, 1983.
[4]	T. F. Coleman, J. G. Liu and W. Yuan, A new trust-region algorithm for equality constrained optimization, Computational Optimization and Applications, 21 (2002), 177-199.doi: 10.1023/A:1013764800871.
[5]	A. R. Conn, N. I. M. Gould, D. Orban and Ph. L. Toint, A primal-dual trust region algorithm for non-convex nonlinear programming, Math. Programming, Ser. B, 87 (2000), 215-249.
[6]	R. S. Dembo, S. C. Eisenstat and T. Steihaug, Inexact Newton methods, SIAM Journal on Numerical Anlysis, 19 (1982), 400-408.doi: 10.1137/0719025.
[7]	J. E. Dennis and L. N. Vicente, On the convergence theory of trust-region-based algorithms for equality-constrained optimization, SIAM Journal on Optimization, 7 (1994), 527-550.
[8]	J. E. Dennis, M. Heinkenschloss and L. N. Vicente, Trust-region interior-point SQP algorithms for a class of nonlinear programming problems, SIAM Journal on Control and Optimization, 36 (1998), 1750-1794.doi: 10.1137/S036012995279031.
[9]	G. Di Pillo and L. Grippo, Exact penalty functions in constrained optimization, SIAM J. on Control and Optimization, 27 (1989), 1333-1360.doi: 10.1137/0327068.
[10]	G. Di Pillo, G. Liuzzi, S. Lucidi and L. Palagi, A truncated Newton method in an augmented Lagrangian framework for nonlinear programming, Computational Optimization and Applications, 45 (2010), 311-352.doi: 10.1007/s10589-008-9216-3.
[11]	G. Di Pillo and S. Lucidi, On exact Augmented Lagrangian functions in nonlinear programming, In " Nonlinear Optimization and Applications"(eds. G. Di Pillo and F. Giannessi), Plenum Press, New York, (1996), 85-100.
[12]	G. Di Pillo and S. Lucidi, An augmented Lagrangian function with improved exactness properties, SIAM Journal on Optimization, 12 (2001), 376-406.doi: 10.1137/S1052623497321894.
[13]	G. Di Pillo, S. Lucidi and L. Palagi, Convergence to second-order stationary points of a primal-dual algorithm model for nonlinear programming, Mathematics of Operations Research, 30 (2005), 897-915.doi: 10.1287/moor.1050.0150.
[14]	M. M. El-Alem, Convergence to a second-order point of a trust-region algorithm with a nonmonotonic penalty parameter for constrained optimization, Journal of Optimization Theory and Applications, 91 (1996), 61-79.doi: 10.1007/BF02192282.
[15]	F. Facchinei, Minimization of SC1 functions and the Maratos effect, Operations Research Letters, 17 (1995), 131-137.doi: 10.1016/0167-6377(94)00059-F.
[16]	F. Facchinei, A. Fischer and C. Kanzow, On the accurate identification of active constraints, SIAM Journal on Optimization, 9 (1998), 14-32.doi: 10.1137/S1052623496305882.
[17]	F. Facchinei and S. Lucidi, Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems, Journal of Optimization Theory and Applications, 85 (1995), 265-289.doi: 10.1007/BF02192227.
[18]	F. Facchinei and S. Lucidi, Convergence to second order stationary points in inequality constrained optimization, Mathematics of Operations Research, 23 (1998), 746-766.doi: 10.1287/moor.23.3.746.
[19]	G. Fasano and S. Lucidi, A nonmonotone truncated Newton-Krylov method exploiting negative curvature directions, for large scale unconstrained optimization, Optimization Letters, 3 (2009), 521-535.doi: 10.1007/s11590-009-0132-y.
[20]	A. Forsgren and W. Murray, Newton methods for large-scale linear inequality constrained minimization, SIAM Journal on Optimization, 7 (1997), 162-176.doi: 10.1137/S1052623494279122.
[21]	L. Grippo, F. Lampariello and S. Lucidi, A truncated Newton method with nomonotone linesearch for unconstrained optimization, Journal of Optimization Theory and Applications, 60 (1989), 401-419.doi: 10.1007/BF00940345.
[22]	J. B. Hiriart-Urruty, J. J. Strodiot and V. H. Nguyen, Generalized Hessian matrix and second-order optimality conditions for problems with C^1,1 data, Applied Mathematics and Optimization, 11 (1984), 43-56.doi: 10.1007/BF01442169.
[23]	S. Lucidi, F. Rochetich and M. Roma, Curvilinear stabilization techniques for truncated Newton methods in large scale unconstrained optimization: The complete results, SIAM Journal on Optimization, 8 (1998), 916-939.doi: 10.1137/S1052623495295250.
[24]	G. P. McCormick, "Nonlinear Programming: Theory, Algorithms and Applications," John Wiley & Sons, New York, 1983.
[25]	J. M. Moguerza and F. J. Prieto, An augmented Lagrangian interior point method using directions of negative curvature, Mathematical Programming, 95 (2003), 573-616.doi: 10.1007/s10107-002-0360-8.
[26]	J. J. Moré and D. C. Sorensen, On the use of directions of negative curvature in a modified Newton method, Mathematical Programming, 16 (1979), 1-20.doi: 10.1007/BF01582091.
[27]	J. J. Moré and D. C. Sorensen, Computing a trust region step, SIAM Journal on Scientific and Statistical Computing, 4 (1983), 553-572.
[28]	H. Mukai and E. Polak, A second-order method for the general nonlinear programming problem, Journal of Optimization Theory and Applications, 26 (1978), 515-532.doi: 10.1007/BF00933150.
[29]	L. Qi and J. Sun, A nonsmooth version of Newton's method, Mathematical Programming, 58 (1993), 353-367.doi: 10.1007/BF01581275.
[30]	D. C. Sorensen, Newton's method with a model trust region modification, SIAM Journal on Numerical Analysis, 19 (1982), 409-426.doi: 10.1137/0719026.
[31]	P. Tseng, A convergent infeasible interior-point trust-region method for constrained optimization, SIAM Journal on Optimization, 13 (2002), 432-469.doi: 10.1137/S1052623499357945.