Assume the function $f(x,y) = 3x + 3y$ and the constraint set: $$ S =
\{ x \in \mathbb{R}^n : x^2 + \frac{y^2}{9} \leq 1 \} $$ Complete one
step of the Projected Gradient algorithm with $x_o =
\left(\frac12, \frac12 \right)^{T}$ as the initial point.
To begin with, the standard method would be to calculate
$$
z_o = x_o – \frac{1}{\gamma} \nabla f(x_o)
$$
and then solve the problem:
$$
\min_{y \in S} \lVert y – z_o \rVert^2
$$
using Kuhn-Tucker-Lagrange (quite challenging for this example, as it comes down to a fourth-degree equation and requires Newton-Raphson).
However, when some special geometry is involved, there are formulas from which $y_o = P_S (z_o)$ (the projection of $z_0$ on $S$) can be yielded directly. For example, when $S$ is a sphere,
$$
y_0 = -\frac{\nabla f(x_0)}{\lVert \nabla f(x_0) \rVert ^2}
$$
Is there a similar way to approach this example where $S$ is an elliptic surface?
Best Answer
Since $$\frac{\partial f(x,y)}{\partial x}=3\ne 0$$ the extremas must be situated on the curve $$x^2+\frac{y^2}{9}=1$$ The maximum is given by $$3\sqrt{10}$$ with the coordinate $$x=\frac{1}{\sqrt{10}},y=\frac{9}{\sqrt{10}}$$