Blog/
Convex Optimization
Convex Optimization

Convex Optimization

Created
Jan 30, 2022
Description
Convex Optimization
Featured
Category
Mathematics
Tags
notion image
Useful tricks in Convex Optimization
https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook_extra_exercises.pdf
https://www.dropbox.com/s/9ck2p07mibvwrmg/main.pdf
 
Convex Optimization ProblemsLinear optimization programmingGradient Descent
 

Convex Optimization Problems

Optimization usually has the form of
minimizef0(x)        subject tofi(x)≤0,    i=1,…,mhi(x)=0,    i=1,…,p\begin{aligned}&\text{minimize} & f_0(x)~~~~~~~~ & \\ &\text{subject to} & f_i(x) \le 0, ~~~~& i=1,\ldots,m \\ &&h_i(x) = 0, ~~~~& i =1, \ldots, p\end{aligned}
to describe the optimization function with optimization variable x∈Rnx\in\mathbf{R}^n and the objective function f0:Rn→Rf_0:\mathbf{R}^n\rightarrow\mathbf{R}.
 

Linear optimization programming

minimizef0(x)subject toGx≼hAx=b\begin{aligned}&\text{minimize} & f_0(x) \\ &\text{subject to} & Gx \preccurlyeq h \\ & & Ax = b\end{aligned}
where G∈Rm×nG \in \mathbf{R}^{m\times n} and A∈Rp×nA \in \mathbf{R}^{p\times n}.
 
The following problems can be formulated as LPs.
Minimize ∥Ax−b∥∞\|Ax-b\|_\infty.
This is equivalent to the LP:
minimizetsubject toAx−b≼t1Ax−b≽−t1\begin{aligned} &\text{minimize} & t \\ &\text{subject to} & Ax-b \preccurlyeq t\mathbf{1} \\ & & Ax-b \succcurlyeq -t\mathbf{1} \end{aligned}
This follows from that ∣akTx−bk∣≤t.|a_k^Tx-b_k|\le t. That is, t≥max⁡k∣akTx−bk∣=∥Ax−b∥∞t \ge \max_{k} |a_k^Tx - b_k| = \|Ax-b\|_\infty.
Minimize ∥Ax−b∥1\|Ax-b\|_1.
This is equivalent to the LP:
minimize1Tssubject toAx−b≼sAx−b≽−s\begin{aligned} &\text{minimize} & \mathbf{1}^T s \\ &\text{subject to} & Ax-b \preccurlyeq s \\ & & Ax-b \succcurlyeq -s \end{aligned}
This follows from that ∣akTx−bk∣≤sk|a_k^Tx-b_k|\le s_k. The LP is optimal when sk=∣akTx−bk∣s_k =|a_k^Tx-b_k|. Then, it implies that 1Ts=∥Ax−b∥1\mathbf{1}^Ts = \|Ax-b\|_1 is optimal.
Minimize ∥Ax−b∥1\|Ax-b\|_1 subject to ∥x∥∞≤1\|x\|_\infty \le 1.
This is equivalent to the LP:
minimize1Tssubject to−s≼Ax−b≼s−1≼x≼1\begin{aligned} &\text{minimize} & \mathbf{1}^T s \\ &\text{subject to} & -s \preccurlyeq Ax-b \preccurlyeq s \\ & & -\mathbf{1} \preccurlyeq x \preccurlyeq \mathbf{1} \\ \end{aligned}
Minimize ∥x∥1\|x\|_1 subject to ∥Ax−b∥∞≤1\|Ax-b\|_\infty \le 1.
This is equivalent to the LP:
minimize1Tysubject to−1≼Ax−b≼1−y≼x≼y\begin{aligned} &\text{minimize} & \mathbf{1}^T y \\ &\text{subject to} & -\mathbf{1} \preccurlyeq Ax-b \preccurlyeq \mathbf{1} \\ & & -y \preccurlyeq x \preccurlyeq y \\ \end{aligned}
Minimize ∥Ax−b∥1+∥x∥∞\|Ax-b\|_1 +\|x\|_\infty.
This is equivalent to the LP:
minimize1Ty+tsubject to−y≼Ax−b≼y−t1≼x≼t1\begin{aligned} &\text{minimize} & \mathbf{1}^T y + t \\ &\text{subject to} & -y\preccurlyeq Ax-b \preccurlyeq y\\ & & -t\mathbf{1} \preccurlyeq x \preccurlyeq t\mathbf{1} \\ \end{aligned}
 
 
 

