最优化导论总结

凸集合

1. 仿射，凸集，锥

1. 组合：θ₁x₁+...+θ_kx_k被称为点x₁，...，x_k的...组合当...
   1. 仿射组合： θ₁+...+θ_k = 1
   2. 凸组合：θ₁+...+θ_k = 1；θ₁，...，θ_k > 0
   3. 凸锥组合：θ₁，...，θ_k > 0
2. 包：C ⊆ Rⁿ 中点的所有...组合组成的集合
   1. 仿射包： aff C
   2. 凸包 ：conv C
   3. 锥包：是包含 C 的最小锥
   4. 闭包：cl C
3. 仿射有关：
   1. C 是一个仿射集合且 x₀∈C，则 V = C - x₀ 是一个子空间，即关于加法和数乘是封闭的，经过原点。反之，仿射空间可以表示为一个子空间加上一个偏移。
   2. 仿射维数：C 的仿射维数为其仿射包的维数。
   3. 相对内部 relint C：如果 C ⊆ Rⁿ 的仿射维度小于 n，那么 Rⁿ ≠ Rⁿ 中。C 的相对内部为 Rⁿ 的内部。
   4. 相对边界：cl  relint C

2. 重要的例子

1. 超平面：{ x|a^Tx = b}
   1. 是一个关于 x 的非平凡线性方程的解空间，故是一个仿射集
   2. 可以看作 法线方向 为 a 的超平面，而常数 b 决定这个平面从原点的 偏移。
2. 半空间：{ x|a^Tx ≤ b}
   1. 一个超平面将 Rⁿ 划分为两个半空间。
   2. 是凸的，但不是仿射的。
   3. { x|a^Tx < b} 是半空间 { x|a^Tx ≤ b} 的内部，称为半开空间。
3. 范数有关：设|| · ||是 Rⁿ 中的范数
   1. 范数球：{ x | ||x - x_c|| ≤ r} 以 x_c 为圆心，r 为半径，是凸的。
   2. 范数锥：{ (x,t) | ||x|| ≤ r} ⊆ Rⁿ⁺¹，是凸锥。
4. 多面体：有限个半空间和超平面的交集
   1. 仿射集合，射线，线段，半空间都是多面体，多面体是凸集。
5. 半正定锥：用 Sⁿ 表示对称的 n×n 的矩阵集合，Sⁿ₊ 表示对称半正定矩阵的集合，Sⁿ₊₊ 表示对称正定矩阵的集合。
   1. Sⁿ₊ 是一个凸锥。

3. 保凸运算

1. 交集

2. 仿射函数：函数 f : Rⁿ → R^m 是仿射的，如果它是一个线性函数和一个常数的和，即具有 f (x) = Ax + b 的形式，其中 A ∈ R^n×m，b ∈ R^m。假设 S 包含于 Rⁿ 是凸的，并且 f : Rⁿ → R^m是仿射函数。那么，s 在 f 下的象：f (S) = {f (x)|x ∈ S} 是凸的。

   1. 例子：平移 S + a；伸缩 aS

3. 透视函数：定义 P：Rⁿ⁺¹ → Rⁿ，P(z,t) = z/t 为透视函数，其定义域 dom P = Rⁿ × R₊₊

   1. 例子，例如（2，3，4）经过透视函数后为（2/4，3/4)。

4. 线性分式函数：由透视函数与仿射函数复合而成：f(x) = (Ax + b) / (c^Tx + d) dom f = {x|c^Tx + d > 0}

   1. 可以将仿射函数与透视函数视为特殊的线性分式函数。

   2. 例子： \[ 设 A = \begin{bmatrix}1&2\\3&4\end{bmatrix}, b = \begin{bmatrix}1\\1\end{bmatrix}, c = \begin{bmatrix}1\\2\end{bmatrix}, d = 3, x = \begin{bmatrix}x_1\\x_2\end{bmatrix} \]

      \[ \text{则线性分式函数} y = f(x)=\frac{\begin{bmatrix}1&2\\3&4\end{bmatrix}\begin{bmatrix}x_1\\x_2\end{bmatrix}+\begin{bmatrix}1\\1\end{bmatrix}}{\begin{bmatrix}1&2\end{bmatrix}\begin{bmatrix}x_1\\x_2\end{bmatrix}+3} \]

      \[ \text{所以} y=\begin{bmatrix}\frac{x_1 + 2x_2+1}{x_1 + 2x_2+3}\\\frac{3x_1 + 4x_2+1}{x_1 + 2x_2+3}\end{bmatrix} \]

4. 广义不等式

1. 正常锥：称 K ∈ Rⁿ 为正常锥，如果它满足

   • K 是凸的
   • K 是闭的
   • K 是实的，即具有非空内部
   • K 是尖的，即不包含直线

   正常锥可以定义广义不等式：x ≤_K y ⇔ y - x ∈ K；x <_K y ⇔ y - x ∈ int K

2. 广义不等式的性质：

   • 对于加法保序的
   • 具有传递性
   • 对于非负数乘是保序的
   • 是自反的
   • 是反对称的
   • 对于极限运算是保序的

3. 最小元：对于每个 y ∈ S， 均有 x ≤_K y， 称 x ∈ S 是最小元，最小元唯一。

4. 极小元：如果 y ∈ S， x ≤_K y 推出 y = x 称 x ∈ S 是极小元，极小元可以有多个。

5. 分离与支撑超平面

1. 分离超平面定理：两个不相交凸集 C、D，存在 a ≠ 0 和 b 使得对于所有 x ∈ C 有 a^Tx ≤ b，对于所有 x ∈ D 有 a^Tx ≥ b，超平面 { x|a^Tx = b} 被称为分离超平面。
2. 严格分离，即对于所有 x ∈ C 有 a^Tx < b，对于所有 x ∈ D 有 a^Tx > b：不相交凸集不一定严格分离。
3. 支撑超平面定理：
   1. 设 C ⊆ Rⁿ 而 x₀ 是其边界 bd C 上的一点，即 x₀ ∈ bd C = cl C  int C，如果 a ≠ 0 并且对任意 x ∈ C 满足 a^Tx ≤ a^Tx₀ 那么称超平面 { x|a^Tx = b} 为集合 C 在 x₀ 处的支撑超平面。
   2. 任意非空凸集 C 和 x₀ ∈ bd C，在 x₀ 处存在 C 的支撑超平面。

6. 对偶锥与广义不等式

1. 对偶锥：令 K 为一个锥。集合 K^* = { y | x^Ty ≥ 0, ∀ x ∈ K} 称为 K 的对偶锥，且总是凸的。
2. 对偶锥的性质：
   • K^* 是闭凸锥
   • K₁ ⊆ K₂ 可导出 K^*₁ ⊆ K^*₂
   • 如果 K 有非空内部，则 K^* 是尖的。
   • 如果 K 的闭包是尖的，则 K^* 有非空内部
   • K^** 是 K 的凸包的闭包（如果 K 是闭和凸的，则 K^* = K）
3. 广义不等式的对偶：凸锥 K 是正常锥，可以导出广义不等式 ≤_K。其对偶锥 K^* 也是正常的，也可以导出广义不等式 ≤_K^*,称其为 ≤_K 的对偶。
4. 广义不等式及其对偶的性质：（以下 λ 与 K 中任意两个元素x、y的夹角都小于90°，其可以看作 x 与 y 到 λ 上的投影）
   1. x ≤_K y 当且仅当对于任意 λ ≥_K^* 0 有 λ^Tx ≤ λ^Ty。
   2. x <_K y 当且仅当对于任意 λ ≥_K^* 0 和 λ ≠ 0 有 λ^Tx < λ^Ty。
5. 最小元对偶性质：x 是 S 上关于广义不等式 K 的最小元的充要条件是，对于所有 λ >_K^* 0 ，x 是 z ∈ S 上极小化 λ^Tz 的唯一最优解。(可以理解为 λ^Tz 是 z 到 λ 的投影，只有 z 是 x 的时候 λ^Tz 极小)
   1. 几何上：对于任意λ >_K^* 0，超平面 { y | λ^T(z - x) = 0} 是在 x 处对 S 的一个严格支撑超平面（严格说明只相交于x）
