06-约束优化问题

本章讨论优化问题：

minimize subject to f (x) h_{i} (x) = 0, i = 1, \dots, m g_{j} (x) ⩽ 0, j = 1, \dots, p

其中, $x \in R^{n}, f : R^{n} \to R, h_{i} : R^{n} \to R, g_{j} : R^{n} \to R, m ⩽ n$

只含等式的约束优化问题

我们定义可行集为所有可行点组成的集合： ${x \in R^{n} : h_{i} (x) = 0}$

我们定义正则点为满足以下形式的点：满足约束 $h_{1} (x^{*}) = 0, \dots, h_{m} (x^{*}) = 0$ 的点 $x^{*}$ , 梯度向量 $\nabla h_{1} (x^{*}), \dots, \nabla h_{m} (x^{*})$ 是线性无关的。

我们定义切线空间：曲面 $S = {x \in R^{n} : h (x) = 0}$ 中点 $x^{*}$ 处的切线空间为集合 $T (x^{*}) =$ ${y : Dh (x^{*}) y = 0}$ 可以看出，切线空间 $T (x^{*})$ 是矩阵 $D h (x^{*})$ 的零空间:

T (x^{*}) = N (D h (x^{*}))

我们定义法线空间：曲面 $S = {x \in R^{n} : h (x) = 0}$ 中点 $x^{*}$ 处的法线空间 $N (x^{*}) = {x \in R^{n} : x = D h (x^{*})^{⊤} z, z \in R^{m}}$ 即: $N (x^{*}) = R (D h (x^{*})^{⊤}) = span [\nabla h_{1} (x^{*}), \dots, \nabla h_{m} (x^{*})]$

我们定义拉格朗日函数： $l : R^{n} \times R^{m} \to R$

l (x, λ) ≜ f (x) + λ^{⊤} h (x)

拉格朗日条件

一阶必要条件

\nabla f (x^{*}) + λ^{* ⊤} \nabla h (x^{*}) = 0^{⊤}

二阶必要条件

对于所有 $y \in T (x^{*})$ 都有:

y^{⊤} L (x^{*}, λ^{*}) y \geq 0

其中 $L (x^{*}, λ^{*}) = F (x^{*}) + λ H (x^{*})$ ， $F (x^{*})$ 是 $f (x)$ 在 $x^{*}$ 处的 $Hess ian$ 矩阵； $H (x^{*})$ 是 $h_{i} (x)$ 在 $x^{*}$ 处的 $Hess ian$ 矩阵。即：

H_{i} (x) = \frac{\partial ^{2} h _{i}}{\partial x _{1}^{2}} (x) ⋮ \frac{\partial ^{2} h _{i}}{\partial x _{1} \partial x _{n}} (x) \dots \dots \frac{\partial ^{2} h _{i}}{\partial x _{n} \partial x _{1}} (x) ⋮ \frac{\partial ^{2} h _{i}}{\partial ^{2} x _{n}} (x)

二阶充分条件

函数 $f, h \in C^{2}$ , 如果存在点 $x^{*} \in R^{n}$ 和 $λ^{*} \in R^{m}$ , 使得

$\nabla f (x^{*}) + λ^{* ⊤} \nabla h (x^{*}) = 0^{⊤}$
对于所有 $y \in T (x^{*})$ , $y \neq = 0$ , 都有 $y^{⊤} L (x^{*}, λ^{*}) y > 0$ 那么, $x^{*}$ 是 $f$ 在约束条件 $h (x) = 0$ 下的严格局部极小点。

注：若 $x^{*}$ 满足拉格朗日条件, 且 $L (x^{*}, λ^{*})$ 在 $T (x^{*})$ 上正定, 则 $x^{*}$ 是严格局部极小点。反之, 当 $L (x^{*}, λ^{*})$ 在 $T (x^{*})$ 上负定时, $x^{*}$ 是一个严格局部极大点。

含不等式约束优化问题

问题描述&相关定义

本章考虑的一般形式的优化问题:

minimize subject to f (x) h (x) = 0 g (x) ⩽ 0

