基础概念
行列式（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：
局部最优解的基本条件：如果 $\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
$$约束的凸性和目标函数的凸性：约翰的条件强调了约束集和目标函数的凸性对最优解的影响。它要求目标函数 $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：
原始问题：
$$
\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
$$构造拉格朗日函数：
$$
\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 对偶，最优性分析