0
$\begingroup$

From what I understand:

  • When semidefinite programs (SDPs) don't obey Slater conditions, it is not guaranteed that interior-point methods (IPMs) converge.

  • It appears that facial reduction (FR) algorithms resolve this by re-writing such SDPs into equivalent SDPs (i.e., the solution of the new SDP gives us the solution of the old one) where the Slater condition does hold. However, a step in such FR algorithms requires solving a SDP that is very similar to the original one. There appears to be no guarantee that this SDP satisfies Slater conditions or is in fact in any way any easier than the original problem.

Please correct me if I am wrong. Is applying FR just blindly hoping for the best or is there any reason to believe the SDPs it requires to be solved are better behaved than the original SDP?

(I understand that if the individual FR steps terminate, FR will terminate but that appears to be a big unlikely assumption. If we are assuming all SDPs on the cone in question terminate by IPM we don't need FR anymore we can just solve the original problem by IPM by assumption.)

$\endgroup$
2
  • 1
    $\begingroup$ Do you agree with my edits? Do you have references on FR algorithms? Had never heard of them $\endgroup$ Commented Dec 5 at 11:19
  • $\begingroup$ felix-zhou.com/notes/co471.pdf Can't vouch for it being a great as I haven't done more than skim but it is linkable and discusses Facial Reduction. (Actually I should try to read it. It might contain the answer.) Algorithm example: arxiv.org/abs/1710.08954 $\endgroup$ Commented Dec 5 at 15:39

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.