2
$\begingroup$

Suppose we want to find a vector $x\in R^n$ that satisfies the constraints $g_i(x)\leq 0$, for $i\in 1,\ldots, m$, where all $g_i$ are convex functions. The functions can be given by an oracle access: there is an oracle that, given x, returns $g_i(x)$. If this helps, we can also have an oracle for their derivative $g_i′(x)$.

This is a special case of convex programming, and it is known that it can be solved (at least approximately) by the ellipsoid method.

But to use the ellipsoid method, we need an initial ellipsoid, that contains the feasible region. In all papers I read, this step is either skipped, or it is assumed that the initial ellipsoid is given. I did not find an explanation of how such an initial ellipsoid can be computed, given just the functions $g_i$.

QUESTIONS:

  • Is there a general procedure for finding an ellipsoid for a given convex program, that can be used to initialize the ellipsoid method?
  • If there is no general procedure, then what are some special cases in which such an ellipsoid can be computed efficiently? What conditions are needed so that the initial ellipsoid can be computed efficiently?
Improve this question
$\endgroup$
4
  • $\begingroup$ It probably depends on the functions $g$. How are the functions $g$ presented (represented) in the input? $\endgroup$ Commented Sep 19, 2023 at 15:42
  • $\begingroup$ Please edit the question to incorporate that information into the question -- don't just put it in the comments. Thank you! $\endgroup$ Commented Sep 20, 2023 at 16:11
  • $\begingroup$ @D.W. done........ $\endgroup$ Commented Sep 21, 2023 at 6:18
  • $\begingroup$ if you're not successful getting the answer here you may want to consider math.stackexchange.com $\endgroup$ Commented Sep 22, 2023 at 9:00

1 Answer 1

Reset to default
1
$\begingroup$

So considering this answer for unconstrained minimization:

For any $n$, let $f$ be a $\sigma$ strongly convex function, write $$\epsilon = \left\|\nabla f(0) \right\|_2$$ then the ball of radius $\epsilon / \sigma$ around 0 includes the minimum.

I suppose one could use the penalty method or barrier method in terms of converting the constrained optimization problem to an unconstrained one and finding an initial ellipsoid. It looks like you don't really have an optimization term here, so we could just have the value "0" for the constrained version. Since that answer specifies needing a $\sigma$ strongly convex function to be optimized you could most likely achieve this using the penalty method - the value of the penalty constants shouldn't matter I believe since these would then come out naturally into the calculation of $\sigma$ and $\epsilon$ and I believe would cancel out.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I did not understand that answer: why is it true? Speficically, why do you take the gradient of f at 0 and not any other point? $\endgroup$ Commented Sep 24, 2023 at 13:34
  • 1
    $\begingroup$ So see xingyuzhou.org/blog/notes/strong-convexity in particular proposition b and substitute in x=0 and y as the optimal solution (hence with 0 gradient). The result immediately follows since you get that $||y|| \leq \frac{\epsilon}{\sigma}$ $\endgroup$ Commented Sep 25, 2023 at 16:10
  • $\begingroup$ And you are correct in that you could use any x instead of 0 and that would be the center of the ellipsoid then. However there is no reason not to use 0. $\endgroup$ Commented Sep 26, 2023 at 7:21
  • $\begingroup$ Now I understand the other question. Thanks! But, I am not sure how the barrier method here. Suppose we use a logarithmic barrier. Let $f$ be the unconstrained objective function with the barrier. If $0$ is outside the original feasible region, then $f(0)$ is not defined (it may be "behind" one of the barriers, where the barrier function is a logarithm of a negative number). So to use this method, we must find some vector $x$ that is inside the original feasible region - which is exactly the problem we are trying to solve... $\endgroup$ Commented Sep 28, 2023 at 10:32
  • $\begingroup$ Note that the penalty method doesn't suffer from this issue $\endgroup$ Commented Oct 6, 2023 at 5:52

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.