×
Griva, Igor; Polyak, Roman A.

Primal-dual nonlinear rescaling method with dynamic scaling parameter update. (English) Zbl 1134.90494

Math. Program. 106, No. 2 (A), 237-259 (2006).
Summary: In this paper we developed a general primal-dual nonlinear rescaling method with dynamic scaling parameter update (PDNRD) for convex optimization. We proved the global convergence, established 1.5-Q-superlinear rate of convergence under the standard second order optimality conditions. The PDNRD was numerically implemented and tested on a number of nonlinear problems from COPS and CUTE sets. We present numerical results, which strongly corroborate the theory.

Cited in 27 Documents

MSC:

90C30 Nonlinear programming
90C46 Optimality conditions and duality in mathematical programming

Keywords:

Nonlinear rescaling; duality; Lagrangian; primal-dual; multipliers method

Software:

LIPSOL
PDF BibTeX XML Cite
\textit{I. Griva} and \textit{R. A. Polyak}, Math. Program. 106, No. 2 (A), 237--259 (2006; Zbl 1134.90494)
Full Text: DOI

References:

[1] Auslender, A., Comminetti, R., Haddou M.: Asymptotic analysis of penalty and barrier methods in convex and linear programming. Mathematics of Operations Research 22, 43–62 (1997) · Zbl 0872.90067
[2] Bendsoe, M., Ben-Tal, A., Zowe, J.: Optimization Methods for Truss Geometry and Topology Design. Structural Optimization 7, 141–159 (1994)
[3] Ben-Tal, A., Yuzefovich, I., Zibulevski, M.: Penalty/Barrier Multiplier Method for minimax and constrained smooth convex problems. Research Report 9/92, Optimization Laboratory, Faculty of Industrial Engineering and Management, Technion, 1992
[4] Ben-Tal, A., Zibulevski, M.: Penalty-barrier methods for convex programming problems. SIAM Journal on Optimization, 7, 347–366 (1997) · Zbl 0872.90068
[5] Bondarenko, A.S., Bortz, D.M., More J.J.: COPS: Large-scale nonlinearly constrained optimization problems. Mathematics and Computer Science Division, Argonne National Laboratory, Technical Report ANL/MCS-TM-237 (1999)
[6] Bongartz, I., Conn, A.R., Gould, N., Toint, Ph.L.: Constrained and unconstrained testing environment. http://www.cse.clrc.ac.uk/Activity/CUTE+74 · Zbl 0886.65058
[7] Breitfelt, M., Shanno D.: Experience with modified log-barrier method for nonlinear programming. Annals of Operations Research, 62, 439–464 (1996) · Zbl 0848.90108
[8] Cominetti, R., Dussault, J.-P.: A stable exponential-penalty algorithm with superlinear convergence. Journal of Optimization Theory and Applications, 83, (1994) · Zbl 0827.90125
[9] Dussault, J.-P.: Augmented penalty algorithms. I.M.A. Journal on Numerical Analysis, 18, 355–372 (1998) · Zbl 0907.65059
[10] Forsgren, A., Gill, P.: Primal-dual interior methods for nonconvex nonlinear programming. SIAM Journal on Optimization 8, 1132–1152 (1998) · Zbl 0915.90236
[11] Gay, D.M., Overton, M.L., Wright, M.H.: A primal-dual interior method for nonconvex nonlinear programming, A primal-dual interior method for nonconvex nonlinear programming, Advances in Nonlinear Programming. Ed. Y. Yuan, Kluwer Academic Publishers, Dordrecht, pp. 31–56 · Zbl 0908.90236
[12] Gould, N.I.M.: On the accurate determination of search directions for simple differentiable penalty functions. I.M.A. Journal on Numerical Analysis, 6, 357–372 (1986) · Zbl 0691.65054
[13] Gould, N.I.M.: On the convergence of a sequential penalty function method for constrained minimization. SIAM Journal on Numerical Analysis, 26, 107–108 (1989) · Zbl 0667.65050
[14] Gould, N.I.M., Orban, D., Sartenaer, A., Toint P.: Superlinear convergence of primal-dual interior point algorithms for nonlinear programming. SIAM Journal on Optimization, 11, 974–1002 (2001) · Zbl 1003.65066
[15] Kort, B.W., Bertsekas, D.P.: Multiplier methods for convex programming. Proceedings, IEEE Conference on Decision and Control. San Diego, California, pp. 428–432, 1973
[16] Lustig, I., Marsten, R., Shanno, D.: Computational experience with globally convergent primal-dual predictor-corrector algorithm for linear programming. Mathematical Programming 66, 23–135 (1994) · Zbl 0811.90068
[17] Megiddo, N.: Pathways to the optimal set in linear programming. in N. Megiddo, ed., Interior Point and Related Methods, Springer-Verlag, New York, Ch. 8, pp. 131–158, 1989 · Zbl 0687.90056
[18] Mehrotra, S.: On implementation of a primal-dual interior point method. SIAM Journal on Optimization 2, 575–601 (1992) · Zbl 0773.90047
[19] Melman, A., Polyak, R.: The Newton Modified Barrier Method for QP Problems. Annals of Operations Research, 62, 465–519 (1996) · Zbl 0848.90099
[20] Nash, S., Polyak, R., Sofer, A.: A numerical comparison of Barrier and Modified Barrier Method for Large-Scale Bound-Constrained Optimization. in ”Large Scale Optimization, state of the art”, Ed. by W. Hager, D. Hearn and P. Pardalos, Kluwer Academic Publisher, pp. 319–338, 1994 · Zbl 0811.90101
[21] Ng, E., Peyton, B.W.: Block sparse Cholesky algorithms on advanced uniprocessor computers. SIAM Journal of Scientific Computing, 14, 1034–1056 (1993) · Zbl 0785.65015
[22] Nocedal, J., Wright, S.: Numerical Optimization. Springer, New York, 1999 · Zbl 0930.65067
[23] Polyak, B.T.: Iterative methods for optimization problems with equality constraints using Lagrange multipliers. Journal of computational mathematics and mathematical physics, 10, 1098–1106 (1970) · Zbl 0217.27501
[24] Polyak, R.: Modified Barrier Functions Theory and Methods. Mathematical Programming 54, 177–222 (1992) · Zbl 0756.90085
[25] Polyak, R., Teboulle, M.: Nonlinear Rescaling and Proximal-like Methods in convex optimization. Mathematical Programming 76, 265–284 (1997) · Zbl 0882.90106
[26] Polyak, R., Griva, I., Sobieski, J.: The Newton Log-Sigmoid method in Constrained Optimization. A Collection of Technical Papers, 7th AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and Optimization 3, 2193–2201 (1998)
[27] Polyak, R.: Log-Sigmoid Multipliers Method in Constrained Optimization. Annals of Operations Research 101, 427–460 (2001) · Zbl 0996.90088
[28] Polyak, R.: Nonlinear rescaling vs. smoothing technique in convex optimization. Mathematical Programming 92, 197–235 (2002) · Zbl 1022.90014
[29] Polyak, R., Griva, I.: Primal-Dual Nonlinear Rescaling method for convex optimization. Technical Report 2002-05-01, George Mason University, to appear in JOTA in July 2004, ( http://mason.gmu.edu/\(\sim\)rpolyak/papers.html ). · Zbl 1129.90339
[30] Shanno, D., Vanderbei, R.: An interior-point algorithm for nonconvex nonlinear programming. COAP 13, 231–252 (1999) · Zbl 1040.90564
[31] Vanderbei, R.: Symmetric Quasidefinite Matrices. SIAM Journal on Optimization, 5, 100–113 (1995) · Zbl 0822.65017
[32] Wright, S.: Primal-Dual Interior Points methods. SIAM, 1997 · Zbl 0863.65031
[33] Zhang, Y.: Solving Large-Scale Linear Programs by Interior-Point Methods Under MATLAB Environment. Dept. of Computational and Applied Mathmatics, Rice University, Houston, 1996
[34] Zhang, Y., Tapia, R., Dennis, J.: On the superlinear and quadratic convergence at primal-dual interior point linear programming algorithms. SIAM Journal on Optimization 2, 304–324 (1992) · Zbl 0763.90066
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.