0
$\begingroup$

Suppose I have a convex cost function $f(x)$. I want to use a first-order optimization algorithm (eg bisection method) to minimize $f(x)$ with respect to $x$. But $x$ is constraint to be between $0$ and $1$: do I need to make it a constraint optimization problem or is it enough to minimize $f(x)$ with respect to $x$ and whenever x is outside of the interval of $0$ and $1$ to just make it $0$ or $1$? If I analyze it visually, it seems that it is okay to round it back to $0$ or $1$ if the optimal $x$ is outside the $0,1$ interval.

If this is okay: why? And if not: why? :)

Any help is appreciated.

$\endgroup$

2 Answers 2

2
$\begingroup$

Local minima of a convex function are global minima. Hence if $[0,1]$ does not contain a local minimum, it must be monotonic on the interval and so the constrained minimum will occur at $0$ or $1$.

$\endgroup$
1
  • $\begingroup$ thanks for the clear explanation, @copper.hat $\endgroup$ Jun 20, 2019 at 19:00
1
$\begingroup$

Ok, so if you were talking about anything other than a scalar optimization, I would question it, but in this case I think that works.

To formally prove it, your original problem is

$$\begin{array}{ll} \min_x &f(x)\\ \mathrm{s.t.} &0 \leq x \leq 1.\end{array} \qquad (1) $$

Define $g^* = \frac{\partial f}{\partial x} (x^*)$ where $x^*$ is the optimal solution to (1). If $0 < x^* < 1$, we already established everything is fine. If $x^* = 0$ or $x^* = 1$, then the optimality condition says that $-g^*$ points in the normal cone of the constraint; that is

$$ \left(x^* = 0 \text{ and } -g^* \leq 0\right) \text{ or } \left(x^* = 1 \text{ and } -g^* \geq 0\right)\qquad(2)$$.

If you give me an $x^*$ and (2) is satisfied, then that is the optimal solution to (1).

Now you are going to run gradient descent without the constraint, and get some solution $\hat x$. If $0 \leq \hat x \leq 1$, then $\hat x = x^*$ and no problems.

Now consider if $\hat x < 0$. Then by mean value theorem, $f'(0) > 0$, and thus $x^* = 0$ is optimal. And, if $\hat x > 1$, then by mean value theorem, $f'(1) < 0$, and thus $x^* = 1$ is optimal.

So your method always satisfies condition (2), and will get you to the global optimum.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .