优化理论之最优化条件

Nov 3, 2019 · 优化理论  ·
分享到:

我们在本文主要谈论最小化： f:Rn→R，f为连续函数。对于f的可行域Ω，求min⁡x∈Ωf(x)f:\mathbb{R}^n→R，f为连续函数。对于f的可行域\Omega，求\\ \min_{x ∈ \Omega} f(x)

我们需要指出的是，函数并没有指出在可行域内有最优解。即使有最优解，也未必在可行域内。因此，我们需要明确哪些情况最优解是一定存在的。

根据基本的维尔思特拉斯极值定理有

定理1：维尔思特拉斯极值定理：每一定义在紧集上的连续函数，都可以在定义域内取到极值点。这也表明：紧集上的连续函数都是有界的。

在此基础上，我们介绍一个更深的定理，但是现阶段不太会用到：

定理2： 若函数ff在n维闭区域SS上连续并且向正无穷发散(coercive，即如果lim∣∣x∣∣⇒∞,f(x)=+∞lim||x||⇒∞,f(x)=+∞)，那么ff在SS上一定有全局最小值。

以上定理只能保证最小值存在，没有建立最小值和极小值之间的关系。但是，对于一类特殊的函数，它在一定区域内的极小值一定是最小值，这类函数即凸函数。凸函数为定义在凸区间上的一种函数，它满足任意两点的连线位于抽象的函数曲面之下；而凸区间则满足任意两点连线仍然在区间中。定义在凸区间内的严格凸函数有唯一的极小值，该极小值为该函数在该区间上的最小值。

本节研究无约束问题：（基于费马引理） min⁡f(x),x∈Rn（1）\min f(x),x\in R^n（1） 的最优性条件，包括一阶条件和二阶条件。

应该指出，实际上我们只是求一个局部（局部严格）极小点，而非总体最小点。尽管我们也会考虑总体最小值的情况，但是一般来说这是一个相当困难的任务。在很多实际应用中，求局部最小值已经满足了问题的要求。因此本文章所指的极小值是指局部极小值。仅当问题具有某种凸性质，局部最小值才是总体最小值。

设ff的一阶导数和二阶导数存在，且分别表示为： g(x)=∇f(x),G(x)=∇2f(x),g(x)=\nabla f(x),G(x)=\nabla^2f(x), 则我们有以下三个定理：

定理1：（一阶必要条件） 设f:D⊂Rn→R1f:D\subset R^n\rightarrow R^1在开集D上连续可微，若x∗∈Dx^\ast\in D是（1）上的局部极小点，则 g(x∗)=0(2)g(x^\ast)=0(2)

证明1： 反证法

假定g(x∗)≠0g(x^\ast)\neq0，即存在非0梯度，那么取下降的负梯度d=−g(x∗)d=-g(x^\ast)，则 g(x∗)Td=−g(x∗)Tg(x∗)<0g(x^\ast)^Td=-g(x^\ast)^Tg(x^\ast)<0 由于d是下降法向，从而在以x∗x^\ast为中心邻域存在δ>0\delta>0，使得 f(x∗+αd)<f(x∗),∀α∈(0,δ).f(x^\ast+\alpha d)<f(x^\ast),\forall\alpha\in(0,\delta). 那我们可以取δ‾=δ∥d∥\overline{\delta}=\delta\|d\|，因α<δ\alpha<\delta，故有： ∥αd∥=α∥d∥=δ‾\|\alpha d\|=\alpha\|d\|=\overline{\delta} 因此，存在x∗+αd∈N(x∗)x^\ast+\alpha d\in N(x^\ast)，使得 f(x∗+αd)<f(x∗)，f(x^\ast+\alpha d)<f(x^\ast)， 这与x∗x^\ast是局部极小点矛盾。

证明1完。

我们也可以用费马引理来更简单的说明这个定理：

引理1：费马引理：设函数f(x)f(x)在点x0x_0的某邻域U(x0)U(x_0)内有定义，并且在x0x_0处可导，如果对任意的x∈U(x0)x\in U(x_0)，有 f(x)≤f(x0)或f(x)≥f(x0)f(x)\le f(x_0)或f(x)\ge f(x_0) 那么f′(x0)=0f^\prime(x_0)=0。

