×

Convergence analysis of a regularized interior point algorithm for the barrier problems with singular solutions. (English) Zbl 1279.65081

Summary: A. Wächter and L. T. Biegler [Math. Program. 106, No. 1 (A), 25–57 (2006; Zbl 1134.90542)] presented and implemented an interior point filter line search method (called IPOPT) for large scale nonlinear programming. To make IPOPT efficient and robust, they add some safeguards in their implementation. One crucial safeguard is to apply the inertia correction technique to modify the KKT matrix. We focus on the degenerate problems in which the KKT matrix might be singular. To complement theoretical foundation of this technique in the degenerate case, we propose and analyze a regularized interior point method for the barrier problems with singular solutions which largely relies on IPOPT. Based on the inertia correction technique, the matrix arising in the KKT equation is corrected to be a nonsingular one so that the Newton step can be calculated at each iteration even in the degenerate case. We emphasize that the special inertia correction for the KKT matrix does not impose any negative impact on the fast convergence of our algorithm. Under some local error bound condition, we prove that the rate of quadratic convergence is achieved when the second order condition or some constraint qualification condition fails to hold (or both).

MSC:

65K05 Numerical mathematical programming methods
90C55 Methods of successive quadratic programming type

Citations:

Zbl 1134.90542

Software:

Ipopt
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anitescu, M., Degenerate nonlinear programming with a quadratic growth condition, SIAM J. Optim., 10, 1116-1135 (2000) · Zbl 0994.65073
[2] Bonnans, J. F.; Ioffe, A., Second-order sufficiency and quadratic growth for nonisolated minima, Math. Oper. Res., 20, 801-819 (1995) · Zbl 0846.90095
[3] Cheng, S. H.; Higham, N. J., A modified cholesky algorithm based on a symmetric indefinite factorization, SIAM J. Matrix Anal. Appl., 19, 1097-1110 (1998) · Zbl 0949.65022
[4] Dan, H.; Yamashita, N.; Fukushima, M., Convergence properties of the inexact Levenberg-Marquardt method under local error bound conditions, Optim. Methods Softw., 17, 605-626 (2002) · Zbl 1030.65049
[5] Facchinei, F.; Fischer, A.; Kanzow, C., On the accurate identification of active constraints, SIAM J. Optim., 9, 1, 14-32 (1998) · Zbl 0960.90080
[6] Fan, J. Y., Convergence rate of the trust region method for nonlinear equations under local error bound condition, Comput. Optim. Appl., 34, 215-227 (2006) · Zbl 1121.65054
[7] Fan, J. Y.; Yuan, Y. X., On the quadratic convergence of the Levenberg-Marquardt method nonsingularity assumption, Computing, 74, 1, 23-39 (2005) · Zbl 1076.65047
[8] Fernández, D.; Solodov, M., Stabilized sequential quadratic programming for optimization and a stabilized Newton-type method for variational problems, Math. Program., 125, 47-73 (2010) · Zbl 1203.90144
[9] Fischer, A., Modified Wilson method for nonlinear programs with nonunique multipliers, Math. Oper. Res., 24, 699-727 (1999) · Zbl 0944.90085
[10] Gould, N. I.M., On practical conditions for the existence and uniqueness of solutions to the general equality quadratic programming problem, Math. Program., 32, 90-99 (1985) · Zbl 0591.90068
[11] Hager, W. W., Stabilized sequential quadratic programming, Comput. Optim. Appl., 12, 253-273 (1999) · Zbl 1040.90566
[12] Hager, W. W.; Gowda, M. S., Stability in the presence of degeneracy and error estimation, Math. Program., 85, 181-192 (1999) · Zbl 0956.90049
[13] Hoffman, A. J., On approximate solutions of systems of linear inequalities, J. Res. Nat. Bur. Standards, 49, 263-265 (1952)
[14] Ioffe, A., On sensitivity analysis of nonlinear programs in Banach spaces: the approach via composite unconstrained optimization, SIAM J. Optim., 4, 1-43 (1994) · Zbl 0820.90105
[15] Li, D. H.; Fukushima, M.; Qi, L.; Yamashita, N., Regularized newton methods for convex minimization problems with singular solutions, Comput. Optim. Appl., 28, 131-147 (2004) · Zbl 1056.90111
[17] Ralph, D.; Wright, S. J., Superlinear convergence of an interior-point method despite dependent constraints, Math. Oper. Res., 25, 179-194 (2000) · Zbl 0977.90082
[18] Shen, C. G.; Chen, X. D.; Liang, Y. M., A regularized Newton method for degenerate unconstrained optimization problems, Optim. Lett., 6, 8, 1913-1933 (2012) · Zbl 1258.90106
[20] Wächter, A.; Biegler, L. T., On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 25-57 (2006) · Zbl 1134.90542
[21] Wright, S. J., Superlinear convergence of a stabilized SQP method to a degenerate solution, Comput. Optim. Appl., 11, 253-275 (1998) · Zbl 0917.90279
[22] Wright, S. J., Modifying SQP for degenerate problems, SIAM J. Optim., 13, 470-497 (2002) · Zbl 1026.90097
[23] Wright, S. J., An algorithm for degenerate nonlinear programming with rapid local convergence, SIAM J. Optim., 15, 3, 673-696 (2005) · Zbl 1077.90067
[24] Yamashita, N.; Fukushima, M., On the rate of convergence of the Levenberg-Marquardt method, Computing, Suppl. 15, 237-249 (2001) · Zbl 1001.65047
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.