What are the general steps to check if the given solution is optimal for given problem?

65 Views Asked by At

Could you describe step-by-step how to check if given vector is an optimal solution to the problem?

For example:

Check if the point [1, 1, 0] is an optimal solution for the problem

minimize $x^2+2y+(z-1)^2$

subject to:

$x^2+y^2\leq2$

$x\geq0$

$y\geq0$

$z\geq0$

(I just made the problem up, it probably doesn't make much sense. It's just to visualize what I'm talking about)

1

There are 1 best solutions below

1
On

The first thing to notice is that the problem decomposes into disjoint subproblems: one involving $x$ and $y$, and one involving $z$ only. For the $z$ subproblem, you want to minimize $(z-1)^2$ subject to $z \ge 0$, and $z=1$ is the unique optimal solution, so your $(1,1,0)$ with $z=0$ is not optimal.