3. 凸规划问题

# 定义

标准形式的优化问题如下：

$$\begin{align*} \min_{x} \quad & f_0(x) \\ \text{s.t.} \quad & f_i(x) \leq 0,\quad i=1,\dots, m \\ & h_j(x) = 0,\quad j=1,\dots, p \end{align*}$$

• $x \in \mathbb{R}^n$ 是优化变量
• $f_0: \mathbb{R}^n \to \mathbb{R}$ 为目标函数（cost/objective function）
• $f_i: \mathbb{R}^n \to \mathbb{R},\ i=1,\dots, m$ 是不等式约束函数
• $h_j: \mathbb{R}^n \to \mathbb{R},\ j=1,\dots, p$ 是等式约束函数

最优值定义：

$$p^* = \inf \left\{ f_0(x)\mid f_i(x) \leq 0,\ i=1,\dots, m;\ h_j(x) = 0,\ j=1,\dots, p \right\}$$

• 如果无可行解（即不存在任何 $x$ 满足所有约束），则 $p^* = +\infty$
• 如果问题无界下，即 $f_0(x)$ 可以趋于 $-\infty$，则 $p^* = -\infty$

相关定义：

• 若 $x \in \text{dom}\ f_0$ 且满足所有约束，则称 $x$ 为可行解（feasible）
• 若 $x$ 可行且 $f_0(x) = p^*$，则 $x$ 为最优解，所有最优解组成集合 $X^*_\text{opt}$
• 若满足存在 $R>0$，在 $|z-x|_2 \leq R$ 内 $x$ 对应的局部子问题最优，则 $x$ 为局部最优

举例（$n=1$, $m=p=0$）：

• $f_0(x) = 1/x,\ \mathrm{dom}\ f_0 = \mathbb{R}_{++}$：$p^* = 0$，但不存在最优点
• $f_0(x) = -\log x,\ \mathrm{dom}\ f_0 = \mathbb{R}_{++}$：$p^* = -\infty$
• $f_0(x) = x\log x,\ \mathrm{dom}\ f_0 = \mathbb{R}_{++}$：$p^* = -1/e,\ x=1/e$ 达到最优
• $f_0(x) = x^3 - 3x$：$p^* = -\infty$，但 $x=1$ 处有局部最小

优化问题的标准形式隐含一个域约束 $x \in D= \bigcap_{i=0}^m \mathrm{dom}\ f_i \cap \bigcap_{j=1}^p \mathrm{dom}\ h_j$，其中 $D$ 称为问题的域，$f_i(x) \leq 0, h_j(x)=0$ 为显式约束。若 $m=p=0$，即为无约束问题。

例子：

$$\min_x \ -\sum_i \log(b_i - a_i^T x)$$

这是无显式约束问题，但隐含约束 $a_i^T x < b_i$。

凸规划/凸优化问题定义

当满足：

• 目标函数 $f_0$ 是凸函数
• 所有不等式约束 $f_i$ 均为凸函数
• 所有等式约束 $h_j$ 为仿射函数（即 $h_j(x) = a_j^T x + b_j$，线性函数）

时，标准形式问题称为凸优化问题。

根据凸集性质或凸集定义易证：凸优化问题的可行域一定为凸集。

# 非凸问题与等价（转化）问题

某些非凸优化问题可通过变量变换、等式消除或引入 slack 变量等方式转化为凸问题。常见保持凸性的等价变换有：

• 消除等式约束：

  $$\min_x\ f_0(x)\quad \text{s.t.}\ f_i(x)\leq 0,\ Ax=b$$

  等价于

  $$\min_z\ f_0(Fz + x_0)\quad \text{s.t.}\ f_i(Fz+x_0)\leq 0$$

  其中 $x=Fz + x_0$ 表示满足 $Ax=b$ 的所有 $x$。

• 引入 slack 变量：

  $$a_i^T x \leq b_i\ \Leftrightarrow\ a_i^T x + s_i = b_i,\ s_i\geq 0$$

• 上凸包/epigraph 形式：

  $$\min_{x,t} \ t\quad \text{s.t.}\ f_0(x) - t \leq 0$$