Gradient Descent

for k in range(0, N):
	Approximate f by f_k according to x(k)
	Do something using f_k (e.g., setting x(k+1) = argmmin f_k(x))
There are multiple forms of approximations
First-order approximation: f(y)≈f(x)+⟨∇f(x),y−x⟩f(y) \approx f(x) + \langle\nabla f(x), y-x\rangle
Usually, the algorithm here looks like
for k in range(0, N):
	if gradient(x(k)) <= eps:
		return x(k)
	x(k+1) = x(k) - step_size * gradient(x(k))
Theorem: Let f∈C2(Rn)f\in\mathcal{C}^2(\mathbb{R}^n). For any μ≥0\mu\ge0, the following are equivalent:
  1. ∥∇f(x)−∇f(y)∥2≤L∥x−y∥2\|\nabla f(x)-\nabla f(y)\|_2 \le L \|x-y\|_2 for all x,y∈Rnx,y\in\mathbb{R}^n
  1. −L≼∇2f(x)≼L-L\preccurlyeq\nabla^2f(x) \preccurlyeq L for all x∈Rnx \in \mathbb{R}^n
  1. f(y)=f(x)+∇f(x)⊤(y−x)±L2∥y−x∥22f(y) = f(x) + \nabla f(x)^\top (y-x) \pm \frac{L}{2}\|y-x\|_2^2 for all x,y∈Rnx,y\in\mathbb{R}^n
 
Theorem: Let ff be a function with LL-Lipschitz gradient and x∗x^* be any minimizer of ff. The gradient descent with step size h=1Lh=\frac{1}{L} outputs a point xx such that ∥∇f(x)∥2≤ϵ\|\nabla f(x)\|_2 \le \epsilon in 2Lϵ2(f(x(0))−f(x∗))\frac{2L}{\epsilon^2}\left(f(x^{(0)}) - f(x^*)\right) iterations.
 
Second-order approximation: f(y)≈f(x)+⟨∇f(x),y−x⟩+(y−x)⊤∇2f(x)(y−x)f(y)\approx f(x) + \langle\nabla f(x),y-x\rangle + (y-x)^\top \nabla^2f(x) (y-x)
Stochastic Approximation: ∑ifi(x)≈fj(x)\sum_if_i(x)\approx f_j(x) for a random jj
Matrix Approximation: Approximate AA by a simpler BB with 12A≼B≼2A\frac{1}{2}A \preccurlyeq B \preccurlyeq 2A
Set Approximation: Approximate a convex set by an ellipsoid or a polytope
Barrier Approximation: Approximate a convex set by a smooth function that blows up on the boundary
Polynomial Approximation: Approximate a function by a polynomial
Partial Approximation: Split the problem into two parts and approximate only one part
Taylor Approximation: f(y)≈∑k=0KDkf(x)[y−x]kf(y)\approx \sum_{k=0}^{K}D^kf(x)[y-x]^k
Mixed ℓ2\ell^2-ℓp\ell^p Approximation: f(y)≈f(x)+⟨∇f(x),y−x⟩+∑i=1nαi(yi−xi)2+βi(yi−xi)pf(y)\approx f(x) + \langle\nabla f(x), y-x\rangle + \sum_{i=1}^{n}\alpha_i(y_i-x_i)^2 + \beta_i(y_i-x_i)^p
Stochastic Matrix Approximation: Approximate AA by a simpler random BB with B≼2A B \preccurlyeq 2A and EB≽12A\mathbf{E} B\succcurlyeq \frac{1}{2}A
Homotopy Method: Approximate a function by a family of functions