拉格朗日鞍點

基本介紹

拉格朗日鞍點(Lagrange saddle point)是非線性規(guī)劃問題中滿足特定條件的點。對于非線性規(guī)劃問題(NP)(參見下文“非線性規(guī)劃”)，它的拉格朗日函數(shù)是指目標(biāo)函數(shù)和約束條件中函數(shù)的如下線性組合：

其中滿足條件

的點稱為(NP)的拉格朗日鞍點。

定理 設(shè)是凸優(yōu)化問題的KKT點，則為對應(yīng)的拉格朗日函數(shù)的鞍點，同時也是該凸優(yōu)化問題的全局極小點1。

鞍點定理

鞍點定理(saddle point theorem)是關(guān)于拉格朗日函數(shù)的鞍點與約束優(yōu)化問題最優(yōu)點之間的關(guān)系定理。鞍點是函數(shù)平穩(wěn)點的一種，應(yīng)用鞍點的性質(zhì)，可以推得最優(yōu)點的充分條件如下：對于約束極小化問題，如果其拉格朗日函數(shù)的鞍點存在，即有，那么相應(yīng)的必是該約束極小化問題的最優(yōu)點。由于沒有涉及函數(shù)的凸性與可微性，適用范圍較廣，但因求解鞍點很困難， 且即使原問題的最優(yōu)點存在，它的拉格朗日函數(shù)也不一定有鞍點，故目前并不實用2。

相關(guān)概念

非線性規(guī)劃

非線性規(guī)劃(nonlinear programming)是數(shù)學(xué)規(guī)劃的一個重要分支，它研究目標(biāo)函數(shù)或約束條件中的函數(shù)有一個或多個是變量的非線性函數(shù)的數(shù)學(xué)規(guī)劃問題。其研究的問題，稱為非線性規(guī)劃問題，簡稱非線性規(guī)劃，記為(NP)。極小化形式的非線性規(guī)劃問題的數(shù)學(xué)模型為

其中是n維歐氏空間中的向量，是目標(biāo)函數(shù)，和是約束條件，并且在和中至少有一個是的非線性函數(shù)，因q個等式約束可以化成與它等價的個不等式約束

故非線性規(guī)劃的數(shù)學(xué)模型可寫成另一形式，其中。

拉格朗日法

拉格朗日法(Lagrange method)是利用拉格朗日函數(shù)，把約束非線性規(guī)劃問題轉(zhuǎn)化為無約束極小化問題求解的一種方法。對于非線性規(guī)劃問題

設(shè)均具有一階連續(xù)偏導(dǎo)數(shù)，將拉格朗日函數(shù)表示為上述非線性規(guī)劃問題的目標(biāo)函數(shù)與加權(quán)約束函數(shù)之和：

其中是拉格朗日乘子。令其各偏導(dǎo)數(shù)為零，得到一方程組，解此方程組可得到非線性規(guī)劃問題的最優(yōu)解3。