6. 极小元对偶性质： 如果 λ >_K^* 0 ，x 在 z ∈ S 上极小化 λ^Tz ，那么是 x 极小的。逆命题一般不成立：S 上的极小元 x 可以对于任何 λ 都不是 z ∈ S 上极小化 λ^Tz 的解。（需要 S 是凸集才成立，即对于凸集 S 上的任何极小元 x 存在非零的 λ >_K^* 0 是 z ∈ S 上极小化 λ^Tz 的解。）
7. 最小元与极小元的对偶性质的对比：要满足最小元，需要对偶锥中所有的 λ，x 都是在 z ∈ S 上极小化的 λ^Tz，而极小元只需要在一个 λ 上满足 x 是 z ∈ S 上极小化的 λ^Tz。

凸函数

1. 基本性质

1. 一个函数 f: Rⁿ → R 称为凸函数，如果对于任意的 x₁, x₂ ∈ dom f 和 θ ∈ [0, 1]，有以下不等式成立： \[ f(\theta x_1+(1 - \theta)x_2) \leq \theta f(x_1)+(1 - \theta)f(x_2) \]

   1. 将定义中的小于等于改为小于，则定义的为严格凸函数。
   2. 几何意义：函数 f 的图像在任意两点之间的线段位于函数曲线的上方或与函数曲线重合。凸函数的这种性质确保了它们没有局部极小值，任意局部极小点也是全局极小点。

2. 拓展值延伸：将 f(x) 的定义域由原 dom f 扩展到全域，在 dom f 外的函数值定为 +∞。

3. 一阶条件：假设 f 可微（即其梯度 ∇f 在开集 dom f 内处处存在），则函数 f 是凸函数的充要条件是 dom f 是凸集且对于任意 x, y ∈ dom f，下式成立： \[ f(\theta x_1+(1 - \theta)x_2) \leq \theta f(x_1)+(1 - \theta)f(x_2) \]

   1. 将定义中的大于等于改为大于，则定义的为严格凸函数。
   2. 几何意义：这意味着在 f 每个点，函数图像的切线不会超过函数图像本身。

4. 对于二次可微函数，函数 f 是凸的，当且仅当它的 Hessian 矩阵∇²f (x) 是半正定的，即： \[ ∇²f(x) \geq 0 \]

   1. 这表示 Hessian 矩阵的所有特征值都是非负的。
   2. 将定义中的大于等于改为大于，则定义的为严格凸函数。

2. 例子

1. 指数函数：对于任意的a∈R,函数 e^ax在 R 上是凸的。

2. 幂函数：当 a ≥ 1或 a ≤ 0时，x^a  在 R₊₊ 上是凸函数，当 0 ≤ a ≤ 1时，x^a 在 R₊₊ 上是凹函数。

3. 绝对值幂函数：当 p ≥ 1时，函数|x|^p在 R 上是凸函数。

4. 对数函数：函数 log x在 R₊₊ 上是凹函数。

5. 负熵

   1. 定义：负熵 f(x) = xlog(x)，定义域为 R₊₊ 或 R₊，当 x = 0 时定义函数值为0。
   2. 可通过二阶条件证明f^''(x) > 0，所以负熵是严格凸函数。

6. 范数：Rⁿ 上任意范数均为凸函数。（三角不等式可得）

7. 最大值函数：函数 f(x) = max{x₁+...+x_n} 在 Rⁿ 上是凸函数。

8. 二次-线性分式函数：f(x, y) = xⁿ / y，在其定义域为 dom f = R × R₊₊ = {(x, y) ∈ Rⁿ | y > 0}是凸函数。

9. 指数和的函数：函数f(x) = log(∑e^x_i)在 Rⁿ 是凸函数

   1. 这个函数可以看作最大值函数的可微近似.因为

      max{x₁+...+x_n} ≤ f(x) ≤ max{x₁+...+x_n} + log n

10. 几何平均函数：f(x) = （∏x_i)^1/n, 在定义域 dom f = Rⁿ₊₊ 上是凹函数。

11. 对数行列式：f(x) = log det x, 在定义域 dom f = Sⁿ₊₊ 上是凹函数。

3. 有关概念

1. 下水平集

   1. 定义：函数 f:Rⁿ → R 的 α - 下水平集定义为Cα = {x∈dom f|f(x) ≤ α}.
   2. 凸函数的下水平集都是凸集，但下水平集都是凸集的函数不一定是凸函数。例如，函数 f(x) = -e^x在R上不是凸函数(实质上，它是严格凹函数)，但是其所有下水平集均为凸集。
   3. 如果 f 是凹函数，则由 {x∈dom f|f(x) ≥ α} 定义的 α - 上水平集也是凸函数。

2. 上境图 epi f

   1. 定义：函数 f:Rⁿ → R 的图像定义为{(x,f (x))|x∈dom f},它是 Rⁿ⁺¹ 空间的一个子集。函数 f:Rⁿ → R 的上境图定义为： \[ \text{epi } f =\{(x,t)|x\in\text{dom } f,f (x) \leq t\} \] 简单来说，上境图包含了函数图像之上的所有点。

   2. 对应有亚图 hypo ：hypo f = {(x,t)|t <= f (x)} 简单来说，亚图包含了函数图像以下的所有点。

   3. 凸性与上境图的关系：

      1. 凸函数的上境图是凸集，反之，如果一个函数的上境图是凸集，那么这个函数是凸函数。
      2. 凹函数的亚图是凸集，反之如果一个函数的亚图是凸集，那么这个函数是凹函数。

3. Jensen不等式及其扩展

   1. f(θx₁ + (1 - θ)x₂) ≤ θf(x₁) + (1 - θ)f(x₂)
   2. f(θ₁x₁ + ... + θ_kx_k) ≤ θf(x₁) + ... + θ_kf(x_k), S.T. θ₁  + ... + θ_k = 1; θ₁ ，...， θ_k > 0
   3. ...

4, 保凸运算

1. 非负加权求和

2. 复合仿射映射：函数 f:Rⁿ → R，A ∈ R^n×m ，b ∈ R^m ，定义 g R^m → R为： \[ g(x)=f(Ax + b) \]

   1. 若函数 f 是凸函数，则 g 是凸函数；若函数 f 是凹函数，则 g 是凹函数。
   2. 二阶条件可证明

3. 逐点最大：设 f1 (x)，f2 (x)，……，fm (x) 是凸函数，则逐点最大值定义为： \[ f(x)=\max\{f_1(x), f_2(x), \cdots, f_m(x)\} \] 新函数 f (x) 仍然是凸函数。

4. 逐点上确界：设 f (x,y) 是一个关于 x 和 y 的函数，A 是 y 的取值范围，逐点上确界函数 g (x) 定义为： \[ g(x)=\sup_{y\in A} f(x,y) \]

   1. 逐点上确界函数是逐点最大函数的推广,指的是对于每个 x，找到所有函数值的上界。具体来说，固定 x，再根据参数 y 的范围，找到所有对应的函数值 f(x,y) 的上确界 。（前提是 f(x,y) 对x是凸的）

   2. 从上境图的角度理解，一系列函数的逐点上确界对应着这些函数上境图的交集：对于函数 f，g 以及 A， 我们有 \[ \text{epi } g = \prod \text{epi } f(\cdot,y) \] 函数 g 的凸性可以由一系列凸集的交集仍然是凸集得到。

5. 复合：本节给定函数 h：Rⁿ → R 以及 g：Rⁿ → R，定义复合函数 f = h∘g：Rⁿ → R 为 \[ f(x) = h(g(x)), \quad \text{dom } f = \{ x \in \text{dom } g \mid g(x) \in \text{dom } h \} \] 我们考虑当函数 f 保凸或者保凹时，函数 h 和 g 必须满足的条件。

   1. 标量复合：即上面定义中 k = 1 的情况。 h̃ 为函数h的扩展值延伸。

      如果h是凸函数且 h̃ 非减，g 是凸函数，则 f 是凸函数,

      如果h是凸函数且 h̃ 非增，g 是凹函数，则 f 是凸函数,

      如果h是凹函数且 h̃ 非减，g 是凹函数，则 f 是凹函数，

      如果h是凹函数且 h̃ 非增，g 是凸函数，则 f 是凹函数。

      内外凹凸一样，外函数要非减，内外凹凸不一样，外函数要非增，最后复合函数与外函数凹凸性一致。

   2. 矢量复合：即定义中 k ≥ 1 的情况。

      如果 h 是凸函数且在每维分量上 h 非减，g_i 是凸函数，则 f 是凸函数;

      如果 h 是凸函数且在每维分量上 h 非增，g_i 是凹函数，则 f 是凸函数;

      如果 h 是凹函数且在每维分量上 h 非减，g_i 是凹函数，则 f 是凹函数;

      如果 h 是凹函数且在每维分量上 h 非增，g_i 是凸函数，则 f 是凹函数;

