Weak Infeasibility in Second Order Cone Programming

Bruno F. Lourenco (flourenco.b.aam.titech.ac.jp)
Masakazu Muramatsu (muramatucs.uec.ac.jp)
Takashi Tsuchiya (tsuchiyagrips.ac.jp)

Abstract: The objective of this work is to study weak infeasibility in second order cone programming. For this purpose, we consider a relaxation sequence of feasibility problems that 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 approach 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.

Keywords: weak infeasibility; second order cone programming; feasibility problem

Category 1: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Citation:

Download: [PDF]

Entry Submitted: 09/17/2015
Entry Accepted: 09/17/2015
Entry Last Modified: 11/16/2015

Modify/Update this entry