• 变量消元（最小化部分变量）：

  $$\min_{x_1, x_2} f_0(x_1, x_2),\ \text{s.t.}\ f_i(x_1)\leq 0$$

  等价于

  $$f_0(x_1) := \inf_{x_2} f_0(x_1, x_2)$$

# 準凸（Quasiconvex）优化

如果 $f_0$ 是準凸函数（quasiconvex），约束 $f_i$ 凸，等式约束仿射，问题一般不是凸优化，但可用一些手段处理（例如二分法/bisection——通过求解一系列凸可行性问题 $\varphi_t(x)\leq 0, f_i(x)\leq 0, Ax=b$ 来近似 $p^*$）。

举例：

• 分式目标 $f_0(x) = \frac{p(x)}{q(x)}$，$p$ 凸、$q$ 凸且 $q > 0$，可用 $\varphi_t(x) = p(x) - t q(x)$ 替换，$\varphi_t$ 关于 $x$ 是凸函数。

# 例子

1. 线性规划 (Linear Programming, LP)

   $$\begin{align*} \min_x \quad & c^T x \\ \text{s.t.} \quad & Gx \preceq h \\ & Ax = b \end{align*}$$

   • 目标函数和约束函数都是仿射函数（线性函数）
   • 可行域是多面体（polyhedron）

2. 线性分式规划 (Linear-Fractional Program)

   $$\begin{align*} \min_x \quad & f_0(x) = \frac{a^T x + d}{e^T x + f} \\ \text{s.t.} \quad & Gx \preceq h \\ & Ax = b \end{align*}$$

   • 目标函数是线性分式函数，定义域为 $\text{dom}\ f_0 = \{x \mid e^T x + f > 0\}$
   • 这是一个拟凸优化问题（quasiconvex optimization problem），不是凸优化问题
   • 可以通过二分法（bisection）求解：通过求解一系列凸可行性问题来近似最优值
   • 可以等价转化为线性规划：引入变量 $y = x/(e^T x + f)$ 和 $z = 1/(e^T x + f)$，则原问题等价于

     $$\begin{align*} \min_{y,z} \quad & c^T y + d z \\ \text{s.t.} \quad & Gy \preceq h z \\ & Ay = b z \\ & e^T y + f z = 1 \\ & z \geq 0 \end{align*}$$

   • 其中 $c = a$，转化后的问题是线性规划

3. 广义线性分式规划 (Generalized Linear-Fractional Program)

   • 目标函数为多个线性分式函数的最大值或加权和
   • 形式更一般，但仍可通过类似方法转化为线性规划或使用二分法求解

4. 二次规划 (Quadratic Programming, QP)

   $$\begin{align*} \min_x \quad & (1/2)x^T P x + q^T x + r \\ \text{s.t.} \quad & Gx \preceq h \\ & Ax = b \end{align*}$$

   • 目标函数是二次函数，其中 $P \succeq 0$（半正定矩阵）
   • 约束函数是仿射函数
   • 当 $P \succ 0$ 时，目标函数是严格凸函数，有唯一最优解

5. 二次约束二次规划 (Quadratically Constrained Quadratic Programming, QCQP)

   $$\begin{align*} \min_x \quad & (1/2)x^T P_0 x + q_0^T x + r_0 \\ \text{s.t.} \quad & (1/2)x^T P_i x + q_i^T x + r_i \leq 0,\quad i=1,\dots, m \\ & Ax = b \end{align*}$$

   • 目标函数和约束函数都是二次函数
   • 要求 $P_i \succeq 0,\ i=0,1,\dots, m$（所有二次项系数矩阵半正定）

6. 半正定规划 (Semidefinite Programming, SDP)

   $$\begin{align*} \min_x \quad & c^T x \\ \text{s.t.} \quad & x_1 F_1 + x_2 F_2 + \cdots + x_n F_n + G \preceq 0 \\ & Ax = b \end{align*}$$

   • 约束包含线性矩阵不等式 (LMI)
   • 其中 $F_i, G \in S^k$（$k \times k$ 对称矩阵）
   • 这是线性规划的推广，将向量不等式推广到矩阵不等式

