Amenable cones: error bounds without constraint qualifications. (English) Zbl 1459.90205
Summary: We provide a framework for obtaining error bounds for linear conic problems without assuming constraint qualifications or regularity conditions. The key aspects of our approach are the notions of amenable cones and facial residual functions. For amenable cones, it is shown that error bounds can be expressed as a composition of facial residual functions. The number of compositions is related to the facial reduction technique and the singularity degree of the problem. In particular, we show that symmetric cones are amenable and compute facial residual functions. From that, we are able to furnish a new Hölderian error bound, thus extending and shedding new light on an earlier result by Sturm on semidefinite matrices. We also provide error bounds for the intersection of amenable cones, this will be used to prove error bounds for the doubly nonnegative cone. At the end, we list some open problems.
MSC:
| 90C31 | Sensitivity, stability, parametric optimization |
| 65G99 | Error analysis and interval analysis |
| 17C55 | Finite-dimensional structures of Jordan algebras |
Keywords:
error bounds; amenable cones; facial reduction; singularity degree; symmetric cones; feasibility problem; subtransversalityReferences:
| [1] | Arima, N.; Kim, S.; Kojima, M.; Toh, K-C, Lagrangian-conic relaxations, part I: a unified framework and its applications to quadratic optimization problems, Pac. J. Optim., 14, 1, 161-192 (2018) · Zbl 1474.90314 |
| [2] | Arima, N.; Kim, S.; Kojima, M.; Toh, K-C, A robust Lagrangian-DNN method for a class of quadratic optimization problems, Comput. Optim. Appl., 66, 3, 453-479 (2017) · Zbl 1366.90152 |
| [3] | Baes, M.; Lin, H., A Lipschitzian error bound for monotone symmetric cone linear complementarity problem, Optimization, 64, 11, 2395-2416 (2015) · Zbl 1327.90191 |
| [4] | Barker, GP, Perfect cones, Linear Algebra Appl., 22, 211-221 (1978) · Zbl 0396.15009 |
| [5] | Bauschke, HH; Borwein, JM; Li, W., Strong conical hull intersection property, bounded linear regularity, Jameson’s property (G), and error bounds in convex optimization, Math. Program., 86, 1, 135-160 (1999) · Zbl 0998.90088 |
| [6] | Borwein, JM; Wolkowicz, H., Facial reduction for a cone-convex programming problem, J. Aust. Math. Soc. (Ser. A), 30, 3, 369-380 (1981) · Zbl 0464.90086 |
| [7] | Borwein, JM; Wolkowicz, H., Regularizing the abstract convex program, J. Math. Anal. Appl., 83, 2, 495-530 (1981) · Zbl 0467.90076 |
| [8] | Borwein, JM; Wolkowicz, H.; Guignard, M., Characterizations of optimality without constraint qualification for the abstract convex program, Optimality and Stability in Mathematical Programming, 77-100 (1982), Berlin: Springer, Berlin · Zbl 0495.90085 |
| [9] | Cheung, Y-L; Schurr, S.; Wolkowicz, H.; Bailey, DH; Bauschke, HH; Borwein, P.; Garvan, F.; Théra, M.; Vanderwerff, JD; Wolkowicz, H., Preprocessing and regularization for degenerate semidefinite programs, Computational and Analytical Mathematics, 251-303 (2013), New York: Springer, New York · Zbl 1288.90060 |
| [10] | Chua, CB, Relating homogeneous cones and positive definite cones via T-algebras, SIAM J. Optim., 14, 2, 500-506 (2003) · Zbl 1046.90058 |
| [11] | Chua, CB; Tunçel, L., Invariance and efficiency of convex representations, Math. Program., 111, 113-140 (2008) · Zbl 1157.90010 |
| [12] | Drusvyatskiy, D.; Li, G.; Wolkowicz, H., A note on alternating projections for ill-posed semidefinite feasibility problems, Math. Program., 162, 1, 537-548 (2017) · Zbl 1360.90188 |
| [13] | Drusvyatskiy, D.; Pataki, G.; Wolkowicz, H., Coordinate shadows of semidefinite and euclidean distance matrices, SIAM J. Optim., 25, 2, 1160-1178 (2015) · Zbl 1320.90054 |
| [14] | Drusvyatskiy, D., Wolkowicz, H.: The many faces of degeneracy in conic optimization. Technical report, University of Washington (2017) |
| [15] | Faraut, J.; Korányi, A., Analysis on Symmetric Cones (1994), Oxford: Clarendon Press, Oxford · Zbl 0841.43002 |
| [16] | Faybusovich, L., On Nesterov’s approach to semi-infinite programming, Acta Appl. Math., 74, 2, 195-215 (2002) · Zbl 1027.90098 |
| [17] | Faybusovich, L., Jordan-algebraic approach to convexity theorems for quadratic mappings, SIAM J. Optim., 17, 2, 558-576 (2006) · Zbl 1165.90591 |
| [18] | Faybusovich, L., Several Jordan-algebraic aspects of optimization, Optimization, 57, 3, 379-393 (2008) · Zbl 1191.90034 |
| [19] | Friberg, HA, A relaxed-certificate facial reduction algorithm based on subspace intersection, Oper. Res. Lett., 44, 6, 718-722 (2016) · Zbl 1408.90172 |
| [20] | Gowda, MS; Sznajder, R., Schur complements, Schur determinantal and Haynsworth inertia formulas in Euclidean Jordan algebras, Linear Algebra Appl., 432, 6, 1553-1559 (2010) · Zbl 1264.15014 |
| [21] | Hoffman, AJ, On approximate solutions of systems of linear inequalities, J. Res. Natl. Bur. Stand., 49, 4, 263-265 (1957) |
| [22] | Ioffe, AD, Variational Analysis of Regular Mappings: Theory and Applications (2017), Berlin: Springer, Berlin · Zbl 1381.49001 |
| [23] | Ito, M.; Lourenço, BF, A bound on the Carathéodory number, Linear Algebra Appl., 532, 347-363 (2017) · Zbl 1373.52008 |
| [24] | Ito, M.; Lourenço, BF, The \(p\)-cones in dimension \(n\ge 3\) are not homogeneous when \(p\ne 2\), Linear Algebra Appl., 533, 326-335 (2017) · Zbl 1447.52008 |
| [25] | Ito, M.; Lourenço, BF, The automorphism group and the non-self-duality of p-cones, J. Math. Anal. Appl., 471, 1, 392-410 (2019) · Zbl 1407.52003 |
| [26] | Kim, S.; Kojima, M.; Toh, K-C, A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems, Math. Program., 156, 1, 161-187 (2016) · Zbl 1342.90123 |
| [27] | Koecher, M., The Minnesota Notes on Jordan Algebras and Their Applications (1999), Berlin: Springer, Berlin · Zbl 1072.17513 |
| [28] | Lewis, AS; Pang, J-S; Crouzeix, J-P; Martínez-Legaz, J-E; Volle, M., Error bounds for convex inequality systems, Generalized Convexity, 75-110 (1998), New York: Springer, New York · Zbl 0953.90048 |
| [29] | Liu, M.; Pataki, G., Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming, Math. Program., 167, 2, 435-480 (2018) · Zbl 1402.90115 |
| [30] | Lourenço, B.F., Muramatsu, M., Tsuchiya, T.: Solving SDP completely with an interior point oracle. arXiv e-prints arXiv:1507.08065 (2015) |
| [31] | Lourenço, BF; Muramatsu, M.; Tsuchiya, T., Facial reduction and partial polyhedrality, SIAM J. Optim., 28, 3, 2304-2326 (2018) · Zbl 1401.90259 |
| [32] | Lourenço, BF; Fukuda, EH; Fukushima, M., Optimality conditions for problems over symmetric cones and a simple augmented Lagrangian method, Math. Oper. Res., 43, 4, 1233-1251 (2018) · Zbl 1510.90288 |
| [33] | Luo, Z.; Sturm, JF; Wolkowicz, H.; Saigal, R.; Vandenberghe, L., Error analysis, Handbook of Semidefinite Programming: Theory, Algorithms, and Applications (2000), Dordrecht: Kluwer Academic Publishers, Dordrecht · Zbl 0962.90001 |
| [34] | Luo, Z., Sturm, J.F., Zhang, S.: Duality results for conic convex programming. Technical report, Econometric Institute, Erasmus University Rotterdam, The Netherlands (1997) |
| [35] | Pang, J-S, Error bounds in mathematical programming, Math. Program., 79, 1, 299-332 (1997) · Zbl 0887.90165 |
| [36] | Pataki, G.; Wolkowicz, H.; Saigal, R.; Vandenberghe, L., The geometry of semidefinite programming, Handbook of Semidefinite Programming: Theory, Algorithms, and Applications (2000), Dordrecht: Kluwer Academic Publishers, Dordrecht · Zbl 0957.90531 |
| [37] | Pataki, G., On the connection of facially exposed and nice cones, J. Math. Anal. Appl., 400, 1, 211-221 (2013) · Zbl 1267.90098 |
| [38] | Pataki, G.; Bailey, DH; Bauschke, HH; Borwein, P.; Garvan, F.; Théra, M.; Vanderwerff, JD; Wolkowicz, H., Strong duality in conic linear programming: facial reduction and extended duals, Computational and Analytical Mathematics, 613-634 (2013), New York: Springer, New York · Zbl 1282.90231 |
| [39] | Permenter, F.: Private Communication (2016) |
| [40] | Permenter, F.; Friberg, HA; Andersen, ED, Solving conic optimization problems via self-dual embedding and facial reduction: a unified approach, SIAM J. Optim., 27, 3, 1257-1282 (2017) · Zbl 1368.90123 |
| [41] | Permenter, F.; Parrilo, P., Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone, Math. Program., 171, 1-54 (2017) · Zbl 1405.90098 |
| [42] | Pólik, I., Terlaky, T.: Exact duality for optimization over symmetric cones. AdvOL Report 2007/10, McMaster University, Advanced Optimization Lab, Hamilton, Canada. http://www.optimization-online.org/DB_HTML/2007/08/1754.html (2007) · Zbl 1251.90391 |
| [43] | Renegar, J., “Efficient” subgradient methods for general convex optimization, SIAM J. Optim., 26, 4, 2649-2676 (2016) · Zbl 1351.90129 |
| [44] | Rockafellar, RT, Convex Analysis (1970), Princeton: Princeton University Press, Princeton · Zbl 0193.18401 |
| [45] | Roshchina, V., Facially exposed cones are not always nice, SIAM J. Optim., 24, 1, 257-268 (2014) · Zbl 1291.90175 |
| [46] | Roshchina, V.; Tunçel, L., Facially dual complete (nice) cones and lexicographic tangents, SIAM J. Optim., 29, 3, 2363-2387 (2019) · Zbl 1425.52004 · doi:10.1137/17M1126643 |
| [47] | Sturm, JF, Error bounds for linear matrix inequalities, SIAM J. Optim., 10, 4, 1228-1248 (2000) · Zbl 0999.90027 |
| [48] | Sturm, JF, Similarity and other spectral relations for symmetric cones, Linear Algebra Appl., 312, 1-3, 135-154 (2000) · Zbl 0973.90093 |
| [49] | Sung, C-H; Tam, B-S, A study of projectionally exposed cones, Linear Algebra Appl., 139, 225-252 (1990) · Zbl 0724.52001 |
| [50] | Tam, B-S, A note on polyhedral cones, J. Aust. Math. Soc., 22, 4, 456-461 (1976) · Zbl 0338.52002 |
| [51] | Tunçel, L.; Wolkowicz, H., Strong duality and minimal representations for cone optimization, Comput. Optim. Appl., 53, 2, 619-648 (2012) · Zbl 1284.90080 |
| [52] | Waki, H.; Muramatsu, M., Facial reduction algorithms for conic optimization problems, J. Optim. Theory Appl., 158, 1, 188-215 (2013) · Zbl 1272.90048 |
| [53] | Yamashita, H.: Error bounds for nonlinear semidefinite optimization. Optimization Online (2016). http://www.optimization-online.org/DB_HTML/2016/10/5682.html |
| [54] | Yoshise, A., Matsukawa, Y.: On optimization over the doubly nonnegative cone. In: IEEE International Symposium on Computer-Aided Control System Design (CACSD), pp 13-18 (2010). doi:10.1109/CACSD.2010.5612811 |
| [55] | Zhu, Y.; Pataki, G.; Tran-Dinh, Q., Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs, Math. Program. Comput., 11, 3, 503-586 (2019) · Zbl 1479.90155 |
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.
