Optimal Error Bounds in the Absence of Constraint Qualifications with Applications to p-Cones and Beyond

References

• [1] Attouch H, Bolte J, Redont P, Soubeyran A (2010) Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Łojasiewicz inequality. Math. Oper. Res. 35(2):438–457.Link, Google Scholar
• [2] Bauschke HH, Borwein JM, Li W (1999) Strong conical hull intersection property, bounded linear regularity, Jameson’s property (G), and error bounds in convex optimization. Math. Programming 86(1):135–160.Crossref, Google Scholar
• [3] Bolte J, Daniilidis A, Lewis A (2007) The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optim. 17(4):1205–1223.Crossref, Google Scholar
• [4] Bolte J, Nguyen TP, Peypouquet J, Suter BW (2017) From error bounds to the complexity of first-order descent methods for convex functions. Math. Programming 165(2):471–507.Crossref, Google Scholar
• [5] Borwein JM, Wolkowicz H (1981) Regularizing the abstract convex program. J. Math. Anal. Appl. 83(2):495–530.Crossref, Google Scholar
• [6] Chares R (2009) Cones and interior-point algorithms for structured convex optimization involving powers and exponentials. Unpublished PhD thesis, Université catholique de Louvain, Louvain-la-Neuve, Belgium.Google Scholar
• [7] Drusvyatskiy D, Lewis AS (2018) Error bounds, quadratic growth, and linear convergence of proximal methods. Math. Oper. Res. 43(3):919–948.Link, Google Scholar
• [8] Eldar YC, Mishali M (2009) Robust recovery of signals from a structured union of subspaces. IEEE Trans. Inform. Theory 55(11):5302–5316.Crossref, Google Scholar
• [9] Faraut J, Korányi A (1994) Analysis on Symmetric Cones. Oxford Mathematical Monographs (Clarendon Press, Oxford, UK).Crossref, Google Scholar
• [10] Faybusovich L (2008) Several Jordan-algebraic aspects of optimization. Optimization 57(3):379–393.Crossref, Google Scholar
• [11] Gowda MS, Trott D (2014) On the irreducibility, Lyapunov rank, and automorphisms of special Bishop–Phelps cones. J. Math. Anal. Appl. 419(1):172–184.Crossref, Google Scholar
• [12] Hoffman AJ (1952) On approximate solutions of systems of linear inequalities. J. Res. Natl. Bureau Standards 49(4):263–265.Crossref, Google Scholar
• [13] Ito M, Lourenço BF (2017) The p-cones in dimension n≥3 are not homogeneous when p≠2. Linear Algebra Its Appl. 533:326–335.Crossref, Google Scholar
• [14] Ito M, Lourenço BF (2019) The automorphism group and the non-self-duality of p-cones. J. Math. Anal. Appl. 471(1):392–410.Crossref, Google Scholar
• [15] Karimi M, Tunçel L (2020) Domain-Driven Solver (DDS) Version 2.0: A MATLAB-based software package for convex optimization problems in domain-driven form. Preprint, submitted November 10, https://arxiv.org/abs/1908.03075.Google Scholar
• [16] Kloft M, Brefeld U, Sonnenburg S, Zien A (2011) ℓp-norm multiple kernel learning. J. Machine Learn. Res. 12(26):953–997.Google Scholar
• [17] Lewis AS, Pang JS (1998) Error bounds for convex inequality systems. Crouzeix JP, Martínez-Legaz JE, Volle M, eds. Generalized Convexity, Generalized Monotonicity: Recent Results (Springer, New York), 75–110.Crossref, Google Scholar
• [18] Li G, Pong TK (2018) Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods. Foundations Comput. Math. 8(5):1199–1232.Crossref, Google Scholar
• [19] Lindstrom SB, Lourenço BF, Pong TK (2022) Error bounds, facial residual functions and applications to the exponential cone. Math. Programming 200(1):229–278.Crossref, Google Scholar
• [20] Liu T, Lourenço BF (2024) Convergence analysis under consistent error bounds. Foundations Comput. Math. 24:429–479.Google Scholar
• [21] Lourenço BF (2021) Amenable cones: Error bounds without constraint qualifications. Math. Programming 186(1–2):1–48.Crossref, Google Scholar
• [22] Lourenço BF, Muramatsu M, Tsuchiya T (2018) Facial reduction and partial polyhedrality. SIAM J. Optim. 28(3):2304–2326.Crossref, Google Scholar
• [23] Lourenço BF, Muramatsu M, Tsuchiya T (2021) Solving SDP completely with an interior point oracle. Optim. Methods Software 36(2–3):425–471.Crossref, Google Scholar
• [24] Lourenço BF, Roshchina V, Saunderson J (2022) Amenable cones are particularly nice. SIAM J. Optim. 32(3):2347–2375.Crossref, Google Scholar
• [25] Luo ZQ, Sturm JF (2000) Error analysis. Wolkowicz H, Saigal R, Vandenberghe L, eds. Handbook of Semidefinite Programming: Theory, Algorithms, and Applications (Springer Science + Business Media, New York), 163–189.Crossref, Google Scholar
• [26] Luo ZQ, Tseng P (1993) Error bounds and convergence analysis of feasible descent methods: A general approach. Ann. Oper. Res. 46(1):157–178.Crossref, Google Scholar
• [27] Nesterov Y (2012) Toward non-symmetric conic optimization. Optim. Methods Software 27(4–5):893–917.Crossref, Google Scholar
• [28] Orlitzky M (2022) On the symmetry of induced norm cones. Optimization 71(3):441–447.Crossref, Google Scholar
• [29] Pang JS (1997) Error bounds in mathematical programming. Math. Programming 79(1):299–332.Crossref, Google Scholar
• [30] Papp D, Yıldız S (2022) Alfonso: Matlab package for nonsymmetric conic optimization. INFORMS J. Comput. 34(1):11–19.Link, Google Scholar
• [31] Pataki G (2013) Strong duality in conic linear programming: Facial reduction and extended duals. Bailey DH, Bauschke HH, Borwein P, Garvan F, Théra M, Vanderwerff JD, Wolkowicz H, eds. Computational and Analytical Mathematics: In Honor of Jonathan Borwein’s 60th Birthday, vol. 50 (Springer, New York), 613–634.Crossref, Google Scholar
• [32] Skajaa A, Ye Y (2015) A homogeneous interior-point algorithm for nonsymmetric convex conic optimization. Math. Programming 150(2):391–422.Crossref, Google Scholar
• [33] Vinberg EB (1963) The theory of homogeneous convex cones. [In Russian.] Trans. Moscow Math. Soc. 12:340–403.Google Scholar
• [34] Waki H, Muramatsu M (2013) Facial reduction algorithms for conic optimization problems. J. Optim. Theory Appl. 158(1):188–215.Crossref, Google Scholar
• [35] Xue G, Ye Y (2000) An efficient algorithm for minimizing a sum of p-norms. SIAM J. Optim. 10(2):551–579.Crossref, Google Scholar
• [36] Yu P, Li G, Pong TK (2021) Kurdyka–Łojasiewicz exponent via Inf-projection. Foundations Comput. Math. 22(4):1171–1217.Crossref, Google Scholar
• [37] Yuan M, Lin Y (2006) Model selection and estimation in regression with grouped variables. J. Royal Statist. Soc. Ser. B. Statist. Methodology 68(1):49–67.Crossref, Google Scholar
• [38] Zhou Z, So AMC (2017) A unified approach to error bounds for structured convex optimization problems. Math. Programming 165(2):689–728.Crossref, Google Scholar
• [39] Zhou Z, Zhang Q, So AMC (2015) ℓ1,p-norm regularization: Error bounds and convergence rate analysis of first-order methods. Bach F, David Blei D, eds. Proc. 32nd Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 37 (PMLR, New York), 1501–1510.Google Scholar