6. 最小化：当 f (x,y) 关于 x、y 都是凸函数，C是非空凸集时，有：

   g (x) = inf f (x,y) （y∈C）是凸函数。

   1. 最小化与逐点上确界的区别：最小化的定义中要求 f (x,y) 关于x、y都是凸函数；而逐点上确界仅要求 f (x,y) 关于x是凸函数。

7. 透视函数：给定函数 f:Rⁿ→R，则 f 的透视函数 g: Rⁿ⁺¹→R 定义为： \[ \begin{align*} g(x,t)&=tf\left(\frac{x}{t}\right)& \text{dom }g=\{(x,t)\mid\frac{x}{t}\in\text{dom }f,t > 0\} \end{align*} \]

   1. 几何上，透视函数对应于将低维空间的图形或曲线通过投影的方式拉升到高维空间。（t 是引入的新变量）例如，原来的函数图像在 Rⁿ 中是一条曲线，透视变换后，它会成为在 Rⁿ⁺¹ 中的一张曲面。
   2. 可以通过二阶条件证明。

5. 共轭函数

1. 定义：设函数 f：Rⁿ → R，定义函数 f^*：Rⁿ → R为

   ​ f^* (y) = sup (y^Tx - f(x)) (x 属于 dom f)

   1. f(x) 的共轭函数 f^* (y) 表示过原点以 y 为斜率的直线与 f(x) 差值的最大值。
   2. 如果 f 可微，在满足f' (x) = y 的点 x 处差值最大。
   3. 无论 f 是否是凸函数，f^* 都是凸函数。

2. 例子：

   1. 仿射函数：f (x) = ax + b，

      当且仅当 y = a（常数）时，yx - ax - b 有界，共轭函数 f^* 定义域为单点集 {a}，f^*(a)= -b。

   2. 负对数函数：f (x)= -log x，定义域为 R₊₊。

      当 y ≥ 0 时，函数 xy + log x 无上界；

      当 y < 0 时，在 x = -1/y 处取最大值，dom f^* = { y|y < 0}= -R₊₊，f^*(y) = -log (-y) - 1 (y < 0)。

   3. 指数函数：f (x) = e^x，

      当 y < 0 时，xy - e^x 无界；

      当 y > 0 时，在 x = log y 处取最大值，y = 0 时，f^*(y)=0，dom f^* = R₊，f^*(y)=y log y - y (规定 0 log 0 = 0)。

   4. 负熵函数：f (x)=x log x，定义域为 R₊， (同样规定 0 log 0 = 0)

      对所有 y，xy - x log x 有上界，dom f^* = R，在 x = e^{(y - 1)} 处取最大值，f^*(y) = e^{(y - 1)}。

   5. 反函数：f (x) = 1/x (x∈R₊₊)，

      当 y > 0 时，yx - 1/x 无上界；

      当 y = 0 时，上确界为 0；

      当 y < 0 时，在 x = (-y)^-1/2 处取上确界，f^*(y) = -2 (-y)^1/2，dom f^*= -R₊。

3. 基本性质

   1. Fenchel不等式：由共轭函数定义可知：f(x) + f^*(y) ≥ x^Ty

   2. 凸函数的共轭函数的共轭函数是原函数。

   3. 可微函数 f 的共轭函数亦称为函数 f 的 Legendre 变换：

      设函数 f 如函数且可微，使 y^Tx - f(x) 最大的 x^* 满足 y = ∇f( x^*)，反之也成立。因此，如果 y = ∇f( x^*)，我们有： \[ f^{\ast}(y) = x^{\ast T} \nabla f(x^{\ast}) - f(x^{\ast}) \]

   4. 仿射变换的共轭： \[ g(x) = af(x) + b \quad \longrightarrow \quad g^*(y) = af^*(y^*/a) - b \]

   5. 复合仿射变换的共轭： \[ g(x) = f(Ax + b) \quad \longrightarrow \quad g^{\ast}(y) = f^{\ast}(A^{-T}y) - b^{T}A^{-T}y \]

      1. 以上证明关键步骤：**sup((变量)x - f(x)) = f^*(变量)**

   6. 独立函数的和：如果函数 f(u, v) = f₁(u) + f₂(v)，其中 f₁ 和 f₂ 使凸函数，则：f^*(w, z) = f₁^*(w) + f₂^*(z)

6. 拟凸函数

1. 定义：

   函数 f：Rⁿ → R 被称为拟凸函数 ，如果其定义域及所有的下水平集 S_a = {x ∈ dom f |f (x) ≤ α} 是凸集。

   函数 f 是拟凹函数，如果 -f 是拟凸函数，即每个上水平集 {x ∈ dom f |f (x) ≥ α} 是凸集。

   若某函数既是拟凸函数又是拟凹函数，其为拟线性函数，其定义域和所有水平集{x ∈ dom f |f (x) = α}都是凸集。就是单调函数。

2. 基本性质：

   1. 凸函数是拟凸的：所有凸函数都是拟凸函数。
   2. 局部最小值是全局最小值：对于拟凸函数，如果在某点 x 达到局部最小值，那么它也是全局最小值。
   3. 保凸性：拟凸函数的下水平集是凸的，这一性质使得拟凸函数能够被用于求解某些优化问题。
   4. 变换的 Jensen 不等式：f(θx + (1 - θ)y) ≤ max{f(x), f(y)}。即线段中任意一点的函数值不超过其端点函数值中最大的那个。
   5. 连续函数是拟凸的，则一下至少一个条件成立：
      1. 函数 f 是非减的
      2. 函数 f 是非增的
      3. 存在一点 c ∈ dom f，使得对于 t ≤ c，f 非增，对于 t ≥ c，f 非减，c 可以在全局最小点任取一个。

3. 可微拟凸函数

   1. 一阶条件：对于任意 x₁，x₂，如果 f (x₁) ≤ f (x₂)，则∇f (x₂)ᵀ(x₁ - x₂) ≤ 0

   2. 二阶条件：假设函数 f 二次可微。如果函数 f 是拟凸函数，则对于任意 x ∈ dom f以及任意 y ∈ R ⁿ 有 \[ y^{T}\nabla f(x) = 0 \Rightarrow y^{T}\nabla^{2} f(x)y \geq 0 \] 对于定义在 R 上的拟凸函数，上述条件可以简化为如下条件 \[ f^{\prime}(x) = 0 \Rightarrow f^{\prime\prime}(x) \geq 0 \] 也就是在一阶导为0的点，二阶导必须为正；扩展到高维，即在各个方向上一阶导都为0的点，它的二阶导Hessian 矩阵须为正定的。

4. 保拟凸运算

   1. 非负加权最大：f = max{w₁f₁，...，w_mf_m}
   2. 复合：
      1. 如果函数 g：Rⁿ → R是拟凸函数，且函数h：R → R是非减的，则复合函数 f = h∘g 是拟凸函数。
      2. 和仿射函数或者线性分式函数复合：如果 f 是拟凸函数，则 g(x) = f(Ax + b) 是拟凸函数，且函数 g(x) = (Ax + b)/(c^Tx + d) 是拟凸函数。
   3. 最小化：如果函数 f(x,y) 是 x 和 y 的联合拟凸函数，且 C 是凸集，则函数：g(x) = inf f(x,y) (y ∈ C) 是拟凸函数。

7. 对数-凹函数和对数-凸函数

1. 定义：如果对所有的 x ∈ dom f 有 f(x) > 0 且 log f 是凸函数或者凹函数，则称函数对数凸或者对数凹函数。

   1. 函数是对数凸的，当且仅当 1/f 是对数凹的

2. 对数凸函数性质：

   1. f(θx₁ + (1 - θ)x₂) ≤ f(x₁)^θf(x₂)^{1 - θ}
   2. log f(θx₁ + (1 - θ)x₂) ≤ θ log f(x₁) + (1 - θ) log f(x₂)

3. 例子

   1. 仿射函数：函数 f(x) = a^Tx + b 在{x | a^Tx + b > 0} 上是对数凹函数。
   2. 幂函数：函数 f(x) = x^a 在 R₊₊ 上当 a ≤ 0 是对数凸函数；当 a ≥ 0 时是对数凹函数。
   3. 指数函数：函数 f(x) = e^ax 既是对数凸函数又是对数凹函数。

