×

zbMATH — the first resource for mathematics

An interior point method for nonlinear optimization with a quasi-tangential subproblem. (English) Zbl 1388.90112
Summary: We present an interior point method for nonlinear programming in this paper. This method follows Byrd and Omojokun’s idea of step decomposition, which splits the trial step into a normal step and a tangential step. The method employs a new idea of quasi-tangential subproblem, which is used to generate a tangential step that does not lie strictly on the tangent space of the constraints. Quasi-tangential subproblem is finally formulated into an unconstrained quadratic problem by penalizing the constraints. This method is different and maybe simpler than similar ideas, for example, the relaxed tangential step in trust funnel methods ([N. I. M. Gould and Ph. L. Toint, Math. Program. 122, No. 1 (A), 155–196 (2010; Zbl 1216.90069)]; [F. E. Curtis et al., Math. Program. 161, No. 1–2 (A), 73–134 (2017; Zbl 1355.65075)]). Also, our method does not need to compute a base of the null space. A line search trust-funnel-like strategy is used to globalize the algorithm. Global convergence theorem is presented and applications to mathematical programs with equilibrium constraints are given.

MSC:
90C30 Nonlinear programming
90C51 Interior-point methods
Software:
ipfilter; Ipopt; LOQO; MacMPEC
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] El-Bakry, A.; Tapia, R.; Tsuchiya, T.; Zhang, Y., On the formulation and theory of the Newton interior-point method for nonlinear programming, J. Optim. Theory Appl., 89, 507-541, (1996) · Zbl 0851.90115
[2] Byrd, R.; Hribar, M.; Nocedal, J., An interior point algorithm for large-scale nonlinear programming, SIAM J. Optim., 9, 4, 877-900, (1999) · Zbl 0957.65057
[3] Ulbrich, M.; Ulbrich, S.; Vicente, L. N., A globally convergent primal-dual interior-point filter method for nonlinear programming, Math. Program., 100, 2, Ser. A, 379-410, (2004) · Zbl 1070.90110
[4] Curtis, F. E.; Schenk, O.; Wächter, A., An interior-point algorithm for large-scale nonlinear optimization with inexact step computations, SIAM J. Sci. Comput., 32, 6, 3447-3475, (2010) · Zbl 1220.49018
[5] Gondzio, J., Interior point methods 25 years later, European J. Oper. Res., 218, 3, 587-601, (2012) · Zbl 1244.90007
[6] Yamashita, H.; Yabe, H., Superlinear and quadratic convergence of some primal-dual interior point methods for constrained optimization, Math. Program., 75, 3, 377-397, (1996) · Zbl 0874.90175
[7] Forsgren, A.; Gill, P. E., Primal-dual interior methods for nonconvex nonlinear programming, SIAM J. Optim., 8, 4, 1132-1152, (1998) · Zbl 0915.90236
[8] Vanderbei, R. J., LOQO: an interior point code for quadratic programming, Optim. Methods Softw., 11, 1-4, 451-484, (1999) · Zbl 0973.90518
[9] 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, 1, 25-57, (2006) · Zbl 1134.90542
[10] Byrd, R. H.; Gilbert, J. C.; Nocedal, J., A trust region method based on interior point techniques for nonlinear programming, Math. Program., 89, 1, Ser. A, 149-185, (2000) · Zbl 1033.90152
[11] Curtis, F. E.; Huber, J.; Schenk, O.; Wächter, A., A note on the implementation of an interior-point algorithm for nonlinear optimization with inexact step computations, Math. Program., 136, 1, 209-227, (2012) · Zbl 1255.49043
[12] Nocedal, J.; Öztoprak, F.; Waltz, R. A., An interior point method for nonlinear programming with infeasibility detection capabilities, Optim. Methods Softw., 29, 4, 837-854, (2014) · Zbl 1306.90152
[13] R. Byrd, Robust trust region methods for constrained optimization, in: Third SIAM Conference on Optimization, 1987.
[14] Omojokun, E., Trust Region Algorithm for Optimization with Equalities and Inequalities Constraints, (1989), University of Cororado at Boulder, (Ph.D. thesis)
[15] Heinkenschloss, M.; Ridzal, D., An inexact trust-region SQP method with applications to PDE-constrained optimization, (Kunisch, K.; Of, G.; Steinbach, O., Numerical Mathematics and Advanced Applications, (2008), Springer Berlin Heidelberg), 613-620 · Zbl 1157.65385
[16] Gould, N. I.M.; Toint, Ph. L., Nonlinear programming without a penalty function or a filter, Math. Program., 122, 1, 155-196, (2010) · Zbl 1216.90069
[17] Curtis, F. E.; Gould, N. I.M.; Robinson, D. P.; Toint, Ph. L., An interior-point trust-funnel algorithm for nonlinear optimization, Math. Program., 161, 1, 73-134, (2017) · Zbl 1355.65075
[18] Bielschowsky, R. H.; Gomes, F. A.M., Dynamic control of infeasibility in equality constrained optimization, SIAM J. Optim., 19, 3, 1299-1325, (2008) · Zbl 1178.65063
[19] Xue, W. J.; Shen, C. G.; Pu, D. G., A penalty-function-free line search SQP method for nonlinear programming, J. Comput. Appl. Math., 228, 1, 313-325, (2009) · Zbl 1169.65060
[20] Shen, C. G.; Xue, W. J.; Pu, D. G., An infeasible nonmonotone SSLE algorithm for nonlinear programming, Math. Methods Oper. Res., 71, 103-124, (2010) · Zbl 1187.65071
[21] Qiu, S. Q.; Chen, Z. W., Global and local convergence of a class of penalty-free-type methods for nonlinear programming, Appl. Math. Model., 36, 7, 3201-3216, (2012) · Zbl 1252.90078
[22] Qiu, S. Q.; Chen, Z. W., A new penalty-free-type algorithm based on trust region techniques, Appl. Math. Comput., 218, 22, 11089-11099, (2012) · Zbl 1282.90182
[23] Byrd, R. H.; Liu, G.; Nocedal, J., On the local behavior of an interior point method for nonlinear programming, (Griffiths, D.; Higham, D., Numerical Analysis, (1997), Addison-Wesley Longman Reading, MA, USA), 37-56 · Zbl 0902.65021
[24] Vardi, A., A trust region algorithm for equality constrained minimization: convergence properties and implementation, SIAM J. Numer. Anal., 22, 3, 575-591, (1985) · Zbl 0581.65045
[25] Levenberg, K., A method for the solution of certain problems in least squares, Quart. Appl. Math., 2, 164-168, (1944) · Zbl 0063.03501
[26] Marquardt, D. W., An algorithm for least-squares estimation of nonlinear parameters, J. Soc. Ind. Appl. Math., 11, 2, 431-441, (1963) · Zbl 0112.10505
[27] Moré, J. J., The Levenberg-Marquardt algorithm: implementation and theory, (Numerical Analysis, (1978), Springer), 105-116 · Zbl 0372.65022
[28] Wright, S. J.; Nocedal, J., Numerical Optimization, Vol. 2, (1999), Springer New York · Zbl 0930.65067
[29] Yamashita, N.; Fukushima, M., On the rate of convergence of the Levenberg-Marquardt method, (Topics in Numerical Analysis, (2001), Springer), 239-249 · Zbl 1001.65047
[30] Fan, J. Y.; Yuan, Y. X., On the quadratic convergence of the Levenberg-Marquardt method without nonsingularity assumption, Computing, 74, 1, 23-39, (2005) · Zbl 1076.65047
[31] Zhang, J. L., On the convergence properties of the Levenberg-Marquardt method, Optimization, 52, 6, 739-756, (2003) · Zbl 1059.90132
[32] Kimiaei, M., Nonmonotone self-adaptive Levenberg-Marquardt approach for solving systems of nonlinear equations, Numer. Funct. Anal. Optim., 1-20, (2017)
[33] Conn, A. R.; Gould, N. I.M.; Orban, D.; Toint, P. L., A primal-dual trust-region algorithm for non-convex nonlinear programming, Math. Program., 87, 2, Ser. B, 215-249, (2000) · Zbl 0970.90116
[34] Yamashita, H.; Yabe, H.; Tanabe, T., A globally and superlinearly convergent primal-dual interior point trust region method for large scale constrained optimization, Math. Program., 102, 111-151, (2005) · Zbl 1062.90036
[35] Wächter, A.; Biegler, L. T., Line search filter methods for nonlinear programming: motivation and global convergence, SIAM J. Optim., 16, 1, 1-31, (2005) · Zbl 1114.90128
[36] Stewart, G. W.; Sun, J. G., Matrix Perturbation Theory, Vol. 175, (1990), Academic Press New York
[37] De Silva, A. H., Sensitivity Formulas for Nonlinear Factorable Programming and their Application to the Solution of an Implicitly Defined Optimization Model of us Crude Oil Production, (1978), George Washington University Washington D.C., (Dissertation)
[38] Friesz, T. L.; Tobin, R. L.; Cho, H. J.; Mehta, N. J., Sensitivity analysis based heuristic algorithms for mathematical programs with variational inequality constraints, Math. Program., 48, 1, 265-284, (1990) · Zbl 0723.90070
[39] Outrata, J.; Zowe, J., A numerical approach to optimization problems with variational inequality constraints, Math. Program., 68, 1-3, 105-130, (1995) · Zbl 0835.90093
[40] S. Leyffer, MacMPEC: Ampl collections of mpecs, (August 2005). http://www.msc.anl.gov/ leyffer/MacMPEC.
[41] Henderson, J.; Quandt, R., Microeconomic Theory, (1980), McGraw-Hill New York
[42] Facchinei, F.; Jiang, H.; Qi, L., A smoothing method for mathematical problems with equilibrium constraints, Math. Program., 85, 107-134, (1999) · Zbl 0959.65079
[43] Outrata, J. V., On optimization problems with variational inequality constraints, SIAM J. Optim., 4, 2, 340-357, (1994) · Zbl 0826.90114
[44] Vanderbei, R., Symmetric quasidefinite matrices, SIAM J. Optim., 5, 1, 100-113, (1995) · Zbl 0822.65017
[45] Friedlander, M. P.; Tseng, P., Exact regularization of convex programs, SIAM J. Optim., 18, 4, 1326-1350, (2007) · Zbl 1176.90457
[46] Friedlander, M. P.; Orban, D., A primal-dual regularized interior-point method for convex quadratic programs, Math. Program. Comput., 4, 1, 71-107, (2012) · Zbl 1279.90193
[47] Wright, S. J., Modifying SQP for degenerate problems, SIAM J. Optim., 13, 2, 470-497, (2002) · Zbl 1026.90097
[48] Wright, S. J., Superlinear convergence of a stabilized SQP method to a degenerate solution, Comput. Optim. Appl., 11, 3, 253-275, (1998) · Zbl 0917.90279
[49] Hager, W. W., Stabilized sequential quadratic programming, Comput. Optim. Appl., 12, 1-3, 253-273, (1999) · Zbl 1040.90566
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.