其中, $f : R^{n} \to R, h : R^{n} \to R^{m}, m ⩽ n, g : R^{n} \to R^{p}$ 。

对于一个不等式约束 $g_{j} (x) ⩽ 0$ , 如果在 $x^{*}$ 处 $g_{j} (x^{*}) = 0$ , 那么称该不等式约束是 $x^{*}$ 处的起作用的约束; 如果在 $x^{*}$ 处 $g_{j} (x^{*}) < 0$ , 那么称该约束是 $x^{*}$ 处的不起作用的约束。等式约束 $h_{i} (x) = 0$ 当作总是起作用的约束。

我们定义可行集下的正则点：设 $x^{*}$ 满足 $h (x^{*}) = 0, g (x^{*}) ⩽ 0$ , 设 $J (x^{*})$ 为起作用不等式约束的下标集:

J (x^{*}) ≜ {j : g_{j} (x^{*}) = 0}

如果向量

\nabla h_{i} (x^{*}), \nabla g_{j} (x^{*}), 1 ⩽ i ⩽ m, j \in J (x^{*})

是线性无关的，则称 $x^{*}$ 是一个正则点。

定义如下矩阵为高阶拉格朗日函数:

L (x, λ, μ) = F (x) + [λ H (x)] + [μ G (x)]

其中, $F (x)$ 是 $f$ 在点 $x$ 处的黑塞矩阵, $[λH (x)]$ 与之前一样, 表示

[λ H (x)] = λ_{1} H_{1} (x) + \dots + λ_{m} H_{m} (x)

类似地, $[μ G (x)]$ 表示

[μ G (x)] = μ_{1} G_{1} (x) + \dots + μ_{p} G_{p} (x)

其中, $G_{k} (x)$ 是 $g_{k}$ 在 $x$ 处的黑塞矩阵:

G_{k} (x) = \frac{\partial ^{2} g _{k}}{\partial ^{2} x _{1}} (x) ⋮ \frac{\partial ^{2} g _{k}}{\partial x _{1} \partial x _{n}} (x) \dots \dots \frac{\partial ^{2} g _{k}}{\partial x _{n} \partial x _{1}} (x) ⋮ \frac{\partial ^{2} g _{k}}{\partial ^{2} x _{n}} (x)

在接下来的定理中, 用

T (x^{*}) = {y \in R^{n} : \nabla h (x^{*}) y = 0, \nabla g_{j} (x^{*}) y = 0, j \in J (x^{*})}

代表由起作用约束所定义曲面的切线空间。

KKT条件

$KK T$ 条件是满足极小点的必要条件。满足：

原始可行性： $h (x^{*}) = 0$ ; $g (x^{*}) ⩽ 0$
对偶可行性 $μ^{*} ⩾ 0$ ;
原始最优性 $\nabla f (x^{*}) + λ^{* ⊤} \nabla h (x^{*}) + μ^{* ⊤} \nabla g (x^{*}) = 0^{⊤}$ ;
互补松弛条件 $μ^{* ⊤} g (x^{*}) = 0$ ;

主要思想就是引入了KKT算子，提出了 $μ ⩾ 0$ 。下面分情况讨论推导过程。

$g (x^{*}) < 0$ 此时 $g (x^{*})$ 不起约束，转换成仅含等式约束的问题，使用拉格朗日乘数法解决即可。

$g (x^{*}) = 0$ 也是转换成仅含等式约束问题，使用拉格朗日乘数法解决即可。

$g (x^{*}) > 0$ 此时 $x^{*}$ 不满足约束，忽略。 所以仅需考虑条件 (1), (2) 即可 (1). 若 $g (x^{*}) = 0$ ，引入乘子 $μ$ ，并且规定 $μ ⩾ 0$ ¹ (2). 若 $g (x^{*}) < 0$ ，规定 $μ = 0$ 。综合起来就是 $μ^{* ⊤} g (x^{*}) = 0$

注意，这里讨论的KKT条件是针对开头对应约束优化问题。倘若改为极大化条件或者不等式约束不等号方向相反，而需要对原函数或者不等式约束条件进行变号处理。然后用新的问题写KKT条件。

