A recursive quadratic programming algorithm that uses differentiable exact penalty functions.(English)Zbl 0598.90079
Considered is the equality constrained nonlinear minimization problem: minimize \(f(x)\) subject to \(c(x)=0\), where \(f: \mathbb R^ n\to \mathbb R^ 1\) and \(c: \mathbb R^ n\to R^ m\) are twice continuously differentiable functions. The recursive quadratic programming method presented here for solving the above problem uses approximations to Fletcher’s differentiable exact penalty function [R. Fletcher, ibid. 5, 129–150 (1973;Zbl 0278.90063)] as line search functions. The algorithm has the important feature that approximations to the derivatives of Lagrange multipliers are employed that avoid the need to calculate any second derivatives. Global convergence and local superlinear convergence results are proved. Numerical results are also given.
Reviewer: C.A.Botsaris
MSC:
| 90C20 | Quadratic programming |
| 49M37 | Numerical methods based on nonlinear programming |
| 65K05 | Numerical mathematical programming methods |
Keywords:
equality constrained nonlinear minimization;recursive quadratic programming;differentiable exact penalty function;line search;approximations to the derivatives of Lagrange multipliers;Global convergence;local superlinear convergenceCitations:
Zbl 0278.90063Software:
NPSOLCite
Full Text:DOI
References:
| [1] | M.C. Biggs, ”On the convergence of some constrained minimization algorithms based on recursive quadratic programming”,J. Inst. Math. Appl. 21 (1978) 67–82. ·Zbl 0373.90056 ·doi:10.1093/imamat/21.1.67 |
| [2] | M.C. Bartholomew-Biggs, ”A recursive quadratic programming algorithm based on the augmented Lagrangian function”, Technical Report No. 139, Numerical Optimisation Centre, The Hatfield Polytechnic, 1983. ·Zbl 0636.90079 |
| [3] | D.P. Bertsekas, ”Augmented Lagrangian and differentiable exact penalty methods”, in: M.J.D. Powell, ed.,Nonlinear optimization 1981 (Academic Press, London, 1982) pp. 223–234. |
| [4] | D.P. Bertsekas,Constrained optimization and Lagrange multiplier methods (Academic Press, New York, 1982). ·Zbl 0572.90067 |
| [5] | P.T. Boggs, J.W. Tolle and P. Wang, ”On the local convergence of quasi-Newton methods for constrained optimization”,SIAM Journal of Control and Optimization 20 (1982) 161–171. ·Zbl 0494.65036 ·doi:10.1137/0320014 |
| [6] | R.M. Chamberlain, C. Lemarechal, H.C. Pedersen and M.J.D. Powell, ”The watchdog technique for forcing convergence in algorithms for constrained optimization”,Mathematical Programming Studies 16 (1982) 1–17. ·Zbl 0477.90072 ·doi:10.1007/BFb0120945 |
| [7] | G. Di Pillo, L. Grippo and F. Lampariello, ”A method for solving equality constrained optimization problems by constrained minimization”, in: K. Iracki, K. Malanowski and S. Walukiewicz, eds.,Optimization techniques Part 2, Lecture Notes in Control and Information Sciences 23 (Springer-Verlag, Berlin, 1980) pp. 96–105. ·Zbl 0445.90062 |
| [8] | R. Fletcher, ”A class of methods for nonlinear programming with termination and convergence properties”, in: J. Abadie, ed.,Integer and nonlinear programming (North Holland, Amsterdam, 1970). ·Zbl 0332.90039 |
| [9] | R. Fletcher, ”An exact penalty function for nonlinear programming with inequalities”,Mathematical Programming 5 (1973) 129–150. ·Zbl 0278.90063 ·doi:10.1007/BF01580117 |
| [10] | R. Fletcher, ”Penalty functions”, in: A. Bachem, M. Grotschel and B. Korte, eds.,Mathematical programming, the state of the art (Springer-Verlag, Berlin, 1983) pp. 87–113. ·Zbl 0542.90087 |
| [11] | P.E. Gill, W. Murray, M.A. Saunders and M.H. Wright, ”User’s guide for SOL/NPSOL:A fortran package for nonlinear programming”, Technical Report SOL 83-12. Department of Operations Research, Stanford University, Stanford. |
| [12] | S.P. Han, ”Superlinearly convergent variable metric algorithms for general nonlinear programming problems”,Mathematical Programming 11 (1976) 263–282. ·Zbl 0364.90097 ·doi:10.1007/BF01580395 |
| [13] | S.P. Han, ”A globally convergent method for nonlinear programming”,Journal of Optimization Theory and Applications 22 (1977) 297–309. ·Zbl 0336.90046 ·doi:10.1007/BF00932858 |
| [14] | M.J.D. Powell, ”A fast algorithm for nonlinearly constrained optimization calculations”, in: G.A. Watson, ed.,Numerical analysis Dundee 1977, Lecture Notes in Mathematics 630 (Springer-Verlag, Berlin, 1978) pp. 144–157. |
| [15] | M.J.D. Powell, ”The convergence of variable metric methods for nonlinear constrained optimization calculations”, in: O.L. Mangasarian, R.R. Meyer and S.M. Robinson, eds.,Nonlinear programming 3 (Academic Press, New York, 1978) pp. 27–63. ·Zbl 0464.65042 |
| [16] | M.J.D. Powell, ”Variable metric methods for constrained optimization”, in: A. Bachem, M. Grotschel and B. Korte, eds.,Mathematical programming, the state of the art (Springer-Verlag, Berlin, 1983) pp. 288–311. ·Zbl 0536.90076 |
| [17] | M.J.D. Powell, ”The performance of two subroutines for constrained optimization on some difficult test problems”, in: P.T. Boggs, R.H. Boyd and R.B. Schnabel, eds.,Numerical optimization 1984 (SIAM, Philadelphia, 1985) pp. 160–177. |
| [18] | K. Schittkowski, ”The nonlinear programming method of Wilson, Han, and Powell with an augmented Lagrangian type line search function, Part I: convergence analysis”,Numerische Mathematik 38 (1981) 83–114. ·Zbl 0534.65030 ·doi:10.1007/BF01395810 |
| [19] | K. Schittkowski, ”On the convergence of a sequential quadratic programming method with an augmented Lagrangian line search function”,Mathematische Operationsforschung und Statistik, Ser. Optimization 14 (1983) 197–216. ·Zbl 0523.90075 |
| [20] | R.B. Wilson, A simplicial algorithm for concave programming, Ph.D. Dissertation, Graduate School of Business Administration, Harvard University, Boston, 1963. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
