<p>In <a href="https://citeseerx.ist.psu.edu/document?repid=rep1&amp;type=pdf&amp;doi=8c3cb6395a35cb504019f87f447d65cb6cf1cdf0" rel="nofollow noreferrer">Nemirovxki's lecture notes on interior point methods</a>, I found the following.</p>
<p><a href="https://i.sstatic.net/nKdLC.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/nKdLC.png" alt="enter image description here" /></a></p>
<p>He defines an approximate solution as satisfying the following, for any given <span class="math-container">$\epsilon&gt;0$</span>:</p>
<p><a href="https://i.sstatic.net/7S2Pl.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/7S2Pl.png" alt="enter image description here" /></a></p>
<p>that is: the constraints represented by the functions <span class="math-container">$g_j$</span> are not satisfied exactly - they are satisfied only approximately (up to <span class="math-container">$\epsilon$</span>).</p>
<p>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 &quot;gives up&quot; on this possibility from the beginning. I am trying to understand why.</p>
<p>QUESTIONS:</p>
<ul>
<li>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?</li>
<li>Suppose we do need exactly-feasible solutions. For what classes of convex programs (except linear programming) this can be found in polynomial time?</li>
</ul>

CC BY-SA 4.0
2023-11-22T19:07:44.257Z
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.
Tassle
CC BY-SA 4.0
2023-11-23T12:46:47.837Z
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. https://link.springer.com/book/10.1007/978-3-642-78240-4
Chandra Chekuri
<convex-optimization>
Convex optimization: is it possible to find solutions that are exactly feasible and approximately optimal in polynomial time?
Erel Segal-Halevi
# Convex optimization: is it possible to find solutions that are exactly feasible and approximately optimal in polynomial time?

(Asked by: username_0 on 2023-11-22)

In [Nemirovxki's lecture notes on interior point methods](https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=8c3cb6395a35cb504019f87f447d65cb6cf1cdf0), I found the following.

[![enter image description here](https://i.sstatic.net/nKdLC.png)](https://i.sstatic.net/nKdLC.png)

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

[![enter image description here](https://i.sstatic.net/7S2Pl.png)](https://i.sstatic.net/7S2Pl.png)

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?

**Tags:** convex-optimization
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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. https://link.springer.com/book/10.1007/978-3-642-78240-4  

---

## 0 answers

