Projection Onto Convex Sets

xLS=min⁡x∈Rn12∥Ax−b∥2x_{LS}=\underset{x\in\R^n}{\min}\frac{1}{2}\lVert Ax-b\rVert^2

where AA is m×nm\times n.

min⁡12∥Ax−b∥2⇔min⁡12∥z−b∥2 subject to z∈range(A)\min \frac{1}{2} \lVert Ax-b\rVert^2 \Leftrightarrow \min \frac{1}{2} \lVert z-b\rVert^2 \text{ subject to } z\in range(A)

Then (“orthogonal” or “Euclidean”) projection of a vector b∈Rnb\in \R^n onto C⊆RnC\subseteq \R^n convex is the solution of the convex optimization problem

projC(b)=min⁡z∈Rn12∥z−b∥2 subject to z∈Cproj_C(b)=\underset{z\in\R^n}{\min}\frac{1}{2}\lVert z-b\rVert^2 \text{ subject to } z\in C

  • Convex optimization problem

  • Objective is strictly convex ⇒ solution is unique

Properties of projC(b)\text{proj}_C(b)

  • if b∈Cb\in C ⇒ projC(b)=bproj_C(b)=b

  • projC(b)proj_C(b) is unique

  • z=projC(b)z=proj_C(b) ↔ (b−z)T(y−z)≤0,∀y∈C(b-z)^T(y-z)\le 0, \forall y\in C

−∇f(z)∈NC(z)-\nabla f(z)\in N_C(z)

b−z∈NC(z)b-z \in N_C(z) ⇔use definition of Normal Cone(b−z)T(y−z)≤0,∀y∈C\overset{\text{use definition of Normal Cone}}{\Leftrightarrow}(b-z)^T(y-z)\le 0, \forall y\in C

PreviousOptimality for Convex OptimizationNextStochastic Gradient Descent (SGD)

Last updated