等式约束的优化问题求解

基本概念

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

minimizef(x)subject toh(x)=0\begin{align*} minimize\quad f(x)\\ subject\ to\quad h(x)=0 \end{align*}

其中x∈Rn,f:Rn→R,h:Rn→Rm,h=[h1,...,hm]T,m≤nx\in R^{n},f:R^{n}\to R,h:R^{n}\to R^{m},h=[h_{1},...,h_{m}]^{T},m\le n，假定函数hh连续可微，即h∈C1h\in C^{1}。 下面介绍几个基本概念：

正则点：对于满足约束 h1(x∗)=0,...,hm(x∗)=0h_{1}(x^{*})=0,...,h_{m}(x^{*})=0 的点x∗∗x^{**}，如果梯度向量 ∇h1(x∗),...,∇hm(x∗)\nabla h_{1}(x^{*}),...,\nabla h_{m}(x^{*}) 是线性无关的，则称x∗x^{*}是该约束的一个正则点。

切线空间：曲面S=x∈Rn:h(x)=0S={x\in R^{n}:h(x)=0}中点x∗x^{*}处的切线空间为集合T(x∗)={y:Dh(x∗)y=0}T(x^{*})=\{ y:Dh(x^{*})y=0\} 。可以看出切线空间T(x^{_})是矩阵Dh(x^{_})的零空间，即T(x^{_})=N(Dh(x^{_}))。

法线空间：曲面S=x∈Rn:h(x)=0S={x\in R^{n}:h(x)=0}中点x∗x^{*}处的法线空间为集合N(x∗)={x∈Rn:x=Dh(x∗)Tz,z∈Rm}N(x^{*})=\{ x\in R^{n}:x=Dh(x^{*})^{T}z,z\in R^{m}\} 。可以看出法线空间N(x^{_})是矩阵Dh(x^{_})的零空间，即N(x^{_})=R(Dh(x^{_})^{T})。

拉格朗日条件

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

x(t)=[x1(t),x1(t)]T,t∈(a,b),x∗=x(t∗),x˙(t∗)≠0,t∗∈(a,b)\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*}

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

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

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

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

利用链式法则可以得到

ddth(x(t))=∇h(x(t))Tx˙(t)=0\frac{d}{dt}h(x(t))=\nabla h(x(t))^{T}\dot{x}(t)=0

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

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

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

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

利用链式法则可以得到

ddtϕ(t∗)=∇f(x(t∗))Tx˙(t∗)=∇f(x∗)Tx˙(t∗)=0\frac{d}{dt}\phi(t^{*})=\nabla f(x(t^{*}))^{T}\dot{x}(t^{*})=\nabla f(x^{*})^{T}\dot{x}(t^{*})=0

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

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

∇f(x∗)+λ∗∇h(x∗)=0\nabla f(x^{*})+\lambda^{*}\nabla h(x^{*})=0

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

Df(x∗)+λ∗TDh(x∗)=0D f(x^{*})+\lambda^{*T}D h(x^{*})=0

二阶条件

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

1.Df(x∗)+λ∗TDh(x∗)=0TD f(x^{*})+\lambda^{*T}D h(x^{*})=0^{T} 2.对于所有的y∈T(x∗)y\in T(x^{*})，都有yTL(x∗,λ∗)y≥0y^{T}L(x^{*},\lambda^{*})y\ge 0

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

1.Df(x∗)+λ∗TDh(x∗)=0TD f(x^{*})+\lambda^{*T}D h(x^{*})=0^{T} 2.对于所有的y∈T(x∗)y\in T(x^{*})，都有yTL(x∗,λ∗)y>0y^{T}L(x^{*},\lambda^{*})y> 0

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

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

  • 技术