4. 二次可微的对数-凸/凹函数：设函数 f 二次可微，其中 dom f 是凸集，我们有 \[ \nabla^{2}\log f(x) = \frac{1}{f(x)}\nabla^{2}f(x)-\frac{1}{f(x)^{2}}\nabla f(x)\nabla f(x)^{T} \] 事实上，函数 f 是对数 - 凸函数，当且仅当对任意 x∈dom f，下式成立（二阶条件） \[ f(x)\nabla^{2}f(x) \geq \nabla f(x)\nabla f(x)^{T} \] 函数 f 是对数 - 凹函数，当且仅当对任意 x∈dom f，下式成立（二阶条件） \[ f(x)\nabla^{2}f(x) \leq \nabla f(x)\nabla f(x)^{T} \]

5. 乘积、和、以及积分运算

   1. 对数-凹/对数-凸函数的乘积是对数-凹/对数-凸函数；
   2. 对数-凹函数的和一般不是对数-凹函数；
   3. 对数-凸函数的和仍然是对数-凸函数；
   4. 对数-凹/对数-凸函数的积分是对数-凹/对数-凸函数。

凸优化问题

1. 优化问题

1. 基本术语

   1. 基本形式： \[ \begin{align*} &\text{minimize} & f_0(x)\\ &\text{subject to} & f_i(x) \leq 0, & i = 1,\cdots,m\\ & & h_i(x) = 0, & i = 1,\cdots,p \end{align*} \] 三个部分分布称为：目标函数、不等式约束、等式约束。

      我们称这个形式为优化问题的标准形式

   2. 可行域：对目标和所有约束函数有定义的点的集合。 \[ \mathcal{D} = \bigcap_{i = 0}^{m} \text{dom } f_i \cap \bigcap_{i = 1}^{p} \text{dom } h_i \] 如果 D 为空集，那么原问题的最优解就是 +∞。

      如果最优值 = -∞，则称问题无下界。

   3. ε-次优集

      满足 f₀(x) ≤ p^* + ε (其中 ε > 0， p^*为最优解的函数值)  的可行解 x 称为 ε -次优。所有 ε -次优解的集合称为问题的 ε -次优集。

   4. 极小值，局部最优

      我们称可行解 x 为局部最优，如果存在 R > 0 使得 \[ f_0(x) = \inf \{ f_0(z) \mid f_i(z) \leq 0, \; i = 1,\cdots,m, \\ h_i(z) = 0, \; i = 1,\cdots,p, \; \| z - x \|_2 \leq R \} \] 或换言之 x 是关于 z 的优化问题 \[ \begin{align*} &\text{minimize} & f_0(z)\\ &\text{subject to} & f_i(z) \leq 0, & i = 1,\cdots,m\\ & & h_i(z) = 0, & i = 1,\cdots,p\\ & & \| z - x \|_2 \leq R \end{align*} \]

2. 等价问题

1. 变量变换：就是让 x 和 z 一一映射

2. 目标函数和约束函数的变换

   1. 目标函数：若 φ₀ 单调增，则 f₀(x) 与 φ₀(f₀(x)) 等价。
   2. 不等式约束：若 φ_i 满足 当且仅当 u ≤ 0 时， φ_i (u) ≤ 0 则 f_i(x) 与 φ_i(f_i(x)) 等价。
   3. 等式约束：若 φ_i 满足 当且仅当 u = 0 时， φ_i (u) = 0 则 h_i(x) 与 φ_i(h_i(x)) 等价。

3. 松弛变量：若有不等式约束 f_i(x) ≤ 0，可以引入松弛变量 s_i ≥ 0 使得 f_i(x) + s_i = 0

4. 消除等式约束：就是通过等式约束，解出 x = φ(z) 代入即可。

5. 引入等式约束：消除等式约束的逆过程。

6. 优化部分变量：如果优化参数有多个参数，且对每个参数的约束相互独立，则可先优化部分参数，以下为例子：

   设变量 x∈Rⁿ 被分为 x = (x₁，x₂)，其中 x₁∈Rⁿ¹ x₂∈Rⁿ²，并且 n₁ + n₂ = n。考虑问题 \[ \begin{align*} &\text{minimize} & f_0(x_1,x_2)\\ &\text{subject to} & f_{i_1}(x_1)\leq 0, & i = 1,\cdots,m_1\\ & & f_{i_2}(x_2)\leq 0, & i = 1,\cdots,m_2 \end{align*} \] 其约束相互独立，也就是说每个约束函数只与 x₁ 或 x₂ 相关。我们首先优化 x₂。定义 x₁ 的函数 f₀ 为 \[ \tilde{f}_0(x_1) = \inf \{ f_0(x_1,z) \mid \tilde{f}(z)\leq 0, \; i = 1,\cdots,m_2 \} \] 则问题等价于 \[ \begin{align*} &\text{minimize} & \tilde{f}_0(x_1)\\ &\text{subject to} & f_{i_1}(x_1)\leq 0, & i = 1,\cdots,m_1 \end{align*} \]

7. 上境图问题形式：标准问题的上境图形式为： \[ \begin{align*} &\text{minimize} & t\\ &\text{subject to} & f_0(x)-t\leq 0\\ & & f_i(x)\leq 0, & i = 1,\cdots,m\\ & & h_i(x)= 0, & i = 1,\cdots,p \end{align*} \] 上境图将一个优化问题（即最小化问题）等价地转化为对一个集合的判定。

   几何解释：找到上境图中“最低”一点。

8. 隐式与显式约束：就是改改定义域

3. 凸优化

1. 标准形式： \[ \begin{align*} &\text{minimize} & f_0(x)\\ &\text{subject to} & f_i(x) \leq 0, & i = 1,\cdots,m\\ & & a_i^T x = b_i, & i = 1,\cdots,p \end{align*} \] 和普通优化问题（4.1）相比较，凸优化问题有三个条件：

   1. 目标函数必须是凸的，（如果是拟凸的，则是拟凸优化的标准形式）。
   2. 不等式约束函数必须是凸的。
   3. 等式约束函数 h_i(x) = a_i^Tx - b 必须是仿射的。

2. 性质：

   1. 凸优化问题的可行集是凸的。
   2. 凸优化问题的局部最优解就是全局最优解。

3. 可微目标函数的最优性准则：设凸优化问题的目标函数 f₀  是可微的，对于所有的 x, y ∈ dom f₀ 有 \[ f_0(y) \geq f_0(x)+\nabla f_0(x)^T(y - x) \] 令 X 表示其可行集，即 \[ X = \{ x \mid f_i(x) \leq 0, \; i = 1,\cdots,m, \; h_i(x) = 0, \; i = 1,\cdots,p \} \] 那么，x 是最优解，当且仅当 x ∈ X 且 \[ \nabla f_0(x)^T(y - x) \geq 0, \quad \forall y\in X. \] 几何解释：

   1. 当x点梯度大于0时，y就比x大，所以x处的函数值就比任意y处的函数值小，x是最优解；
   2. 当x点梯度小于0时，y就比x小，所以x处的函数值就比任意y处的函数值小，x是最优解；
   3. 如果 ∇f₀(x) ≠ 0，那么意味着 -∇f₀(x) 在 x 处定义了可行集的一个支撑超平面。

4. 无约束问题：无约束问题中x是最优解的充要条件是：∇f₀(x) = 0。

5. 只含等式约束的问题：用Lagrange乘子法：将约束问题转换为无约束问题，引入Lagrange乘子 v，构造拉格朗日函数： \[ L(x, v) = f_0(x) + v^T(Ax - b) \] 然后通过求解拉格朗日函数梯度为 0 的条件，得到优化条件。

   例子： \[ \begin{align*} &求解凸优化问题\\ &\quad \min_{x} \quad x^2\\ &\quad \text{s.t.} \quad Ax - b=0\\ &\quad 其中A是m\times n矩阵，b是m维向量。\\ &1. 构造Lagrange函数\\ &\qquad L(x,\lambda)=x^2+\lambda^T(Ax - b)\\ &2. 求偏导数并令其为0\\ &\qquad \nabla_x L(x,\lambda)=2x+A^T\lambda = 0，可得x=-\frac{1}{2}A^T\lambda\\ &\qquad \nabla_{\lambda} L(x,\lambda)=Ax - b = 0，将x=-\frac{1}{2}A^T\lambda代入可得：\\ &\qquad A(-\frac{1}{2}A^T\lambda)-b = 0\\ &\qquad 解出\lambda，再代入x=-\frac{1}{2}A^T\lambda得到最优解x^*。\\ \end{align*} \]