7. 锥规划 (Cone Programming)

   $$\begin{align*} \min_x \quad & c^T x \\ \text{s.t.} \quad & Fx + g \preceq_{\mathcal{K}} 0 \\ & Ax = b \end{align*}$$

   • 使用广义不等式 $\preceq_{\mathcal{K}}$，其中 $\mathcal{K}$ 是正常锥（proper cone）
   • 当 $\mathcal{K} = \mathbb{R}_+^n$ 时，退化为线性规划
   • 当 $\mathcal{K} = S_+^n$ 时，为半正定规划
   • 当 $\mathcal{K}$ 为洛伦兹锥时，为二阶锥规划 (SOCP)

8. 几何规划 (Geometric Programming, GP)

   • 通过变量替换可以转化为凸优化问题
   • 原始形式不是凸的，但可以通过对数变换转化为凸问题

9. 最小二乘问题 (Least Squares)

   $$\min_x \quad \|Ax - b\|_2^2$$

   • 无约束二次优化问题
   • 当 $A$ 列满秩时，有解析解 $x^* = (A^T A)^{-1} A^T b$

10. 带约束的最小二乘

$$\begin{align*} \min_x \quad & \|Ax - b\|_2^2 \\ \text{s.t.} \quad & Cx = d \\ & \|x\|_2 \leq R \end{align*}$$

• 约束可以是等式约束或范数约束

# 平方和

平方和（Sum of Squares, SOS）优化是凸优化中的一个重要主题，与正多项式和半正定规划密切相关。

1. Hilbert's 17th Problem

   • 问题：一个在 $\mathbb{R}^n$ 上非负的多项式是否总能表示为有理函数的平方和？
   • 答案：对于多项式，不一定能表示为多项式的平方和，但可以表示为有理函数的平方和
   • 对于矩阵情况，有类似的结论

2. 平方和多项式 (Sum of Squares Polynomials)

   • 一个多项式 $p(x)$ 是平方和多项式，如果存在多项式 $q_i(x)$ 使得

     $$p(x) = \sum_{i=1}^k q_i^2(x)$$

   • 平方和多项式一定是非负的（$p(x) \geq 0$ 对所有 $x$）
   • 但非负多项式不一定是平方和多项式（反例由 Motzkin 给出）

3. 平方和与半正定规划的关系

   • 判断一个多项式是否为平方和可以转化为半正定规划问题
   • 给定多项式 $p(x)$，寻找 Gram 矩阵 $Q \succeq 0$ 使得 $p(x) = z(x)^T Q z(x)$
   • 其中 $z(x)$ 是包含 $x$ 的单项式向量（monomial vector）
   • 这可以表述为线性矩阵不等式（LMI）约束

4. 平方和优化 (SOS Optimization)

   • 优化问题：在平方和约束下优化目标函数
   • 形式：

     $$\begin{align*} \min \quad & c^T x \\ \text{s.t.} \quad & p_i(x) \text{ 是平方和多项式},\quad i=1,\dots, m \end{align*}$$

   • 这类问题可以转化为半正定规划问题求解

# 多目标优化

多目标优化（Multicriterion Optimization）问题同时考虑多个目标函数，需要在多个目标之间进行权衡。

1. 多目标优化问题形式

   $$\begin{align*} \min_x \quad & (f_1(x), f_2(x), \ldots, f_k(x)) \\ \text{s.t.} \quad & f_i(x) \leq 0,\quad i=1,\dots, m \\ & h_j(x) = 0,\quad j=1,\dots, p \end{align*}$$

   • 有 $k$ 个目标函数 $f_1, f_2, \ldots, f_k: \mathbb{R}^n \to \mathbb{R}$
   • 目标函数值构成向量 $(f_1(x), f_2(x), \ldots, f_k(x)) \in \mathbb{R}^k$
   • 通常不存在一个解能同时最小化所有目标函数

