凸优化期末复习

基础概念

行列式（determinant）

向量空间：存在零向量（加法），每个向量都有加法逆元，向量的标量乘法满足结合律和分配律，存在单位标量（乘法）

子空间（Subspace）：向量空间的一个子空间，包含零向量，加法封闭，数乘封闭

生成空间（SPAN）：一组向量线性组合形成的空间

基（basis）：线性无关、能够生成整个空间

子空间的维度：子空间基的向量数量

秩（Rank）：线性无关向量的最大数量（行秩、列秩）

可逆矩阵（Invertible Matrix）：$A⋅B=B⋅A=I$，可逆条件（满秩方阵）

向量范数（Vector Norms）：向量空间中给每一个向量分配一个非负数以此来表示向量的大小。（非负性、齐次性、三角不等式）

欧几里得范数（L2）：$\|\mathbf{v}\|_2 = \sqrt{v_1^2 + v_2^2 + \dots + v_n^2}$

曼哈顿范数（L1）：$\|\mathbf{v}\|_1 = |v_1| + |v_2| + \dots + |v_n|$

最大范数（L∞ 范数）：$\|\mathbf{v}\|_\infty = \max\{|v_1|, |v_2|, \dots, |v_n|\}$

p-范数：$\|\mathbf{v}\|_p = \left( |v_1|^p + |v_2|^p + \dots + |v_n|^p \right)^{1/p}$

内积（Inner product）：$\mathbf{u} \cdot \mathbf{v} = u_1 v_1 + u_2 v_2 + \dots + u_n v_n = \sum_{i=1}^{n} u_i v_i$

投影（projections）：表示一个向量在另一个向量上面的分量，$\text{Proj}_{\mathbf{v}} \mathbf{u} = \frac{\mathbf{u} \cdot \mathbf{v}}{\mathbf{v} \cdot \mathbf{v}} \mathbf{v}$

CH02. Convexity

仿射（affine）集合：仿射集合是指对于集合 SS 中任意两点 $\mathbf{x_1}$ 和 $\mathbf{x_2}$，和任意标量 $\lambda \in \mathbb{R}$，其仿射组合 $(1-\lambda)\mathbf{x_1} + \lambda \mathbf{x_2}$ 都属于集合$S$。

凸集（Convex Set）：$C \text{ 是凸的} \iff \forall \mathbf{x_1}, \mathbf{x_2} \in C, \ \forall \lambda \in [0, 1], \ (1 - \lambda)\mathbf{x_1} + \lambda \mathbf{x_2} \in C$

凸组合（Convex Combinations）：$\mathbf{x} = \lambda_1 \mathbf{x_1} + \lambda_2 \mathbf{x_2} + \dots + \lambda_n \mathbf{x_n}$，$\sum_{i=1}^n \lambda_i = 1$

典型的凸集：非负正交象限（Non-negative Orthant）（所有坐标都非负数），超平面（Hyperplane），半空间（Half Space），欧几里得球（Euclidean Ball），凸锥（Convex Cone）（封闭性+非负性）

Convex Set 的两个性质：投影（Projection），分离（Separation）

Projection：投影点是存在且唯一的，计算投影可以考虑$\|\mathbf{x} - \mathbf{p}\| = \min_{\mathbf{y} \in C} \|\mathbf{x} - \mathbf{y}\|$

Separation：

假设 $C_1$ 和 $C_2$ 是两个凸集，且 $C_1 \cap C_2 = \emptyset$，并且至少有一个集合是开集。则存在一个超平面 $H$，使得：

$C_1 \subseteq \{ \mathbf{x} \mid \mathbf{a}^\top \mathbf{x} \leq \alpha \}, \quad C_2 \subseteq \{ \mathbf{x} \mid \mathbf{a}^\top \mathbf{x} \geq \beta \}$

其中，$\mathbf{a}$ 是超平面的法向量，且 $\alpha$和 $\beta$ 是常数。

考点：判断凸集、投影（两个定理）。

CH03.Convex Functions

凸函数（Convex Functions）：有效域（Effective Domain）（在什么定义域上面有凸性），上图集（Epigrhaph）（直观理解在曲线上方的点）（如果一个函数是Convex的，那么它的Epigraph也是Convex的,反之同理），琴生不等式（$f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)]$）。

凸性运算（Convexity-Preserving Operations）：凸集或者凸函数经过凸性运算之后仍然保持凸性。