推论1：函数ff在定义域Ω\Omega内的最大值和最小值只能在边界上，不可导的点，或驻点取得。

因此，对于连续可微函数，我们只需要在驻点和端点查找最小值即可。驻点即为一阶导数为0的点。

如果只是一阶导数是0，那么到底能不能确定这个点是极小值点呢？这就需要二阶导数。如果二阶导数的海森矩阵半正定那就是极小值点，半负定就是极大值点，不定就是鞍点。

定理2：（二阶必要条件）设f:D⊂Rn→R1f:D\subset R^n\rightarrow R^1在开集DD上二阶连续可微，若x∗∈Dx^\ast\in D是（1）的局部极小点，则： g(x∗)=0G(x∗)≥0(3)g(x^\ast)=0\quad G(x^\ast)\geq0 (3)

证明2： 反证法

(3)的前半部分已经在证明1得证。为了证明第二部分，即半正定，我们先假设G(x∗)G(x^\ast)不定，并设Nδ(x∗)N_\delta(x^\ast)是x∗x^\ast的邻域。有连续性可知，对所有x∈Nδ(x∗)x\in N_\delta(x^\ast)，G(x)G(x)不定。今选择ϵ\epsilon和向量d，使得x∗+ϵd∈Nδ(x∗)x^\ast+\epsilon d\in N_\delta(x^\ast)，且满足dTG(x∗+ϵd)d<0d^TG(x^\ast+\epsilon d)d<0。利用g(x∗)=0g(x^\ast)=0，有f(x+ϵd)f(x+\epsilon d)在x∗x^\ast处的泰勒展开式： f(x∗+ϵd)=f(x∗)+12ϵ2dTG(x∗+θϵd)df(x^\ast+\epsilon d)=f(x^\ast)+\frac{1}{2}\epsilon^2d^TG(x^\ast+\theta\epsilon d)d 其中，0≤θ≤10\leq\theta\leq1，从而，f(x∗+ϵd)<f(x∗)f(x^\ast+\epsilon d)<f(x^\ast)。这与x∗x^\ast是局部极小点矛盾。所以G(x∗)G(x^\ast)在邻域内必须大于等于0，即半正定。

满足g(x∗)=0g(x^\ast)=0的点x∗x^\ast称为函数ff的平稳点或驻点。如果g(x∗)=0g(x^\ast)=0，则有可能是极小点，也可能是极大点，也可能不是极值点，即鞍点。

定理3：（二阶充分条件）设f:D⊂Rn→R1f:D\subset R^n\rightarrow R^1在开集DD上二阶连续可微，则x∗∈Dx^\ast\in D是ff的一个严格局部极小点的充分条件是： g(x∗)=0且G(x∗)是正定矩阵(4)g(x^\ast)=0 且G(x^\ast)是正定矩阵(4)

一般地，目标函数的平稳点不一定是极小值点。但若目标函数是凸函数，则其平稳点就是其极小点，且为最小点。

定理4：（凸充分条件）设f:D⊂Rn→R1f:D\subset R^n\rightarrow R^1在开集DD上为凸函数，且f∈C1f\in C^1，则x∗x^\ast是总体极小点的充分必要条件是：g(x∗)=0g(x^\ast)=0

有约束条件的可行域不再是整个空间RnR^n，我们记可行域是Ω\Omega，即 min⁡x⃗f(x⃗)subjectto:x⃗∈Ω\min_{\vec x} f(\vec x)\\ subject\quad to:\quad \vec x ∈ \Omega 我们假定ff是连续可微函数，并且可行域是非空闭集。

我们在研究无约束优化一阶条件的基础上，特别想知道有哪些结论可以直接用到有约束情况下的。首先我们考虑可行方向：

定义1：可行方向：对于可行域Ω⊂Rn\Omega \subset R^n，有一个点x⃗∈Ω\vec x∈ \Omega，我们说向量d⃗\vec d是可行方向，如果存在一个步长tˉ>0，∀t∈[0,tˉ]，x⃗+td⃗∈Ω\bar t>0，\forall t ∈[0,\bar t]，\vec x+t\vec d ∈ \Omega.