2. Pareto 最优解 (Pareto Optimal Solution)

   • 定义：可行解 $x^*$ 是 Pareto 最优的，如果不存在另一个可行解 $x$ 使得
     • $f_i(x) \leq f_i(x^*)$ 对所有 $i=1,\ldots, k$ 成立
     • 且至少存在一个 $j$ 使得 $f_j(x) < f_j(x^*)$
   • 也称为非支配解（non-dominated solution）或有效解（efficient solution）
   • Pareto 最优解集：所有 Pareto 最优解组成的集合，称为 Pareto 前沿（Pareto frontier）

3. 标量化方法 (Scalarization)
   将多目标优化问题转化为单目标优化问题：

   加权和方法 (Weighted Sum Method)

   $$\min_x \quad \sum_{i=1}^k w_i f_i(x)$$

   • 其中 $w_i \geq 0, i=1,\ldots, k$ 且 $\sum_{i=1}^k w_i = 1$（或 $\sum_{i=1}^k w_i > 0$）
   • 当所有 $f_i$ 是凸函数时，加权和也是凸函数
   • 通过改变权重 $w_i$ 可以得到不同的 Pareto 最优解
   • 注意：并非所有 Pareto 最优解都能通过加权和方法得到（特别是非凸情况）

   $\epsilon$-约束方法 ($\epsilon$-Constraint Method)

   $$\begin{align*} \min_x \quad & f_j(x) \\ \text{s.t.} \quad & f_i(x) \leq \epsilon_i,\quad i=1,\ldots, k,\ i \neq j \\ & \text{其他约束} \end{align*}$$

   • 选择一个目标函数作为主目标，其他目标函数作为约束
   • 通过调整 $\epsilon_i$ 可以得到不同的 Pareto 最优解

4. 凸多目标优化

   • 当所有目标函数 $f_i$ 都是凸函数，且约束函数也是凸函数时，称为凸多目标优化问题
   • 对于凸多目标优化，加权和方法可以找到所有 Pareto 最优解
   • Pareto 前沿在目标空间中通常是凸的

# 可微无约束优化问题的最优性条件

对于可微的无约束优化问题，最优性条件基于目标函数的梯度。

1. 无约束优化问题的最优性条件

   考虑无约束优化问题：

   $$\min_x \quad f_0(x)$$

   一阶必要条件（First-Order Necessary Condition）

   • 若 $x^*$ 是局部最优解，且 $f_0$ 在 $x^*$ 处可微，则

     $$\nabla f_0(x^*) = 0$$

   • 满足 $\nabla f_0(x) = 0$ 的点称为驻点（stationary point）或临界点（critical point）
   • 驻点包括：局部最小值、局部最大值、鞍点

   二阶条件（Second-Order Conditions）

   • 二阶必要条件：若 $x^*$ 是局部最优解，且 $f_0$ 在 $x^*$ 处二次可微，则

     $$\nabla f_0(x^*) = 0, \quad \nabla^2 f_0(x^*) \succeq 0$$

   • 二阶充分条件：若 $f_0$ 在 $x^*$ 处二次可微，且

     $$\nabla f_0(x^*) = 0, \quad \nabla^2 f_0(x^*) \succ 0$$

     则 $x^*$ 是严格局部最小值

   凸函数情况

   • 对于凸函数 $f_0$，一阶条件 $\nabla f_0(x^*) = 0$ 是充要条件
   • 即：$x^*$ 是全局最优解 $\iff$ $\nabla f_0(x^*) = 0$ 且 $x^* \in \text{dom}\ f_0$
   • 这是因为凸函数的任意局部最小值都是全局最小值

2. 等式约束优化问题的最优性条件

   考虑等式约束优化问题：

   $$\begin{align*} \min_x \quad & f_0(x) \\ \text{s.t.} \quad & Ax = b \end{align*}$$

   最优性条件

   • $x^*$ 是最优解当且仅当存在拉格朗日乘子向量 $\nu \in \mathbb{R}^p$ 使得

     $$x^* \in \text{dom}\ f_0, \quad Ax^* = b, \quad \nabla f_0(x^*) + A^T \nu = 0$$

   • 这等价于：$\nabla f_0(x^*)$ 属于 $A$ 的行空间（或 $A^T$ 的列空间）
   • 对于凸函数，这也是充要条件