典型凸性运算：非负线性组合（加法），点wise上确界（Pointwise Supremum）（取每一个点的最大值），单调非递减的凸函数复合，Restrictions on line（凸函数复合一个直线函数也是凸函数）

可微凸函数（Differentiable Convex Functions）：凸函数，且在定义上的每个点都存在梯度$\nabla f(x)$

可微凸函数的基本性质：梯度不减少（切平面在函数下方），二阶梯度是半正定的（Hessian矩阵判定）

不可微凸函数（Non-Differentiable Convex Functions）：凸函数，但是不一定可微

次梯度（Subgradient）：$f(x) \geq f(x_0) + g^\top (x - x_0), \quad \forall x \in \mathbb{R}^n$

次微分（Subdifferential）：所有次梯度构成的集合

考点：判定凸函数（定义，Hessian矩阵）

CH04.Duality

标准线性规划形式（Standard LP Form）:
$$\text{minimize } \mathbf{c}^\top \mathbf{x} \\\text{subject to } A \mathbf{x} = \mathbf{b}, \quad \mathbf{x} \geq 0$$
多面体（Polyhedron）：由有限个超平面所围成的凸集合

Farkas Lemma：如果存在一个非负向量 $\mathbf{y}$，使得 $\mathbf{y}^\top A = 0$且 $\mathbf{y}^\top \mathbf{b} > 0$，则线性系统 $A \mathbf{x} \leq \mathbf{b}$ 具有解；否则，系统没有解。

弱对偶性（Weak Duality）：原始问题的最优目标值大于或者等于对偶问题的最优目标值，所以对偶问题为原问题提供一个下界（最小化问题当中）

弱对偶性定理（Weak Duality Theorem）：对于任何原始问题的可行解 $\mathbf{x}$ 和任何对偶问题的可行解 $\mathbf{y}$，它们的目标值之间存在以下关系：
$$\mathbf{c}^\top \mathbf{x} \leq \mathbf{b}^\top \mathbf{y}$$
强对偶性（Strong Duality）：原始问题和对偶问题在一定条件下有相同的最优值（类似夹逼）

强对偶性定理（Strong Duality）：如果原始问题有最优解且对偶问题有最优解，且原始问题的可行域是非空的（即原始问题可行），则原始问题的最优值等于对偶问题的最优值。即：
$$\mathbf{c}^\top \mathbf{x}^* = \mathbf{b}^\top \mathbf{y}^*$$
最优条件：原始问题可行，Slater条件成立，原始问题和对偶问题都有界

Slater条件：约束函数是凸函数，存在一个严格可行解

互补松弛定理（Complementary Slackness Theorem）：如果 $\mathbf{x}^*$ 是原始问题的最优解，$\mathbf{y}^*$ 是对偶问题的最优解，则对于每个约束 $i$，有：
$$y_i^* (A \mathbf{x}^* - \mathbf{b})_i = 0, \quad i = 1, 2, \dots, m$$
KTT条件：

原始可行性：$A \mathbf{x}^* \leq \mathbf{b}, \quad \mathbf{x}^* \geq 0$

对偶可行性：$A^\top \mathbf{y}^* \geq \mathbf{c}, \quad \mathbf{y}^* \geq 0$

齐次性：$\mathbf{c} + A^\top \mathbf{y}^* = 0$

互补松弛性：$y_i^* (A \mathbf{x}^* - \mathbf{b})_i = 0$

线性规划松弛（LP Relaxation）：在整数规划中，决策变量通常被约束为整数或二进制值。松弛过程就是将这些整数或二进制约束去掉，让变量变为连续的，变成一个标准的线性规划问题。

考点：线性规划的标准形式和对偶形式、凑Farkas定理45

CH05.Conic Linear Programming

锥形线性规划（Conic Linear Programming）：是一种线性规划的推广形式，约束条件涉及到锥结构
$$\text{maximize} \quad \mathbf{c}^\top \mathbf{x} \\ \text{subject to} \quad \mathbf{x} \in K, \quad A\mathbf{x} \leq \mathbf{b}$$
几种特殊的锥形线性规划形式：

线性规划（LP）：取非负正交锥$K = \mathbb{R}^n_+$

