Solutions

Here, we’ll review the solutions to the exercise problems of constrained optimization.

Exercise 1: A simple contained problem

The first problem was:

$$\min_{x, y} x^3 - y \\ s.t.: 3x - y = 1 \\ x^3 > -1$$

Here, we have two constraints. The first one is a good constraint. We can use it to reduce the number of variables. Let’s use it to get rid of the $x$ variable:

$$\min_x x^3 - 3x + 1 \\ s.t.: x^3 > -1$$

Now we have a univariate problem with a single constraint. This constraint is a bad constraint. But we know a method to solve this kind of problem. As $x^3 > -1$, then $x > -1$. If we look at the graph of the function, we see that it’s bitonic for those values of $x$ and that the minimum lies somewhere between $0$ and $2$. So we can solve the problem with a ternary search.