3. 非负象限上的优化问题

   考虑非负约束优化问题：

   $$\begin{align*} \min_x \quad & f_0(x) \\ \text{s.t.} \quad & x \succeq 0 \end{align*}$$

   最优性条件

   • $x^*$ 是最优解当且仅当

     $$x^* \in \text{dom}\ f_0, \quad x^* \succeq 0, \quad \begin{cases} \nabla f_0(x^*)_i \geq 0 & x_i^* = 0 \\ \nabla f_0(x^*)_i = 0 & x_i^* > 0 \end{cases}$$

   • 这称为互补松弛条件（complementary slackness condition）
   • 对于凸函数，这也是充要条件

4. 应用示例

   • 无约束问题：$\min_x \|Ax - b\|_2^2$ 的最优解满足 $A^T A x = A^T b$
   • 等式约束：$\min_x \ c^T x$ s.t. $Ax = b$ 的最优解满足 $c + A^T \nu = 0$ 对某个 $\nu$
   • 非负约束：$\min_x \ c^T x$ s.t. $x \succeq 0$ 的最优解满足 $c \succeq 0$ 且 $c_i x_i = 0$ 对所有 $i$

# 可微有约束优化问题的最优性条件

对于可微的有约束优化问题，最优性条件基于拉格朗日乘子理论和KKT条件。

1. 标准形式的约束优化问题

   $$\begin{align*} \min_x \quad & f_0(x) \\ \text{s.t.} \quad & f_i(x) \leq 0,\quad i=1,\dots, m \\ & h_j(x) = 0,\quad j=1,\dots, p \end{align*}$$

   其中 $f_0, f_i, h_j: \mathbb{R}^n \to \mathbb{R}$ 都是可微函数。

