ConvOpt

2_math

导数（Derivative）与梯度（Gradient）

$f(\bm x)$的导数$f'(\bm x)$是行向量，梯度$\nabla f$是列向量。

常见函数的导数：

• $f(\bm x)=\bm{a^Tx}$，则$f'(\bm x)=\bm{a^T}$，$\nabla f = \bm a$；
• $f(\bm x)=\bm{x^TAx}$，则$f'(\bm x)=\bm{x^T(A+A^T)}$，$\nabla f = (\bm A+\bm A^T)\bm x$；
• $\bm f(\bm x)=\bm A\bm x$，则$\bm f'(\bm x)=\bm A$，$\nabla \bm f = \bm A^T$；

总结

一般来讲求梯度用的比较多，因为梯度是$n\times m$的，而自变量是$n\times 1$的，所以两者会比较相像（特别是$m=1$时，而大多数凸优化问题就需要用到这个情况）。

对于求梯度的方法，我们应该从里往外（对比：求导数是从外往里）。比如$\nabla \bm f(\bm g(\bm x)) = \nabla \bm g(\bm x)\nabla \bm f(\bm g(\bm x))$

Range和Null

对于矩阵$\bm Q\in\mathbb R^{m\times n}$，定义：

$$\begin{aligned} \text{Range}(\bm Q) &= \{\bm Q\bm x : \bm x\in \mathbb R^n\} \\ \text{Null}(\bm Q) &= \{\bm x : \bm Q\bm x = \bm 0\} \end{aligned}$$

定义$\mathbb R^n$向量集合$A$，则定义$n$维向量$\bm b\perp A$为

$$\bm b^T \bm x = 0, \forall \bm x \in A$$

定义$A^{\perp} = \{\bm b: \bm b^T\bm x = 0, \bm x\in A\}$。

有$$\text{Range}(\bm Q^T){\perp} = \text{Null}(\bm Q)$$

证明

$$\forall \bm y \in \text{Range}(\bm Q^T), \exists \bm x \in \mathbb R^m, \bm Q^T\bm x = 0$$

对于Null: $$\forall \bm b\in \text{Null}(\bm Q), \bm Q\bm b = 0$$

有: $$\langle\bm y, \bm b\rangle = \bm y^T \bm b = \bm x^T \bm Q\bm b = \bm x^T \bm 0 = 0$$

Hessian

记为$\nabla^2 f(\bm x)$，是一个$n\times n$的矩阵，有对称性。

Chain Rule

设$g:\mathbb{R}^m\to \mathbb{R}^n$，$f:\mathbb{R}^n\to \mathbb{R}$，则复合函数$h(\bm{x})=f(g(\bm{x}))$的梯度为

$$\nabla h(\bm{x})=\nabla g(\bm{x})\nabla f(g(\bm{x}))$$

导数的形式为

$$h'(\bm{x})=f'(g(\bm{x}))g'(\bm{x})$$

这里定义梯度为导数（加科比）的转置。

Taylor Expansion

设$f:\mathbb{R}^n\to \mathbb{R}$在点$\bm{x}$处二阶可导，则对于任意的$\bm{d}\in \mathbb{R}^n$，都有

$$f(\bm{x}+\bm{d})=f(\bm{x})+\nabla f(\bm{x})^T\bm{d}+\frac{1}{2}\bm{d}^T\nabla^2 f(\bm{x})\bm{d} + o(\|\bm{d}\|^2)$$

正定

正定记为$\bm{Q}\succ \bm{O}$；半正定记为$\bm{Q}\succeq \bm{O}$；负定记为$\bm{Q}\prec \bm{O}$；半负定记为$\bm{Q}\preceq \bm{O}$。

• 如果Hessian正定（positive definite），则函数是严格凸（convex）的。

正定判别用顺序主子式。

• 如果Hessian半正定（positive semi-definite），则函数是凸的。

半正定判别用主子式。

• 如果Hessian负定（negative definite），则函数是严格凹（concave）的。
• 如果Hessian半负定（negative semi-definite），则函数是凹的。

如果不是正定或负定（indefinite），则函数既不是凸的也不是凹的。

特征向量与特征值（Eigenvalue and Eigenvector）

正定矩阵的所有特征值均为正；
半正定矩阵的所有特征值均为非负；
负定矩阵的所有特征值均为负；
半负定矩阵的所有特征值均为非正；
不定矩阵的特征值有正有负。

特征值分解（Eigendecomposition）。
二次型（Quadratic Form）。

二次型上下界

设$\bm{Q}\in \mathbb{R}^{n\times n}$是一个对称矩阵，且其特征值为$\lambda_1,\lambda_2,\cdots,\lambda_n$，则对于任意的$\bm{x}\in \mathbb{R}^n$，都有

$$\lambda_{\min}(\bm{Q})\bm{x^Tx}\leq \bm{x^TQx}\leq \lambda_{\max}(\bm{Q})\bm{x^Tx}$$

证明时利用对称矩阵可以被正交对角化。

First-order Necessary Condition for Convexity(一次必要条件)

设$\bm x^*$是函数$f:\mathbb{R}^n\to \mathbb{R}$的一个局部最小点，且函数在$\bm x^*$可导，则有

$$\nabla f(\bm x^*)=\bm 0$$

利用方向向量转化为单变量函数可证明。

如果$x^*$恰好在边界上（不在也成立），则对于任意的feasible direction $\bm d$，都有

$$\bm d^T\nabla f(\bm x^*) \geq 0$$

Bounds on Quadratic Forms

设$\bm{Q}\in \mathbb{R}^{n\times n}$是一个对称矩阵，且其特征值为$\lambda_1,\lambda_2,\cdots,\lambda_n$，则对于任意的$\bm{x}\in \mathbb{R}^n$，都有

$$\lambda_{\min}(\bm{Q})\bm{x^Tx}\leq \bm{x^TQx}\leq \lambda_{\max}(\bm{Q})\bm{x^Tx}$$

Second-order Necessary Condition for Convexity(二次必要条件)

设$\bm x^*$是函数$f:\mathbb{R}^n\to \mathbb{R}$的一个局部最小点，且函数在$\bm x^*$二阶可导，则有

$$\nabla^2 f(\bm x^*) \text{ is positive semi-definite}$$

也就是说，对于任意的$\bm d\in \mathbb{R}^n$，都有

$$\bm d^T\nabla^2 f(\bm x^*)\bm d \geq 0$$

Second-order Sufficient Condition for Convexity(二次充分条件)

如果某个点$\bm x^*$满足

1. $\nabla f(\bm x^*)=\bm 0$；
2. $\nabla^2 f(\bm x^*)$ is positive definite；

则$\bm x^*$是函数$f:\mathbb{R}^n\to \mathbb{R}$的一个严格局部最小点。

3_convset

Line, line segment, ray

设$\bm{x_1},\bm{x_2}\in \mathbb{R}^n$，则通过$\bm{x_1}$和$\bm{x_2}$的直线（line）定义为

$$\{\bm{x}=\theta \bm{x_1}+\bar \theta \bm{x_2}:\theta\in \mathbb{R}\}$$

当$\theta\in [0,1]$时，上述集合称为通过$\bm{x_1}$和$\bm{x_2}$的线段（line segment）；
当$\theta\geq 0$时，上述集合称为从$\bm{x_1}$出发经过$\bm{x_2}$的射线（ray）。

线段上的点称为convex combination。

Convex Set

设$C\subseteq \mathbb{R}^n$是一个集合，如果对于任意的$\bm{x_1},\bm{x_2}\in C$及任意的$\theta\in [0,1]$，都有

$$\theta \bm{x_1}+\bar \theta \bm{x_2}\in C$$

则称$C$为$\mathbb{R}^n$中的一个凸集（convex set）。

• intersection of convex sets is still convex set.

超平面

对于$\mathbb{R}^n$中的一个非零向量$\bm{w}$和一个实数$b$，定义集合

$$H=\{\bm{x}\in \mathbb{R}^n:\bm{w^T}\bm{x}=b\}$$

集合$H$称为$\mathbb{R}^n$中的一个超平面（hyperplane）。

所以超平面方程为：

$$\bm{w^T}\bm{x}=b$$

half-space：

$$\bm{w^T}\bm{x}<b$$

Affine Space

Affine Space$$S = {x\in \mathbb R^n:\bm A\bm x = \bm b}$$是convex set。

Polyhedra

A polyhedron $P = \{x\in\mathbb R^n: \bm A\bm x \leq \bm b\}$ is convex.

可以视作多个超平面的交集。

显然Polyhedra的交集也是Polyhedron。

Norm balls

A closed ball $\overline B(\bm x_0, r) = \{\bm x\in\mathbb R^n: \|\bm x - \bm x_0\|\leq r\}$ is convex.

Ellipsoids

An ellipsoid $\mathcal{E} = \{\bm x_0 + \bm A\bm u: \|\bm u\|_2\leq 1\}, \bm A\succ \bm O$ is convex.

利用特征值分解转化为一个norm ball的变体可以证明。

Affine transformation preserves convexity

$\mathbb C$ is convex, $\bm f(\bm x) = \bm A\bm x + \bm b, \bm x\in\mathbb C$，则$\bm f(\mathbb C) = \{\bm A\bm x + \bm b: \bm x\in\mathbb C\}$ is convex.

Positive semidefinite matrices