对于存在可行方向的点，我们存在以下定理

定理5：有可行方向的有约束一阶条件：对于一个局部最优点x⃗\vec x，在这个点所有存在的可行方向f′(x⃗+td⃗)f'(\vec x+t\vec d)，我们都有f′(x⃗+td⃗)≥0f'(\vec x+t\vec d)≥0.

显然这个定理是无约束条件的类比版，只不过可行方向受到可行域限制。对于凸多边形，可行方向法是充分的，我觉得单纯性法就是可行方向法的一个应用。但是对于很多曲线，可行方向法就不适用了，例如： Ω={(x1,x2):x12+x22=1}\Omega=\{(x_1,x_2):x_1^2+x_2^2=1\} 每个点的可行方向都是0⃗\vec 0，这就没法做了。

为了克服可行方向法的弊端，我们使引入切锥。切锥是通过序列极限定义的：

定义2：切锥：给定非空闭集C⊂RnC \subset R^n。如果在CC内，存在收敛到x⃗\vec x的序列{x⃗k}\{\vec x^k\}和收敛到00的正数序列{τk}\{\tau^k\}，使得向量d⃗k=(x⃗k−x)/τk→d⃗\vec d^k=(\vec x^k-x)/\tau^k→\vec d。那么d⃗\vec d就是点x⃗\vec x的切线方向。点x⃗\vec x所有的切线方向组成的锥，就是切锥。 Tc(x⃗)={d⃗∈Rn:∃{x⃗k}∈C}和{τk}→0,d=lim⁡k→∞x⃗k−x⃗τk}T_c(\vec x)=\{\vec d ∈ R^n:\exists\{\vec x^k\}∈ C\}和\{\tau^k\}→0,d=\lim_{k→ ∞}\frac{\vec x^k-\vec x}{\tau^k}\}

这个定义主要在说什么呢？假设有一个闭集，然后有一点x⃗\vec x在闭集内，与此同时闭集内还有一组逐渐收敛于x⃗点的序列。在点\vec x点的序列。在点x附近（neighborhood）所有可以收敛的方向都是这个点的tangent direction。看完这个定义会发现，点$x在该闭集上的tangent cone一般来讲是从该点作切线，并包含闭集内部的向外延伸的锥。下图是几个例子：

切锥

Figure 1: 切锥

切锥

可行方向的约束作用在一些情况下略显严格，会导致空集的产生（例如非凸集合）。因此，我们需要适当放宽这个约束。因此，我们考虑用切锥来替代。在约束条件是凸集的情况下，切锥等同于可行方向，而对于非凸情况，切锥避免了空集的产生。因此，我们可以放宽定理5：

定理6：切锥下的有约束一阶条件：对于一个局部最优点x⃗\vec x，有 ∇f(x⃗)Td⃗≥0,∀d∈T(x⃗∣Ω)\nabla f(\vec x)^T\vec d≥0,\forall d ∈ T(\vec x|\Omega)

显然，无约束一阶条件是定理6的特殊情况。

详见《KKT与拉格朗日》

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

IXMRBAL.png

Figure 2: IXMRBAL.png

IXMRBAL.png

将这些模棱两可的方向的集合称为“关键锥”（critical cone） C(x⋆,γ)={w∈F(x)∣∇dj(x⋆)Tw=0,∀j∈A(x⋆) with λj>0}\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\} 其中 F(x)={p∣p 满足 {∇ci(x)Tp=0∀i∇dj(x)Tp≥0∀dj∈A(x)}\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. pT∇2L(x⋆,γ)p≥0∀p∈C(x⋆,γ)p^T\nabla^2\mathcal{L}(x^{\star},\gamma)p\ge 0 \quad \forall p\in\mathcal{C}(x^{\star},\gamma)
  • E1. 满足KKT条件
  • E2. pT∇2L(x⋆,γ)p>0∀p∈C(x⋆,γ)p^T\nabla^2\mathcal{L}(x^{\star},\gamma)p\gt 0 \quad \forall p\in\mathcal{C}(x^{\star},\gamma)

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

最优化二阶条件

Figure 3: 最优化二阶条件

最优化二阶条件

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