Weak infeasibility in second order cone programming

Weak infeasibility in second order cone programming

0.00 Avg rating0 Votes
Article ID: iaor20163745
Volume: 10
Issue: 8
Start Page Number: 1743
End Page Number: 1755
Publication Date: Dec 2016
Journal: Optimization Letters
Authors: , ,
Keywords: heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.