6. 非负象限中的极小化：凸函数在非负象限中的极小化由两种情况

   1. 最优解x处的梯度为0，
   2. 最优解x处的梯度 ∇f₀(x) 不为0时，∇f₀(x) > 0且 x=0。

4. 拟凸优化

1. 最优解条件 \[ x \in X, \quad \nabla f_0(x)^T(y - x)>0, \quad \forall y \in X \backslash \{x\} \] 这个条件表示：在 x 处的梯度方向不会使 f(x) 减小。

   与凸优化问题的不同

   1. 但这个条件为拟凸优化问题的最优性的充分条件
   2. 要求 ∇f₀(x) 非 0

2. 解决拟凸优化问题的方法

   1. 凸可行性问题： \[ \begin{align*} &\quad\text{find } \quad\quad\quad\quad x \\ &\text{ subject to } \quad \phi_t(x) \leq 0,\\ &\quad\quad\qquad\qquad f_i(x) \leq 0,\\ &\quad\quad\qquad\qquad Ax = b \end{align*} \] 其中，φ_t(x) 是拟凸函数 f(x) 的水平集。f₀(x) ≤ t ⇔ φ_t(x) ≤ 0

   2. 判断可行性问题的解：

      • 若可行，则表明拟凸优化问题的最优值p^* ≤ t；
      • 若不可行，则说明p^* ≥ t。

   3. 使用二分法来调整t的值，不断缩小包含最优解的区间，从而得到拟凸优化问题的近似最优解。

5. 线性规划问题

1. 定义：当目标函数和约束函数都是仿射时，问题称作线性规划（LP）。一般的线性规划具有以下形式： \[ \begin{align*} \text{minimize}\quad & c^T x + d \\ \text{subject to} \quad & Gx \leq h \\ & Ax = b \end{align*} \] 其中 G ∈ R^m×n, A ∈ R^p×n。线性规划是凸优化问题。（d 常省略）

2. 标准形式与不等式形式

   1. 标准形式：在标准形式线性规划中仅有的不等式都是分量的非负约束 x ≥ 0： \[ \begin{align*} \text{minimize}\quad & c^T x \\ \text{subject to}\quad & Ax = b \\ & x \geq 0 \end{align*} \]

   2. 不等式形式：如果线性规划问题没有等式约束，则称为不等式形式线性规划，常写作： \[ \begin{align*} \text{minimize} \quad & c^T x \\ \text{subject to} \quad & Ax \leq b \end{align*} \]

3. 将线性规划转换为标准形式：将一般的线性规划形式转化为标准的线性规划形式

   1. 第一步是为不等式引入松弛变量 s_i，得到 \[ \begin{align*} \text{minimize} \quad & c^T x + d \\ \text{subject to} \quad & Gx + s = h \\ & Ax = b \\ & s \geq 0 \end{align*} \]

   2. 第二步是将变量 x 表示为两个非负变量 x⁺ 和 x^- 的差，即 x = x⁺ - x^- ，其中 x⁺ > 0 、 x^- > 0，从而得到问题 \[ \begin{align*} \text{minimize} \quad & c^T x^+ - c^T x^- + d \\ \text{subject to} \quad & Gx^+ - Gx^- + s = h \\ & Ax^+ - Ax^- = b \\ & x^+ \geq 0, \quad x^- \geq 0, \quad s \geq 0 \end{align*} \] 这是标准形式的线性规划，其优化变量是 x⁺、x^- 和 s 。

6. 线性分式规划

1. 定义：在多面体上极小化仿射函数之比的问题称为线性分式规划： \[ \begin{align*} \text{minimize} \quad & f_0(x) \\ \text{subject to} \quad & Gx \succeq h \\ & Ax = b \end{align*} \] 其目标函数由 \[ f_0(x) = \frac{c^T x + d}{e^T x + f}, \quad \text{dom} f_0 = \{x \mid e^T x + f > 0\} \] 给出。这个目标函数是拟凸的（事实上是拟线性的），因此线性分式规划是一个拟凸优化问题。

2. 转化为线性规划：如果可行集 \[ \{x \mid Gx \preceq h, Ax = b, e^T x + f > 0\} \] 非空，线性分式规划可以转换为等价的线性规划 \[ \begin{align*} \text{minimize} \quad & c^T y + dz \\ \text{subject to} \quad & Gy - hz \preceq 0 \\ & Ay - bz = 0 \\ & e^T y + fz = 1 \\ & z \geq 0 \end{align*} \] 其优化变量为 y，z。

   为显示这个等价性，我们首先说明如果 x 是线性分式规划的可行解，那么 \[ y = \frac{x}{e^T x + f}, \quad z = \frac{1}{e^T x + f}，\quad x = \frac{y}{z} \] 是线性规划的可行解，且具有相同的目标函数值 c^Ty + dz = f₀(x)。

7. 二次优化问题

1. 定义：当凸优化问题的目标函数是(凸)二次型并且约束函数为仿射时，该问题称为二次规划（QP）。二次规划可以表述为 \[ \begin{align*} \text{minimize} \quad & (1/2)x^T P x + q^T x + r \\ \text{subject to} \quad & Gx \preceq h \\ & Ax = b \end{align*} \] 本质是在二次规划问题中，在多面体上极小化一个凸二次函数。

   如果不仅目标函数，其不等式约束也是(凸)二次型，该问题称为二次约束二次规划（QCQP）。二次约束二次规划可以表述为 \[ \begin{align*} \underset{x}{\text{minimize}} \quad & (1/2)x^T P_0 x + q_0^T x + r_0 \\ \text{subject to} \quad & (1/2)x^T P_i x + q_i^T x + r_i \leq 0, \quad i = 1, \ldots, m \\ & Ax = b \end{align*} \] 本质是在椭圆的交集构成的可行集上极小化凸二次函数。

8. 几何规划

几何规划的自然形式并不是凸的。但通过变量替换或目标函数、约束函数的变换，可以将它们转换为凸优化问题。

1. 单项式与正项式

   1. 单项式定义：函数 f：Rⁿ → R，dom f = Rⁿ₊₊ 定义为 \[ f(x) = c x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n}, \quad c > 0, \quad a_i \in \mathbb{R} \] 它被称为单项式函数或简称为单项式。单项式的指数 a_i 可以是任意实数，包括分数或负数，但系数 c 必须非负。

   2. 正项式定义:单项式的和是正项式函数（或简称为正项式）： \[ f(x) = \sum_{k = 1}^{K} c_k x_1^{a_{1k}} x_2^{a_{2k}} \cdots x_n^{a_{nk}}, \quad c_k > 0 \]

2. 几何规划（GP）形式： \[ \begin{align*} \text{minimize} \quad & f_0(x) \\ \text{subject to} \quad & f_i(x) \leq 1, \quad i = 1, \ldots, m \\ & h_i(x) = 1, \quad i = 1, \ldots, p \end{align*} \] 被称为几何规划（GP）其中 f₀，...，f_m 为正项式，h₁，...，h_p 为单项式，这个问题定义域为 D = Rⁿ₊₊， 约束 x ＞ 0 式隐式的。

