0

So, we have the problem for $n=2$: minimize $c^Tx$ subject to $x\geq 0$ and $x_1+x_2=1$ and we are asked to visualize the solution (optimal x) for $c=\begin{bmatrix} 1 \\ 1\end{bmatrix}$.

I know that, generally, we have to plot some level sets of $c^Tx$ and find one that intersects the feasible set, and the intersection point will be the optimal one.

But in this case, the feasible set is "lying" on a level set of $c^Tx=x_1+x_2$, so what am i supposed to do?

I also used $cvx$ to solve the problem and got that the optimal point is $x_*=\begin{bmatrix} 0.5 \\ 0.5\end{bmatrix}$ but i do not understand why that happens geometrically.

Any help will be appreciated

TrapTengu
  • 1
  • The problem is convex, but not strictly convex. Any point of the segment $x_1 + x_2 = 1, x \ge 0$ is a solution of the problem. Depending on the method you use to solve the problem, you're going to end up in a corner point (if you use the simplex method) or some other point of the segment (if you use, say, an interior-point method). Your solution $x^* = (0.5, 0.5)$ (probably obtained with an interior-point method) is on the segment, therefore it is a solution of the problem (there is no feasible direction to move towards that strictly decreases the objective.) – Charlie Vanaret Jan 18 '22 at 16:53
  • @cvanaret Yes, I understand now that the point computed via $cvx$ is not unique. Thank you for the insight! – TrapTengu Jan 19 '22 at 13:19

1 Answers1

1

Optimal points usually fall at some point of symmetry of a system. For example, for constant area, what quadrilateral minimizes the perimeter? That's a square. Suppose the base of a right triangle is a diameter of a circle, What point on the circle gives you the third point of the triangle to maximize the area? That's where the perpendicular bisector of the hypotenuse intersects the circle. Not the solution usually cuts the figure into equal parts.

Given a constraint, like $f(x,y)=xy=A$, $A$ a constant, and an objective function $g(x,y)$ like $g(x,y)=2(x+y)$, the extreme of $g(x,y)$ tend to fall at places where the gradients of either function are parallel, another geometric property. This is the basis for extrema problems called Lagrange Multipliers.

TurlocTheRed
  • 5,683