Does projected gradint descent(pgd) results in the same minimizer as the one given by unconstrained gd and projected back on the constrained set?

108 Views Asked by At

For $f: \mathbb{R}^n \mapsto \mathbb{R}$ with $f(x) < \infty,\;\forall x \in \mathbb{R}^n$ and for convenience let's assume $f$ is continuously differentiable.

Suppose we are trying to solve the optimization problem: $ \min_{x \in C} f(x)$ s.t $C \subset \mathbb{R}$ and let $x^* = \arg\min_x f(x)$ but $x^* \in \mathbb{R}\setminus C$. Is the projection of $x^*$ on C $\left(i.e \Pi_C(x^*)\right)$ will be same as the solution given by projected gradient descent(given the same starting point and the same step size) ?

If they are not equal in general will it hold if $f$ is convex in $\mathbb{R}$ ?

1

There are 1 best solutions below

1
On BEST ANSWER

If I am not mistaken, the projected gradient descent should converge towards the minimizer of $f$ over $C$. In general, this minimizer is not the projection of the unconstrained minimizer onto the set $C$ if $n > 1$. It is easy to construct a counterexample and I advice you to do it yourself.

[Another reasoning to see that this cannot hold: The Euclidean scalar product does not posses any special properties on $\mathbb R^n$, which are linked to your question. Hence, if your claim would be true, it would be true for any scalar product. But if you project a point onto the set $C$ w.r.t. different scalar products, you get different projections. But not all of them could equal the minimizer!]