A useful little fact for constrained optimization. Let be a convex set, and consider and its projection on

As quickly follows from the separation theorem with hyperplane containing for any the angle between and is obtuse. Consequently, the following “Pythagorean inequality” holds for any (note the inequality direction and also that the norm is squared):

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

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

Advertisements

Pingback: Subradient Projection method | Mimicking the Oracle

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

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