二阶必要条件

$μ^{*} ⩾ 0, \nabla f (x^{*}) + λ^{* ⊤} \nabla h (x^{*}) + μ^{* ⊤} \nabla g (x^{*}) = 0^{⊤}, μ^{* ⊤} g (x^{*}) = 0$ ;
对于所有 $y \in T (x^{*})$ , 都有 $y^{⊤} L (x^{*}, λ^{*}, μ^{*}) y ⩾ 0$ 成立。

二阶充分条件

$μ^{*} ⩾ 0, \nabla f (x^{*}) + λ^{* ⊤} \nabla h (x^{*}) + μ^{* ⊤} \nabla g (x^{*}) = 0^{⊤}, μ^{* ⊤} g (x^{*}) = 0$ ;
对于所有 $y \in T (x^{*}, μ^{*}), y \neq = 0$ , 都有 $y^{⊤} L (x^{*}, λ^{*}, μ^{*}) y > 0$ 。其中： $\tilde{T} (x^{*}, μ^{*})$ 定义为：

\tilde{T} (x^{*}, μ^{*}) = {y : D h (x^{*}) y = 0, D g_{i} (x^{*}) y = 0, i \in \tilde{J} (x^{*}, μ^{*})}

其中, $\tilde{J} (x^{*}, μ^{*}) = {i : g_{i} (x^{*}) = 0, u_{i}^{*} > 0}$ 。注意 $\tilde{J} (x^{*}, μ^{*})$ 是 $J (x^{*})$ 的子集, $J (x^{*}, μ^{*}) \subset J (x^{*})$ 成立。这意味着, $T (x^{*})$ 是 $T (x^{*}, μ^{*})$ 的子集。

投影法

考虑优化问题：

minimi ze f (x) s u bj ec t t o x \in Ω

$Ω = {x : l_{i} ⩽ x_{i} ⩽ u_{i}, i = 1, \dots, n}$

如果使用无约束的常见迭代格式 $x^{(k + 1)} = x^{(k)} + α_{k} d^{(k)}$ 可能不满足条件。

定义 (投影) : 设 $Ω \in R^{n}$ 是非空闭凸集。任意 $x \in R^{n}$ 在 $Ω$ 上的投影为

Π [x] = x \in Ω ar g min ∥ z - x ∥

也就是 $Ω$ 中最接近 $x$ 的点。

投影性质：
- 若 $Ω$ 是非空闭凸集，投影存在且唯一
- $x *$ 是 $x$ 在 $Ω$ 上的投影 $\Leftrightarrow (x - x^{*})^{T} (z - x^{*}) ⩽ 0$ , 是任意 $z \in Ω$ 。等号成立当且仅当 $Ω$ 是仿射流形。
投影方法：
- 无约束线搜索: $x^{(k + 1)} = x^{(k)} + α_{k} d^{(k)}$
- 投影方法: $x^{(k + 1)} = Π [x^{(k)} + α_{k} d^{(k)}]$
- 投影梯度方法: $x^{(k + 1)} = Π [x^{(k)} - α_{k} \nabla f (x^{(k)})]$

搜索迭代示意图

仿射约束上的投影方法

考虑优化问题：

minimi ze f (x) s u bj ec t t o A x = b

其中， $f : R^{n} \to R, A \in R^{m \times n}, m < n, rank A = m, b \in R^{m}$ 对于约束集是 $Ω : A x = b$ ,可以使用正交投影算子作为 $Π$ 。定义为如下的正交投影算子矩阵 $P$ :

P = I_{n} - A^{⊤} (A A^{⊤})^{- 1} A

设 $v \in R^{n}$ , 那么当且仅当 $v \in R (A^{⊤})$ 时, $P v = 0$ , 即 $N (P) = R (A^{⊤})_{。}$ 此外, 当且仅当 $v \in R (P)$ , 有 $A v = 0$ , 即 $N (A) = R (P)$ 。

无约束优化: $x^{*}$ 是局部极小点的一阶必要条件是 $\nabla f (x^{*}) = 0$ 。

