×

A primal-dual modified log-barrier method for inequality constrained nonlinear optimization. (English) Zbl 1460.90181

Summary: We present a primal-dual modified log-barrier algorithm to solve inequality constrained nonlinear optimization problems. Basically, the algorithm is a Newton-like method applied to a perturbation of the optimality system that follows from a reformulation of the initial problem by introducing a modified log-barrier function to handle inequality constraints. The algorithm uses an outer/inner iteration scheme and the globalization is performed in the primal-dual space by means of a new primal-dual merit function. The robustness and efficiency of the algorithm is improved using quadratic extrapolation. The numerical performance of the new method is illustrated by comparing it with a primal-dual classical log-barrier method and two well-established interior-point solvers on two sets of problems from COPS and Hock-Schittkowski collections, including a set of problems that exhibits degeneracy.

MSC:

90C30 Nonlinear programming

Software:

COPS; OPTMODEL; SAS; Ipopt
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Armand, P.; Benoist, J.; Omheni, R.; Pateloup, V., Study of a primal-dual algorithm for equality constrained minimization, Comput. Optim. Appl., 59, 3, 405-433 (2014) · Zbl 1304.49050 · doi:10.1007/s10589-014-9679-3
[2] Armand, P.; Omheni, R., A globally and quadratically convergent primal-dual augmented lagrangian algorithm for equality constrained optimization, Optim. Methods Softw., 32, 1, 1-21 (2017) · Zbl 1365.90209 · doi:10.1080/10556788.2015.1025401
[3] Armand, P.; Omheni, R., A mixed logarithmic barrier-augmented lagrangian method for nonlinear optimization, J. Optim. Theory Appl., 173, 2, 523-547 (2017) · Zbl 1370.49022 · doi:10.1007/s10957-017-1071-x
[4] Armand, P., Orban, D.: The squared slacks transformation in nonlinear programming. Sultan Qaboos University Journal for Science [SQUJS] 17(1), (2012)
[5] Ben-Tal, A.; Zibulevsky, M., Penalty/barrier multiplier methods for convex programming problems, SIAM J. Optim., 7, 2, 347-366 (1997) · Zbl 0872.90068 · doi:10.1137/S1052623493259215
[6] Breitfeld, MG; Shanno, DF; Hager, WW; Hearn, DW; Pardalos, PM, Preliminary computational experience with modified log-barrier functions for large-scale nonlinear programming, Large Scale Optim. State Art, 45-67 (1994), US: Springer, US · Zbl 0811.90093
[7] Breitfeld, MG; Shanno, DF, Computational experience with penalty-barrier methods for nonlinear programming, Ann. Oper. Res., 62, 439-463 (1996) · Zbl 0848.90108 · doi:10.1007/BF02206826
[8] Byrd, RH; Gilbert, JC; Nocedal, J., A trust region method based on interior point techniques for nonlinear programming, Math. Program., 89, 1, 149-185 (2000) · Zbl 1033.90152 · doi:10.1007/PL00011391
[9] Conn, AR; Gould, N.; Toint, PL, A globally convergent lagrangian barrier algorithm for optimization with general inequality constraints and simple bounds, Math. Comput., 66, 261-288 (1992) · Zbl 0854.90125 · doi:10.1090/S0025-5718-97-00777-1
[10] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[11] Dolan, E.D., Moré, J.J., Munson, T.S.: Benchmarking optimization software with COPS 3.0. Tech. rep., Argonne National Laboratory (2004)
[12] Fiacco, AV; McCormick, GP, Nonlinear Programming: Sequential Unconstrained Minimization Techniques (1968), New York: Wiley, New York · Zbl 0193.18805
[13] Forsgren, A.; Gill, PE, Primal-dual interior methods for nonconvex nonlinear programming, SIAM J. Optim., 8, 4, 1132-1152 (1998) · Zbl 0915.90236 · doi:10.1137/S1052623496305560
[14] Frisch, K.R.: The logarithmic potential method of convex programming. Memorandum, University Institute of Economics, Oslo (1955)
[15] Gay, D.M., Overton, M.L., Wright, M.A.H.: A primal-dual interior method for nonconvex nonlinear programming. In: Advances in nonlinear programming (Beijing, 1996), Appl. Optim., vol. 14, pp. 31-56. Kluwer Acad. Publ., Dordrecht (1998) · Zbl 0908.90236
[16] Gill, P.E., Murray, W., Wright, M.H.: Practical optimization. Academic Press Inc. [Harcourt Brace Jovanovich Publishers], London (1981) · Zbl 0503.90062
[17] Goldfarb, D.; Polyak, R.; Scheinberg, K.; Yuzefovich, I., A modified barrier-augmented Lagrangian method for constrained minimization, Comput. Optim. Appl., 14, 1, 55-74 (1999) · Zbl 0951.90042 · doi:10.1023/A:1008705028512
[18] Hock, W., Schittkowski, K.: Test examples for nonlinear programming codes, Lecture Notes in Economics and Mathematical Systems, vol. 187. Springer, Berlin (1981) · Zbl 0452.90038
[19] Murray, W., Analytical expressions for the eigenvalues and eigenvectors of the Hessian matrices of barrier and penalty functions, J. Optim. Theory Appl., 7, 189-196 (1971) · Zbl 0198.52504 · doi:10.1007/BF00932477
[20] Murray, W.; Wright, MH, Line search procedures for the logarithmic barrier function, SIAM J. Optim., 4, 2, 229-246 (1994) · Zbl 0806.65062 · doi:10.1137/0804013
[21] Nash, S.G., Polyak, R., Sofer, A.: A numerical comparison of barrier and modified barrier methods for large-scale bound-constrained optimization. In: Large scale optimization (Gainesville, FL, 1993), pp. 319-338. Kluwer Acad. Publ., Dordrecht (1994) · Zbl 0811.90101
[22] Nocedal, J.; Wright, SJ, Numerical optimization, Springer Series in Operations Research and Financial Engineering (2006), New York: Springer, New York · Zbl 1104.65059
[23] Polyak, R., Modified barrier functions (theory and methods), Math. Program., 54, 2, 177-222 (1992) · Zbl 0756.90085 · doi:10.1007/BF01586050
[24] SAS Institute: The optmodel procedure. In: SAS/OR 14.3 Users Guide: Mathematical Programming, pp. 23-189 (2017)
[25] Shanno, DF; Vanderbei, RJ, Interior-point methods for nonconvex nonlinear programming: orderings and higher-order methods, Math. Program., 87, 2, 303-316 (2000) · Zbl 1054.90091 · doi:10.1007/s101070050116
[26] Silva, R.; Soares, J.; Vicente, LN, Local analysis of the feasible primal-dual interior-point method, Comput. Optim. Appl., 40, 1, 41-57 (2008) · Zbl 1192.90248 · doi:10.1007/s10589-007-9075-3
[27] Wächter, A.; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 1, 25-57 (2006) · Zbl 1134.90542 · doi:10.1007/s10107-004-0559-y
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.