3. 几何规划转换为凸优化

   几何规划(一般)不是凸优化问题，但是通过变量代换以及目标、约束函数的转换，它们可以被转换为凸问题。本质是优化问题的等价变换：变量变换+复合变换。

   1. 单项式转换方法：我们用 y_i = log x_i 定义变量，因此 x_i = e^y_i 。

      如果 f 是 x 的单项式函数，即： \[ f(x) = c x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n} \] 那么 \[ \begin{align*} f(x) &= f(e^{y_1}, \ldots, e^{y_n}) \\ &= c (e^{y_1})^{a_1} \cdots (e^{y_n})^{a_n} \\ &= e^{a^T y + b} \end{align*} \] 其中 b = log c，变量变换 y_i = log x_i ，将一个单项式函数转换为以仿射函数为指数的函数。

   2. 正项式转换方法：类似的，如果 f 是正项式，即 \[ f(x) = \sum_{k = 1}^{K} c_k x_1^{a_{1k}} x_2^{a_{2k}} \cdots x_n^{a_{nk}} \] 于是 \[ f(x) = \sum_{k = 1}^{K} e^{a_k^T y + b_k} \] 其中a_k = (a_1k，...，a_2k) b_k = log c_k，变量变换 y_i = log x_i ，将正项式函数转换为以仿射函数为指数的函数的和。

   3. 几何规划问题的转换

      几何规划用新变量 y 表示： \[ \begin{align*} \text{minimize} \quad & \sum_{k = 1}^{K_0} e^{a_{0k}^T y + b_{0k}} \\ \text{subject to} \quad & \sum_{k = 1}^{K_i} e^{a_{ik}^T y + b_{ik}} \leq 1, \quad i = 1, \ldots, m \\ & \sum_{k = 1}^{K_i} e^{a_{ik}^T y + b_{ik}} = 1, \quad i = 1, \ldots, p \end{align*} \] 其中 a^ik ∈Rⁿ，i = 0，...，m，包含了以正项式为指数的不等式约束，g_i ∈Rⁿ，i = 0，...，p，包含了原几何规划中以单项式为指数的等式约束。

      采用对数函数将目标函数和约束函数进行转换，得到问题： \[ \begin{align*} \text{minimize} \quad & \tilde{f}_0(y) = \log \left(\sum_{k = 1}^{K_0} e^{a_{0k}^T y + b_{0k}}\right) \\ \text{subject to} \quad & \tilde{f}_i(y) = \log \left(\sum_{k = 1}^{K_i} e^{a_{ik}^T y + b_{ik}}\right) \leq 0, \quad i = 1, \ldots, m \\ & \tilde{h}_i(y) = g_i^T y + h_{i0} = 0, \quad i = 1, \ldots, p \end{align*} \] 因为函数 f_i 是凸的 h_i 是仿射的，所以该问题是一个凸优化问题。我们称其为凸形式的几何规划。为将其与原始的几何规划相区别，我们称原本的含正项式的为正项式形式的几何规划。

对偶

1. Language 函数

1. Language：考虑标准形式的优化问题： \[ \begin{align*} &\text{minimize} & f_0(x)\\ &\text{subject to} & f_i(x) \leq 0, & i = 1,\cdots,m\\ & & h_i(x) = 0, & i = 1,\cdots,p \end{align*} \] 这里没有假设问题是凸优化问题。

   其Language函数定义为： \[ L(x, \lambda, \nu) = f_0(x) + \sum_{i = 1}^{m} \lambda_i f_i(x) + \sum_{i = 1}^{p} \nu_i h_i(x) \] λ_i 称为第 i 个不等式约束 f_i(x) ≤ 0 对应的 Language乘子，v_i 称为第 i 个不等式约束 h_i(x) = 0 对应的 Language乘子。向量 λ 和 v 称为对偶变量或者是问题的 Language乘子向量

   拉格朗日函数的目标是通过引入乘数将约束 “惩罚” 融入到目标函数中。具体来说，λ 和 v 为调整各约束 “惩罚” 权重的因子：

   • 当约束 f_i(x) ≤ 0 被破坏（即 f_i(x) ≥ 0）时，对应的项 λ_if_i(x) 对函数值产生负面影响。
   • 当约束 h_i(x) = 0 不成立（即 h_i(x) ≠ 0）时，项 v_ih_i(x) 亦产生偏移。

2. Language 对偶函数

1. 定义：为 Language 函数关于 x 取得的最小值 \[ g(\lambda, \nu) = \inf_{x \in D} L(x, \lambda, \nu) = \inf_{x \in D} \left( f_0(x) + \sum_{i = 1}^{m} \lambda_i f_i(x) + \sum_{i = 1}^{p} \nu_i h_i(x) \right) \] 如果 Language 函数关于 x 无下界，则对偶函数取值为 -∞。因为对偶函数是一族关于 (λ , v) 的仿射函数的逐点下确界，所以即使原问题不是凸的，对偶函数也是凸函数。

2. 最优值的下界：对偶函数构成了原问题最优值 p^* 的下界:即对任意 λ ≥ 0和 v 下式成立: \[ g(\lambda, \nu) \leq p^* \] 设 x 是原问题一个可行解，即 f_i(x) ≤ 0 且 h_i(x) = 0 根据假设，λ_i ≥ 0，我们有： \[ \sum_{i = 1}^{m} \lambda_i f_i(x) + \sum_{i = 1}^{p} \nu_i h_i(x) \leq 0 \] 称满足 λ ≥ 0 以及 (λ , v) ∈ dom g 即 g (λ , v) > -∞ 的 (λ , v) 是对偶可行的。

3. Lagrange对偶函数和共轭函数

   回忆共轭函数定义： \[ f^*(y) = \sup_{x \in \text{dom} f} (y^T x - f(x)) \] 考虑一个优化问题，具有线性不等式和等式约束： \[ \begin{align*} \text{minimize} \quad & f_0(x) \\ \text{subject to} \quad & Ax \preceq b \\ & Cx = d \end{align*} \] 利用函数 f₀ 的共轭函数，我们可以将问题的对偶函数表述为 \[ \begin{align*} g(\lambda, \nu) &= \inf_{x} \left( f_0(x) + \lambda^T (Ax - b) + \nu^T (Cx - d) \right) \\ &= -b^T \lambda - d^T \nu + \inf_{x} \left( f_0(x) + (A^T \lambda + C^T \nu)^T x \right) \\ &= -b^T \lambda - d^T \nu - f_0^*(-A^T \lambda - C^T \nu) \end{align*} \] 函数 g 的定义域也可以由 f₀^* 的定义域得到： \[ \text{dom } g = \{ (\lambda, \nu) \mid -A^T \lambda - C^T \nu \in \text{dom } f_0^* \} \]

3. Lagrange对偶问题

1. 定义：Lagrange 对偶函数给出了优化问题的最优值 p*的一个下界。那么Lagrange 对偶函数的最大值就是原问题的最好下界。

   所以Lagrange 对偶问题为： \[ \begin{align*} \text{maximize} \quad & g(\lambda, \nu) \\ \text{subject to} \quad & \lambda \succeq 0 \end{align*} \] 对偶可行的 (λ , v) 是对偶问题的一个可行解。称最优解为对偶最优解或者最优 Language 乘子。

2. 标准形式线性规划的Language对偶

   标准形式线性规划 \[ \begin{align*} \text{minimize} \quad & c^T x \\ \text{subject to} \quad & Ax = b \\ & x \geq 0 \end{align*} \] 的 Lagrange 对偶函数为 \[ g(\lambda, \nu) = \begin{cases} - b^T \nu & A^T \nu - \lambda + c = 0 \\ -\infty & \text{其他情况} \end{cases} \] 所以对偶问题为 \[ \begin{align*} \text{maximize} \quad & g(\lambda, \nu) = \begin{cases} - b^T \nu & A^T \nu - \lambda + c = 0 \\ -\infty & \text{其他情况} \end{cases}\\ \text{subject to} \quad & \lambda \geq 0 \end{align*} \] 该问题等式约束条件为隐式的，写成显示表达对偶约束为： \[ \begin{align*} \text{maximize} \quad & - b^T \nu \\ \text{subject to} \quad & A^T \nu - \lambda + c = 0 \\ & \lambda \geq 0 \end{align*} \] 可进一步简化为 \[ \begin{align*} \text{maximize} \quad & - b^T \nu \\ \text{subject to} \quad & A^T \nu + c \geq 0 \end{align*} \]

3. 不等式形式线性规划的 Lagrange 对偶

   不等式形式的线性规划问题 \[ \begin{align*} \underset{x}{\text{minimize}} \quad & c^T x \\ \text{subject to} \quad & Ax \leq b \end{align*} \] Lagrange函数为 \[ L(x, \lambda) = c^T x + \lambda^T (Ax - b) = -b^T \lambda+(A^T \lambda + c)^T x, \] 对偶函数为 \[ g(\lambda)=\inf_{x} L(x, \lambda)=-b^T \lambda+\inf_{x}(A^T \lambda + c)^T x. \] 若线性函数不是恒值，则线性函数的下确界是 -∞，因此上述问题的对偶函数为 \[ g(\lambda) = \begin{cases} - b^T \lambda & A^T \lambda + c = 0 \\ -\infty & \text{其他情况} \end{cases} \] 显式表达对偶可行的条件并作为约束来重新描述对偶问题： \[ \begin{align*} {\text{maximize}} \quad & -b^T \lambda \\ \text{subject to} \quad & A^T \lambda + c = 0 \\ & \lambda \geq 0, \end{align*} \] 我们注意到标准形式线性规划和不等式形式线性规划以及它们的对偶问题之间的有趣的对称性，标准形式线性规划的对偶问题是只含有不等式约束的线性规划问题，反之亦然。