仅含等式约束 $Ω = {x : A x = b}$ 的优化, $x^{*}$ 是局部极小点的一阶必要条件是 $P \nabla f (x^{*}) = 0$ 。

约束集 $Ω = {x : A x = b}$ 的投影梯度法迭代公式:

x^{(k + 1)} = x^{(k)} - α_{k} P \nabla f (x^{(k)})

迭代点 ${x^{(k)}}$ 满足 $f (x^{(k + 1)}) < f (x^{(k)})$

对于任意初始点，只要步长足够大，梯度投影算法一步即可德奥最优解。

拉格朗日法

拉格朗日法-等式约束

利用梯度法更新决策变量和朗格朗日乘子向量。
等式约束优化的拉格朗日法: $minimi ze f (x) s u bj ec t t o h (x) = 0$ 其中, $h : R^{n} \to R^{m}$ 拉格朗日函数为: $l (x, λ) = f (x) + λ^{⊤} h (x)$ 拉格朗日法迭代公式:

x^{(k + 1)} λ^{(k + 1)} = x^{(k)} - α_{k} (\nabla f (x^{(k)}) + D h (x^{(k)})^{⊤} λ^{(k)}) = λ^{(k)} + β_{k} h (x^{(k)})

$x^{(k)}$ 的更新是拉格朗日函数关于 $x$ 极小化的梯度算法; $λ^{(k)}$ 的更新是拉格朗日函数关于 $λ$ 极大化的梯度算法。

拉格朗日法更新 $x^{(k)}$ 和 $λ^{(k)}$ 的过程中, 产生的向量对 $(x^{*}, λ^{*})$ 是一个不动点 $\Leftrightarrow (x^{*}, λ^{*})$ 满足拉格朗日条件。

拉格朗日法-不等式约束

考虑问题:

minimi ze f (x) s u bj ec t t o g (x) ⩽ 0

其中 $g : R^{n} \to R^{p}$
拉格朗日函数为： $l (x, μ) = f (x) + μ^{⊤} g (x)$ 拉格朗日法迭代公式：

x^{(k + 1)} = x^{(k)} - α_{k} (\nabla f (x^{(k)}) + D g (x^{(k)})^{⊤} μ^{(k)}) μ^{(k + 1)} = [μ^{(k)} + β_{k} g (x^{(k)})]_{+}

其中, $[\cdot]_{+} = max {\cdot, 0}$

$x^{(k)}$ 的更新是拉格朗日函数关于 $x$ 极小化的梯度算法; $μ^{(k)}$ 的更新是拉格朗日函数关于 $μ$ 极大化的投影梯度算法。

拉格朗日法更新 $x^{(k)}$ 和 $μ^{(k)}$ 的过程中, 产生的向量对 $(x^{*}, μ^{*})$ 是一个不动点 $\Leftrightarrow (x^{*}, μ^{*})$ 满足KKT条件。当 $α$ 和 $β$ 足够小时, 存在 $(x^{*}, μ^{*})$ 的一个邻域, 如果 $(x^{(0)}, μ^{(0)})$ 属于该邻域，那么, 拉格朗日算法: (1) 不起作用约束条件的乘子在有限的时间内减小到零, 此后一直保持为零; (2) 算法至少以线性速度收敛到 $(x^{*}, μ^{*})$

罚函数法

将约束优化问题近似处理成无约束优化问题 约束优化： $minimi ze f (x) s u bj ec t t o x \in Ω$ 等价于约束优化： $minimi ze f (x) + l_{Ω} (x)$ 其中 $l_{Ω}$ 是指示函数:

