# Do we need constraint optimization for a convex function

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.

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$$.

• thanks for the clear explanation, @copper.hat Jun 20, 2019 at 19:00

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.