0
$\begingroup$

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}$ ?

$\endgroup$
  • $\begingroup$ No. Everyone should come up with a 1D counterexample of their own, to show that this is not the case. $\endgroup$ – dohmatob Jun 20 '16 at 19:40
0
$\begingroup$

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!]

$\endgroup$
  • $\begingroup$ Thanks @gerw got it. It was silly question. $\endgroup$ – aroyc Jun 22 '16 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.