Optimizing over a sphere

75 Views Asked by At

Let $f(x,y,z)=\frac12(x-x_0)^2+\frac12(y-y_0)^2+\frac12(z-z_0)^2$ for some $(x_0,y_0,z_0)\in\mathbb R^3$ and $X=\{(x,y,z)\in\mathbb R^3, (x-1)^2+(y-1)^2+z^2\le 9\}$. We wish to find the minimum of $f$ over $X$.

Firstly, it is easy to see by Heine's theorem that there is a unique solution to this problem since $X$ is compact and $f$ is continuous and strictly convex. Furthermore, if we let $h(x,y,z)=(x-1)^2+(y-1)^2+z^2-9$, we can rewrite the problem as : Minimize $f(x,y,z)$ for $h(x,y,z)\le0$. Since the problem is convex, we can apply the KKT conditions to the unique minimizer $(x',y',z')$ of $f$ over $X$ which gives : $$\nabla f(x',y',z')+\mu\nabla h(x',y',z')=0$$ with $\mu\ge0$ and $\mu h(x',y',z')=0$. From there, I feel like we should distinguish the cases $\mu=0$ and $\mu\ne0$, but I'm not sure how to make progress. I tried $\mu=0$ which gave $(x',y',z')=(x_0,y_0,z_0)$ and then $f(x',y',z')=0$ which would obviously qualify as a minimum since $f\ge0$. But then why should $(x_0,y_0,z_0)$ belong to $X$? I think I am a little confused, thank you very much for any help.

1

There are 1 best solutions below

0
On BEST ANSWER

The KKT conditions for this problem are, \begin{align} 0 &= \nabla f(x,y,z)+\mu\nabla h(x,y,z) \\ 0 &\geq h(x,y,z) \\ 0 &\leq \mu \\ 0 &= \mu h(x,y,z) \end{align} You correctly stated that if $\mu = 0$ then $0 = \nabla f(x,y,z) \implies (x',y',z') = (x_0,y_0,z_0)$. But notice that one of the KKT conditions is $0 \geq h(x,y,z)$. So if it is also the case that $0 \geq h(x_0,y_0,z_0)$ then $(x_0,y_0,z_0)$ is an optimal solution, i.e., if $(x_0,y_0,z_0)\in X$ then it is optimal. However, it doesn't have to be the case that $(x_0,y_0,z_0)\in X$, as you pointed out, and therefore the KKT condition $0 \geq h(x,y,z)$ will not be satisfied. This implies that our assumption that $\mu = 0$ was wrong and you have to check the case when $\mu > 0$ which implies that $0 = h(x,y,z)$.