Projection on a convex set is closer to any point of the set

A useful little fact for constrained optimization. Let  \mathcal{X}  be a convex set, and consider  x \in \mathcal{X},  y \notin \mathcal{X},  and its projection on  \mathcal{X}:

\displaystyle \Pi_{\mathcal{X}}(y) = \min_{x \in \mathcal{X}} \|x-y\|_2.

As quickly follows from the separation theorem with hyperplane containing \Pi_{\mathcal{X}}(y),  for any  x \in \mathcal{X}  the angle between  \displaystyle \Pi_{\mathcal{X}}(y)\, y  and  \displaystyle \Pi_{\mathcal{X}}(y)\, x  is obtuse.  Consequently, the following “Pythagorean inequality” holds for any  x \in \mathcal{X}  (note the inequality direction and also that the norm is squared):

\displaystyle \|y-\Pi_{\mathcal{X}}(y)\|_2^2 + \|\Pi_{\mathcal{X}}(y) - x\|_2^2 \le \|y-x\|_2^2.

In particular, the projection of any external point  y  is closer to each point of the set than the initial point:


\displaystyle \|\Pi_{\mathcal{X}}(y) - x\|_2^2 \le \|y-x\|_2^2.


This fact is used in the analysis of the  Subgradient Projection Method,  a basic method for nonsmooth constrained optimization.

About Dmitry Ostrovsky

PhD student with interests in statistics, optimization, and machine learning.
This entry was posted in Convex Optimization, Course on Convex Optimization, Memos and tagged . Bookmark the permalink.

3 Responses to Projection on a convex set is closer to any point of the set

  1. Pingback: Subradient Projection method | Mimicking the Oracle

  2. Артур says:

    Да тебя прям какая-то муза настигла.

  3. Pingback: Subgradient Projection method II — smooth objective | Look at the corners!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s