The set of all positive semidefinite matrices $\mathbb S^n_+ = \{\bm X\in\mathbb R^{n\times n}: \bm X = \bm X^T, \bm X\succeq \bm O\}$ is convex.

Convex Combination

凸集中多个点的凸组合仍在该凸集中（利用定义即可）。

Convex Hull

中文名为凸包。设$S\subseteq \mathbb{R}^n$是一个集合，则$S$的凸包（convex hull）定义为包含$S$的所有凸集的交集，记为$\text{conv}S$。

可以证明$\text{conv}S$等于$S$中有限个点的所有凸组合的集合，即

$$\text{conv}S=\left\{\sum_{i=1}^k \theta_i \bm{x_i}:\bm{x_i}\in S,\theta_i\geq 0,\sum_{i=1}^k \theta_i=1,k\in \mathbb{N}\right\}$$

Affinely Independent Points

设$\bm{x_1},\bm{x_2},\cdots,\bm{x_k}\in \mathbb{R}^n$是$k$个点，如果向量组

$$\{\bm{x_2}-\bm{x_1},\bm{x_3}-\bm{x_1},\cdots,\bm{x_k}-\bm{x_1}\}$$

线性无关，则称点$\bm{x_1},\bm{x_2},\cdots,\bm{x_k}$为$\mathbb{R}^n$中的仿射无关点（affinely independent points）。

Simplexes

设$\bm{x_1},\bm{x_2},\cdots,\bm{x_{k+1}}\in \mathbb{R}^n$是$k+1$个仿射无关点，则称集合

$$\text{conv}\{\bm{x_1},\bm{x_2},\cdots,\bm{x_{k+1}}\}$$

为$\mathbb{R}^n$中的一个**$k$-单纯形**（$k$-simplex）。

probability simplex:

$$\Delta_n = \{\bm{\theta}\in\mathbb R^n: \bm 1^T\bm \theta = 1, \bm \theta \geq \bm 0\}$$

is a simplex.

Convex Cone

设$C\subseteq \mathbb{R}^n$是一个集合，如果对于任意的$\bm{x}\in C$及任意的$\theta\geq 0$，都有$\theta \bm{x}\in C$，则称$C$为$\mathbb{R}^n$中的一个锥（cone）。

如果$C$同时是一个凸集，则称$C$为$\mathbb{R}^n$中的一个凸锥（convex cone）。

对于一个矩阵$\bm{A}\in \mathbb{R}^{m\times n}$，定义集合

$$C=\{\bm{Ax}:\bm{x}\geq \bm{0}\}$$

则$C$是$\mathbb{R}^m$中的一个凸锥，称为由$\bm{A}$生成的凸锥（convex cone）。

这里是怎么回事呢？将$\bm{A}$写作列向量的形式：

$$\bm{A}=[\bm{a_1},\bm{a_2},\cdots,\bm{a_n}]$$

则$\bm{Ax}$可以写作

$$\bm{Ax}=x_1\bm{a_1}+x_2\bm{a_2}+\cdots+x_n\bm{a_n}$$

所以$C$中的元素就是$\bm{A}$的列向量的非负线性组合。

证明$C$是一个凸锥：

1. 锥的性质：对于任意的$\bm{y}\in C$，存在$\bm{x}\geq \bm{0}$，使得$\bm{y}=\bm{Ax}$。对于任意的$\theta\geq 0$，有

   $$\theta \bm{y}=\theta \bm{Ax}=\bm{A}(\theta \bm{x})$$

   因为$\theta \bm{x}\geq \bm{0}$，所以$\theta \bm{y}\in C$。

2. 凸集的性质：对于任意的$\bm{y_1},\bm{y_2}\in C$，存在$\bm{x_1},\bm{x_2}\geq \bm{0}$，使得$\bm{y_1}=\bm{Ax_1}$且$\bm{y_2}=\bm{Ax_2}$。对于任意的$\theta\in [0,1]$，有

   $$\theta \bm{y_1}+\bar \theta \bm{y_2}=\theta \bm{Ax_1}+\bar \theta \bm{Ax_2=\bm{A}(\theta \bm{x_1}+\bar \theta \bm{x_2})}$$

   因为$\theta \bm{x_1}+\bar \theta \bm{x_2}\geq \bm{0}$，所以$\theta \bm{y_1}+\bar \theta \bm{y_2}\in C$。

实际上，形象理解的话，凹进去的向量不会产生作用，只有突出来的有用。

Projection onto Convex Sets

定义$\bm x$到$C$的distance为

$$\operatorname{dist}(\bm x,C) = \inf_{\bm z \in C} \|\bm x - \bm z\|_2$$

设$C\subseteq \mathbb{R}^n$是一个非空闭凸集，则对于任意的$\bm{x}\in \mathbb{R}^n$，存在唯一的$\bm{\hat x}\in C$，使得

$$\|\bm{x}-\bm{\hat x}\|_2=\operatorname{dist}(\bm x, C)$$

记为$$\bm{\hat x} = \mathcal P_C(\bm x)$$

证明：

存在性（existence）：随便找一个$\bm z_0\in C$，令$K = B(\bm x, \|\bm x - \bm z_0\|_2)\cap C$，则$K$是Compact Set，距离函数$$|\bm x - \bm z|_2$$对于$\bm z$在$K$上连续，所以存在最小值点。

唯一性（uniqueness）：反证法，假设存在两个，则找中点，更近。

设$C\subseteq \mathbb{R}^n$是一个非空闭凸集，$\bm x\in \mathbb{R}^n$，则$\bm{\hat x}=\mathcal P_C(\bm x)$的充分必要条件是对于任意的$\bm z\in C$，都有

$$(\bm x - \bm{\hat x})^T(\bm z - \bm{\hat x}) \leq 0$$

证明：

$$\begin{aligned} \bm{\hat x} = \mathcal P_C(\bm x) \iff& \|\bm z - \bm{\hat x} + \bm{\hat x} - \bm{x}\|_2\geq \|\bm{\hat x} - \bm x\|_2 & ,\forall\bm z\in C\\ \iff& -2(\bm x - \bm{\hat x})^T(\bm z - \bm{\hat x}) + \|\bm z - \bm{\hat x}\|_2^2\geq 0 & ,\forall\bm z\in C\\ \end{aligned}$$

当$\bm z = \bm{\hat x}$时，结论自然成立；

当$\bm z \neq \bm{\hat x}$时，可以看作一个关于$\|\bm z - \bm{\hat x}\|_2$的二次函数，所以对称轴（$\cos\theta$）非正时，结论成立。这对应了结论中的不等式。

反之，很容易得到充分性。

$$\|\bm x - \bm y\|_2\geq\|\mathcal P(\bm x) - \mathcal P(\bm y)\|_2$$

证明：

$$\begin{aligned} \|\bm{x} - \bm{y}\|_2^2 &= \|\bm{x} - \bm{\hat x} + \bm{\hat x} - \bm{\hat y} +\bm{\hat y} - \bm{y}\|_2^2 \\ &= \|\bm{\hat x} - \bm{\hat y}\|_2^2 + \|\bm{x} - \bm{\hat x} + \bm{\hat y} - \bm{y} \|_2^2 + 2\langle\bm{\hat x} - \bm{\hat y}, \bm{x} - \bm{\hat x} + \bm{\hat y} - \bm{y} \rangle\\ &\geq \|\bm{\hat x} - \bm{\hat y}\|_2^2 + 2\langle\bm{\hat x} - \bm{\hat y}, \bm{x} - \bm{\hat x} + \bm{\hat y} - \bm{y} \rangle\\ &= \|\bm{\hat x} - \bm{\hat y}\|_2^2 - 2\langle\bm{\hat y} - \bm{\hat x}, \bm{x} - \bm{\hat x}\rangle - 2\langle \bm{\hat x} - \bm{\hat y}, \bm{y} - \bm{\hat y}\rangle\\ &\geq \|\bm{\hat x} - \bm{\hat y}\|_2^2 \\ \end{aligned}$$

其中最后一步用了上一个结论。

考虑非空闭凸集$C$，对于$\bm x_0\notin C$，存在$\bm w\neq \bm 0$，满足$$\sup_{\bm x\in C}\langle\bm w, \bm x\rangle < \langle\bm w, \bm x_0\rangle$$

证明：令$\bm w = \bm x_0 - \mathcal P(\bm x_0)$即可。

Supporting Hyperplane

根据以上推导，可以很自然引出Supporting Hyperplane的定义：

设$C\subseteq \mathbb{R}^n$是一个非空凸集，$\bm x_0\in \partial C$，则存在$\bm w\neq \bm 0$，使得$$\langle\bm w, \bm x\rangle \leq \langle\bm w, \bm x_0\rangle = b, \forall \bm x\in C$$

构造一个数列$\{\bm x_k\}$，使得$\bm x_k\to \bm x_0$，且每一个元素都在$\overline C$外，利用之前结论即可证明。

这里需要用到一个Lemma:

If $C$ is convex, then $\operatorname{int} C = \operatorname{int} \overline C$且$\partial C = \partial \overline C$。

Separating Hyperplane

两个非空凸集没有交集，就可以用一个超平面把它们分开。即存在$\bm w\neq \bm 0$和$b$，使得$$\langle\bm w, \bm x\rangle \leq b, \forall \bm x\in C$$且$$\langle\bm w, \bm y\rangle \geq b, \forall \bm y\in D$$