2. 拉格朗日函数 (Lagrangian Function)

   $$L(x, \lambda, \mu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{j=1}^p \mu_j h_j(x)$$

   • $\lambda = [\lambda_1, \ldots, \lambda_m]^T \in \mathbb{R}^m$ 是不等式约束的拉格朗日乘子
   • $\mu = [\mu_1, \ldots, \mu_p]^T \in \mathbb{R}^p$ 是等式约束的拉格朗日乘子

3. KKT 条件 (Karush-Kuhn-Tucker Conditions)

   若 $x^*$ 是局部最优解，且在 $x^*$ 处满足某些约束品性（constraint qualification），则存在拉格朗日乘子 $\lambda^* \in \mathbb{R}^m$ 和 $\mu^* \in \mathbb{R}^p$ 使得以下KKT条件成立：

   稳定性条件（Stationarity Condition）

   $$\nabla_x L(x^*, \lambda^*, \mu^*) = \nabla f_0(x^*) + \sum_{i=1}^m \lambda_i^* \nabla f_i(x^*) + \sum_{j=1}^p \mu_j^* \nabla h_j(x^*) = 0$$

   原问题可行性条件（Primal Feasibility）

   $$f_i(x^*) \leq 0,\quad i=1,\ldots, m; \quad h_j(x^*) = 0,\quad j=1,\ldots, p$$

   对偶可行性条件（Dual Feasibility）

   $$\lambda_i^* \geq 0,\quad i=1,\ldots, m$$

   互补松弛条件（Complementary Slackness）

   $$\lambda_i^* f_i(x^*) = 0,\quad i=1,\ldots, m$$

   满足KKT条件的点 $x^*$ 称为KKT点或KKT解，是局部最优解（充分条件）。

4. 约束品性 (Constraint Qualification)

   约束品性用于保证局部最优解满足KKT条件。常见的约束品性包括：

   线性无关约束品性 (LICQ - Linear Independence Constraint Qualification)

   • 在可行点 $x^*$ 处，所有起作用的约束（active constraints）的梯度线性无关
   • 起作用的不等式约束：$I(x^*) = \{i \mid f_i(x^*) = 0\}$
   • LICQ要求：$\{\nabla f_i(x^*), i \in I(x^*); \nabla h_j(x^*), j=1,\ldots, p\}$ 线性无关

   其他约束品性

   • Mangasarian-Fromovitz约束品性（MFCQ）
   • Slater约束品性（适用于凸优化问题）

   注意：即使不满足约束品性，最优解仍可能满足KKT条件；但若不满足约束品性，最优解不一定满足KKT条件。

5. Fritz John 条件 (Fritz John Conditions)

   若在局部最优解 $x^*$ 处有 $L_O(x^*) = T_O(x^*)$（线性化可行方向锥等于切锥），则存在 $\lambda_0 \geq 0, \lambda \in \mathbb{R}_+^m, \mu \in \mathbb{R}^p$，使得：

   稳定性条件

   $$\lambda_0 \nabla f_0(x^*) + \sum_{i=1}^m \lambda_i \nabla f_i(x^*) + \sum_{j=1}^p \mu_j \nabla h_j(x^*) = 0$$

   原问题可行性条件

   $$f_i(x^*) \leq 0,\ i=1,\ldots, m; \quad h_j(x^*) = 0,\ j=1,\ldots, p$$

   对偶可行性条件

   $$\lambda_i \geq 0,\quad i=1,\ldots, m$$

   互补松弛条件

   $$\lambda_i f_i(x^*) = 0,\quad i=1,\ldots, m$$

   满足上述条件的点称为Fritz John点或Fritz John解。

   与KKT条件的关系

   • 当 $\lambda_0 > 0$ 时，Fritz John条件等价于KKT条件（可归一化使 $\lambda_0 = 1$）
   • 当 $\lambda_0 = 0$ 时，称为异常情况（abnormal case），此时目标函数梯度不参与条件

6. 凸优化问题的KKT条件

   对于凸优化问题（$f_0, f_i$ 凸，$h_j$ 仿射），KKT条件是充要条件：

   • 若 $x^*$ 是可行解且满足KKT条件，则 $x^*$ 是全局最优解
   • 若 $x^*$ 是全局最优解且满足Slater约束品性（存在严格可行点），则存在拉格朗日乘子使得KKT条件成立

7. KKT条件的应用与局限性

   应用

   • 可以验证一个解是否可能为最优解
   • 帮助排除可行域中很多不是最优的解
   • 当不容易验证约束品性时，可以先求出所有KKT解，然后从中比较找出最优解

   局限性

   • 有时局部最优点不一定满足KKT条件（当约束品性不满足时）
   • 有些问题的最优解不是KKT解（如例3.3：$\min_{x^2 \leq 0} x$，最优解 $x=0$ 不满足KKT条件）
   • 有些问题满足KKT条件的解不存在，但存在最优解（如例3.5：$\min_{(x+y-2)^2 \leq 0} -xy$，最优解 $x=y=1$ 但不存在KKT解）

8. 例子

   例1：$\min_{x^2 \leq 0} x$

   • 最优解为 $x=0$，约束起作用
   • 在 $x=0$ 处，$\nabla f_1(x) = 0$，只有一个全零向量，线性相关，不满足LICQ条件
   • 对于任意 $\lambda \geq 0$，$\nabla f_0(x) + \lambda \nabla f_1(x) = 1 + \lambda \cdot 0 = 1 \neq 0$，无法满足KKT条件
   • 因此最优解不是KKT解

   例2：$\min_{x^2 \leq 0} x^2$

   • 最优解为 $x=0$，约束起作用
   • 在 $x=0$ 处，$\nabla f_1(x) = 0$，不满足LICQ条件
   • 但对于任意 $\lambda \geq 0$，$\nabla f_0(x) + \lambda \nabla f_1(x) = 0 + \lambda \cdot 0 = 0$，满足KKT条件
   • 因此虽然不满足LICQ条件，但最优解是KKT解

   例3：$\min_{(x+y-2)^2 \leq 0} -xy$

   • 该题中满足KKT条件的解不存在
   • 但该题存在最优解 $x=y=1$