非線性規劃指的是目標函數 f 是非線性函數，或者約束集 X 是由非線性的等式和不等式給定的優化問題。一直以來，優化理論和方法都在工程實踐以及管理決策等方面有著重要的應用，例如近年來如日中天的機器學習方法中，對loss function的的優化的梯度下降方法和牛頓方法等都是優化理論中的經典方法。

在接下來的一系列文章中，我會不斷更新非線性規劃的相關理論知識以及一些重要的優化方法，我相信當進一步了解優化理論之後，無論是對於傳統的機器學習方法抑或是深度學習方法的學習與研究都將是大有裨益的！

我們首先來看下面一個問題：

minmize f(x) s.t. xin X

這是一個簡單的函數最小化問題，決策變數 x 可以是離散或者連續的，其可行域為 X ，當目標函數 f 是一個非線性函數時候這就是一個非線性優化問題，那麼如果要求解這個問題我們需要哪些條件呢？

一、最優性條件

我們在高中的時候都學過導數的概念，對於一個複雜函數可以通過對其求導的方式求解其極值，在這裡我們將極值的概念進一步擴展。

在這裡我們首先討論無約束情況下的優化問題

1.1 局部最小值和全局最小值

當向量 x^{*} 是 f 的一個無約束局部最小值點，那麼在該點處的鄰域內存在 varepsilon>0 滿足：

f(x^{*})leq f(x),qquad forall x,||x-x^{*}||<varepsilon

在這裡 ||x|| 為歐式範數，即n維向量空間上的距離。

而當向量 x^{*} 被稱作 f 無約束的全局最小值點，是指該點的函數值不大於其他所有點的函數值，即滿足：

f(x^{*})leq f(x),qquad forall xin R^{n}

如下圖所示，圓形區域內的就是局部最小值點，而矩形區域內的就是全局最小點：

需要補充的是，如果對於上述的不等式都有 x e x^{*} ，那麼 最小值點x^{*} 就被稱之為「嚴格」的，即嚴格局部最小、嚴格全局最小。

1.2 最優性的必要條件

如果目標函數是可微的，那麼我們可以利用梯度和泰勒展開來探索最優性的必要條件，首先我們假定某個向量 x^{*} 的一個微小梯度為 Delta x ，那麼根據一階的泰勒展開我們可以得到：

f(x^{*}+Delta x) -f(x^{*})approx abla f(x^{*})^{T}Delta x

如果 x^{*} 是一個無約束的局部最小值點，那麼我們可以得到：

abla f(x^{*})^{T}Delta xgeq0

在這裡因為 Delta x 是可正可負的，所以我們可以得到 abla f(x^{*})geq0 以及 abla f(x^{*})leq0 ，很顯然我們得到了最優性的第一個條件--一階導數為0：

abla f(x^{*})=0

現在我們接著進行二階泰勒展開：

f(x^{*}+Delta x) -f(x^{*})approx abla f(x^{*})^{T}Delta x+frac{1}{2}Delta x^{T} abla ^{2}f(x^{*})Delta x

應用第一個條件的結論我們可以得到 Delta x^{T} abla ^{2}f(x^{*})Delta xgeq0 ,因此可知 abla ^{2}f(x^{*}) 必定是半正定的。

綜上可知最優性的必要條件為： abla f(x^{*})=0 且 abla ^{2}f(x^{*})succeq0 。

1.3 二階最優性的充分條件

假設向量 x^{*} 滿足一階最優性的必要條件，即 abla f(x^{*})=0 ，同時它又滿足二階最優性必要條件的增強形式: abla ^{2}f(x^{*}) 為正定（即Hessian矩陣正定，而不是我們之前所說的半正定形式），那麼對於所有 Delta x e 0 我們都有： Delta x^{T} abla ^{2}f(x^{*})Delta x>0 .。

下面將通過嚴格的證明來說明其充分性：

首先我們令 lambda 為 abla ^{2}f(x^{*}) 最小的特徵值，根據正定矩陣的性質我們知道 lambda>0 ，接著我們對所有的 x-x^{*}=din R^{n} 我們基於條件 abla f(x^{*})=0 對f 二階泰勒展開有：

f(x^{*}+d)-f(x^{*})= abla f(x^{*})^{T}d+frac{1}{2}d^{T} abla^{2}f(x^{*})d+o(||d||^{2})

qquadqquadqquadqquadgeq frac{lambda}{2}||d||^{2}+o(||d||^{2}) （1）

qquadqquadqquadqquad=(frac{lambda}{2}+frac{o(||d||^{2})}{||d||^{2}})||d||^{2}

qquadqquadqquadqquadgeqfrac{lambda}{2}||d||^{2}=frac{lambda}{2}||x-x^{*}||^{2}>0