做一个$E = \{ \bm x - \bm y: \bm x\in C, \bm y\in D\}$，则$E$也是凸集，且$\bm 0\notin E$。利用之前的结论即可证明。

Farka’s Lemma

设$\bm{A}$是一个$m\times n$矩阵，$\bm{b}\in \mathbb{R}^m$。则下列命题恰有一个成立：

1. 存在$\bm{x}\in \mathbb{R}^n$，使得$\bm{Ax}=\bm{b}$且$\bm{x}\geq \bm{0}$。
2. 存在$\bm{y}\in \mathbb{R}^m$，使得$\bm{A^Ty}\geq \bm{0}$且$\bm{b^Ty}<0$。

证明较为复杂。首先可以得到命题1成立可以推出命题2不成立，所以两者不可能同时成立（使用$\operatorname{cone} A$）。然后需要证明如果命题1不成立，则命题2成立（使用分离定理）。

4_convfunc

Convex Function

设$C\subseteq \mathbb{R}^n$是一个凸集，函数$f:C\to \mathbb{R}$称为凸函数，如果对于任意的$\bm{x_1},\bm{x_2}\in C$及任意的$\theta\in [0,1]$，都有

$$f(\theta \bm{x_1}+\bar \theta\bm{x_2})\leq \theta f(\bm{x_1})+\bar\theta f(\bm{x_2})$$

其中$\bar \theta=1-\theta$。如果不等式方向反过来，则称$f$为凹函数（concave function）。

Strict Convex Function：当$\bm{x_1}\neq \bm{x_2}$且$\theta\in (0,1)$时，上述不等式严格成立（不取等）。

一个凸函数的连续一段要不是严格凸的（相对端点），要不是线性的。

Restriction to lines

$f$ is convex iff for any $\bm{x}\in\text{dom}f$ and any direction $\bm{d}$, the function $g:\mathbb{R}\to \mathbb{R}$ defined by

$$g(t)=f(\bm{x}+t \bm{d})$$

is convex in its domain.

严格凸函数只要$\bm{d}\neq \bm{0}$且$\theta\in (0,1)$时，上述不等式严格成立。

注意了，这里的direction $\bm d$可以是任意向量，并不要求是单位向量。

证明比较简单，用对应关系就好。

Extended-value Extension

设$f:C\to \mathbb{R}$是定义在凸集$C\subseteq \mathbb{R}^n$上的函数，则其扩展值扩展（extended-value extension）定义为$\tilde f:\mathbb{R}^n\to \mathbb{R}\cup \{+\infty\}$，其中

$$\tilde f(\bm{x})=\begin{cases}f(\bm{x}),&\bm{x}\in C\\ +\infty,&\bm{x}\notin C\end{cases}$$

则$f$是凸函数的充分必要条件是$\tilde f$是凸函数。

注意，这里认为$+\infty\cdot 0 = 0$。

First-order Condition for Convexity(一次充分必要条件)

设$f:\mathbb{R}^n\to \mathbb{R}$是一个可微函数，则$f$是凸函数的充分必要条件是对于任意的$\bm{x_1},\bm{x_2}\in \text{dom}f$（open），都有

$$f(\bm{x_2})\geq f(\bm{x_1})+\nabla f(\bm{x_1})^T(\bm{x_2}-\bm{x_1})$$

证明一个方向用$\lim$，另一个方向中间取个点用凸性。

严格就让$\bm{x_1}\neq \bm{x_2}$，然后不取等。

First-order Condition for univariate function

设$f:\mathbb{R}\to \mathbb{R}$是一个在开区间上的可微函数，则$f$是凸函数的充分必要条件是$f'$单调递增。

Optimality for stationary point

设$f:\mathbb{R}^n\to \mathbb{R}$是一个可微凸函数，$\bm x^*\in \text{dom}f$且$\nabla f(\bm x^*)=\bm 0$，则$\bm x^*$是$f$的全局最小点。

Second-order Condition for Convexity(二次充分必要条件)

设$f:\mathbb{R}^n\to \mathbb{R}$是一个二阶可导函数，则$f$是凸函数的充分必要条件是对于任意的$\bm{x}\in \text{dom}f$，都有

$$\nabla^2 f(\bm x) \text{ is positive semi-definite}$$

这个有点意思，利用构造辅助函数$g(t) = f(\bm x + t \bm d)$，$g''(0)\geq 0$即可证明。

如果是strict convexity，则Hessian严格正定（只是充分条件）。

一定要记住Hessian半正定等价于$\bm d^T \nabla^2 f(\bm x) \bm d \geq 0, \forall \bm d$。

Global Minima of Convex Functions

local minimum = global minimum

这个很容易证明，假设+反证即可。

严格凸函数global minimum唯一。

证明：假设存在两个不同的global minimum，则取中点，利用strict convexity即可得到矛盾。

Sublevel sets

设$f:\mathbb{R}^n\to \mathbb{R}$是一个凸函数，则对于任意的$\alpha\in \mathbb{R}$，其$\alpha$下水平集（$\alpha$-sublevel set）

$$C_\alpha=\{\bm{x}\in \text{dom}f:f(\bm{x})\leq \alpha\}$$

是一个凸集。

对应的命题是superlevel set for concave function.

它的逆命题不为真（非凸函数的所有下水平集也可能都是凸的）。

Epigraph

设$f:\mathbb{R}^n\to \mathbb{R}$是一个函数，则其上图（epigraph）定义为集合

$$\text{epi}f=\{(\bm{x},y)\in \mathbb{R}^{n+1}: \bm{x}\in \text{dom}f, y\geq f(\bm{x})\}$$

$\tilde f$和$f$有相同的epigraph。

$f$是凸函数$\iff$其epigraph是凸集。

Holder’s Inequality

设$p,q\in [1,+\infty]$满足$\frac{1}{p}+\frac{1}{q}=1$（conjugate exponents共轭指数），则对于任意的$\bm{x},\bm{y}\in \mathbb{R}^n$，都有

$$\bm{|x^Ty|}\leq \|\bm x\|_p \|\bm y\|_q$$

利用$\log$的concave条件（Jensen’s Inequality）即可证明。

$\bm x$和$\bm y$中每一维都取绝对值依然成立。

Minkowski’s Inequality

设$p\in [1,+\infty]$，则对于任意的$\bm{x},\bm{y}\in \mathbb{R}^n$，都有

$$\|\bm x + \bm y\|_p \leq \|\bm x\|_p + \|\bm y\|_p$$

证明见讲义。

Nonnegative combinations

设$f_i:\mathbb{R}^n\to \mathbb{R}, i=1,2,\cdots,m$是$m$个凸函数，且$\alpha_i\geq 0, i=1,2,\cdots,m$，则函数

$$f(\bm x) = \sum_{i=1}^m \alpha_i f_i(\bm x)$$

是一个凸函数。

Affine composition

设$f:\mathbb{R}^m\to \mathbb{R}$是一个凸函数，$\bm{A}\in \mathbb{R}^{m\times n}$，$\bm{b}\in \mathbb{R}^m$，则函数

$$g(\bm x) = f(\bm{Ax}+\bm{b})$$

是一个凸函数。

Scalar composition

设$g:\mathbb{R}\to \mathbb{R}$是一个凸函数，且$f:\mathbb{R}^n\to \mathbb{R}$是一个凸函数，如果$g$是increasing的，则函数

$$h(\bm x) = g(f(\bm x))$$

是一个凸函数。

如果改成decreasing，则变为concave function。

对于多元函数，有以下结论：

设$g:\mathbb{R}^m\to \mathbb{R}$是一个凸函数，且$f_i:\mathbb{R}^n\to \mathbb{R}, i=1,2,\cdots,m$是$m$个凸/凹函数，如果在$g$的每个变量上都是：(1)$g\uparrow\wedge f\,\text{convex}$或者(2)$g\downarrow\wedge f\,\text{concave}$的，则函数

$$h(\bm x) = g(f_1(\bm x), f_2(\bm x), \cdots, f_m(\bm x))$$

是一个凸函数。

Pointwise maximum

设$f_i:\mathbb{R}^n\to \mathbb{R}, i=1,2,\cdots,m$是$m$个凸函数，则函数

$$f(\bm x) = \max_{1\leq i \leq m} f_i(\bm x)$$

是一个凸函数。

Pointwise supremum

设$\mathcal A$是一个非空集合，且对于每个$\alpha\in \mathcal A$，函数$f_\alpha:\mathbb{R}^n\to \mathbb{R}$是一个凸函数，则函数

$$f(\bm x) = \sup_{\alpha\in \mathcal A} f_\alpha(\bm x)$$

是一个凸函数。

利用intersection of epigraphs is still convex。

Partial minimization

设$C\subseteq \mathbb{R}^n\times \mathbb{R}^m$是一个凸集，且函数$f:C\to \mathbb{R}$是一个凸函数，则定义在集合

$$D=\{\bm x\in \mathbb{R}^n: \exists \bm y\in \mathbb{R}^m, (\bm x, \bm y)\in C\}$$

上的函数

$$g(\bm x) = \inf\{f(\bm x, \bm y): \bm y\in \mathbb{R}^m, (\bm x, \bm y)\in C\}$$

是一个凸函数。

证明：

首先有$$\forall \varepsilon > 0, \exists \bm y, f(\bm x, \bm y) < g(\bm x) + \varepsilon$$

