3
$\begingroup$

Suppose we have a convex optimizatiom program: \begin{align} \min &\quad f_0(x)\\ s.t. &\quad h_i(x) = 0 && i=1,\ldots, p\\ &\quad g_i(x) \leq 0 && i=1,\ldots, m\\ &\quad x \in \mathbb{R}^n \end{align}

Where the objective function $f_0$ is convex, the functions $h_i$ are affine and the functions $g_i$ are convex.

To my understanding, in order to use the ellipsoid method to approximate such program we need (among other things) a starting ellipsoid $E_0$ that contains the entire feasible region and a constant $\upsilon >0$ that serves as a lower bound on the volume of the feasible region.

I read here (The Ellipsoid Method: A Survey by Bland, Goldfarb and Todd, page 10) that when the program is linear we can simply take $S(0,2^L)$ as the starting ellipsoid where $S$ is the ball centered at the origin with radius $2^L$ where $L$ represents the length of the input.

Do other cases exist for which it is known how to construct a starting ellipsoid and an appropriate constant $\upsilon$?

Specifically, what are the most general assumptions (rather than linearity) we need to make over the convex functions ($f_0$ and $g_i$) that will allow us to construct these requirements?

$\endgroup$
2
  • $\begingroup$ Is this a school assignment, or for curiosity.intellectual development, or do you actually just want to numerically solve nonlinear convex optimization problems? If the latter, I recommend you just use an off-the-shelf-solver. $\endgroup$ Sep 18, 2023 at 23:52
  • $\begingroup$ @MarkL.Stone I'm looking for theoretical guarantees. I reduced a problem I'm investigating into a (nonlinear) convex optimization problem where the functions $g_i$ are partially dependent on the problem input - we have only limited information about them (e.g., we assume we can calculate their gradient to construct a separation oracle). Since I haven't found yet a general way to construct a starting ellipsoid and a min vol, I'm not sure if it can be solved -theoretically- in polynomial time. If so, how and in what accuracy, and, if not, what assumptions can I add that will make it possible. $\endgroup$ Sep 19, 2023 at 6:27

1 Answer 1

2
$\begingroup$

Not all convex optimization problems can be solved in polynomial time unless P = NP.

Copositve Programs are convex optimization problems. Per this Copositive Programming chapter by Samuel Burer, many NP-Complete problems can be formulated as copositive programs. Therefore, unless P = NP, not all convex optimization problems can be solved in polynomial time.

Many conic optimization problems can be solved in polynomial time. But there are not known polynomial time algorithms to solve even all conic optimization problems, themselves being a subset of all convex optimization problems - see for instance this Mathematics Stack Exchange answer by Michal Adamaszek

$\endgroup$
1
  • $\begingroup$ That is very helpful, thank you! $\endgroup$ Sep 19, 2023 at 11:46

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.