凸优化核心基本概念（详细解析）

凸优化是优化理论的核心分支，其核心优势是局部最优解即为全局最优解，而这一特性依赖于“凸函数”“凸集”等基础概念的严格定义。以下是凸优化中所有关键基本概念的详细拆解，包含定义、数学表达、几何意义及核心性质：

一、优化问题的标准形式

凸优化的问题形式基于“目标函数+约束条件”，核心分为线性规划和二次规划（二者均为凸优化的特殊情形，也是最常用的类型）。

1. 线性规划（Linear Programming, LP）

定义

目标函数和所有约束条件均为线性函数的优化问题，是凸优化中最简单、应用最广泛的类型（如资源分配、生产计划等）。

一般形式

$$\{\begin{array}{ll}\min /\max & {\mathbf{c}}^T\mathbf{x}\\ \text{s.t.}& \mathbf{A}\mathbf{x}\le \mathbf{b}(\text{不等式约束})\\ & {\mathbf{A}}_{eq}\mathbf{x}={\mathbf{b}}_{eq}(\text{等式约束})\\ & \mathbf{x}\ge 0(\text{非负约束，可选})\end{array}$$

符号与含义

• $\mathbf{x}\in {\mathbb{R}}^n$：优化变量（$n$ 维实向量）；
• $\mathbf{c}\in {\mathbb{R}}^n$：目标函数系数向量（线性目标的斜率）；
• $\mathbf{A}\in {\mathbb{R}}^{m\times n}$：不等式约束系数矩阵（$m$ 个不等式约束）；
• ${\mathbf{A}}_{eq}\in {\mathbb{R}}^{p\times n}$：等式约束系数矩阵（$p$ 个等式约束）；
• $\mathbf{b}\in {\mathbb{R}}^m$、${\mathbf{b}}_{eq}\in {\mathbb{R}}^p$：约束右侧常数向量。

核心性质

• 目标函数是凸函数（线性函数既是凸函数也是凹函数）；
• 可行域是凸集（线性约束的交集为凸集）；
• 最优解若存在，必在可行域的顶点上（这是 simplex 算法的理论基础）。

2. 二次规划（Quadratic Programming, QP）

定义

目标函数为二次函数，约束条件仍为线性函数的优化问题（适用于含二次成本的场景，如最小二乘、控制问题）。

一般形式

$$\{\begin{array}{ll}\min & \frac{1}{2}{\mathbf{x}}^T\mathbf{H}\mathbf{x}+{\mathbf{c}}^T\mathbf{x}\\ \text{s.t.}& \mathbf{A}\mathbf{x}\le \mathbf{b}\\ & {\mathbf{A}}_{eq}\mathbf{x}={\mathbf{b}}_{eq}\\ & \mathbf{x}\ge 0(\text{可选})\end{array}$$

符号与核心条件

• $\mathbf{H}\in {\mathbb{S}}^n$：目标函数的 Hessian 矩阵（$n$ 阶对称矩阵，${\mathbb{S}}^n$ 表示对称矩阵集合）；
• 凸二次规划的关键条件：$\mathbf{H}⪰0$（$\mathbf{H}$ 半正定），此时目标函数为凸函数，问题是凸优化。

特殊情形

• 无约束二次规划：$\min \frac{1}{2}{\mathbf{x}}^T\mathbf{H}\mathbf{x}+{\mathbf{c}}^T\mathbf{x}$，若 $\mathbf{H}$ 正定，最优解为 ${\mathbf{x}}^{\ast }=-{\mathbf{H}}^{-1}\mathbf{c}$（直接由梯度为零求解）。

二、凸函数（Convex Function）

凸函数是凸优化的“核心灵魂”，其定义本质是“函数图像的弦在函数之上”，保证了局部最优即为全局最优。

1. 定义（基础形式）

设函数 $f:{\mathbb{R}}^n\to \mathbb{R}$，其定义域 $\text{dom}(f)\subseteq {\mathbb{R}}^n$ 为凸集（关键前提）。若对任意 ${\mathbf{x}}_1,{\mathbf{x}}_2\in \text{dom}(f)$ 和任意 $t\in [0,1]$，满足：
$$f(t{\mathbf{x}}_1+(1-t){\mathbf{x}}_2)\le tf({\mathbf{x}}_1)+(1-t)f({\mathbf{x}}_2)$$

几何意义

• 对于一维函数（$n=1$）：连接函数上两点 $({\mathbf{x}}_1,f({\mathbf{x}}_1))$ 和 $({\mathbf{x}}_2,f({\mathbf{x}}_2))$ 的线段（弦），始终在函数图像的上方；
• 对于高维函数（$n>1$）：定义域内任意两点的凸组合（加权平均，权重和为1）对应的函数值，不超过两点函数值的凸组合。

严格凸函数（加强版）

若不等式严格成立（$<$），则称 $f$ 为严格凸函数。例如：$f(x)=x^2$ 是严格凸函数，$f(x)=x$ 是凸函数但非严格凸。

2. 一阶条件（可微凸函数的判定）

若 $f$ 在 $\text{dom}(f)$ 内可微（梯度 $\nabla f(\mathbf{x})$ 存在），则 $f$ 是凸函数的充要条件为：
$$f(\mathbf{x})\ge f(\mathbf{y})+\nabla f(\mathbf{y}{)}^T(\mathbf{x}-\mathbf{y})\forall \mathbf{x},\mathbf{y}\in \text{dom}(f)$$

几何意义

• 函数在任意点 $\mathbf{y}$ 处的切线（或切平面），始终在函数图像的下方；
• 若 $f$ 是严格凸函数，不等式严格成立（切线严格在函数下方）。

例子

• 一维凸函数 $f(x)=x^2$：梯度 $\nabla f(y)=2y$，切线方程为 $y_t(x)=2y(x-y)+y^2=2yx-y^2$，显然 $x^2\ge 2yx-y^2$（即 $(x-y{)}^2\ge 0$），满足一阶条件。

3. 二阶条件（二次可微凸函数的判定）

若 $f$ 在 $\text{dom}(f)$ 内二次可微（Hessian 矩阵 ${\nabla }^{2}f(\mathbf{x})$ 存在），则 $f$ 是凸函数的充要条件为：
$${\nabla }^{2}f(\mathbf{x})⪰0\forall \mathbf{x}\in \text{dom}(f)$$
（Hessian 矩阵半正定：对任意非零向量 $\mathbf{v}\in {\mathbb{R}}^n$，有 ${\mathbf{v}}^T{\nabla }^{2}f(\mathbf{x})\mathbf{v}\ge 0$）。

严格凸的二阶条件

$${\nabla }^{2}f(\mathbf{x})\succ 0\forall \mathbf{x}\in \text{dom}(f)$$
（Hessian 矩阵正定：${\mathbf{v}}^T{\nabla }^{2}f(\mathbf{x})\mathbf{v}>0$ 对任意非零 $\mathbf{v}$ 成立）。

例子

• 二维函数 $f(x_1,x_2)=x_1^2+x_2^2$：Hessian 矩阵为 $\left[\begin{array}{cc}2& 0\\ 0& 2\end{array}\right]$，正定，故 $f$ 是严格凸函数；
• 文档中填空题1的函数 $f(x_1,x_2)=\frac{3}{2}(x_1^2+x_2^2)+(1+a)x_1{x}_2-(x_1+x_2)-b$：Hessian 为 $\left[\begin{array}{cc}3& 1+a\\ 1+a& 3\end{array}\right]$，半正定的充要条件是顺序主子式非负，即 $\det (\mathbf{H})=9-(1+a{)}^2\ge 0$，故 $-4\le a\le 2$。

三、凸集相关概念（Convex Set）

凸集是凸函数的定义域基础，也是可行域的核心性质，以下是凸优化中最常用的凸集相关概念：

1. α-下水平集（α-Sublevel Set）

定义

对函数 $f:{\mathbb{R}}^n\to \mathbb{R}$，其 $\alpha$-下水平集是所有满足“函数值不超过 $\alpha$”的点的集合：
Sα={x∈dom(f)∣f(x)≤α} S_\alpha = \{\boldsymbol{x} \in \text{dom}(f) \mid f(\boldsymbol{x}) \leq \alpha\} Sα​={x∈dom(f)∣f(x)≤α}

核心性质

• 凸函数的下水平集必为凸集（反之不成立：下水平集是凸集的函数不一定是凸函数）；
• 应用：将“函数值约束”转化为“集合约束”，便于分析可行域的凸性（如文档中填空题1的集合 $S=\{(x_1,x_2{)}^T\mid f(x_1,x_2)\le 0\}$，因 $f$ 是凸函数，故 $S$ 是凸集）。

2. 上境图（Epigraph）

定义

函数 $f$ 的上境图是“函数图像及其上方所有点”构成的集合：
$$\text{epi}(f)=\{(\mathbf{x},t)\in \text{dom}(f)\times \mathbb{R}\mid f(\mathbf{x})\le t\}$$

核心性质（凸函数的等价定义）

• 函数 $f$ 是凸函数 当且仅当 其上境图 $\text{epi}(f)$ 是凸集；
• 几何意义：凸函数的“上方区域”是凸集，非凸函数的上方区域存在“凹陷”（非凸集）。

例子

• 凸函数 $f(x)=x^2$ 的上境图是 $\{(x,t)\mid t\ge x^2\}$（抛物线上方区域，是凸集）；
• 非凸函数 $f(x)=-x^2$ 的上境图是 $\{(x,t)\mid t\ge -x^2\}$（抛物线下方区域，非凸集）。

四、共轭函数与对偶范数

1. 共轭函数（Conjugate Function）

定义

对函数 $f:{\mathbb{R}}^n\to \mathbb{R}$，其共轭函数 f∗:Rn→R∪{+∞}f^*: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}f∗:Rn→R∪{+∞} 定义为：
$$f^{\ast }(\mathbf{y})=\underset{\mathbf{x}\in \text{dom}(f)}{\sup }\left({\mathbf{y}}^T\mathbf{x}-f(\mathbf{x})\right)$$
（$\sup$ 表示上确界，即“最小的上界”；若上确界不存在，$f^{\ast }(\mathbf{y})=+\infty$）。

本质与作用

• 共轭函数是 $f$ 的“对偶变换”：将原函数 $f$ 转化为关于 $\mathbf{y}$ 的函数，核心是“对原函数的线性逼近的偏差取最大值”；
• 凸性：无论 $f$ 是否为凸函数，其共轭函数 $f^{\ast }$ 必为凸函数（上确界操作保持凸性）；
• 应用：将非凸优化问题转化为凸优化问题（如最大化问题转最小化问题），或简化约束条件。

常见例子

• 文档中计算题10a：$f(\mathbf{x})={\max }_{i=1,...,n}{x}_i$（逐点最大值函数），其共轭函数为：
  $$f^{\ast }(\mathbf{y})=\{\begin{array}{ll}0& \text{若 }\mathbf{y}\ge 0\text{ 且 }{\sum }_{i=1}^n{y}_i=1\\ +\infty & \text{其他情况}\end{array}$$
• 文档中计算题10b：$f(x)=\frac{|x{|}^p}{p}$（$p>1$），其共轭函数为 $f^{\ast }(y)=\frac{|y{|}^q}{q}$（$q=p/(p-1)$，$p$ 和 $q$ 为共轭指数）。

2. 对偶范数（Dual Norm）

定义

设 $\Vert \cdot \Vert$ 是 ${\mathbb{R}}^n$ 上的范数（如 ${\ell }_1,{\ell }_2,{\ell }_{\infty }$ 范数），其对偶范数 $\Vert \cdot {\Vert }_{\ast }$ 定义为：
$$\Vert \mathbf{y}{\Vert }_{\ast }=\underset{\Vert \mathbf{x}\Vert \le 1}{\sup }{\mathbf{y}}^T\mathbf{x}$$
（即“$\mathbf{y}$ 与单位范数球内向量的内积的最大值”）。

核心性质

• 对偶范数本身是范数；
• 共轭性：$(\Vert \cdot {\Vert }_{\ast }{)}_{\ast }=\Vert \cdot \Vert$（对偶的对偶是原范数）；
• 常见范数的对偶：
  • ${\ell }_2$ 范数的对偶是自身（$\Vert \mathbf{y}{\Vert }_2^{\ast }=\Vert \mathbf{y}{\Vert }_2$）；
  • ${\ell }_1$ 范数的对偶是 ${\ell }_{\infty }$ 范数（$\Vert \mathbf{y}{\Vert }_1^{\ast }=\Vert \mathbf{y}{\Vert }_{\infty }={\max }_{i=1,...,n}|y_i|$）；
  • ${\ell }_{\infty }$ 范数的对偶是 ${\ell }_1$ 范数。

与共轭函数的关系

• 范数 $\Vert \cdot \Vert$ 的共轭函数就是其对偶范数的指示函数：$f(\mathbf{x})=\Vert \mathbf{x}\Vert$ 的共轭函数为 $f^{\ast }(\mathbf{y})=\{\begin{array}{ll}0& \text{若 }\Vert \mathbf{y}{\Vert }_{\ast }\le 1\\ +\infty & \text{其他}\end{array}$。

五、线搜索方法（Line Search）

线搜索是凸优化数值算法（如梯度下降、牛顿法）的核心步骤，目的是“在给定下降方向后，找到最优步长 $t$”。

1. 核心思想

设当前迭代点为 ${\mathbf{x}}^{(k)}$，下降方向为 ${\mathbf{d}}^{(k)}$（如梯度负方向 $-\nabla f({\mathbf{x}}^{(k)})$），线搜索的目标是找到步长 $t>0$，使得：
$$f({\mathbf{x}}^{(k)}+t{\mathbf{d}}^{(k)})<f({\mathbf{x}}^{(k)})$$
（即函数值下降）。

2. 精确线搜索（Exact Line Search）

定义

找到步长 $t_k$，使得函数值在该方向上达到全局最小值：
$$t_k=\arg \underset{t\ge 0}{\min }f({\mathbf{x}}^{(k)}+t{\mathbf{d}}^{(k)})$$

优点与缺点

• 优点：每一步都能找到最优步长，收敛速度理论上更快；
• 缺点：计算量大（需求解一维最小值问题，可能涉及解方程），适用于低维问题或简单函数（如二次函数）。

例子

• 文档中计算题11a：梯度下降法的精确线搜索，通过构造一维函数 $g(t)=f({\mathbf{x}}^{(1)}+t{\mathbf{d}}^{(1)})$，求导得 $g^{\prime }(t)=0$，解得 $t=1/4$。

3. 不精确线搜索（Inexact Line Search）

定义

不需要找到全局最优步长，只需满足“函数值充分下降”的准则（如 Armijo 准则、Wolfe 准则），核心是平衡“下降效果”和“计算效率”。

常用准则：Armijo 准则

找到 $t>0$，使得：
$$f({\mathbf{x}}^{(k)}+t{\mathbf{d}}^{(k)})\le f({\mathbf{x}}^{(k)})+c_{1}t\nabla f({\mathbf{x}}^{(k)}{)}^T{\mathbf{d}}^{(k)}$$
其中 $0<c_1<1$（通常取 $c_1=10^{-4}$）。

几何意义

• 函数值的下降量至少是“线性近似下降量”的 $c_1$ 倍（避免步长过小导致收敛过慢，或步长过大导致函数值上升）；
• 优点：计算量小（只需验证不等式，无需解方程），适用于高维问题，是实际算法的首选。

六、对偶性（Duality）

对偶性是凸优化的核心理论工具，通过构造“对偶问题”来逼近原问题的最优值，适用于原问题约束复杂或难以直接求解的场景。

1. 原问题与对偶问题

设原最小化问题（Primal Problem）为：
$$p^{\ast }=\underset{\mathbf{x}}{\min }{f}_0(\mathbf{x})\text{s.t.}{f}_i(\mathbf{x})\le 0(i=1,...,m),\mathbf{A}\mathbf{x}=\mathbf{b}$$
（$p^{\ast }$ 为原问题最优值）。

通过 Lagrange 对偶变换，构造对偶问题（Dual Problem）为：
$$d^{\ast }=\underset{\lambda \ge 0,\nu }{\max }g(\lambda ,\nu )$$
其中 $g(\lambda ,\nu )={\inf }_{\mathbf{x}}\left(f_0(\mathbf{x})+{\sum }_{i=1}^m{\lambda }_i{f}_i(\mathbf{x})+{\nu }^T(\mathbf{A}\mathbf{x}-\mathbf{b})\right)$ 是对偶函数，$\lambda \in {\mathbb{R}}_{+}^m$（对偶变量，对应不等式约束），$\nu \in {\mathbb{R}}^p$（对偶变量，对应等式约束）。

2. 弱对偶性（Weak Duality）

定义

对任意原问题和对偶问题，恒有：
$$d^{\ast }\le p^{\ast }$$
（对偶问题的最优值不超过原问题的最优值）。

本质与作用

• 弱对偶性无条件成立，无需任何凸性假设；
• 提供原问题最优值的“下界”：若对偶问题易求解，可通过 $d^{\ast }$ 估计 $p^{\ast }$ 的范围；
• 对偶间隙：KaTeX parse error: Undefined control sequence: \gap at position 1: \̲g̲a̲p̲ ̲= p^* - d^* \ge…（衡量对偶问题对原问题的逼近程度）。

3. 强对偶性（Strong Duality）

定义

若对偶间隙为零，即：
$$d^{\ast }=p^{\ast }$$
则称强对偶性成立。

成立条件（约束规范）

强对偶性需满足额外条件，最常用的是Slater 条件（适用于凸优化问题）：

• 原问题是凸优化问题（$f_0$ 凸，$f_i$ 凸，等式约束 $\mathbf{A}\mathbf{x}=\mathbf{b}$ 线性）；
• 存在可行点 ${\mathbf{x}}_0$，使得所有不等式约束严格成立：$f_i({\mathbf{x}}_0)<0(i=1,...,m)$，且 $\mathbf{A}{\mathbf{x}}_0=\mathbf{b}$。

作用

• 强对偶性成立时，可通过求解对偶问题得到原问题的最优值（对偶问题可能更简单，如无约束或约束更少）；
• 是 KKT 条件的前提（强对偶性+KKT 条件可直接得到最优解）。

七、约束优化的关键概念

1. 可行域（Feasible Set）

定义

满足所有约束条件的优化变量 $\mathbf{x}$ 的集合，记为 $\mathcal{F}$：
F={x∈Rn∣fi(x)≤0 (i=1,...,m), Ax=b} \mathcal{F} = \{\boldsymbol{x} \in \mathbb{R}^n \mid f_i(\boldsymbol{x}) \leq 0 \ (i=1,...,m), \ \boldsymbol{A}\boldsymbol{x} = \boldsymbol{b}\} F={x∈Rn∣fi​(x)≤0 (i=1,...,m), Ax=b}

核心性质

• 凸优化问题的可行域必为凸集（凸函数的下水平集+线性约束的交集为凸集）；
• 可行域非空是优化问题有解的必要条件（若 $\mathcal{F}=\varnothing$，问题无解）。

例子

• 文档中问题9的线性规划：$\min 2x_1+3x_2$，$\text{s.t.}{x}_1+x_2=1$，$x_1\ge 0$，$x_2\ge 0$；
• 可行域 $\mathcal{F}=\{(x_1,x_2)\mid x_1+x_2=1,x_1\ge 0,x_2\ge 0\}$（连接 $(0,1)$ 和 $(1,0)$ 的线段，是凸集）。

2. Slater 条件（Slater’s Condition）

定义（针对凸优化问题）

存在可行点 ${\mathbf{x}}_0\in \mathcal{F}$，使得：
$$f_i({\mathbf{x}}_0)<0(i=1,...,m),\mathbf{A}{\mathbf{x}}_0=\mathbf{b}$$
（等式约束无需严格成立，只需满足；不等式约束需严格小于0）。

作用

• 是强对偶性成立的充分条件（非必要条件）；
• 文档中问题9的 Slater 条件：存在可行点 $(0.5,0.5)$，满足 $x_1=0.5>0$，$x_2=0.5>0$（严格满足不等式约束），故 Slater 条件成立，强对偶性成立。

3. KKT 条件（Karush-Kuhn-Tucker Conditions）

定义

KKT 条件是约束优化问题最优解的必要条件，对于凸优化问题，也是充分条件。设 ${\mathbf{x}}^{\ast }$ 是原问题的最优解，${\lambda }^{\ast }\ge 0$（不等式约束对偶变量），${\nu }^{\ast }$（等式约束对偶变量）是对应的对偶最优解，则 KKT 条件包括以下4点：

（1）梯度条件（stationarity）

$$\nabla f_0({\mathbf{x}}^{\ast })+\sum _{i=1}^m{\lambda }_i^{\ast }\nabla f_i({\mathbf{x}}^{\ast })+{\mathbf{A}}^T{\nu }^{\ast }=0$$
（原问题的梯度与对偶变量加权的约束梯度平衡）。

（2）互补松弛条件（complementary slackness）

$${\lambda }_i^{\ast }{f}_i({\mathbf{x}}^{\ast })=0(i=1,...,m)$$
（对偶变量 ${\lambda }_i^{\ast }$ 与约束函数值 $f_i({\mathbf{x}}^{\ast })$ 至少一个为零）。

• 含义：若 ${\lambda }_i^{\ast }>0$（对偶变量非零），则 $f_i({\mathbf{x}}^{\ast })=0$（对应约束是“紧约束”，即最优解在约束边界上）；
• 若 $f_i({\mathbf{x}}^{\ast })<0$（约束是“松约束”，最优解在约束内部），则 ${\lambda }_i^{\ast }=0$（对偶变量无作用）。

（3）约束满足条件（primal feasibility）

$$f_i({\mathbf{x}}^{\ast })\le 0(i=1,...,m),\mathbf{A}{\mathbf{x}}^{\ast }=\mathbf{b}$$
（最优解必须在可行域内）。

（4）对偶变量非负条件（dual feasibility）

$${\lambda }_i^{\ast }\ge 0(i=1,...,m)$$
（不等式约束的对偶变量非负）。

应用

• 直接求解最优解：通过解 KKT 方程组（梯度条件+互补松弛条件+约束条件），可直接得到 ${\mathbf{x}}^{\ast }$、${\lambda }^{\ast }$、${\nu }^{\ast }$；
• 验证最优解：若某点满足 KKT 条件，且原问题是凸优化，则该点必为最优解。

例子（文档问题9的 KKT 条件）

原问题：$\min 2x_1+3x_2$，$\text{s.t.}{x}_1+x_2=1$，$x_1\ge 0$，$x_2\ge 0$；

• Lagrangian 函数：$L=2x_1+3x_2-\lambda (x_1+x_2-1)-{\mu }_1{x}_1-{\mu }_2{x}_2$（$\lambda$ 为等式约束乘子，${\mu }_1,{\mu }_2\ge 0$ 为不等式约束乘子）；
• KKT 条件：
  1. 梯度条件：$\{\begin{array}{l}2-\lambda -{\mu }_1=0\\ 3-\lambda -{\mu }_2=0\end{array}$；
  2. 互补松弛：${\mu }_1{x}_1=0$，${\mu }_2{x}_2=0$；
  3. 约束满足：$x_1+x_2=1$，$x_1\ge 0$，$x_2\ge 0$；
  4. 对偶变量非负：${\mu }_1\ge 0$，${\mu }_2\ge 0$。

求解得最优解：$x_1^{\ast }=1$，$x_2^{\ast }=0$，${\lambda }^{\ast }=2$，${\mu }_1^{\ast }=0$，${\mu }_2^{\ast }=1$（满足所有 KKT 条件）。

总结：凸优化基本概念的逻辑框架

凸优化的核心逻辑是：通过“凸函数+凸集”定义凸优化问题，利用“对偶性”转化问题，通过“线搜索”实现数值求解，通过“KKT条件”判定最优解。各概念的衔接关系如下：

1. 基础：优化问题形式（LP/QP）→ 可行域（凸集）；
2. 核心：凸函数（定义+一/二阶条件）→ 上境图/下水平集（凸集验证）；
3. 工具：共轭函数（对偶变换）→ 对偶范数（范数的对偶）；
4. 理论：弱对偶性（恒成立）→ 强对偶性（Slater条件）；
5. 求解：线搜索（步长选择）→ KKT条件（最优解判定）。