4. 对偶性

1. 弱对偶性：Language 对偶问题的最优值，我们用 d^* 表示，根据定义，这是通过 Language 函数得到原问题最优值 p^* 的最好下界。特别的，我们有下面简单但是非常重要的不等式 \[ d^* \leq p^* \] 即使原问题不是凸问题，上述不等式亦成立。这个性质被称为弱对偶性。

   定义差值 p^* - d^* 是原问题的最优对偶间隙。

2. 强对偶性：如果等式 d^* = p^* 成立，即最优对偶间隙为零，那么强对偶性成立。这说明从 Language 对偶函数得到的最好下界是紧的。

3. Slater 约束准则：一般强对偶性不成立，但是，如果目标函数是凸函数，不等式约束函数是凸函数，等式约束函数是仿射函数，即 \[ \begin{align*} &\text{minimize} & f_0(x)\\ &\text{subject to} & f_i(x) \leq 0, & i = 1,\cdots,m\\ & & a_i^T x = b_i, & i = 1,\cdots,p \end{align*} \] 除此之外还需要满足一些强对偶性条件，这些条件称为约束准则。

   1. 一个简单的约束准则是 Slater 约束准则：存在一点 x ∈ relint D 使得式 f_i(x) < 0 成立，即不等式约束严格成立。
   2. 弱化的Slater约束准则：简言之，当约束函数 f_i 是仿射函数时，不等式约束不需要严格成立，但当约束函数 f_i 不是仿射函数时，不等式约束需要严格成立。称为弱化的Slater约束准则。

5. 几何解释

6. 鞍点解释

1. 定义：我们称 w̃ ∈ W，z̃ ∈ Z 是函数 f（以及 W 和 Z）的鞍点，如果对于任意 w ∈ W，z ∈ Z 下式成立 \[ f(\overline w, z) \leq f(\overline w,\overline z) \leq f(w,\overline z) \] 换言之，f(w, z̃) 在 w̃ 处取得最小值（关于变量 w ∈ W），f(w̃, z) 在 z̃ 处取得最大值（关于变量 z ∈ Z）： \[ f(\tilde{w}, \hat{z}) = \inf_{w \in W} f(w, \hat{z})\quad f(\tilde{w}, \hat{z}) = \sup_{z \in Z} f(\tilde{w}, z) \] 上式意味着强极大极小性质成立 \[ \sup_{z \in Z} \inf_{w \in W} f(w, z) = \inf_{w \in W} \sup_{z \in Z} f(w, z) \] 且共同值为 f(w̃, z̃)。

2. 关于 Language 对偶：如果 x* 和 λ* 是原问题和对偶问题的最优点，且强对偶性成立，则它们是 Language 函数的一个鞍点。反之亦然。

7. 最优性条件

1. 互补松弛性：如果强对偶性成立，在原问题最优点 x* 处有 \[ \sum_{i = 1}^{m} \lambda_i^* f_i(x^*) = 0. \] 事实上，求和项的每一项都非正，因此有 \[ \lambda_i^* f_i(x^*) = 0. \quad i = 1,\cdots,m \] 上述条件称为互补松弛性：它对任意原问题最优解 x*以及对偶问题最优解( λ* , v*) 成立（当强对偶性成立时）。我们也可以将其写成 \[ \lambda_i^* > 0 \quad \Rightarrow \quad f_i(x^*) = 0, \] 或 \[ f_i(x^*) < 0 \quad \Rightarrow \quad \lambda_i^* = 0. \] 上式意味着在最优点处，除了第 i 个约束起作用的情况，最优 Language 乘子的第 i 项都为零。

2. KKT最优性条件

   1. 非凸问题的KKT条件：和前面一样，令 x* 和 ( λ* , v*) 分别是原问题和对偶问题的某对最优解，对偶间隙为零。因为 L( x*, λ* , v*) 关于 x 求极小在 x* 处取得最小值，因此函数在 x* 处的导数必须为零，即 \[ \nabla f_0(x^*) + \sum_{i = 1}^{m} \lambda_i^* \nabla f_i(x^*) + \sum_{i = 1}^{p} \nu_i^* \nabla h_i(x^*) = 0 \] 因此，我们有 \[ \begin{align*} f_i(x^*) &\leq 0, \quad i = 1, \ldots, m \\ h_i(x^*) &= 0, \quad i = 1, \ldots, p \\ \lambda_i^* &\geq 0, \quad i = 1, \ldots, m \\ \lambda_i^* f_i(x^*) &= 0, \quad i = 1, \ldots, m \quad(互补松弛性) \\ &\nabla f_0(x^*) + \sum_{i = 1}^{m} \lambda_i^* \nabla f_i(x^*) + \sum_{i = 1}^{p} \nu_i^* \nabla h_i(x^*) = 0 \end{align*} \] 我们称上式为Karush - Kuhn - Tucker (KKT)条件。 总之，如果强对偶性成立，那么任意一对原问题和对偶问题的最优解必须满足 KKT 条件。

   2. 凸问题的KKT条件：满足KKT条件的点一定是原问题和对偶问题的最优解。 （而在非凸问题中，KKT条件只是必要条件）

数学知识

1. 范数

1. 范数具有如下性质： \[ \begin{align*} & 1. \|x\| \geq 0，且 \|x\| = 0 的充分必要条件是 x = 0；\\& 2. \|\lambda x\| = |\lambda| \cdot \|x\|（对于任意 \lambda \in \mathbb{R}）；\\& 3. \|x + y\| \leq \|x\| + \|y\|（三角不等式），\\& 以及 Cauchy - Schwarz 不等式 \\& |\langle x,y\rangle| \leq \|x\| \cdot \|y\|， 且等号成立的充分必要条件是：x 与 y 共线，即存在 \lambda，使得 x = \lambda y。\\& 将不等式写成分量形式为：\\& \left|\sum_{i = 1}^{n} x_i y_i\right| \leq \left(\sum_{i = 1}^{n} x_i^2\right)^{\frac{1}{2}} \left(\sum_{i = 1}^{n} y_i^2\right)^{\frac{1}{2}}\\& \end{align*} \]

2. 常见的范数：

   1. P - 范数： \[ \|x\|_p = \left(\sum_{i = 1}^{n} |x_i|^p\right)^{\frac{1}{p}} \quad (1 \leq p < \infty)\\ \]

   2. 1 - 范数： \[ \|x\|_p = \sum_{i = 1}^{n} |x_i|\\ \]

   3. 2 - 范数： \[ \|x\|_2 = \left(\sum_{i = 1}^{n} x_i^2\right)^{\frac{1}{2}}\\ \]

   4. ∞ - 范数：

   \[ \|x\|_{\infty} = \max_{1 \leq i \leq n} |x_i| \]

3. 对偶范数：定义如下 \[ \| y \|_* = \sup_{\| x \| \leq 1} y^T x \]

   1. 1 - 范数的对偶范数是 ∞ - 范数
   2. 2 - 范数的对偶范数是 2 - 范数
   3. ∞ - 范数的对偶范数是 1 - 范数

题目总结

1. 将问题转换为线性规划

1. \[ \begin{align*} \min_{X\in\mathbb{R}^n}\|AX - b\|_1&=\min_{X\in\mathbb{R}^n}\sum_{i = 1}^{n}|AX_i - b| =\min_{\substack{X\in\mathbb{R}^n\\z\in\mathbb{R}^n}}\sum_{i = 1}^{n}z_i\\ \text{subject to}&\quad -z\leq AX - b\leq z \end{align*} \]

2. \[ \left\| x \right\|_{\infty} \leq 1 \Rightarrow - 1 \leq x \leq 1 \]

3. \[ \begin{align*} \min_{X\in\mathbb{R}^n}\|X\|_{\infty}=\min_{X\in\mathbb{R}^n}\max_{(i)}\left(|x_i|\right)=\min_{\substack{\\t\in\mathbb{R_+}}}\sum_{i = 1}^{n}t\\ \text{subject to} \quad -t\mathbf{1} \leq X \leq t\mathbf{1} \end{align*} \]

4. \[ \begin{align*} \min_{X\in\mathbb{R}^n}\sum_{i = 1}^{m}\max\{0,a_i^T x + b_i\}\ =\min_{\substack{X\in\mathbb{R}^n\\z\in\mathbb{R_+}^n}}\sum_{i = 1}^{m}z_i\\ \text{subject to}\quad z_i\geq a_i^T x + b_i \end{align*} \]

