Computational Optimization
  • Computational Optimization
  • Basics
  • QR Factorization
  • Regularization
  • Gradients
  • Nonlinear Least-Squares
  • Gradient Descent
  • Descent Methods
  • Scaled Descent
  • Cholesky Factorization
  • Linear Constraints
  • Convex Set
  • Convex Functions
  • Global Optimal of Convex Optimization
  • Optimality for Convex Optimization
  • Projection Onto Convex Sets
  • Stochastic Gradient Descent (SGD)
Powered by GitBook
On this page

Projection Onto Convex Sets

PreviousOptimality for Convex OptimizationNextStochastic Gradient Descent (SGD)

Last updated 1 year ago

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

where AAA is m×nm\times nm×n.

  • Convex optimization problem

  • Objective is strictly convex ⇒ solution is unique

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)min21​∥Ax−b∥2⇔min21​∥z−b∥2 subject to z∈range(A)

Then (“orthogonal” or “Euclidean”) projection of a vector b∈Rnb\in \R^nb∈Rn onto C⊆RnC\subseteq \R^nC⊆Rn 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 CprojC​(b)=z∈Rnmin​21​∥z−b∥2 subject to z∈C

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

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

projC(b)proj_C(b)projC​(b) is unique

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

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

b−z∈NC(z)b-z \in N_C(z)b−z∈NC​(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⇔use definition of Normal Cone(b−z)T(y−z)≤0,∀y∈C

AxLSAx_{LS}AxLS​ projection of bbb onto range(A)range(A)range(A)