# Finding a starting ellipsoid and a minimum volume to approximate a convex optimization problem

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?

• 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. Commented Sep 18, 2023 at 23:52
• @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. Commented Sep 19, 2023 at 6:27