所以一定存在一個標量 varepsilon>0 ，當 forall x 使得 ||x-x^{*}||<varepsilon 滿足上述公式推導的結果，這時候我們可以說 x^{*} 就是在其鄰域內的最小值點，即局部最小值點。

對於證明步驟（1）用到了一個關於實對稱矩陣的相關性質，即：

forall yin R^{n} ，都有 lambda _{min}||y||^{2}leq y^{T}Ayleqlambda_{max}||y||^{2}

證明：

首先記A的n個相互正交的單位特徵向量為 x_{1},x_{2},...x_{n} ，那麼我們定義 y=sum_{i=1}^{n}{xi _{i}x_{i}} ,

所以根據向量的正交性以及單位向量 ||x_{i}||=1 的性質可以推導得到：

y^{T}Ay = (sum_{i=1}^{n}{xi _{i}x_{i}^{T}})A(sum_{i=1}^{n}{xi _{i}x_{i}})

qquad =(sum_{i=1}^{n}{xi _{i}x_{i}^{T}})(sum_{i=1}^{n}{lambda_{i}xi _{i}x_{i}})

qquad =sum_{i=1}^{n}{lambda_{i}|xi_{i}|^{2}||x_{i}||}=sum_{i=1}^{n}{lambda_{i}|xi_{i}|^{2}}

同理我們還可以得到 y^{T}y=sum_{i=1}^{n}{|xi_{i}|^{2}}

所以 lambda _{min}||y||^{2}=sum_{i=1}^{n}{lambda _{min}x_{i}}leq y^{T}Ay=sum_{i=1}^{n}{lambda _{max}x_{i}}leqlambda_{max}||y||^{2}

二、 凸集和凸函數

在討論非線性規劃時，為我們不得不提到關於凸函數優化（又稱凸優化）的概念，即目標函數是凸函數的優化問題。凸性是非線性規劃中的一個最核心的概念，事實上當我們可以證明我們所要優化的函數是一個凸函數時，那麼則說明這個問題可以很好的解決，所以大量有效的優化方法也是針對凸函數的。

Definition：凸集

如果 R^{n} 的子集C滿足：

qquadqquad alpha x+(1-alpha)y in C,qquadforall x,yin C,forallalphain[0,1]

那麼我們可以說C是一個凸集

Definition: 凸函數

設C是 R^{n} 的凸子集，當函數 f 滿足：

qquad f(alpha+(1-alpha)y)leqalpha f(x)+(1-alpha)f(y),quad forall x,y in C,forall alphain [0,1] 那麼我們可以說 f 是一個凸函數

之所以我們會提出凸函數的概念，那是因為凸函數有一個很重要的性質，那就是當目標函數為凸時，局部最小值點和全局最小值點是一致的。

下面我將用反證法證明這一結論：

我們假設 x 是 f 的一個局部最小值點，但不是全局最小值點，那麼必定存在一個 y e x ，使得 f(y)<f(x) ，根據凸函數定義我們可以知道：

f(alpha x+(1-alpha)y)leqalpha f(x)+(1-alpha)f(y)<f(x)

上面這個式子說明了在 x 的鄰域內存在更小值點，這與我們的假設相矛盾。

接著要補充的一個性質，那就是 f 是嚴格凸的，那麼 f 最多只有一個全局最小值點，至於證明也很簡單，在這裡就不再具體展開。

現在我們再考慮一個問題，當目標函數 f 是凸函數，那麼最優性的條件會不會發生改變呢？事實上當 f 是凸函數，那麼向量 x^{*}in X 是 f 在 X 上是全局最優解的充要條件就是：

abla f(x^{*})=0 ，很顯然，條件變得寬鬆了。

這個性質在此也不進行展開證明~

三、總結

在這篇文章中主要介紹了最優化的一些條件以及凸集和凸函數的相關概念以及它們之間的聯繫，那麼我們情不自禁地思考：為什麼要探索最優化的條件呢？

在這裡可以給出幾個參考的想法:

1、它給我們提供了一個理論基礎來幫助我們判斷我們所求的解是否是最優的。

2、它給出了一個最優點所需要滿足的必要條件。

3、幫助我們對大量的候選解進行排除，減少工作量。

當然無法否認的是在很多時候我們很難利用最優化條件來得到優化問題的最優解，有時候甚至求解 abla f(x)=0 不亞於對原函數進行求解。所以在接下來的文章中我也會接著討論一些迭代求解的方法，以數值解來逼近最優解。但是我們仍要記住：最優性條件是很多演算法發展和分析的基礎，譬如充分條件在不同演算法的收斂速度的比較中發揮了重要的作用！

推薦閱讀：

相关文章