4
$\begingroup$

In Nemirovxki's lecture notes on interior point methods, I found the following.

enter image description here

He defines an approximate solution as satisfying the following, for any given $\epsilon>0$:

enter image description here

that is: the constraints represented by the functions $g_j$ are not satisfied exactly - they are satisfied only approximately (up to $\epsilon$).

In some cases, approxiamtely-feasible solutions may be useless - we need solutions that are exactly feasible, even if only approximately optimal. It seems that Nemirovsky "gives up" on this possibility from the beginning. I am trying to understand why.

QUESTIONS:

  • Is there a known impossibility result, showing that it is impossible to find an exactly-feasible solution to a general convex program, even if we are willing to accept an approximately-optimal solution?
  • Suppose we do need exactly-feasible solutions. For what classes of convex programs (except linear programming) this can be found in polynomial time?
$\endgroup$
2
  • $\begingroup$ I know very little about convex optimization, but I would guess that if the functions are regular enough, you can start with an approximate solution (in the sense of the linked document) and project the solution on the feasible set, without losing too much on the approximation. This of course assumes that if you're close to satisfying each constraint you're close to satisfying all of them simultaneously (and that you can find such a close feasible point). Maybe "proximal algorithms" is a relevant keyphrase here. $\endgroup$
    – Tassle
    Nov 22, 2023 at 19:07
  • $\begingroup$ There are several technical issues with convex functions related to how the functions are represented and whether the unique solution for the constraints has irrational coordinates even though the original representation has rational data. Grotschel-Lovasz-Schrijver book discusses some of these issues. link.springer.com/book/10.1007/978-3-642-78240-4 $\endgroup$ Nov 23, 2023 at 12:46

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.