二次锥规划（Second-Order Cone Programming）：取二次顺序锥$K = \left\{ \mathbf{x} \in \mathbb{R}^{n+1}: \| \mathbf{x}_1 \| \leq \mathbf{x}_2 \right\}$

半正定规划（SDP）：取半正定锥

对偶问题：
$$\text{minimize} \quad \mathbf{b}^\top \mathbf{y} \\ \text{subject to} \quad A^\top \mathbf{y} \in K^*, \quad \mathbf{y} \geq 0$$
其中：$K^* = \{\mathbf{y}: \mathbf{x}^\top \mathbf{y} \geq 0 \ \forall \mathbf{x} \in K \}$

在这个条件下，锥形线性规划仍然满足弱对偶性、强对偶性和Slater条件

鲁棒线性规划（Robust LP）：
$$\text{maximize} \quad \mathbf{c}^\top \mathbf{x} \\ \text{subject to} \quad (A + \Delta A) \mathbf{x} \leq \mathbf{b} + \Delta \mathbf{b}, \quad \mathbf{x} \geq 0, \quad \forall (\Delta A, \Delta \mathbf{b}) \in \mathcal{U}_A \times \mathcal{U}_b$$
其中$\mathcal{U}_A$和$\mathcal{U}_B$是两个不确定集

半正定松弛（Semidefinite Relaxation）：可以将问题从
$$\text{maximize} \quad \mathbf{x}^\top Q \mathbf{x} \\ \text{subject to} \quad \mathbf{x}^\top A_i \mathbf{x} \leq b_i \quad \text{for all} \quad i = 1, \dots, m$$
此时引入一个矩阵变量$X = \mathbf{x} \mathbf{x}^\top$，然后将原问题的秩约束$\text{rank}(X) = 1$替换为半正定约束$X \succeq 0$

然后问题就转为为凸优化问题：
$$\text{maximize} \quad \text{trace}(Q X) \\ \text{subject to} \quad \text{trace}(A_i X) \leq b_i \quad \text{for all} \quad i = 1, \dots, m \\ X \succeq 0$$

CH06. Optimality Conditions

无约束问题的最优性条件：梯度为零条件、二阶Hessian矩阵半正定（二阶充分条件）

有约束问题的最优性条件：KTT条件，John Necessary Conditions

John Necessary Conditions：

1. 局部最优解的基本条件：如果 $\mathbf{x}^*$ 是目标函数 $f(\mathbf{x})$ 在有约束优化问题中的局部最优解，那么，存在拉格朗日乘子 $\lambda_i \geq 0$和 $\nu_j$使得下列条件成立：

   $$\nabla f(\mathbf{x}^*) + \sum_{i=1}^{m} \lambda_i \nabla g_i(\mathbf{x}^*) + \sum_{j=1}^{p} \nu_j \nabla h_j(\mathbf{x}^*) = 0$$

2. 约束的凸性和目标函数的凸性：约翰的条件强调了约束集和目标函数的凸性对最优解的影响。它要求目标函数 $f(\mathbf{x})$ 和约束集（包括不等式约束和等式约束）是凸的。

   • 目标函数 $f(\mathbf{x})$ 必须是凸的，这意味着对于任意两点 $\mathbf{x}_1, \mathbf{x}_2$，有：

     $$f(\lambda \mathbf{x}_1 + (1-\lambda) \mathbf{x}_2) \leq \lambda f(\mathbf{x}_1) + (1-\lambda) f(\mathbf{x}_2), \quad \lambda \in [0, 1]$$

   • 约束集，即满足所有不等式约束$g_i(\mathbf{x}) \leq 0$ 和等式约束 $h_j(\mathbf{x}) = 0$的集合，必须是凸的。这保证了局部最优解是全局最优解。

Lagrangian Duality：

1. 原始问题：

   $$\text{minimize} \quad f(\mathbf{x}) \\ \text{subject to} \quad g_i(\mathbf{x}) \leq 0, \quad i = 1, \dots, m \\ h_j(\mathbf{x}) = 0, \quad j = 1, \dots, p$$

2. 构造拉格朗日函数：

   $$\mathcal{L}(\mathbf{x}, \lambda, \nu) = f(\mathbf{x}) + \sum_{i=1}^{m} \lambda_i g_i(\mathbf{x}) + \sum_{j=1}^{p} \nu_j h_j(\mathbf{x})$$

考点：会写KKT条件和Lagrange 对偶，最优性分析