CVXOPT HW2
1) Consider the optimization problem
$$\min f_0(x_1, x_2)$$ Subject to $$2x_1 + x_2 \ge 1$$ $$x_1 + 3x_2 \ge 1$$ $$x_1 \ge 0, x_2 \ge 0$$
Make a sketch of the feasible set. For each of the following objective functions, give the optimal set and the optimal value
a) $f_0(x_1, x_2) = x_1 + x_2$
$f_0$ is an affine function. The constraints are all affine. Even without any formal properties, we can see that the solution is most likely to be in the “vertices”. Our vertices here are $(0, 1), (1, 0), (0.4, 0.2)$. Let us evaluate the function at each of these points
- $f(0, 1) = 1$
- $f(0.4, 0.2) = 0.6$
- $f(1, 0) = 1$
Out of the vertices, $(0.4, 0.2)$ is the minimum. We know that since $f_0$ is strictly increasing, it order to minimize we need to move in the negative direction along both axes. But we cannot possible move in that direction as $(0.4, 0.2)$ is our boundary. Hence we have to settle for a bit of positive direction in either one of the axes.
Just as a sanity check let us evaluate function on the neighbours.
Let us move along the negative direction along $x_1$. Setting $x_1 = 0.39$ we get $x_2 = 1-2x_1 = .22$ and our $f_0$ is $0.61$.
Similarly if we move along the negative direction along $x_2$. Setting $x_2 = 0.19$ we get $x_1 = 1-3x_2 = 0.43$ and $f_0 = 0.62$.
Hence the optimal set is $\boxed{(0.4, 0.2)}$ and the optimal value is $\boxed{0.6}$
b) $f_0(x_1, x_2)= -x_1-x_2$
Notice that we can write this as $-(x_1 + x_2)$. This is strictly decreasing and our constraints allow us to move towards $+\infty$. It is unbounded in that direction. We don’t have a solution here.
c) $f_0(x_1, x_2) = x_1$
This is just minimizing $x_1$.
The optimal set is $\boxed{(0, x_2), x_2\ge1}$ and the optimal value is $0$. This just gives the y-axis > 1.
d) $f_0(x_1, x_2) = \max{x_1, x_2}$
The function gives the larger coordinate out of the two. This corresponds to the $y=x$ line splitting $\mathbb{R}^2$ into two. In order to minimize this function, we need to find the smallest $x_1$ greater than the smallest $x_2$ or vice-versa.
We can write that as $\min_{x\in x_1} {x \ge \min x_2}$ or $\min_{x\in x_2} {x \ge \min x_1}$ Geometrically we’re trying to move down from $(0, 1)$ along $2x_1+x_2\ge 1$ and we’re trying to move up from $(1, 0)$ along $x_1+3x_2 \ge 1$ We see that the minimizer is ${\frac{1}{3}, \frac{1}{3}}$ Moving up or down give a value greater than $\frac{1}{3}$
$e) f(x_1, x_2) = x_1^2 + 9x_2^2$
We see that this is a paraboloid centered at $(0, 0)$. We are only concerned with the positive quadrant, hence we get a pie shape. Since this is convex, we know that the optimal points lie near the vertices. Since we have the equations of the lines, we can parameterize $x_2$ and convert this into a univariate problem. Then we just have to analyze the values of $f_0$ along this $\mathbb{R}^1$ strip. We split this into two regions - $[0, 0.4], [0.4, 1]$.
Let us first consider $[0, 0.4]$, in this region $x_2 = 1 - 2x_1$, then our objective function becomes $x_1^2 + 9(1 - 2x_1)^2 = 37x^2 - 36x + 9$
Differentiating, we get
$$f’(x) = 74x - 36$$
Setting to 0, we find the minima at
$$x = \frac{36}{74} = .48648648648648648648$$
Which is not in the domain.
We see that $f’(x) < 0, x\in[0, 0.4]$, hence the local minima is at $0.4$
The value at $f_0(0.4, 0.2) = 0.52$
In the other domain
Here $x_2 = \frac{1 - x_1}{3}$ $$f_0(x)= x^2 + 9\left(\frac{1 - x_1}{3}\right)^2$$ $$f_0(x)= x^2 + 9\left(\frac{1 + x^2 - 2x}{9}\right)$$ $$f_0(x)= x^2 + 1 + x^2 - 2x$$ $$f_0(x)= x^2 + 1 + x^2 - 2x$$ $$f_0(x)= 2x^2 -2x + 1$$ Differentiating $$f’(x) = 4x - 2$$ The minima is at $x = 0.5$ which is in the domain The value is then $f_0(1/2, 1/6) = 0.5$
Hence the optimal set is $\boxed{(1/2, 1/6)}$ and the optimal value is $\boxed{0.5}$