Worst-Case Iteration Bounds for Log Barrier Methods on Problems with Nonconvex Constraints

References

• [1] Andersen ED (2001) Certificates of primal or dual infeasibility in linear programming. Comput. Optim. Appl. 20:171–183.Crossref, Google Scholar
• [2] Andersen ED, Ye Y (1998) A computational study of the homogeneous algorithm for large-scale convex optimization. Comput. Optim. Appl. 10(3):243–269.Crossref, Google Scholar
• [3] Bian W, Chen X, Ye Y (2015) Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization. Math. Programming 149(1–2):301–327.Crossref, Google Scholar
• [4] Birgin EG, Gardenghi J, Martínez J, Santos S, Toint PL (2016) Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and high-order models. SIAM J. Optim. 26(2):951–967.Crossref, Google Scholar
• [5] Byrd RH, Gilbert JC, Nocedal J (2000) A trust region method based on interior point techniques for nonlinear programming. Math. Programming 89(1):149–185.Crossref, Google Scholar
• [6] Byrd RH, Nocedal J, Waltz RA (2006) KNITRO: An Integrated Package for Nonlinear Optimization. Large-Scale Nonlinear Optimization (Springer, New York), 35–59.Crossref, Google Scholar
• [7] Carmon Y, Duchi JC, Hinder O, Sidford A (2020) Lower bounds for finding stationary points I. Math. Programming 184(1–2):71–120.Crossref, Google Scholar
• [8] Carmon Y, Duchi JC, Hinder O, Sidford A (2021) Lower bounds for finding stationary points II: First-order methods. Math. Programming 185(1–2):315–355.Crossref, Google Scholar
• [9] Cartis C, Gould NI, Toint PL (2011a) Adaptive cubic regularisation methods for unconstrained optimization. Part ii: Worst-case function-and derivative-evaluation complexity. Math. Programming 130(2):295–319.Crossref, Google Scholar
• [10] Cartis C, Gould NI, Toint PL (2011b) On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming. SIAM J. Optim. 21(4):1721–1739.Crossref, Google Scholar
• [11] Cartis C, Gould NI, Toint PL (2014) On the complexity of finding first-order critical points in constrained nonlinear optimization. Math. Programming 144(1–2):93–106.Crossref, Google Scholar
• [12] Cartis C, Gould N, Toint PL (2020) Strong evaluation complexity bounds for arbitrary-order optimization of nonconvex nonsmooth composite functions. Preprint, submitted January 29, https://arxiv.org/abs/2001.10802.Google Scholar
• [13] Chen L, Goldfarb D (2006) Interior-point l2-penalty methods for nonlinear programming with strong global convergence properties. Math. Programming 108(1):1–36.Crossref, Google Scholar
• [14] Conn AR, Gould NI, Toint PL (2000b) Trust Region Methods (SIAM, Philadelphia).Crossref, Google Scholar
• [15] Conn AR, Gould NI, Orban D, Toint PL (2000a) A primal-dual trust-region algorithm for non-convex nonlinear programming. Math. Programming 87(2):215–249.Crossref, Google Scholar
• [16] Curtis FE, Robinson DP, Samadi M (2017) A trust region algorithm with a worst-case iteration complexity of O(ϵ−3/2) for nonconvex optimization. Math. Programming 162(1–2):1–32.Crossref, Google Scholar
• [17] Gander W, Golub GH, Von Matt U (1989) A constrained eigenvalue problem. Linear Algebra Appl. 114:815–839.Crossref, Google Scholar
• [18] Ghojogh B, Karray F, Crowley M (2019) Eigenvalue and generalized eigenvalue problems: Tutorial. Preprint, submitted March 25, https://arxiv.org/abs/1903.11240.Google Scholar
• [19] Gould NI, Orban D, Toint PL (2015) An Interior-Point ℓ1-Penalty Method for Nonlinear Optimization. Numerical Analysis and Optimization (Springer International Publishing, Cham, Switzerland), 51–190.Google Scholar
• [20] Gould NI, Robinson DP, Thorne HS (2010) On solving trust-region and other regularised subproblems in optimization. Math. Programming Comput. 2(1):21–57.Crossref, Google Scholar
• [21] Haeser G, Liu H, Ye Y (2019) Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary. Math. Programming 178:263–299.Crossref, Google Scholar
• [22] Hinder O, Ye Y (2018) A one-phase interior point method for nonconvex optimization. Preprint, submitted January 9, https://arxiv.org/abs/1801.03072.Google Scholar
• [23] John F (1948) Extremum problems with inequalities as side conditions. Stud. Essays: Courant Anniversary Vol., 187–204.Google Scholar
• [24] Karmarkar N (1984) A new polynomial-time algorithm for linear programming. Proc. 16th Annual ACM Sympos. Theory Comput. (ACM, New York), 302–311.Google Scholar
• [25] Kojima M, Mizuno S, Yoshise A (1989a) A polynomial-time algorithm for a class of linear complementarity problems. Math. Programming 44(1):1–26.Crossref, Google Scholar
• [26] Kojima M, Mizuno S, Yoshise A (1989b) A Primal-Dual Interior Point Algorithm for Linear Programming. Progress in Mathematical Programming (Springer, New York), 29–47.Google Scholar
• [27] Mangasarian OL, Fromovitz S (1967) The Fritz John necessary optimality conditions in the presence of equality and inequality constraints. J. Math. Anal. Appl. 17(1):37–47.Crossref, Google Scholar
• [28] Megiddo N (1989) Pathways to the Optimal Set in Linear Programming. Progress in Mathematical Programming (Springer, New York), 131–158.Google Scholar
• [29] Mehrotra S (1992) On the implementation of a primal-dual interior point method. SIAM J. Optim. 2(4):575–601.Crossref, Google Scholar
• [30] Monteiro RD, Adler I (1989) Interior path following primal-dual algorithms. Part I: Linear programming. Math. Programming 44(1):27–41.Crossref, Google Scholar
• [31] Nemirovskii A, Yudin DB (1983) Problem Complexity and Method Efficiency in Optimization (Wiley, New York).Google Scholar
• [32] Nesterov Y (1983) A method of solving a convex programming problem with convergence rate O(1/k2). Soviet Mathematics Doklady. 27:372–376.Google Scholar
• [33] Nesterov Y, Nemirovskii A (1994) Interior-Point Polynomial Algorithms in Convex Programming (SIAM, Philadelphia).Crossref, Google Scholar
• [34] Nesterov Y, Polyak BT (2006) Cubic regularization of newton method and its global performance. Math. Programming 108(1):177–205.Crossref, Google Scholar
• [35] Nocedal J, Wright S (2006) Numerical Optimization (Springer Science & Business Media, New York).Google Scholar
• [36] Pardalos PM, Schnitger G (1988) Checking local optimality in constrained quadratic programming is NP-hard. Oper. Res. Lett. 7(1):33–35.Crossref, Google Scholar
• [37] Renegar J (1988) A polynomial-time algorithm, based on Newton’s method, for linear programming. Math. Programming 40(1–3):59–93.Crossref, Google Scholar
• [38] Richard Johnsonbaugh WP (2010) Foundations of Mathematical Analysis (Dover Publications, Mineola, NY).Google Scholar
• [39] Sorensen DC (1982) Newton’s method with a model trust region modification. SIAM J. Numer. Anal. 19(2):409–426.Crossref, Google Scholar
• [40] Sturm JF (2002) Implementation of interior point methods for mixed semidefinite and second order cone optimization problems. Optim. Methods Softw. 17(6):1105–1154.Crossref, Google Scholar
• [41] Ulbrich S (2004) On the superlinear local convergence of a filter-SQP method. Math. Programming 100(1):217–245.Crossref, Google Scholar
• [42] Vanderbei RJ (1999) LOQO user’s manual—version 3.10. Optim. Methods Softw. 11(1–4):485–514.Crossref, Google Scholar
• [43] Vicente LN, Wright SJ (2002) Local convergence of a primal-dual method for degenerate nonlinear programming. Comput. Optim. Appl. 22(3):311–328.Crossref, Google Scholar
• [44] Wächter A, Biegler LT (2005) Line search filter methods for nonlinear programming: Motivation and global convergence. SIAM J. Optim. 16(1):1–31.Crossref, Google Scholar
• [45] Wächter A, Biegler LT (2006) On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Programming 106(1):25–57.Crossref, Google Scholar
• [46] Ye Y (1991) An O(n3L) potential reduction algorithm for linear programming. Math. Programming 50(1):239–258.Crossref, Google Scholar
• [47] Ye Y (1992) A New Complexity Result on Minimization of a Quadratic Function with a Sphere Constraint. Recent Advances in Global Optimization (Princeton University Press, Princeton, NJ), 19–31.Google Scholar
• [48] Ye Y (1998) On the complexity of approximating a KKT point of quadratic programming. Math. Programming 80(2):195–211.Crossref, Google Scholar
• [49] Ye Y (2018) MS&E311. Lecture note 12. https://web.stanford.edu/class/msande311/handout.shtml.Google Scholar
• [50] Ye Y, Todd MJ, Mizuno S (1994) An O(nL)-iteration homogeneous and self-dual linear programming algorithm. Math. Oper. Res. 19(1):53–67.Link, Google Scholar
• [51] Zhang Y (1994) On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem. SIAM J. Optim. 4(1):208–227.Crossref, Google Scholar