约束优化问题(Constrained Optimization Problem)

对于无约束优化问题一样,我们有判断局部最优解的充分条件和必要条件。通过引进拉格朗日乘子,对于约束优化问题,我们也可以推导出类似的充分条件和必要条件。

回顾无约束优化
必要条件:$x^{\star}$ 是无约束优化问题的局部最优解的必要条件是:$\nabla f(x^{\star})=0$ 且海塞矩阵 $\nabla^2f(x^{\star})$ 是半正定的。
充分条件:任意一点 $x^{\star}$ 如果满足:$\nabla f(x^{\star})=0$ 且海塞矩阵 $\nabla^2f(x^{\star})$ 是正定的,那么这个点就是 $f$ 的一个严格局部最优点。

总览和术语

一般形式
一般化的约束优化问题具有下面的形式:$$\min_{x\in \mathbb{R}^n}f(x)\qquad \text{s.t.}\begin{cases}c_i(x)=0,\quad i=1,\cdots,n_e \\ d_j(x)\ge 0,\quad j=1,\cdots,n_i\end{cases}$$ 等式约束方程为 $c_i:\mathbb{R}^n\to\mathbb{R}$
不等式约束方程为 $d_j:\mathbb{R}^n\to\mathbb{R}$
将可行解的集合记为 $\Omega$,并假设这些函数都是二次可微的。
有效集(Active Set)
一个可行解 $x\in\Omega$ 处的有效集包含所有等式约束和满足 $d_j(x)=0$ 的不等式约束,即$$\mathcal{A}(x)=\bigcup_{i=1}^{n_i}\{c_i\}\cup\{d_j|d_j(x)=0\}$$

一阶必要条件(First-order necessary KKT conditions)

等式约束

我们首先来看等式约束的情况,以下面这个具体的例子来说: $$\min f(x)=x_1+x_2\qquad\text{s.t. }c_1(x)=x_1^2+x_2^2-2=0$$

$\nabla f=(1,1)^T$,$\nabla c_1=(2x_1,2x_2)^T$,我们发现,在最优点 $x^{\star}$ 处,$\nabla f(x^{\star})$ 和 $\nabla c_1(x^{\star})$ 是平行的。
假设 $x\in\Omega$ 是一个可行解,即有 $c_1(x)=0$,如果我们能找到一个找到一个方向 $p$ 使得等式约束依然满足 $$0=c_1(x+p)\approx c_1(x)+\nabla c_1(x)^Tp=\nabla c_1(x)^Tp$$同时使函数值下降$$0>f(x+p)-f(x)\approx \nabla f(x)^Tp$$那么就说明 $x$ 不是最优点。
反过来想,对于一个点 $x$,如果不存在满足上面两个条件的方向 $p$,就可以说这个点是局部最优点。
事实上,只有当 $\nabla f(x)$ 和 $\nabla c_1(x)$ 平行时才不会存在这样的方向,即存在某个实数使得 $\nabla f(x)=\lambda_1\nabla c_1(x)$。

反之,我们可以定义出 $p=-\left(I-\cfrac{\nabla c_1(x)\nabla c_1(x)^T}{||\nabla c_1(x)||^2}\right)\nabla f(x)$ 来满足上述两个条件

注意到,对于点 $x=(1,1)$,$\nabla f(x)$ 和 $\nabla c_1(x)$ 也是平行的。也就是说,这个条件是不能区别最大值点和最小值点的,因为它只用到了一阶导数的信息。
引入拉格朗日乘子 $\lambda_1$,我们可以得到拉格朗日函数:$$L(x,\lambda_1)=f(x)-\lambda_1c_1(x)$$两边关于 $x$ 求导可得 $$\nabla_xL(x,\lambda_1)=\nabla f(x)-\lambda_1\nabla c_1(x)$$ 则 $\nabla f(x^{\star})=\lambda_1^{\star}\nabla c_1(x^{\star})$ 与 $\nabla_xL(x^{\star},\lambda_1^{\star})=0$ 是等价的。

不等式约束

同样以一个例子来说明: $$\min f(x)=x_1+x_2\qquad\text{s.t. }d_1(x)=x_1^2+x_2^2-2\ge0$$

(¶图中应该是 $\nabla d_1$ 而不是 $\nabla c_1$)
类似地,给定一个可行解 $x$,如果我们能找到一个方向 $p$,既满足可行性又使函数值下降,则 $x$ 不是最优解,即 $$\begin{cases}\nabla d_1(x)^Tp\ge0 \\ \nabla f(x)^Tp<0\end{cases}$$ 分大于和等于两种情况讨论

情况1:$x$ 严格在圆的内部,即 $d_1(x)>0$
在这种情况下,只要方向 $p$ 长度足够小,那么就可以满足条件(设想沿使函数值减小的方向前进了极其小的一步,此时依然在圆内)。
比方说选取 $p=-d_1(x)\frac{\nabla f(x)}{||\nabla f(x)||}$ 就可以在 $\nabla f(x)\neq 0$ 时满足条件。
情况2:$x$ 在圆周上,即 $d_1(x)=0$

(¶图中应该是 $\nabla d_1$ 而不是 $\nabla c_1$)
只要选择的方向 $p$ 落在深色的阴影区域中就可以满足那两个条件,那么什么时候这个区域不存在呢?就是存在 $\lambda_1\ge0$ 使得 $\nabla f(x)=\lambda_1\nabla d_1(x)$ 成立时,即 $\nabla f(x)$ 和 $\nabla d_1(x)$ 同向时。