对于$\bm x_1,\bm x_2\in D$：

$$\begin{aligned} g(\theta \bm x_1 + \overline\theta \bm x_2) &= \inf\{f(\theta\bm x_1 + \overline\theta\bm x_2, \bm y):(\bm x,\bm y)\in C\} \\ &\leq f(\theta\bm x_1 + \overline\theta\bm x_2, \bm \theta\bm y_1 + \overline\theta\bm y_2) \\ &\leq \theta f(\bm x_1, \bm y_1) + \overline\theta f(\bm x_2, \bm y_2) \\ &< \theta (g(\bm x_1) + \varepsilon) + \overline\theta (g(\bm x_2) + \varepsilon) \\ &= \theta g(\bm x_1) + \overline\theta g(\bm x_2) + 2\varepsilon \\ \end{aligned}$$

由于$\varepsilon$是任意的，所以

$$g(\theta \bm x_1 + \overline\theta \bm x_2) \leq \theta g(\bm x_1) + \overline\theta g(\bm x_2)$$

5_convopt

Optimization Problems in Standard Form

设$f:\mathbb{R}^n\to \mathbb{R}$是一个目标函数，$g_i:\mathbb{R}^n\to \mathbb{R}, i=1,2,\cdots,m$是$m$个不等式约束函数，$h_j:\mathbb{R}^n\to \mathbb{R}, j=1,2,\cdots,k$是$k$个等式约束函数，则优化问题的标准形式（standard form）定义为

$$\begin{aligned} & \min_{\bm x\in \mathbb{R}^n} & & f(\bm x) \\ & \text{s.t.} & & g_i(\bm x) \leq 0, i=1,2,\cdots,m \\ & & & h_j(\bm x) = 0, j=1,2,\cdots,k \\ \end{aligned}$$

其中

• $\bm x$被称为决策变量（optimization/decision variable），
• $f$被称为目标函数（objective function），
• 函数$g_i, i=1,2,\cdots,m$被称为不等式约束（inequality constraint functions），
• 函数$h_j, j=1,2,\cdots,k$被称为等式约束（equality constraint functions）。

Optimal Value and Optimal Point

$f^* = \inf_{\bm x\in\Omega} f(\bm x)$被称为最优值（optimal value），其中$\Omega = \{\bm x\in \mathbb{R}^n: g_i(\bm x)\leq 0, i=1,2,\cdots,m; h_j(\bm x)=0, j=1,2,\cdots,k\}$被称为可行域（feasible set）。如果$\Omega = \emptyset$，则称该优化问题为不可行的（infeasible），定义$f^* = \infty$；如果$\Omega$内$f$无下界，则定义$f^*=-\infty$。

如果存在$\bm x^*\in \Omega$，使得$f(\bm x^*)=f^*$，则称$\bm x^*$为最优点（optimal point）。如果$f(\bm x_0) < f^* + \epsilon$，则称$\bm x_0$为$\epsilon$-次最优点（$\epsilon$-suboptimal point）。如果$x^*$解决了局部的优化问题（$\|x-x^*\|_2 < \delta$），则称$\bm x^*$为局部最优点（local optimal point）。

Convex Optimization Problem

如果$f, g_i$都是凸函数，且$h_j$都是仿射函数，则称该优化问题为凸优化问题（convex optimization problem）。显然此时可行域为凸集。

凸优化问题的性质：

1. 如果该问题有一个局部最优点，则该点也是全局最优点。
2. 最优值点构成的集合是凸集。
3. 如果$f$是严格凸的，则最优点唯一（如果存在的话）。

First-order Optimality Condition

设$f:\mathbb{R}^n\to \mathbb{R}$是一个可微凸函数，$\bm x^*\in \text{dom}f$，则$\bm x^*$是$f$的最优点的充分必要条件是对于任意的$\bm x\in \text{dom}f$，都有

$$\nabla f(\bm x^*)^T(\bm x - \bm x^*) \geq 0$$

证明：

充分性利用一阶线性条件显然得出；必要性利用凸性取极限即可得出（化为一元函数求导）。

• 如果$\bm x^*$是内点，则必然有$\nabla f(\bm x^*) = \bm 0$。

Linear Program

线性规划问题（linear program, LP）定义为

$$\begin{aligned} & \min_{\bm x\in \mathbb{R}^n} & & \bm c^T\bm x \\ & \text{s.t.} & & \bm{Bx} \leq \bm d \\ & & & \bm{Ax} = \bm b \end{aligned}$$

LP in Standard Form

线性规划问题的标准形式（standard form）定义为

$$\begin{aligned} & \min_{\bm x\in \mathbb{R}^n} & & \bm c^T\bm x \\ & \text{s.t.} & & \bm x \geq \bm 0 \\ & & & \bm{Ax} = \bm b \end{aligned}$$

LP in Inequality Form

线性规划问题的不等式形式（inequality form）定义为

$$\begin{aligned} & \min_{\bm x\in \mathbb{R}^n} & & \bm c^T\bm x \\ & \text{s.t.} & & \bm{Bx} \leq \bm d \end{aligned}$$

Conversion

对于Standard Form，引入松弛变量$s$就可以消除不等式，然后再将所有$x$拆成正负两部分即可。

对于Inequality Form，先转化成Standard Form，然后把等式消掉（等式中某个变量用其他表示）。

LP问题如果有解一定有一个顶点解（Vertex Solution）。

Basic Solution

对于Standard Form的LP问题，设$\bm{A}\in \mathbb{R}^{m\times n}$且满秩（$m\leq n$），则称满足$\bm{Ax}=\bm b$且有$n-m$个分量为零的解$\bm x\in \mathbb{R}^n$为该问题的基本解（basic solution）。

degenerate basic solution：如果基本解中有超过$n-m$个分量为零，则称该基本解为退化基本解（degenerate basic solution）。否则叫non-degenerate basic solution。

如果basic solution满足所有不等式约束，则称该基本解为基本可行解（basic feasible solution，BFS）。

假设对应非零分量的列向量组成的矩阵为$\bm{B}$，则有$\bm x_B = \bm{B}^{-1}\bm b$。

Extreme Point

设$C\subseteq \mathbb{R}^n$是一个凸集，则称$C$中的点$\bm x$为$C$的极点（extreme point），如果不存在$\bm x_1,\bm x_2\in C, \bm x_1\neq \bm x_2$及$\theta\in (0,1)$，使得

$$\bm x = \theta \bm x_1 + \bar \theta \bm x_2$$

另$\Omega = \{\bm x\in \mathbb{R}^n: \bm{Ax}=\bm b, \bm x\geq \bm 0\}$为LP问题的可行域，则$\Omega$的极点与该LP问题的基本可行解一一对应。

证明：

1. 对于一个极点，假设它不是基本可行解，则有超过$n-m$个分量不为零，取对应的列向量组成的矩阵$\bm B$，则$\bm B$的列数超过行数，必然线性相关，存在$\bm d\neq \bm 0$使得$\bm{Bd}=\bm 0$。则对于充分小的$t>0$，都有$\bm x \pm t\bm d \in \Omega$，从而得到矛盾。
2. 对于一个基本可行解，假设它不是极点，则存在$\bm x_1,\bm x_2\in \Omega$，使得$\bm x = \theta \bm x_1 + \bar \theta \bm x_2$，其中$\theta\in (0,1)$。由于$\bm x_1, \bm x_2\geq \bm 0$，所以$\bm x$等于$0$的维度下$\bm x_1,\bm x_2$也是$0$，剩下的维度由于$\bm B$是可逆的，所以只有$\bm x$一个解，也就得到了$\bm x_1 = \bm x_2 = \bm x$，从而得到矛盾。

Fundamental Theorem of Linear Programming

如果LP问题$(L)$存在一个feasible solution，则它一定有一个BFS；
如果LP问题$(L)$存在一个optimal solution，则它一定有一个optimal BFS。

Simplex Method

我们有以下约束，并要使$f$最小：

$$\begin{aligned} f - \bm c^T\bm x &= 0\\ \bm A\bm x &= \bm b \\ \end{aligned}$$

可以写成矩阵形式：

$$\begin{pmatrix} 1 & -\bm c^T\\ 0 & \bm A\\ \end{pmatrix}\cdot \begin{pmatrix} f \\ \bm x \\ \end{pmatrix} = \begin{pmatrix} 0 \\ \bm b \\ \end{pmatrix}$$

然后咱们相当于就是可以对这个矩阵进行消消乐（增广了一行，左边增广的一列可以去掉，没用）。

每次选择一个basis，对于这个basis把对应的列都消成标准形式。

如果第一行的某一列是负的，就说明可以通过增加对应的变量来减小$f$，所以选这个变量进basis。

总流程如下：

Two Phase Simplex Method

设LP问题$(L)$的constraints为$\bm{Ax}=\bm b, \bm x\geq \bm 0$，则其Phase I问题$(F)$定义为

$$\begin{aligned} & \min_{\bm x\in \mathbb{R}^n, \bm y\in \mathbb{R}^m} & & \bm 1^T\bm y \\ & \text{s.t.} & & \bm{Ax} + \bm y = \bm b \\ & & & \bm x \geq \bm 0, \bm y \geq \bm 0 \\ \end{aligned}$$

Phase I的问题的BFS很简单，用$(0, \bm b)$作为初始解即可。