ι_{Ω} (x) := {0, + \infty, if x \in Ω otherwise

等价于： $minimi ze f (x) + γ P (x)$ 其中, $γ \in R$ 是大于零的常数(惩罚因子)。 $P : R^{n} \to R$ 是给定函数(罚函数、罚项)

$P$ 是连续的;
对所有 $x \in R^{n}, P (x) ⩾ 0$ 成立;
$P (x) = 0$ , 当且仅当 $x$ 是可行点 (即 $x \in Ω$ ) 无约束优化与约束优化的逼近程度，取决于 $γ$ 、 $P$ 。 $γ$ 越大，逼近越好。当 $γ \to \infty$ 时，罚函数法可得到约束问题的真解。

约束优化的罚函数法:

x \in R^{n} min f (x) s.t. h (x) = 0, g (x) \leq 0

其中 $h : R^{n} \to R^{p}, g : R^{n} \to R^{m}$

精确罚函数: $min_{x \in R^{n}} f (x) + γ (\sum_{i = 1}^{p} ∣ h_{i} (x) ∣ + \sum_{i = 1}^{m} g_{i}^{+} (x))$ 其中, $g_{i}^{+} (x) = max {0, g_{i} (x)} = {0, g_{i} (x), g_{i} (x) ⩽ 0 g_{i} (x) > 0$
二次罚函数: $min_{x \in R^{n}} f (x) + γ (\sum_{i = 1}^{p} ∣ h_{i} (x) ∣^{2} + \sum_{i = 1}^{m} g_{i}^{+} (x)^{2})$ 注：精确罚函数, 不可微。二次罚（库朗罚函数）,一般可微。
推广罚函数： $min f (x) + P (x) = f (x) + γ (∥ h (x) ∥_{b}^{a} + ∥ [g (x)]^{+} ∥_{b}^{a})$

演示实例

例: 一元函数 $g_{1} (x) = x - 2$ 和 $g_{2} (x) = - (x + 1)^{3}$ 可行域定义为 ${x \in R : g_{1} (x) ⩽ 0, g_{2} (x) ⩽ 0}$ 构造绝对值罚函数:

g_{1}^{+} (x) = max {0, g_{1} (x)} = {0, x - 2, x ⩽ 2 其他 g_{2}^{+} (x) = max {0, g_{2} (x)} = {0, - (x + 1)^{3}, x ⩾ - 1 其他

例：用二次罚函数法求优化问题的解

min f (x) = - x_{1} x_{2} s.t g (x) = x_{1} + 2 x_{2} - 4 = 0

解：二次罚函数为

x min π (x) = - x_{1} x_{2} + \frac{1}{2} γ (x_{1} + 2 x_{2} - 4)^{2}

求解上述含参的无约束优化问题 (即求稳定点) 另外, 对 (*)式写最优性条件, 对比原优化问题的KKT条件, 可得对偶问题的解

λ (γ) = - γ g (x (γ)) = \frac{- 4 γ}{4 γ - 1} ⟶ 令 γ \to + \infty λ = - 1

对数与倒数罚函数法

约束优化（仅有不等式约束或约束集有内点）: $min_{x \in R^{n}} f (x) s . t . g (x) \geq 0$ 其中 $g : R^{n} \to R^{m}$

对数罚函数: $min_{x \in R^{n}} f (x) - \frac{1}{γ} (\sum_{i = 1}^{m} lo g (g_{i} (x)))$
倒数罚函数： $min_{x \in R^{n}} f (x) + \frac{1}{γ} (\sum_{i = 1}^{m} \frac{1}{g _{i} ( x )})$

增广Lagrange函数法

把Lagrange函数与罚函数法结合，解决罚参数过大问题。 $min_{x \in R^{n}} f (x) s . t . h (x) = 0, g (x) \leq 0$ 其中 $h : R^{n} \to R^{p}, g : R^{n} \to R^{m}$ 增广Lagrange 函数 $L : R^{n} \times R^{p} \times R_{+}^{m} \to R$

L (x, λ, μ) = f (x) + i = 1 \sum p λ_{i} h_{i} (x) + i = 1 \sum m μ_{i} g_{i} (x) + γ (i = 1 \sum p ∣ h_{i} (x) ∣^{2} + i = 1 \sum m g_{i}^{+} (x)^{2})

迭代格式:

x^{k + 1} = x \in R^{n} ar g min L (x, λ^{k}, μ^{k}) λ^{k + 1} = λ^{k} + γ i = 1 \sum p h_{i} (x^{k + 1}) μ^{k + 1} = (μ^{k} + γ i = 1 \sum m g_{i}^{+} (x)^{2})^{+}

约束优化的对偶问题

约束优化问题的对偶问题是一种用来求解约束优化问题的数学方法。在这种方法中，原始问题被转化为一个新问题，称为对偶问题，并且可以用来求解原始问题。约束优化问题是一种常见的数学问题，通常表示为最大化或最小化一个目标函数，同时需要满足一组约束条件。

求解约束优化问题的对偶问题通常使用一种称为对偶算法的数学方法。该算法包括以下步骤：

将原始问题转化为对偶问题。这通常需要对目标函数和约束条件进行一些变换，以便将问题转化为一个新问题。
求解对偶问题。通常使用一些标准的数学方法来求解对偶问题，例如单纯形法或者拉格朗日乘子法。
将对偶问题的解转换为原始问题的解。这一步通常也需要进行一些变换，以便将对偶问题的解转化为原始问题的解。

对偶算法的一个优点是它可以在计算上比较高效。例如，如果原始问题中的约束条件比较多，那么使用对偶算法可以将这些约束条件转化为一个较少的数量，因此在求解问题时可能会更加高效。此外，对偶问题的求解过程可能会提供有关原始问题的更多信息，从而帮助我们更好地理解问题。

假设我们要求解以下约束优化问题：

最小化：x + y

约束条件：

x ≥ 0
y ≥ 0
x + y = 1

在这个例子中，我们的目标是最小化目标函数x + y，并且需要满足三个约束条件。要求解这个问题，我们首先要将它转化为对偶问题。这一步需要进行如下变换：

将目标函数的最小化转化为最大化。
将原始问题的约束条件转化为对偶问题的目标函数。
将原始问题的目标函数转化为对偶问题的约束条件。

在这个例子中，我们首先将目标函数x + y的最小化转化为最大化。这样，我们就得到了新的对偶问题：

最大化：x + y

接下来，我们要将原始问题的约束条件转化为对偶问题的目标函数。根据第二个步骤，我们需要将约束条件x + y = 1转化为一个新的目标函数。我们可以将这个约束条件表示为：

x + y = 1

将这个约束条件与原始问题的目标函数x + y相乘，得到：

(x + y) * (x + y) = 1

然后，我们可以用拉格朗日乘子法来求解对偶问题。我们可以用拉格朗日函数来表示对偶问题：

L(x,y,λ) = x + y + λ * (x + y - 1)

然后，我们可以计算拉格朗日函数的偏导数，并求解方程组：

∂L/∂x = 1 + λ = 0 ∂L/∂y = 1 + λ = 0 ∂L/∂λ = x + y - 1 = 0

解这个方程组，得到：

x = 1/2 y = 1/2 λ = -1/2

由于对偶问题的解满足对偶问题的约束条件，所以我们可以将对偶问题的解转换为原始问题的解。根据第三个步骤，我们需要将对偶问题的解转换为原始问题的目标函数。因此，我们得到：

x + y = 1/2 + 1/2 = 1

这就是原始问题的解。由于我们求得的解满足原始问题的约束条件，因此这就是原始问题的最优解。

Lagrange对偶

min f (x) s.t. c_{i} (x) = 0, i \in E c_{i} (x) ⩾ 0, i \in I

记不等式约束组成的向量值函数为 $G (x)$ , 等式约束组成的向量值函数记为 $H (x)$

Lagrange函数为

L (x, u, v) = f (x) - G (x)^{T} u - H (x)^{T} v, x \in R^{n}, u \in R_{+}^{∣ I ∣}, v \in R^{∣ E ∣}

其对偶问题实质就是换个方向求鞍点 |课程PPT

对偶间隙：原规划与对偶问题的最优值之间的差；
完全对偶：对偶间隙为零；
强对偶：对偶间隙为零，原问题和对偶问题都存在最优解；

对偶问题的例题

应用中先求问题关于x的极小点，再求参数的极大点|课程PPT

参考资料

KKT条件，原来如此简单 | 理论+算例实践 ↩

🪴 Quartz 4.0

Explorer

06-约束优化问题