2. 验证是凸集

1. 验证 λx₁ + (1-λ)x₂ ∈ S

3. 验证是凸函数

1. Hesse矩阵 \[ H(f)=\begin{pmatrix} \frac{\partial^{2}f}{\partial x_{1}^{2}}&\frac{\partial^{2}f}{\partial x_{1}\partial x_{2}}&\cdots&\frac{\partial^{2}f}{\partial x_{1}\partial x_{n}}\\ \frac{\partial^{2}f}{\partial x_{2}\partial x_{1}}&\frac{\partial^{2}f}{\partial x_{2}^{2}}&\cdots&\frac{\partial^{2}f}{\partial x_{2}\partial x_{n}}\\ \vdots&\vdots&\ddots&\vdots\\ \frac{\partial^{2}f}{\partial x_{n}\partial x_{1}}&\frac{\partial^{2}f}{\partial x_{n}\partial x_{2}}&\cdots&\frac{\partial^{2}f}{\partial x_{n}^{2}} \end{pmatrix} \] 证明 H(f) 是半正定的即可验证是凸函数（二阶条件）

   1. 计算 Hesse 矩阵的 H(f) 特征值。对于矩阵A，其特征值 λ 满足 det(A - λI) = 0，其中 I 是单位矩阵。如果所有特征值λ_i ≥ 0，则 H(f) 矩阵是半正定的，函数是 f 凸函数。
   2. 定义法：证明对于任意非零向量 x，x^TAx ≥ 0。

4. Jensen 不等式的证明

1. 数学归纳法：从 m 到 m+1 的关键步骤： \[ \begin{align*} & f(\lambda_1 x^{(1)} + \lambda_2 x^{(2)} + \cdots + \lambda_m x^{(m)} + \lambda_{m + 1} x^{(m + 1)}) \\ & = f\left( \sum_{i = 1}^{m} \lambda_i \left( \frac{\lambda_1}{\sum_{i = 1}^{m} \lambda_i} x^{(1)} + \frac{\lambda_2}{\sum_{i = 1}^{m} \lambda_i} x^{(2)} + \cdots + \frac{\lambda_m}{\sum_{i = 1}^{m} \lambda_i} x^{(m)} \right) + \lambda_{m + 1} x^{(m + 1)} \right) \end{align*} \] 记 \[ \hat{x} = \sum_{i = 1}^{m} \frac{\lambda_1}{\sum_{i = 1}^{m} \lambda_i} x^{(1)} + \sum_{i = 1}^{m} \frac{\lambda_2}{\sum_{i = 1}^{m} \lambda_i} x^{(2)} + \cdots + \sum_{i = 1}^{m} \frac{\lambda_m}{\sum_{i = 1}^{m} \lambda_i} x^{(m)} \] 再利用凸函数的定义即可解决。

5. 求共轭函数

1. 建立共轭函数表达式，分情况讨论（一般根据 y 值）。下给例题：

   1. 这一题根据 y 分类。 \[ \begin{flalign} &求下列函数的共轭函数：最大值函数：f(x)=\max x_{i}。 \\&若\|y\|_{1} \leq 1且y \geq 0，则y与x内积时不会改变x分量的符号，且一定成立 y^{T} x \leq \max x_{i}, 故此时f^{*}(y)=0。 \\&若不然，则或有\|y\|_{1}>1。不妨设j=\arg \max x_{i}且y_{j}=1+\delta(\delta>0且 其他坐标取0)，那么 \\& \qquad f^{*}(y)=\sup \left\{y^{T} x - x_{j}\right\} \\& \qquad =\sup \left\{\delta x_{j}\right\} \\& \qquad \rightarrow \infty。 \\&又或存在i使得y_{i}<0，类似可证f^{*}(y)不存在。 \\&综上，f^{*}(y)=0，定义域是\left\{y \in \mathbb{R}^{n} | y \geq 0,\|y\|_{1} \leq 1\right\}。 \end{flalign} \]

   2. 这题既有 y 分类，也有 x 分类，注意最后结论需要考虑 x 所有取值。 \[ \begin{flalign} &对于f(x) = |x|： \\&当x\geqslant0时，f^*(y)=\sup_{x\geqslant0}(xy - x)=\sup_{x\geqslant0}x(y - 1)。 \\& \quad 如果y>1，则当x\to+\infty时，x(y - 1)\to+\infty，所以f^*(y)=+\infty。 \\& \quad 如果y\leqslant1，则x(y - 1)\leqslant0，上确界为0。 \\&当x<0时，f^*(y)=\sup_{x<0}(xy + x)=\sup_{x<0}x(y + 1)。 \\& \quad 如果y< - 1，则当x\to-\infty时，x(y + 1)\to+\infty，所以f^*(y)=+\infty。 \\& \quad 如果y\geqslant - 1，则x(y + 1)\leqslant0，上确界为0。 \\&综合起来，f^*(y)=\left\{\begin{matrix}0, &|y|\leqslant1\\ +\infty, &|y|>1\end{matrix}\right. \end{flalign} \]

2. 求导方式求sup(y^Tx - f(x))。下给例题： \[ \begin{flalign} &证明 计算 f(x) = \frac{1}{2}\|x\|^{2} 的共轭函数 f^*(y) \\&对于函数 f(x) = \frac{1}{2}\|x\|^{2}，共轭函数的定义是： \\& \qquad f^*(y) = \sup_{x\in\mathbb{R}^{n}} \left( \langle y,x \rangle - \frac{1}{2}\|x\|^{2} \right) \\&展开目标函数：\langle y,x \rangle - \frac{1}{2}\|x\|^{2} = \langle y,x \rangle - \frac{1}{2} \sum_{i = 1}^{n} x_{i}^{2} \\&对 x 求导并令其为零： \frac{\partial}{\partial x} \left( \langle y,x \rangle - \frac{1}{2}\|x\|^{2} \right) = y - x = 0 \\&因此，最优解为 x = y。将 x = y 代入原目标函数： \\&f^*(y) = \langle y,y \rangle - \frac{1}{2}\|y\|^{2} = \frac{1}{2}\|y\|^{2} \\&因此， f^*(y) = \frac{1}{2}\|y\|^{2}。 \end{flalign} \]

6. 转换为标准几何规划

1. 注意标准几何规划，用指数形式，＝1，≤ 1： \[ \begin{align*} \text{minimize} \quad & f_0(x,y) = \frac{x}{y} & {\text{minimize}} \quad & f_0(x,y) = x^{-1}y\\ \text{subject to} \quad & 1 \leq x \leq 4 & \text{subject to} \quad & x^{-1} \leq 1 ,\quad\frac{1}{4}x \leq 1\\ & x^2 \leq y^2 && x^2y^{-2} \leq 1\\ & \frac{x}{y^3} = 3 && \frac{1}{3}xy^{-3} = 1\\ \end{align*} \]

7. 求对偶问题

1. 构建拉格朗日函数，求对偶函数（分类讨论和求导），Lagrange 对偶函数的最大值就是原问题的最好下界。（注意把求对偶问题的分类条件放入约束条件）。 \[ \begin{align*} \text{maximize} \quad & g(\lambda, \nu) \\ \text{subject to} \quad & \lambda \succeq 0 \end{align*} \]

8. 求KKT条件与最优解

1. 自带的约束条件，λ ≥ 0，互补松弛性。求导等于0： \[ \begin{align*} f_i(x^*) &\leq 0, \quad i = 1, \ldots, m \\ h_i(x^*) &= 0, \quad i = 1, \ldots, p \\ \lambda_i^* &\geq 0, \quad i = 1, \ldots, m \\ \lambda_i^* f_i(x^*) &= 0, \quad i = 1, \ldots, m \quad(互补松弛性) \\ &\nabla f_0(x^*) + \sum_{i = 1}^{m} \lambda_i^* \nabla f_i(x^*) + \sum_{i = 1}^{p} \nu_i^* \nabla h_i(x^*) = 0 \end{align*} \] 注意：

   1. 求导等于0这里，如果有多个变量，则分别列多个等式，每个等式是对某个变量求导。
   2. λ 是针对不等式约束的，没有不等式约束就没有 λ ≥ 0 和互补松弛性。

2. 最优解：简单方法，直接代入看一下目标值即可。