基本介紹
拉格朗日鞍點(Lagrange saddle point)是非線性規劃問題中滿足特定條件的點。對於非線性規劃問題(NP)(參見下文“非線性規劃”),它的拉格朗日函式是指目標函式和約束條件中函式的如下線性組合:
![拉格朗日鞍點](/img/4/1c7/wZwpmLwMjM1YTO3YzMzATN1UTM1QDN5MjM5ADMwAjMwUzL2MzL1gzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![拉格朗日鞍點](/img/c/3c6/wZwpmL3IzN3gTN5AjMzATN1UTM1QDN5MjM5ADMwAjMwUzLwIzL2QzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
其中滿足條件
![拉格朗日鞍點](/img/d/b1a/wZwpmL4gjM4kjNzEjMzATN1UTM1QDN5MjM5ADMwAjMwUzLxIzL4QzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![拉格朗日鞍點](/img/c/335/wZwpmL3YjMzITO2YzMzATN1UTM1QDN5MjM5ADMwAjMwUzL2MzL3EzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
![拉格朗日鞍點](/img/b/ff6/wZwpmLyETM3czMwkjMzATN1UTM1QDN5MjM5ADMwAjMwUzL5IzL4AzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
的點稱為(NP)的 拉格朗日鞍點。
![拉格朗日鞍點](/img/b/ff6/wZwpmLyETM3czMwkjMzATN1UTM1QDN5MjM5ADMwAjMwUzL5IzL4AzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![拉格朗日鞍點](/img/b/ff6/wZwpmLyETM3czMwkjMzATN1UTM1QDN5MjM5ADMwAjMwUzL5IzL4AzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![拉格朗日鞍點](/img/c/f0b/wZwpmLxUjNyATN0kTMzEzM1UTM1QDN5MjM5ADMwAjMwUzL5EzL4QzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
定理 設是凸最佳化問題的KKT點,則為對應的拉格朗日函式的鞍點,同時也是該凸最佳化問題的全局極小點 。
鞍點定理
![拉格朗日鞍點](/img/b/ff6/wZwpmLyETM3czMwkjMzATN1UTM1QDN5MjM5ADMwAjMwUzL5IzL4AzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![拉格朗日鞍點](/img/d/b1a/wZwpmL4gjM4kjNzEjMzATN1UTM1QDN5MjM5ADMwAjMwUzLxIzL4QzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![拉格朗日鞍點](/img/c/f0b/wZwpmLxUjNyATN0kTMzEzM1UTM1QDN5MjM5ADMwAjMwUzL5EzL4QzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
鞍點定理(saddle point theorem)是關於拉格朗日函式的鞍點與約束最佳化問題最優點之間的關係定理。鞍點是函式平穩點的一種,套用鞍點的性質,可以推得最優點的充分條件如下:對於約束極小化問題,如果其拉格朗日函式的鞍點存在,即有,那么相應的必是該約束極小化問題的最優點。由於沒有涉及函式的凸性與可微性,適用範圍較廣,但因求解鞍點很困難, 且即使原問題的最優點存在,它的拉格朗日函式也不一定有鞍點,故目前並不實用 。
相關概念
非線性規劃
非線性規劃(nonlinear programming)是數學規劃的一個重要分支,它研究目標函式或約束條件中的函式有一個或多個是變數的非線性函式的數學規劃問題。其研究的問題,稱為 非線性規劃問題,簡稱 非線性規劃,記為( NP)。極小化形式的非線性規劃問題的數學模型為
![拉格朗日鞍點](/img/9/cfe/wZwpmL0UTMxkDMxcjMzATN1UTM1QDN5MjM5ADMwAjMwUzL3IzLxYzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
![拉格朗日鞍點](/img/c/6df/wZwpmL4MDO1UDM5MjMzATN1UTM1QDN5MjM5ADMwAjMwUzLzIzL0gzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![拉格朗日鞍點](/img/5/b84/wZwpmL4cTO0kjM5EzNwMzM1UTM1QDN5MjM5ADMwAjMwUzLxczLyczLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![拉格朗日鞍點](/img/3/78e/wZwpmLyMDNzQDM5EjNxADN0UTMyITNykTO0EDMwAjMwUzLxYzL2AzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![拉格朗日鞍點](/img/b/59b/wZwpmL1gDNzQDM5MzMzATN1UTM1QDN5MjM5ADMwAjMwUzLzMzL3EzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
![拉格朗日鞍點](/img/4/b28/wZwpmL4YzM5ETN3EjMzATN1UTM1QDN5MjM5ADMwAjMwUzLxIzLyQzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![拉格朗日鞍點](/img/2/916/wZwpmL0ETOwUDOxQjMzATN1UTM1QDN5MjM5ADMwAjMwUzL0IzL2MzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![拉格朗日鞍點](/img/4/b28/wZwpmL4YzM5ETN3EjMzATN1UTM1QDN5MjM5ADMwAjMwUzLxIzLyQzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![拉格朗日鞍點](/img/1/036/wZwpmL3QzM5YjNzMjM0EDN0UTMyITNykTO0EDMwAjMwUzLzIzL3EzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![拉格朗日鞍點](/img/4/b28/wZwpmL4YzM5ETN3EjMzATN1UTM1QDN5MjM5ADMwAjMwUzLxIzLyQzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![拉格朗日鞍點](/img/b/c35/wZwpmL2gDN2EjMyEjMzATN1UTM1QDN5MjM5ADMwAjMwUzLxIzL0YzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
其中是n維歐氏空間中的向量,是目標函式,和是約束條件,並且在和中至少有一個是的非線性函式,因q個等式約束可以化成與它等價的個不等式約束
![拉格朗日鞍點](/img/2/363/wZwpmL4YzN1cDM4gjMzATN1UTM1QDN5MjM5ADMwAjMwUzL4IzL2IzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![拉格朗日鞍點](/img/0/594/wZwpmL4UTN2YjN4MjMzATN1UTM1QDN5MjM5ADMwAjMwUzLzIzLzQzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![拉格朗日鞍點](/img/4/d3e/wZwpmL4ATOzMDN2MzMzATN1UTM1QDN5MjM5ADMwAjMwUzLzMzL2QzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
故非線性規劃的數學模型可寫成另一形式,其中。
拉格朗日法
拉格朗日法(Lagrange method)是利用拉格朗日函式,把約束非線性規劃問題轉化為無約束極小化問題求解的一種方法。對於非線性規劃問題
![拉格朗日鞍點](/img/5/adb/wZwpmL2EDMycTO2IjMzATN1UTM1QDN5MjM5ADMwAjMwUzLyIzLyAzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
![拉格朗日鞍點](/img/2/916/wZwpmL0ETOwUDOxQjMzATN1UTM1QDN5MjM5ADMwAjMwUzL0IzL2MzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
設均具有一階連續偏導數,將拉格朗日函式表示為上述非線性規劃問題的目標函式與加權約束函式之和:
![拉格朗日鞍點](/img/6/a00/wZwpmLwMTNyUTO2IjMzATN1UTM1QDN5MjM5ADMwAjMwUzLyIzL0AzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![拉格朗日鞍點](/img/a/bb3/wZwpmL3QzN5cDN4kTMzATN1UTM1QDN5MjM5ADMwAjMwUzL5EzLwAzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
其中是拉格朗日乘子。令其各偏導數為零,得到一方程組,解此方程組可得到非線性規劃問題的最優解 。