×

An interior point parameterized central path following algorithm for linearly constrained convex programming. (English) Zbl 1486.90144

Summary: An interior point algorithm is proposed for linearly constrained convex programming following a parameterized central path, which is a generalization of the central path and requires weaker convergence conditions. The convergence and polynomial-time complexity of the proposed algorithm are proved under the assumption that the Hessian of the objective function is locally Lipschitz continuous. In addition, an initialization strategy is proposed and some numerical results are provided to show the efficiency and attractiveness of the proposed algorithm.

MSC:

90C25 Convex programming
90C30 Nonlinear programming
90C51 Interior-point methods
90C60 Abstract computational complexity for mathematical programming problems

Software:

Ipopt
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alder, I.; Monteiro, RD, Limiting behavior of the affine scaling continuous trajectories for linear programming problems, Math. Program., 50, 1, 29-51 (1991) · Zbl 0719.90044
[2] Andrei, N., Predictor-corrector interior-point methods for linear constrained optimization, Stud. Inform. Control., 7, 2, 155-177 (1998)
[3] Andri, N., An unconstrained optimization test functions collection, Adv. Model. Optim., 10, 1, 147-181 (2008) · Zbl 1161.90486
[4] Burke, JV; Xu, S., The global linear convergence of a noninterior path-following algorithm for linear complementarity problems, Math. Oper. Res., 23, 3, 719-734 (1998) · Zbl 0977.90056
[5] Burke, JV; Xu, S., A non-interior predictor-corrector path following algorithm for the monotone linear complementarity problem, Math. Program., 87, 1, 113-130 (2000) · Zbl 1081.90603
[6] Burke, JV; Xu, S., Complexity of a noninterior path-following method for the linear complementarity problem, J. Optim. Theory Appl., 112, 1, 53-76 (2002) · Zbl 1049.90097
[7] Chen, B.; Chen, X., A global and local superlinear continuation-smoothing method for \({P}_0\) and \({R}_0\) NCP or monotone NCP, SIAM J. Optim., 9, 3, 624-645 (1999) · Zbl 0955.90132
[8] Chen, B.; Chen, X., A global linear and local quadratic continuation smoothing method for variational inequalities with box constraints, Comput Optimi Appl., 17, 2-3, 131-158 (2000) · Zbl 0987.90079
[9] Chen, B.; Harker, PT, A non-interior-point continuation method for linear complementarity problems, SIAM J. Matrix Anal. Appl., 14, 4, 1168-1190 (1993) · Zbl 0788.65073
[10] Chen, B.; Xiu, N., A global linear and local quadratic noninterior continuation method for nonlinear complementarity problems based on Chen-Mangasarian smoothing functions, SIAM J. Optim., 9, 3, 605-623 (1999) · Zbl 1037.90052
[11] Chen, X.; Tseng, P., Non-interior continuation methods for solving semidefinite complementarity problems, Math. Program., 95, 3, 431-474 (2003) · Zbl 1023.90046
[12] Chubanov, S., A polynomial-time descent method for separable convex optimization problems with linear constraints, SIAM J. Optim., 26, 1, 856-889 (2016) · Zbl 1338.90299
[13] Den Hertog, D.; Roos, C.; Terlaky, T., On the classical logarithmic barrier function method for a class of smooth convex programming problems, J. Optim. Theory Appl., 73, 1, 1-25 (1992) · Zbl 0794.90044
[14] Dikin, II, Iterative solution of problems of linear and quadratic programming, Dokl. Akad. Nauk SSSR, 174, 747-748 (1967) · Zbl 0189.19504
[15] Drummond, LG; Svaiter, BF, On well definedness of the central path, J. Optim. Theory Appl., 102, 2, 223-237 (1999) · Zbl 0941.90061
[16] Grossmann, C., Asymptotic analysis of a path-following barrier method for linearly constrained convex problems, Optimization, 45, 1-4, 69-87 (1999) · Zbl 0949.90074
[17] Grossmann, C., Penalty/Barrier path-following in linearly constrained optimization, Discuss. Math. Differ. Incl. Control Optim., 20, 1, 7-26 (2000) · Zbl 0980.90085
[18] Kanzow, C., Some noninterior continuation methods for linear complementarity problems, SIAM J. Matrix Anal. Appl., 17, 4, 851-868 (1996) · Zbl 0868.90123
[19] Karmarkar, N., A new polynomial-time algorithm for linear programming, Combinatorica, 4, 4, 373-395 (1984) · Zbl 0557.90065
[20] Kojima, M.; Megiddo, N.; Noma, T., Homotopy continuation methods for nonlinear complementarity problems, Math. Oper. Res., 16, 4, 754-774 (1991) · Zbl 0744.90087
[21] Kojima, M.; Mizuno, S.; Noma, T., Limiting behavior of trajectories generated by a continuation method for monotone complementarity problems, Math. Oper. Res., 15, 4, 662-675 (1990) · Zbl 0719.90085
[22] Kojima, M.; Mizuno, S.; Yoshise, A., A polynomial-time algorithm for a class of linear complementarity problems, Math. Program., 44, 1-3, 1-26 (1989) · Zbl 0676.90087
[23] Kojima, M., Mizuno, S., Yoshise, A.: A primal-dual interior point algorithm for linear programming. In: Progress in mathematical programming (Pacific Grove, CA, 1987), pp. 29-47. Springer, New York (1989) · Zbl 0708.90049
[24] Kojima, M.; Mizuno, S.; Yoshise, A., An \(O (\sqrt{n} {L})\) iteration potential reduction algorithm for linear complementarity problems, Math. Program., 50, 1-3, 331-342 (1991) · Zbl 0738.90077
[25] Kortanek, KO; Potra, F.; Ye, Y., On some efficient interior point methods for nonlinear convex programming, Linear Alg. Appl., 152, 169-189 (1991) · Zbl 0741.65052
[26] Kortanek, KO; Zhu, J., A polynomial barrier algorithm for linearly constrained convex programming problems, Math. Oper. Res., 18, 1, 116-127 (1993) · Zbl 0783.90099
[27] Kortanek, KO; Zhu, J., On controlling the parameter in the logarithmic barrier term for convex programming problems, J. Optim. Theory Appl., 84, 1, 117-143 (1995) · Zbl 0827.90113
[28] Liao, L-Z, A study of the dual affine scaling continuous trajectories for linear programming, J. Optim. Theory Appl., 163, 2, 548-568 (2014) · Zbl 1330.90052
[29] Mclinden, L., An analogue of Moreau’s proximation theorem, with application to the nonlinear complementarity problem, Pac. J. Math., 88, 1, 101-161 (1980) · Zbl 0403.90081
[30] Megiddo, N.: Pathways to the optimal set in linear programming. In: Progress in mathematical programming (Pacific Grove, CA, 1987), pp. 131-158. Springer, New York (1989) · Zbl 0687.90056
[31] Mehrotra, S.; Sun, J., An algorithm for convex quadratic programming that requires \({O}(n^{3.5}{L})\) arithmetic operations, Math. Oper. Res., 15, 2, 342-363 (1990) · Zbl 0714.90075
[32] Mehrotra, S., Sun, J.: An interior point algorithm for solving smooth convex programs based on Newton’s method. In: Mathematical developments arising from linear programming (Brunswick, ME, 1988), Contemp. Math., vol. 114, pp. 265-284. Amer. Math. Soc., Providence, RI (1990) · Zbl 0725.90078
[33] Mehrotra, S.; Sun, J., A method of analytic centers for quadratically constrained convex quadratic programs, SIAM J. Numer. Anal., 28, 2, 529-544 (1991) · Zbl 0742.65046
[34] Mizuno, S.: Polynomiality of the Kojima-Megiddo-Mizuno infeasible interior point algorithm for linear programming. Tech. Rep., Operations Research and Industrial Engineering, Cornell University (1992)
[35] Mizuno, S.; Todd, MJ; Ye, Y., On adaptive-step primal-dual interior-point algorithms for linear programming, Math. Oper. Res., 18, 4, 964-981 (1993) · Zbl 0810.90091
[36] Monteiro, RD, Convergence and boundary behavior of the projective scaling trajectories for linear programming, Math. Oper. Res., 16, 4, 842-858 (1991) · Zbl 0748.90041
[37] Monteiro, RD, On the continuous trajectories for a potential reduction algorithm for linear programming, Math. Oper. Res., 17, 1, 225-253 (1992) · Zbl 0793.90032
[38] Monteiro, RD, A globally convergent primal-dual interior point algorithm for convex programming, Math. Program., 64, 1-3, 123-147 (1994) · Zbl 0820.90086
[39] Monteiro, RD; Adler, I., Interior path following primal-dual algorithms. Part I: Linear programming, Math. Program., 44, 1-3, 27-41 (1989) · Zbl 0676.90038
[40] Monteiro, RD; Adler, I., Interior path following primal-dual algorithms. Part II: Convex quadratic programming, Math. Program., 44, 1-3, 43-66 (1989) · Zbl 0676.90039
[41] Monteiro, RD; Adler, I., An extension of Karmarkar type algorithm to a class of convex separable programming problems with global linear rate of convergence, Math. Oper. Res., 15, 3, 408-422 (1990) · Zbl 0708.90068
[42] Monteiro, RD; Tsuchiya, T.; Wang, Y., A simplified global convergence proof of the affine scaling algorithm, Ann. Oper. Res., 46, 2, 443-482 (1993) · Zbl 0804.90091
[43] Monteiro, RD; Zou, F., On the existence and convergence of the central path for convex programming and some duality results, Comput. Optim. Appl., 10, 1, 51-77 (1998) · Zbl 0907.90222
[44] Necoara, I.; Suykens, J., Interior-point Lagrangian decomposition method for separable convex optimization, J. Optim. Theory Appl., 143, 3, 567-588 (2009) · Zbl 1184.90126
[45] Potra, F.; Ye, Y., A quadratically convergent polynomial algorithm for solving entropy optimization problems, SIAM J. Optim., 3, 4, 843-860 (1993) · Zbl 0788.65071
[46] Qi, L.; Sun, D., Improving the convergence of non-interior point algorithms for nonlinear complementarity problems, Math. Comput., 69, 229, 283-304 (2000) · Zbl 0947.90117
[47] Qian, X., Liao, L.-Z.: Generalized affine scaling trajectory analysis for linearly constrained convex programming. In: International Symposium on Neural Networks, pp. 139-147. Springer (2018)
[48] Qian, X.; Liao, L-Z; Sun, J., Analysis of some interior point continuous trajectories for convex programming, Optimization, 66, 4, 589-608 (2017) · Zbl 1391.90479
[49] Qian, X.; Liao, L-Z; Sun, J., A strategy of global convergence for the affine scaling algorithm for convex semidefinite programming, Math. Program., 179, 1, 1-19 (2020) · Zbl 1435.90103
[50] Qian, X.; Liao, L-Z; Sun, J.; Zhu, H., The convergent generalized central paths for linearly constrained convex programming, SIAM J. Optim., 28, 2, 1183-1204 (2018) · Zbl 1387.90191
[51] Sheu, RL, A generalized interior-point barrier function approach for smooth convex programming with linear constraints, J. Inform. Optim. Sci., 20, 2, 187-202 (1999) · Zbl 0934.90057
[52] Shi, Y., A combination of potential reduction steps and steepest descent steps for solving convex programming problems, Numer. Linear Algebra Appl., 9, 3, 195-203 (2002) · Zbl 1071.90031
[53] Shi, Y., A projected-steepest-descent potential-reduction algorithm for convex programming problems, Numer. Linear Algebra Appl., 11, 10, 883-893 (2004) · Zbl 1164.65428
[54] Sonnevend, G.; Stoer, J.; Zhao, G., On the complexity of following the central path of linear programs by linear extrapolation II, Math. Program., 52, 1-3, 527-553 (1991) · Zbl 0742.90056
[55] Sun, J., A convergence analysis for a convex version of Dikin’s algorithm, Ann. Oper. Res., 62, 1, 357-374 (1996) · Zbl 0848.90101
[56] Sun, J.; Zhu, J.; Zhao, G., A predictor-corrector algorithm for a class of nonlinear saddle point problems, SIAM J. Control. Optim., 35, 2, 532-551 (1997) · Zbl 0868.49006
[57] Todd, MJ; Ye, Y., A centered projective algorithm for linear programming, Math. Oper. Res., 15, 3, 508-529 (1990) · Zbl 0722.90044
[58] Tseng, P.; Luo, ZQ, On the convergence of the affine-scaling algorithm, Math. Program., 56, 1-3, 301-319 (1992) · Zbl 0762.90052
[59] 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
[60] Wolfe, P., A duality theorem for non-linear programming, Quart. Appl. Math., 19, 3, 239-244 (1961) · Zbl 0109.38406
[61] Xu, S.; Burke, JV, A polynomial time interior-point path-following algorithm for LCP based on Chen-Harker-Kanzow smoothing techniques, Math. Program., 86, 1, 91-103 (1999) · Zbl 0978.90097
[62] Ye, Y., An \({O} (n^3{L})\) potential reduction algorithm for linear programming, Math. Program., 50, 1-3, 239-258 (1991) · Zbl 0734.90057
[63] Ye, Y.; Anstreicher, K., On quadratic and \({O}(\sqrt{n}{L})\) convergence of a predictor-corrector algorithm for LCP, Math. Program., 62, 1-3, 537-551 (1993) · Zbl 0799.90111
[64] Ye, Y.; Güler, O.; Tapia, RA; Zhang, Y., A quadratically convergent \({O}(\sqrt{n}{L})\)-iteration algorithm for linear programming, Math. Program., 59, 1-3, 151-162 (1993) · Zbl 0778.90037
[65] Zhu, J., A path following algorithm for a class of convex programming problems, Z. Oper. Res., 36, 4, 359-377 (1992) · Zbl 0761.90078
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.