如果Phase I的最优解能够找到一个使得$\bm y = \bm 0$的解，则说明原问题是feasible的，然后利用这个解$(x_0, 0)$作为初始解去解决Phase II的问题，就可以了。

Quadratic Program (QP)

$$\begin{aligned} \min_{\bm x} & & \frac{1}{2}\bm x^T\bm Q\bm x + \bm c^T x\\ \text{s.t.} & & \bm B\bm x\leq \bm d\\ & & \bm A\bm x = \bm b \end{aligned}$$

如果$\bm Q\succeq \bm 0$，则QP是凸的；如果$\bm Q = \bm 0$，则QP规约到LP。

Quadratic Constrained Quadratic Program (QCQP)

$$\begin{aligned} \min_{\bm x} & & \frac{1}{2}\bm x^T\bm Q\bm x + \bm c^T x & &\\ \text{s.t.} & & \frac{1}{2}\bm x^T\bm Q_i\bm x + \bm c^T_i \bm x + d_i \leq 0 & & i = 1, 2, \cdots, m\\ & & \bm A\bm x = \bm b & & \end{aligned}$$

如果$\forall i, \bm Q_i\succeq 0 \wedge \bm Q\succeq 0$，则QCQP是凸的；如果$\forall i, \bm Q_i = \bm 0$，则QCQP规约到QP。

Solution to Unconstrained QP

令$$f(\bm x) = \frac{1}{2}\bm x^T \bm Q\bm x + \bm c^T \bm x$$

可以得到$$\nabla f(\bm x^) = \bm Q \bm x^ + \bm c = 0$$

1. 若$Q$可逆，直接解得$\bm x^* = -\bm Q^{-1} \bm c$;
2. 若$Q$不可逆，且$\bm c\in \text{Range}(\bm Q)$，则有无穷多解；
3. 若$Q$不可逆，且$\bm c\notin\text{Range}(\bm Q)$，则无解，且$f^*=-\infty$。

对于第三个情况，$\bm c\notin\text{Range}(\bm Q)\iff \bm c\not\perp\text{Null} (\bm Q^T) = \text{Null}(\bm Q)$，所以存在$\bm d\in \text{Null}(\bm Q)$满足$\bm d^T\bm c\neq 0$，那么$f(t\bm d) = \frac{1}{2}t\bm d^T\bm Q\bm d + t\bm c^T\bm d = t\bm c^T\bm d$，那么显然$f$的取值可以任意。

Geometry Program

monomial (单项式):

$$f(\bm x) = \gamma x_1^{a_1}x_2^{a_2}\cdots x_n^{a_n}\,\,\,\,, \bm x\in \mathbb R^n\wedge \bm x > \bm 0\wedge \gamma > 0$$

posynomial (正项式)：sum of monomials

$$f(\bm x) = \sum_{k = 1}^p \gamma_k x_1^{a_{k1}}x_2^{a_{k2}}\cdots x_n^{a_{kn}}$$

Geometry Program (几何规划):

$$f(\bm x), g_i(\bm x)\,\text{are posynomials},\,h_i(\bm x)\text{are monomials}$$

$$\begin{aligned} & & \min_{\bm x} f(\bm x) \\ \text{s.t.} & & g_i(\bm x)\leq 1 & & i = 1, 2, \cdots, m \\ & & h_i(\bm x) = 1 & & i = 1, 2, \cdots, r\\ \end{aligned}$$

取$\log$之后可以化为log-sum-exp函数，是凸的，这也是为什么一定要$\bm x > \bm 0$。

6_gd

Descend Method

每次选一个方向（descent direction）$\bm d_k$，然后选一个步长（step size）$t_k$，更新为

$$\bm x_{k+1} = \bm x_k + t_k \bm d_k$$

Gradient Descent Method

设$f:\mathbb{R}^n\to \mathbb{R}$是一个可微函数，$\bm x_k\in \text{dom}f$，则梯度下降法（gradient descent method）选择的下降方向为

$$\bm d_k = -\nabla f(\bm x_k)$$

Lipschitz Continuity

设$f:\mathbb{R}^n\to \mathbb{R}$是一个可微函数，若存在$L>0$，使得对于任意的$\bm x_1,\bm x_2\in \text{dom}f$，都有

$$\|\nabla f(\bm x_1) - \nabla f(\bm x_2)\| \leq L \|\bm x_1 - \bm x_2\|$$

则称$f$的梯度在$\text{dom}f$上是Lipschitz连续的，$L$被称为Lipschitz常数。

如果梯度$L$连续，则称$f$为$L-smooth$。

Affine Continuity

$f(\bm x) = \bm{Ax} + \bm b$是Lipschitz连续的，Lipschitz常数为$\|\bm A\|$ = $\lambda_{\max{}}^2(\bm A)$。

证明：

$$\begin{aligned} \|f(\bm x_2) - f(\bm x_1)\| &= \|\bm A(\bm x_2 - \bm x_1)\| \\ &= \sqrt{\bm d^T\bm A^2\bm d} & (\text{let } \bm d = \bm x_2 - \bm x_1)\\ &\leq \sqrt{\lambda_{\max{}}^2(\bm A) \bm d^T\bm d} \\ &= \|\bm A\| \|\bm x_2 - \bm x_1\| \\ \end{aligned}$$

Second-order Condition for L-smooth

二阶连续可导凸函数$f:\mathbb{R}^n\to \mathbb{R}$是$L-smooth$的充分必要条件是对于任意的$\bm x\in \text{dom}f$，都有

$$\nabla^2 f(\bm x) \preceq L \bm I$$

二阶连续可导函数$f:\mathbb{R}^n\to \mathbb{R}$是$L-smooth$的充分必要条件是对于任意的$\bm x\in \text{dom}f$，都有

$$-L\bm I \preceq \nabla^2 f(\bm x) \preceq L \bm I$$

证明：作辅助函数$g(\bm x) = \bm u^T\nabla f(\bm x)$。由$$-L\bm I \preceq \nabla^2 f(\bm x) \preceq L \bm I$$，$\nabla g(\bm x) = \nabla^2 f(\bm x)\bm u$的范数不超过$L\|\bm u\|$。则$\bm u^T[\nabla f(\bm x) - \nabla f(\bm y)] = g(\bm x) - g(\bm y) = \nabla g(\bm {\xi})(\bm x - \bm y)\leq L|\bm u||\bm x - \bm y| $。另$\bm u = \nabla f(\bm x) - \nabla f(\bm y)$即可。

另一方面，假设$\|\nabla f(\bm x) - \nabla f(\bm y)\|\leq L\|\bm x - \bm y\|$，则对于任意方向$\bm d$，都有

$$\|\nabla f(\bm x + t\bm d) - \nabla f(\bm x)\| \leq L\|\bm x + t\bm d - \bm x\| = L|t|\|\bm d\|$$

令$t\to 0$，则有

$$\|\nabla^2 f(\bm x)\bm d\| \leq L\|\bm d\|$$

即$-L\bm I\preceq \nabla^2 f(\bm x) \preceq L\bm I$。

或者

证明2

$$\begin{aligned}\|\nabla f(\bm x_1) - \nabla f(\bm x_2)\| &= \|\nabla^2 f(\xi) (\bm x_1 - \bm x_2) \|\\ &\leq L\|\bm x_1 - \bm x_2\| \end{aligned}$$

Quadratic Upper Bound

如果$f$是$L-smooth$的，则对于任意的$\bm x, \bm y\in \text{dom}f$，都有

$$f(\bm y) \leq f(\bm x) + \nabla f(\bm x)^T(\bm y - \bm x) + \frac{L}{2}\|\bm y - \bm x\|^2$$

先证明一维情形，再用$\bm d$拓展到多维情形（利用泰勒展开和$\bm d^T \bm Q\bm d\leq \left|\lambda\right|_{\max}\|\bm d\|^2$容易证明）。

根据这个定理，我们可以证明gradient descent的收敛性。

Convergence of Gradient Descent

首先，$\{\bm x_k\}$满足以下条件：

$$f(\bm x_{k + 1}) \leq f(\bm x_k) - t(1 - \frac{Lt}{2})\|\nabla f(\bm x_k)\|^2$$

证明：观察定义式

$$\bm x_{k + 1} = \bm x_k - t\nabla f(\bm x_k)$$

则$f(\bm x_{k + 1}) - f(\bm x_k)\leq -\nabla f(\bm x_k)^T t\nabla f(\bm x_k) + \frac{L}{2} \|t\nabla f(\bm x)\|^2 = -t(1-\frac{Lt}{2})\|\nabla f(\bm x)\|^2$。

如果$0 < t < \frac{2}{L}$，则上式右边大于$0$，所以$f(\bm x_k)$单调递减。

如果$f$是凸的且$L-smooth$，选择$t\in(0, \frac{1}{L}]$，则有$$f(\bm x_k) - f(\bm x^*) \leq \frac{|\bm x_0 - \bm x^*|2}{2tk}$$

对于连续情况可以证明如果约定

$$\frac{\mathrm d \bm x_k}{\mathrm d k} = -t\nabla f(\bm x_k)$$

那么不等式成立，证明主要步骤如下：

