Lagrangian Conditions under Equality Constraints

基本概念

本文将讨论下类形状的优化问题

$$\min_{x \in \mathbb{R}^n} f(x) \quad \text{s.t. } h(x) = 0$$

其中

• $x \in \mathbb{R}^{n}$，
• $f:\mathbb{R}^{n}\to \mathbb{R}$，
• $h:\mathbb{R}^{n}\to \mathbb{R}^{m}, \; h=[h_{1},...,h_{m}]^{T}, \; m\le n$。

假定函数 $h$ 连续可微，即 $h\in C^{1}$。

---

正则点

设点 $x^{*}$ 满足约束条件

$$h_{1}(x^{*})=0,\ldots,h_{m}(x^{*})=0,$$

如果梯度向量 $\nabla h_{1}(x^{*}),\ldots,\nabla h_{m}(x^{*})$ 线性无关，则称 $x^{*}$ 是该约束的一个 正则点。

---

切线空间

曲面

$$S=\{x\in \mathbb{R}^{n}:h(x)=0\}$$

在点 $x^{*}$ 处的切线空间为

$$T(x^{*})=\{ y \in \mathbb{R}^n : Dh(x^{*})y=0\}.$$

可见切线空间 $T(x^{*})$ 就是矩阵 $Dh(x^{*})$ 的零空间：

$$T(x^{*}) = \mathcal{N}(Dh(x^{*})).$$

---

法线空间

曲面

$$S=\{x\in \mathbb{R}^{n}:h(x)=0\}$$

在点 $x^{*}$ 处的法线空间为

$$N(x^{*})=\{ Dh(x^{*})^{T}z : z\in \mathbb{R}^{m}\}.$$

因此，法线空间是矩阵 $Dh(x^{*})^{T}$ 的值域：

$$N(x^{*}) = \mathcal{R}(Dh(x^{*})^{T}).$$

拉格朗日条件

首先考虑只包含两个决策变量和一个等式约束的优化问题。令$h:R^{2}\to R$为约束函数，可知函数定义域中$x$处的梯度$\nabla h(x)$与通过该点的$h(x)$水平集正交，选择点$x^{*}=[x^{*}_{1},x^{*}_{1}]^{T}$使得$h(x^{*})=0$，且$\nabla h(x^{*})\neq 0$，经过点$x^{*}$的水平集为集合$\{ x:h(x)=0\}$。可利用曲线$x(t)$在$x^{*}$领域内进行参数化，$x(t)$是一个连续可微的向量函数$h:R\to R^{2}$：

$$\begin{align*} x(t)=[x_{1}(t),x_{1}(t)]^{T},t\in (a,b),x^{*}=x(t^{*}),\dot{x}(t^{*})\neq 0,t^{*}\in (a,b) \end{align*}$$

接下来可以证明，$\nabla h(x^{*})$与$\dot{x}(t^{*})$正交。由于$h$在曲线$\{x(t):t\in (a,b)\}$上是常数 0，即对于所有的$t\in (a,b)$都有

$$h(x(t))=0$$

因此对于任意的$t\in(a,b)$都有

$$\frac{d}{dt}h(x(t))=0$$

利用链式法则可以得到

$$\frac{d}{dt}h(x(t))=\nabla h(x(t))^{T}\dot{x}(t)=0$$

因此$\nabla h(x^{*})$和$\dot{x}(t^{*})$正交 当$x^{*}$是$f:R\to R^{2}$在满足$h(x)=0$上的极小点的时候，可以证明，$\nabla f(x^{*})$与$\dot{x}(t^{*})$正交，构造关于$t$的复合函数：

$$\phi(t)=f(x(t))$$

当$t=t^{*}$的时候取得极小值，根据无约束极值问题的一阶必要条件可知

$$\frac{d\phi}{dt}(t^{*})=0$$

利用链式法则可以得到

$$\frac{d}{dt}\phi(t^{*})=\nabla f(x(t^{*}))^{T}\dot{x}(t^{*})=\nabla f(x^{*})^{T}\dot{x}(t^{*})=0$$

因此，$\nabla f(x^{*})$和$\dot{x}(t^{*})$正交，上面已经证明$\nabla f(x^{*})$与$\dot{x}(t^{*})$正交，那么向量$\nabla f(x^{*})$和$\nabla h(x^{*})$平行，那么可以得到这种情况下的拉格朗日定理：

n=2,m=3 时的拉格朗日定理： 设点$x^{*}$是函数$f:R^{2}\to R$的一个极小点，约束条件是$h(x)=0,h:R^{2}\to R$,那么$\nabla f(x^{*})$和$\nabla h(x^{*})$平行，即如果$\nabla h(x^{*})\neq 0$，则存在标量$\lambda^{*}$，使得

$$\nabla f(x^{*})+\lambda^{*}\nabla h(x^{*})=0$$

其中$\lambda^{*}$为拉格朗日乘子。 将这个定理推广到一般情况下，即$f:R^{n}\to R,h:R^{n}\to R^{m},m\le n$的时候，可以得到： 拉格朗日定理： $x^{*}$是$f:R^{n}\to R$的局部极小点（或极大点），约束条件为$h(x)=0,h:R^{n}\to R^{m},m\le n$。如果$x^{*}$是正则点，那么存在$\lambda^{*}\in R^{m}$使得

$$D f(x^{*})+\lambda^{*T}D h(x^{*})=0$$

二阶条件

二阶必要条件： 设$x^{*}$是$f:R^{n}\to R$在约束条件$h(x)=0,h:R^{n}\to R^{m},m\le n,f,h\in C^{2}$下的局部极小点。如果$x^{*}$是正则点，那么存在$\lambda^{*}\in R^{m}$使得

1.$D f(x^{*})+\lambda^{*T}D h(x^{*})=0^{T}$ 2.对于所有的$y\in T(x^{*})$，都有$y^{T}L(x^{*},\lambda^{*})y\ge 0$

二阶充分条件： 函数$f,h\in C^{2}$，如果存在点$x^{*}\in R^{n}$和$\lambda^{*}\in R^{m}$，使得

1.$D f(x^{*})+\lambda^{*T}D h(x^{*})=0^{T}$ 2.对于所有的$y\in T(x^{*})$，都有$y^{T}L(x^{*},\lambda^{*})y> 0$

那么$x^{*}$是$f$在约束条件$h(x)=0$下的严格局部极小点

本文介绍了等式约束下的拉格朗日乘子法，后面还将会介绍不等式约束下的拉格朗日乘子法以及 KKT 条件等