总结上面两种情况:当在 $x^{\star}$ 处不存在可行的下降方向 $p$ 时,应当有 $$\nabla_xL(x^{\star},\lambda_1^{\star})=0,\quad \text{for some }\lambda_1^{\star}\ge0$$ 并且 $$\lambda_1^{\star}d_1(x^{\star})=0\qquad\begin{cases}\text{Case I}&\quad d_1(x^{\star})>0 \\\text{Case II} &\quad d_1(x^{\star})=0\end{cases}$$

***** 一阶必要KKT条件 *****

如果 $x^{\star}$ 是一个弱局部最优解,下面的条件是满足的:$$\begin{array}{l}\color{red}{\nabla f(x^{\star})-\sum\limits_{i=1}^{n_e}\gamma_i \nabla c_i(x^{\star})-\sum\limits_{j=1}^{n_i}\lambda_j\nabla d_j(x^{\star})=0} \\ \color{green}{\lambda_j\ge 0,\quad j=1,…,n_i} \\ \color{purple}{c_i(x^{\star})=0,\quad i=1,…,n_e} \\ \color{purple}{d_j(x^{\star})\ge 0,\quad j=1,…,n_i} \\ \color{orange}{\lambda_j d_j(x^{\star})=0,\quad j=1,…,n_i}\end{array}$$分别表示静止性条件对偶可行性条件原问题可行性条件互补条件

静止性条件(Stationarity)

静止性指的是在点 $x^{\star}$ 处不存在可行的下降方向。

拉格朗日乘子

拉格朗日乘子 $\gamma_i$ 和 $\lambda_j$ 实际上告诉了我们函数最优值 $f(x^{\star})$ 对于每个约束的敏感性,反映出函数值 $f$ 有多么强烈地向方向 $c_i$ 和 $d_j$ 靠近或远离。
如果我们轻微地扰动第 $i$ 个等式约束的右端项,使得 $c_i(x)\ge -\epsilon||\nabla c_i(x^{\star})||$,则有 $$\cfrac{\mathrm{d}f(x^{\star}(\epsilon))}{\mathrm{d}\epsilon}=-\gamma_i||\nabla c_i(x^{\star})||$$

于是,我们可以将约束条件分为三类:

  • 强有效约束(Strong Active):拉格朗日乘子为正数的有效不等约束,和拉格朗日乘子非零的等式约束
  • 弱有效约束(Weak Active):拉格朗日乘子为0的有效约束
  • 无效约束(Inactive):不等于0的不等约束


如果去掉弱有效约束和无效约束,最优值仍不变。也就是说,只有强有效约束对最优值是有影响的。

互补条件(Complementary Conditions)

互补条件 $\lambda_j d_j(x^{\star})=0$ 保证了每个不等约束必须是三类约束之一:

  • 无效约束:$d_j(x^{\star})>0,\lambda_j=0$
  • 强有效约束:$d_j(x^{\star})=0,\lambda_j>0$
  • 弱有效约束:$d_j(x^{\star})=0,\lambda_j=0$

严格互补条件则保证了每个不等约束必须是前两种情况之一,即要么是无效约束,要么是强有效约束。

二阶最优条件(Second-order optimality conditions)

我们知道,满足 $p^T\nabla f(x^{\star})>0$ 的方向 $p$ 可以使函数值增大,满足 $p^T\nabla f(x^{\star})<0$ 的方向 $p$ 可以使函数值减小,但对于 $p^T\nabla f(x^{\star})=0$ 的方向 $p$,我们不知道它到底使函数值增大还是减小。如下图所示,$p^T\nabla f(x^{\star})=0$ 可以使函数值增大、减小或不变。

将这些模棱两可的方向的集合称为“关键锥”(critical cone)
$$\mathcal{C}(x^{\star},\gamma)=\{w\in\mathcal{F}(x)|\nabla d_j(x^{\star})^Tw=0,\forall j\in\mathcal{A}(x^{\star})\text{ with }\lambda_j>0\}$$其中$$\mathcal{F}(x)=\left\{p|p \text{ 满足 }\begin{cases}\nabla c_i(x)^Tp=0\quad \forall i \\ \nabla d_j(x)^Tp\ge 0 \quad\forall d_j\in\mathcal{A}(x)\end{cases}\right\}$$

二阶必要条件

D1. 满足KKT条件
D2. $p^T\nabla^2\mathcal{L}(x^{\star},\gamma)p\ge 0 \quad \forall p\in\mathcal{C}(x^{\star},\gamma)$

二阶充分条件

E1. 满足KKT条件
E2. $p^T\nabla^2\mathcal{L}(x^{\star},\gamma)p\gt 0 \quad \forall p\in\mathcal{C}(x^{\star},\gamma)$

类似于无约束的二阶条件,只不过约束问题的二阶条件是“有选择地”正定(或半正定)即可。

在Case I中,$f(x)$ 的斜率变化快于 $d_1(x)$,所以拉格朗日函数的二次型严格大于零
在Case II中,$f(x)$ 的斜率变化等于 $d_1(x)$,所以拉格朗日函数的二次型等于零
在Case III中,$f(x)$ 的斜率变化慢于 $d_1(x)$,所以拉格朗日函数的二次型严格小于零

参考资料:

  1. Constrained Optimization
  2. NJU《最优化理论与方法》Lecture notes