1. 计算$\frac{\mathrm d f(\bm x_k)}{\mathrm d k}$得出$f$关于$k$递减；
2. 计算$\frac{\mathrm d \|\bm x_k - \bm x^*\|^2}{\mathrm d k}$，其中一次项使用凸性放缩；
3. 从$0$到$k$积分得到$\|\bm x_k - \bm x^*\|^2$的上界，从而化为答案式子。

过程中没有用到$L$-smooth的条件，因为连续情况是无限细分的。

对于离散情况：

用类似方法证明，将求导改为差分，此时需要用$t$的范围以及$L$-smooth条件来约束$\|\bm x_k - \bm x_{k + 1}\|^2$的范围。

Strong Convexity

对于函数$f$，如果对于$m > 0$，函数$\tilde f(\bm x) = f(\bm x) - \frac{m}{2}\|\bm x\|^2$是凸的，则称$f$是$m$-强凸函数（$m$-strongly convex function）。

First-order Condition for Strong Convexity

函数$f$是$m$-强凸函数的充分必要条件是对于任意的$\bm x, \bm y\in \text{dom}f$，都有

$$f(\bm y) \geq f(\bm x) + \nabla f(\bm x)^T(\bm y - \bm x) + \frac{m}{2}\|\bm y - \bm x\|^2$$

注意，这里是充要条件，而$L$-smooth那里是必要条件。

这里是$\geq$，$L$-smooth那里是$\leq$。

证明：

对$\tilde f(\bm x) = f(\bm x) - \frac{m}{2}\|\bm x\|^2$使用一阶充分必要条件即可。

Second-order Condition for Strong Convexity

二阶连续可导函数$f:\mathbb{R}^n\to \mathbb{R}$是$m$-强凸函数的充分必要条件是对于任意的$\bm x\in \text{dom}f$，都有

$$\nabla^2 f(\bm x) \succeq m \bm I$$

证明：

对于$\tilde f(\bm x) = f(\bm x) - \frac{m}{2}\|\bm x\|^2$使用二阶充分必要条件即得。

Bound on Suboptimality Gap

如果$f$是$m$-strongly convex的，则有$$f(\bm x) - f(\bm x^*) \leq \frac{1}{2m}|\nabla f(\bm x)|^2$$

利用一次充分必要条件，左右同时对$\bm y$取$\min$即可。（注意是对$\bm y$取最小值，而不是取$\bm x^*$，此时右边实际上是二次函数取最小值）。

Convergence Analysis for Strongly Convex Functions

先分析连续情况，可以得到

$$\|\bm{\tilde x_T} - \bm x^* \|^2\leq e^{-mT} \|\bm x_0 - \bm x^*\|$$

这里证明步骤如下：

1. 求解$\frac{\mathrm d f(\bm x_k)}{\mathrm d k}$得到递减；
2. 计算$\frac{\mathrm d \|\bm x_k - \bm x^*\|}{\mathrm d k}$，利用strongly convex条件（强于一阶线性条件）放缩，利用之前的递减关系得到$\frac{\mathrm d \|\bm x_k - \bm x^*\|}{\mathrm d k}$和$\|\bm x_k - \bm x^*\|$的不等式关系，可以放缩到指数函数（构造一个递减的函数$e^mT\|\bm x_k - \bm x^*\|$）。

离散版：

如果$f$是$m$-strongly convex且$L$-smooth的，选择$t \in (0, \frac{1}{L}] $，则有$$\|\bm x_k - \bm x^*\|^2 \leq \left(1 - mt\right)^k \|\bm x_0 - \bm x^*\|^2$$

证明过程仿照连续情况，$t$的范围有助于得到递减。

数值版：

$$f(\bm x_{k + 1}) - f(\bm x^*) \leq (1 - mt)^k[f(\bm x_0) - f(\bm x^*)]$$

证明：

$$\begin{cases} f(\bm x_{k}) - f(\bm x_{k + 1})\geq t(1 - \frac{Lt}{2})\|\nabla f(\bm x_k)\|^2\geq \frac{t}{2}\|\nabla f(\bm x_k)\|^2\\ f(\bm x_k) - f(\bm x^*)\leq \frac{1}{2m}\|\nabla f(\bm x_k)\|^2 \end{cases}$$

把中间梯度的平方消掉就好了。

Condition Number

对于可逆矩阵$\bm Q$，Condition Number定义为

$$\kappa(\bm Q) = \frac{\sigma_{\max}(\bm Q)}{\sigma_{\min}(\bm Q)}$$

其中$\sigma$为奇异值，$\sigma(\bm A) = \sqrt{\lambda(\bm A^T\bm A)}$。

奇异值越小，$\frac{L}{m}$就越小，收敛就越快（对于二次型函数而言，如果是一般函数，可视为局部性质）。

对于二次型，如果$\kappa$比较小，则well-conditioned，否则ill-conditioned。

Exact Line Search

观察gd的每一步

$$\bm x_{k + 1} = \bm x_{k} - t_k\nabla f(\bm x_k)$$

注意到这里$t_k$的最优取值是$t_k = \arg\min_s\{f(\bm x_k - s\nabla f(\bm x_k))\}$，每次计算这个就是Exact Line Search。

但是这个显然不划算（对于不好计算的情况）。

可以证明如果$f$同时满足$m$-strongly convex和$L$-smooth，则有

$$f(\bm x_k) - f(\bm x^*)\leq (1 - \frac{m}{L})^k[f(\bm x_0) - f(\bm x^*)]$$

证明

$$f(\bm x_{k} - t\nabla f(\bm x_k)) \leq f(\bm x_k) - t(1 - \frac{Lt}{2})\|\nabla f(\bm x_k)\|^2$$

两边同时对$t$取最小值，可以得到

$$f(\bm x_{k + 1}) \leq f(\bm x_k) - \frac{1}{2L}\|\nabla f(\bm x_k)\|^2$$

同时还有

$$f(\bm x_k) - f(\bm x^*)\leq\frac{1}{2m} \|\nabla f(\bm x_k)\|^2$$

联立消掉就好了。

Backtracking Line Search

Armijo’s Rule:

$$f(\bm x) - f(\bm x - t\nabla f(\bm x))\geq \alpha \|\nabla f(\bm x)\|^2$$

每次先取$t$为$t_0$，然后每次$t\leftarrow \beta t_0$，减小$t$直到满足条件。

由于$t\nabla f(\bm x)$是$\bm x$的增量，那么在局部应该有近似的$\Delta y \approx - t\nabla f(\bm x)^T \nabla f(\bm x)$，所以说$\alpha, \beta\in(0, 1)$的时候应该会收敛。

收敛分析有空补上，也是指数级收敛（不管是外层迭代还是内部迭代）。

Nesterov’s Accelerated Gradient Descent (AGD)

这里可以把$\bm x_{k + 1} - \bm x_k$当作速度来理解，这样就是保留上一次速度的$\beta$倍。

可以证明当$m=0$时，普通GD的精度是$O(\frac{1}{k})$，而AGD的精度是$O(\frac{1}{k^2})$；

当$m > 0$时，令$q = \frac{m}{L}$，则普通GD的精度是$O((1 - q)^k)$，AGD的精度是$O((1 - \sqrt q)^k)$。

Summary

梯度下降复杂度分析最核心的工具就是$L$-smooth和$m$-strongly convex。

$L$-smooth的作用是限制了梯度变化的速率，让梯度在局部的变化不会太大，进而有步长为$-t\nabla f(\bm x_k)$时的上界（和步长乘以斜率成正比，也就是$\|f(\bm x_k)\|^2$）；

$m$-strongly convex是convex条件的升级版，让最值点到当前点的函数值差距缩小到了步长乘以当前点斜率，也就是$\|f(\bm x_k)\|^2$的某个倍数，同时指数级收敛创造了条件（因为strong convexity会保证这个函数比较弯）。

所以没有strong convexity，只能保证反比级收敛，而有了strong convexity就可以保证指数级收敛。

7_newton

Newton’s Method

对于中学学的牛顿迭代法（不断做切线，取和$x$轴交点的横坐标，可以找到零点），做一点改动就可以成为Newton’s Method：

原始状态：

