zbMATH — the first resource for mathematics

Weak infeasibility in second order cone programming. (English) Zbl 1391.90578
Summary: The objective of this work is to study weak infeasibility in second order cone programming. For this purpose, we consider a sequence of feasibility problems which mostly preserve the feasibility status of the original problem. This is used to show that for a given weakly infeasible problem at most \(m\) directions are needed to get arbitrarily close to the cone, where \(m\) is the number of Lorentz cones. We also tackle a closely related question and show that given a bounded optimization problem satisfying Slater’s condition, we may transform it into another problem that has the same optimal value but it is ensured to attain it. From solutions to the new problem, we discuss how to obtain solution to the original problem which are arbitrarily close to optimality. Finally, we discuss how to obtain finite certificate of weak infeasibility by combining our own techniques with facial reduction. The analysis is similar in spirit to previous work by the authors on SDPs, but a different approach is required to obtain tighter bounds on the number of directions needed to approach the cone.

90C30 Nonlinear programming
PDF BibTeX Cite
Full Text: DOI arXiv
[1] Borwein, JM; Moors, WB, Stability of closedness of convex cones under linear mappings, J. Convex Anal., 16, 699-705, (2009) · Zbl 1182.47057
[2] Borwein, JM; Wolkowicz, H, Facial reduction for a cone-convex programming problem, J. Aust. Math. Soc. (Ser. A), 30, 369-380, (1981) · Zbl 0464.90086
[3] Klep, I; Schweighofer, M, An exact duality theory for semidefinite programming based on sums of squares, Math. Oper. Res., 38, 569-590, (2013) · Zbl 1309.13031
[4] Liu, M; Pataki, G, Exact duality in semidefinite programming based on elementary reformulations, SIAM J. Optim., 25, 1441-1454, (2015) · Zbl 1317.90320
[5] Liu, M., Pataki, G.: Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming. Optimization Online (2015). http://www.optimization-online.org/DB_HTML/2015/06/4956.html · Zbl 1402.90115
[6] Lobo, MS; Vandenberghe, L; Boyd, S; Lebret, H, Applications of second-order cone programming, Linear Algebra Appl., 284, 193-228, (1998) · Zbl 0946.90050
[7] Lourenço, B.F., Muramatsu, M., Tsuchiya, T.: A structural geometrical analysis of weakly infeasible SDPs. Optimization Online (2013).http://www.optimization-online.org/DB_HTML/2013/11/4137.html · Zbl 1309.13031
[8] Lourenço, B.F., Muramatsu, M., Tsuchiya, T.: Solving SDP completely with an interior point oracle. Optimization Online (2015).http://www.optimization-online.org/DB_HTML/2015/06/4982.html · Zbl 1317.90320
[9] Luo, Z.Q., Sturm, J.F., Zhang, S.: Duality results for conic convex programming. Tech. rep., Econometric Institute, Erasmus University Rotterdam (1997) · Zbl 0967.65077
[10] Monteiro, RD; Tsuchiya, T, Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions, Math. Program., 88, 61-83, (2000) · Zbl 0967.65077
[11] Nesterov, Y., Nemirovskii, A.: Interior-point polynomial algorithms in convex programming. Soc. Ind. Appl. Math. (1994) · Zbl 0824.90112
[12] Pataki, G, On the closedness of the linear image of a closed convex cone, Math. Oper. Res., 32, 395-412, (2007) · Zbl 1341.90146
[13] Pataki, G.: Strong duality in conic linear programming: facial reduction and extended duals. Comput. Anal. Math. 50, 613-634 (2013) · Zbl 1282.90231
[14] Pólik, I; Terlaky, T, New stopping criteria for detecting infeasibility in conic optimization, Optim. Lett., 3, 187-198, (2009) · Zbl 1167.90586
[15] Rockafellar, R.T.: Convex analysis. Princeton University Press NJ, USA (1970) · Zbl 0193.18401
[16] Tsuchiya, T, A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming, Optim. Methods Softw., 11, 141-182, (1999) · Zbl 0957.90129
[17] Waki, H, How to generate weakly infeasible semidefinite programs via lasserres relaxations for polynomial optimization, Optim. Lett., 6, 1883-1896, (2012) · Zbl 1257.90069
[18] Waki, H; Muramatsu, M, Facial reduction algorithms for conic optimization problems, J. Optim. Theory Appl., 158, 188-215, (2013) · Zbl 1272.90048
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.