$$x_{k + 1} = x_k - \frac{f(x_k)}{f'(x_k)}$$

现在我们把它拓展到多维。由于我们要解决凸优化问题，等价于解决$\nabla f(\bm x) = 0$这个问题，可以对$\nabla f(\bm x)$使用牛顿迭代法：

$$\bm x_{k + 1} = \bm x_k - \nabla^2 f(\bm x_k)^{-1}\nabla f(\bm x_k)$$

实质上是把函数局部二次泰勒展开，并到达泰勒展开式的最低点。

Affine Invariance

Newton’s Method具有仿射不变性：

设$\bm A$是可逆矩阵，$g(\bm x) = f(\bm A\bm x)$。

可以求出

$$\begin{cases} \nabla g(\bm x) = \bm A^T \nabla f(\bm A\bm x) \\ \nabla^2 g(\bm x) = \bm A^T\nabla^2 f(\bm A\bm x) \bm A \\ \end{cases}$$

则对于$g$的newton：

$$\begin{aligned} \bm x_{k + 1} - \bm x_k &= - \nabla^2 g(\bm A\bm x)^{-1}\nabla g(\bm A\bm x) \\ &= [\bm A\nabla^2 f(\bm A\bm x)\bm A]^{-1}\bm A^T\nabla f(\bm A\bm x) \\ &= \bm A^{-1}\nabla^2 f(\bm A\bm x)^{-1}(\bm A^T)^{-1}\bm A^T\nabla f(\bm A\bm x)\\ &= \bm A^{-1} \nabla^2 f(\bm A\bm x)^{-1}\nabla f(\bm A\bm x) \end{aligned}$$

所以对于$f$的$\bm A\bm x$的newton和这个的步骤完全相同，具有仿射不变性。而梯度下降就没有这个性质（会多一个$\bm A\bm A^T$）。

Analysis

有空补，结论是在某一个区域以平方级收敛（$O(e_0^{2^k})$）。

Damped Newton’s Method

牛顿的收敛域仅限optimal point周围，还是用Armijo法则进行约束：

$$f(\bm x_{k}) - f(\bm x_{k + 1}) \geq \alpha t \nabla f(\bm x_{k})^T \bm d$$

其中$d = \nabla^2 f(\bm x_k)^{-1} \nabla f(\bm x_k)$。

$t\bm d$是理论方向，再乘一个$\nabla f(\bm x_k)$就是理论的下降收益，$\alpha$就是降低期望，只要达到理论的$\alpha$倍就认为可以通过。

可以证明Damp只会发生在前几步，到Newton的可行域之后，就不会再使用Damp。

8_prox_gd

Proximal Gradient Descent

有些时候为了增强答案的稀疏性，我们引入一个保证凸性但不保证smooth的函数$h(\bm x)$，让新的优化函数变为$f(\bm x) = g(\bm x) + h(\bm x)$，对$f$进行优化。这个时候我们不能直接用梯度下降（可能没有梯度），可以使用Peoximal Gradient Descent。

梯度下降的形式为

$$\bm x_{k + 1} = \bm x_k - t\nabla f(\bm x_k)$$

这个可以等价地写为（二次函数最小值）：

$$\bm x_{k + 1} = \arg\min_{\bm x} \{\bm f(\bm x_k) + \nabla f(\bm x_k)^T (\bm x - \bm x_k) + \frac{1}{2t_k}\|\bm x - \bm x_k\|^2\}$$

也就是：

$$\bm x_{k + 1} = \arg\min_{\bm x} \frac{1}{2t_k}\|\bm x - (\bm x_k - t_k\nabla f(\bm x_k) )\|^2$$

对于加了$h(\bm x)$的情况，可以写成

$$\bm x_{k + 1} = \arg\min_{\bm x} \{\frac{1}{2t_k}\|\bm x - (\bm x_k - t_k\nabla f(\bm x_k) )\|^2 + h(\bm x)\}$$

也就是

$$\bm x_{k + 1} = \arg\min_{\bm x} \{\frac{1}{2}\|\bm x - (\bm x_k - t_k\nabla f(\bm x_k) )\|^2 + t_kh(\bm x)\}$$

令$\bm y = \bm x_k - t\nabla f(\bm x_k)$

则

$$\bm x_{k + 1} = \operatorname{prox_{t_kh}}(\bm y) = \arg\min_{\bm x}\{\frac{1}{2}\|\bm x - \bm y\|^2 + t_k h(\bm x)\}$$

这又是一个凸优化问题，$\bm y$已知而$t_k h$和二次函数都是凸函数。

Proximal Operator就是

$$\operatorname{prox_{h}}(\bm y) = \arg\min_{\bm x}\{\frac{1}{2}\|\bm x - \bm y\|^2 + h(\bm x)\}$$

$\mathcal{l}_1$ regularization

对于每个维度分象限处理得到：

$$[\operatorname{prox_{\lambda\|\cdot\|_1}}(\bm y)]_i = S_\lambda(y_i) = \begin{cases} y_i - \lambda, & \text{if} y_i > \lambda\\ 0, & \text{if} \left|y_i\right|\leq \lambda\\ y_i + \lambda, & \text{if} y_i < -\lambda \end{cases}$$

Lasso and ISTA

Lasso (Least Absolute Shrinkage and Selection Operator)的问题定义就是

$$\min_{\bm w} F(\bm w) = \frac{1}{2}\|\bm X\bm w - \bm y\|_2^2 + \lambda\|\bm w\|_1$$

$$\nabla f(\bm w) = \bm X^T(\bm X\bm w - \bm y)$$

根据计算，每次梯度下降都是

$$\bm w_{k + 1} = \bm S_{\lambda t}(\bm w_k - t\bm X^T(\bm X\bm w - \bm y))$$

这里的$\bm S_{\lambda t}$表示对每一行都进行$S_{\lambda t}$的运算（注意这里必须有$t$，根据前文推导）。

Convergence Analysis

先滚

9_lagrange

Problems with Affine Equality Constraints

AEC (Affine Equality Constraints)定义如下

$$\begin{aligned} & & \min_{\bm x} f(\bm x)\\ \text{s.t.} & & \bm A\bm x = \bm b \end{aligned}$$

其中$\bm x\in\mathbb R^n$，$\bm b\in\mathbb R^k$。

首先可以看出来$\text{Null}(\bm A)$是所有feasible direction的集合（因为任意解=$\bm A\bm x = \bm 0$的解加上一个特解）。

AEC的解满足什么性质？

对于任意feasible direction $\bm v$，

$$\nabla f(\bm x^*)^T\bm v \geq 0$$

这个性质很好理解，否则就往$\bm v$方向走，更优。

很明显$-\bm v\in\text{Null}(\bm A)$，所以得到

$$\nabla f(\bm x^*)^T\bm v \leq 0$$

综合得到

$$\nabla f(\bm x^*)^T\bm v = 0$$

Lagrange Condition

如果$\bm x^*$是一个local minimum，那么存在$\bm \lambda^*$满足

$$\nabla f(\bm x) + \bm A^T\bm \lambda^* = \bm 0$$

其中$\bm A\in\mathbb R^{k\times n}$，所以$\bm \lambda^*\in \mathbb R^{k}$。

证明

由于费马小定理（之前推出来的那个玩意），

$$\nabla f(\bm x^*)\perp \text{Null}(\bm A)$$

所以说可以得到

$$\nabla f(\bm x^*)\in \text{Range}(\bm A^T)$$

所以说肯定存在$\bm \lambda^*$。

定义Lagrangian (Lagrange Function)

$$\mathcal L(\bm x, \bm \lambda) = f(\bm x) + \bm \lambda^T(\bm A\bm x - \bm b)$$

得到这个函数的KKT equations

$$\begin{aligned}\nabla_{\bm x} \mathcal L(\bm x^*, \bm \lambda^*) &= \nabla f(\bm x^*) + \bm A^T\bm \lambda^*\\ \nabla_{\bm \lambda}\mathcal L(\bm x^*, \bm \lambda^*) &= \bm A\bm x^* - \bm b\\ \end{aligned}$$

注意到满足这两个条件刚好就满足了之前的说法。

这个函数刚好又没了constraints。

Problems with General Equality Constraints

对于问题

$$\begin{aligned} & &\min_{\bm x} f(\bm x) \\ \text{s.t.}& & h_i(\bm x) = 0 && i = 1, 2, \cdots, k \\ \end{aligned}$$

并且保证$f$和$h$都是differentiable。

有类似的结论，所以我们作

$$\mathcal L(\bm x, \bm \lambda) = f(\bm x) + \bm \lambda^T \bm h(\bm x)$$

其中$\bm h(\bm x)$就是把前面的$h_i$打包。

10_kkt

对于问题

$$\begin{aligned} & &\min_{\bm x} f(\bm x) \\ \text{s.t.}& & h_i(\bm x) = 0 && i = 1, 2, \cdots, k \\ &&g_i(\bm x) \leq 0 && i = 1, 2, \cdots, m\\ \end{aligned}$$

可以构造Lagrangian

$$\mathcal L(\bm x, \bm \lambda, \bm \mu) = f(\bm x) + \bm \lambda^T \bm h(\bm x) + \bm \mu^T\bm g(\bm x)$$

其中保证$\bm \mu\geq \bm 0$，这保证了$\bm g(\bm x)\leq \bm 0$。

regular定义；

所有有用的条件的导数independent.

KKT条件在$\bm h$是affine的，$\bm g$是凸的情况下是充分的，但不是必要的（可能会有退化的点）。

11_proj_gd

对于凸集上的凸优化问题，每次gradient descent之后，再使用投影法把它投影到这个凸集上（这也是一个优化问题）。

内层问题可以规约到proximal gradient descent（加上一个$I_{\Omega}(\bm x) = \begin{cases}0 & \text{if}\, \bm x\in\Omega\\ \infty & \text{if}\,\bm x\notin\Omega\end{cases}$），这样就是无限制的。

12_newton_eq

对于有affine等式约束的QP问题，可以写成

$$\begin{aligned} \min_{\bm x} && \frac{1}{2}\bm x^T\bm Q\bm x + \bm g^T\bm x + c \\ \text{s.t.} && \bm A\bm x = \bm b \\ \end{aligned}$$

可以写出KKT condition：

$$\begin{cases} \bm Q\bm x + \bm g + \bm A^T\bm \lambda = \bm 0 \\ \bm A\bm x - \bm b = \bm 0 \\ \end{cases}$$

回顾newton法，每次找到函数的二次泰勒展开的最小值，对于以下优化问题：

$$\begin{aligned} \min_{\bm x} && f(\bm x) \\ \text{s.t.} && \bm A\bm x = \bm b \\ \end{aligned}$$

这个问题的KKT conditions：

$$\begin{cases} \nabla f(\bm x_k) + \bm A^T\bm \lambda = \bm 0 \\ \bm A\bm v = \bm 0 \\ \end{cases}$$

那么每次newton想要找到一个$\bm v$是以下优化问题的解：

$$\begin{aligned} \min_{\bm x} &&\hat f(\bm x_k + \bm v) = f(\bm x_k) + \nabla f(\bm x_k)^T \bm v + \frac{1}{2}\bm v^T\nabla^2 f(\bm x_k)\bm v\\ \text{s.t.} && \bm A\bm v = \bm 0 \end{aligned}$$

写出KKT就是

$$\begin{cases} \nabla^2 f(\bm x_k)\bm v + \nabla f(\bm x_k) + \bm A^T\bm \lambda = \bm 0 \\ \bm A\bm v = \bm 0 \\ \end{cases}$$

也可以写成

$$\begin{pmatrix}\nabla^2 f(\bm x_k) & \bm A^T\\ \bm A & 0\end{pmatrix} \begin{pmatrix} \bm v\\ \bm \lambda \end{pmatrix} = \begin{pmatrix} -\nabla f(\bm x_k)\\ 0 \end{pmatrix}$$

假设左边这个KKT矩阵可逆，那么有唯一解。

首先可以证明$\bm v = \bm 0\iff \bm x = \bm x^*$，联立两个KKT就可以证明$\nabla^2 f(\bm x_k)\bm v=\bm 0$，说明$\bm v$同时是$\nabla^2 f$和$\bm A$的$\text{Null}$里面的，根据满秩，$\bm v = \bm 0$。

在KKT矩阵可逆的情况下，每次解出$\bm v$，并向$\bm v$方向下降就好了。

也可以结合阻尼newton方法来保证收敛。

$\bm v$的方向一定是下降的，因为：

$$\begin{aligned}&\frac{\mathrm d }{\mathrm d t} f(\bm x_k + t\bm v)\mid_{t = 0}\\ =&\nabla f(\bm x_k)^T\bm v\\ =&(-\nabla^2 f(\bm x_k)\bm v - \bm A^T\bm \lambda)^T\bm v\\ =&-\bm v^T\nabla^2 f(\bm x_k)\bm v - \bm \lambda^T\bm A\bm v\\ =& -\bm v^T\nabla^2 f(\bm x_k)\bm v < 0 \end{aligned}$$

因为$\nabla^2 f(\bm x_k)$在等式约束下是正定的（唯一最优解）。

有些时候一开始就不是feasible的，这个时候可以对整个Lagrange函数的梯度进行newton迭代。

13_barrier

对于一般凸优化问题

$$\begin{aligned}\min_{\bm x} && f(\bm x)\\ \text{s.t.} && \bm A\bm x = \bm b\\ && \bm g(\bm x)\leq 0 \end{aligned}$$

我们可以构造一个barrier函数

$$B(\bm x) = \sum_{i =1}^m -\log\left(-g_i(\bm x)\right)$$

这玩意是个凸函数，我们现在求解这个问题

$$\begin{aligned} \min_{\bm x} && f(\bm x) + \frac{1}{\tau}B(\bm x)\\ \text{s.t.}&& \bm A\bm x =\bm b \end{aligned}$$

14_dual_LP

对于一个线性规划问题

$$\begin{aligned} \min_{\bm x} && \bm c^T\bm x\\ \text{s.t.} && \bm A\bm x = \bm b\\ &&\bm G\bm x\geq \bm h \end{aligned}$$

我们引入Lagrange Multipliers $\bm \mu$和$\bm \lambda$，可以得到

$$\begin{aligned} &\bm\lambda^T (\bm A\bm x) + \bm\mu^T(\bm G\bm x)\\ \geq& \bm \lambda^T\bm b + \bm\mu^T\bm h \end{aligned}$$

如果能找到$\bm \lambda, \bm \mu$满足$\bm A^T\bm \lambda + \bm G^T\bm \mu = \bm c$，则可以写出如下LP问题

$$\begin{aligned} \max_{\bm \lambda, \bm\mu} && \bm b^T\bm\lambda + \bm h^T\bm \mu\\ \text{s.t.} && \bm A^T\bm\lambda + \bm G^T\bm \mu = \bm c\\ && \bm \mu\geq \bm 0\\ \end{aligned}$$

Weak Duality

primal problem的最优解$\geq$ dual problem的最优解。

根据定义就可以看出来是成立的。

Strong Duality

两个最优解相等。

这个不一定成立，但是在LP问题限制下是一定成立的。

15_dual_gen

Lagrange Dual Function

对于凸优化问题

$$\begin{aligned} \min_{\bm x} && f(\bm x)\\ \text{s.t.}&& \bm h(\bm x) = \bm A\bm x -\bm b = \bm 0\\ &&\bm g(\bm x) \leq \bm 0 \end{aligned}$$

构造该问题的Lagrange函数：

$$\mathcal L(\bm x, \bm \lambda, \bm \mu) = f(\bm x) + \bm\lambda^T \bm h(\bm x) + \bm\mu^T\bm g(\bm x)$$

函数的定义域是$\bm x\in D, \bm \lambda\in\mathbb R^k, \bm\mu\in\mathbb R^m_+$。

对$\bm x$求下界，则

$$\phi(\bm\lambda, \bm\mu) = \inf_{\bm x\in D} \mathcal L(\bm x, \bm\lambda, \bm \mu)$$

得到对偶问题

$$\begin{aligned} \max_{\bm \mu, \bm \lambda} && \phi(\bm\lambda, \bm\mu) \\ \text{s.t.} && \bm\mu\geq\bm 0\end{aligned}$$

Concavity

即使$f$不是convex的，$\phi$还是concave的。

Weak and Strong duality

首先是Weak duality（$f^*\geq \phi^*$）：

$$\begin{aligned} f^* &= \inf_{\bm x\in D} f(\bm x)\\ &\geq\inf_{\bm x\in D} \mathcal L(\bm x, \bm \lambda, \bm \mu) = f(\bm x) + \underset{(=0)}{\bm\lambda^T\bm h(\bm x)} + \underset{(\leq 0)}{\bm\mu^T\bm g(\bm x)}\\ &\geq\inf_{\bm x} \mathcal L(\bm x, \bm \lambda, \bm \mu)\\ &= \phi(\bm\lambda, \bm\mu) \end{aligned}$$

这里的$\phi$对$\mathbb R^n$取了最小值，但是定义里是对$D$取的，不过应该不影响结论。

Strong duality：$f^*=\phi^*$，可以用slater条件判断。

Duality Gap

对于非凸的primal问题可能存在duality gap：$$f^* - \phi^*$$

Slater’s Condition

对于凸的原问题，如果存在一个点$\bm x$，使得所有$g_i(\bm x)$不等式条件都不取等地满足，且$h_j(\bm x)$的等式条件全部满足，则一定有$$f^* = \phi^*$$

对于affine的条件$g_i$，只满足$g_i(\bm x)\leq 0$也是可以的。

KKT condition for convex problems

假设原问题是凸优化问题。

KKT条件对于一组点$(\bm x, \bm \lambda, \bm \mu)$满足当且仅当：

1. strong duality holds，也就是$f^* = \phi^*$；
2. $\bm x^*$是$f$的最优值点；
3. $(\bm \lambda, \bm \mu)$是$\phi$的最优值点。

凸优化问题总结

一般凸优化问题

在$\bm h(\bm x)=0$的等式约束和$\bm g(\bm x)\leq 0$的不等式约束下，最小化$f(\bm x)$，其中$f,\bm g$是凸函数，$\bm h$是仿射函数。

LP

在$\bm g$和$f$都退化为仿射函数时，问题退化为

$$\begin{aligned} &&\min_{\bm x} f(\bm x) = \bm c^T \bm x\\ \text{s.t.} && \bm A\bm x = \bm b\\ && \bm B\bm x\leq \bm d \end{aligned}$$

引入松弛变量，使$\bm B\bm x + \bm s = \bm d$，并将所有$x_i$拆成$x_i^+-x_i^-$可以化为Standard form

$$\begin{aligned} &&\min_{\bm x} f(\bm x) = \bm c^T \bm x\\ \text{s.t.} && \bm A\bm x = \bm b\\ && \bm x\geq \bm 0 \end{aligned}$$

或者把等式条件消掉，变成Inequality form

$$\begin{aligned} &&\min_{\bm x} f(\bm x) = \bm c^T \bm x\\ \text{s.t.} && \bm B\bm x\leq \bm d \end{aligned}$$

接下来只研究Standard form。

然后引入BFS和Simplex method：

BFS是基本可行解，假设有$m$行constraints，则BFS起码有$n-m$行为$0$。

如果存在最优解，一定存在和最优解一样的BFS。

Simplex method在一开始找到BFS的情况下，不停地找到更优的BFS。

如果发现每一列的第一行都大于等于$0$了，说明已经找到最优解；否则向一个可行方向优化。

如果出现循环问题，用Bland法则判定。

如果有多个可以下降，选最左边的；如果多个比例最小的，选编号最小的。

如果一开始的BFS不容易得到，先强行加入松弛变量$\bm A\bm x + \bm s = \bm b$，此时BFS为$\bm s = \bm b$，然后确认是否存在BFS。