最優(yōu)性條件及二次規(guī)劃

最優(yōu)性條件及二次規(guī)劃一、基本概念1起作用(緊)約束

就是(I)得可行解,若則稱為處得起作用(緊)約束。記處起作用(緊)約束得下標(biāo)集2可行方向記或時有稱為處得可行方向?yàn)?I)或(II)得可行域定義:最優(yōu)性條件(5、1)p若就是得任一可行方向,則有3下降方向時有稱為處得下降方向若就是得任一下降方向,則有若既滿足(1)式又滿足(2)式則稱為得下降可行方向定理1為(I)得局部極小值點(diǎn),在處可微,在處可微在處連續(xù)則在處不存在可行下降方向。即不存在向量同時成立判別條件判別條件定義:二、最優(yōu)性條件1、Gordan引理設(shè)為個維向量,不存在向量P使得成立得充要條件就是存在不全為零得非負(fù)數(shù),使得成立2、FritzeJohn定理(3)成立1(4)(5)(6)3

Kuhn-Tucker條件

設(shè)x*就是非線性規(guī)劃(I)得局部極小點(diǎn)有一階連續(xù)偏導(dǎo)而且X*處得所有起作用約束梯度線性無關(guān),則存在數(shù)使得(7)成立成立(3)(7)并令即得

若x*就是非線性規(guī)劃(II)得局部極小點(diǎn),且x*點(diǎn)得所有起作用約束得梯度與線性無關(guān)。則存在向量使得(7)其中稱為廣義拉格朗日(Lagrange)乘子。庫恩—塔克條件就是確定某點(diǎn)為最優(yōu)點(diǎn)得必要條件,只要就是最優(yōu)點(diǎn)、且此處起作用約束得梯度線性無關(guān)。就必須滿足這個條件。但一般說來它并不就是充分條件,因而,滿足這個條件得點(diǎn)不一定就就是最優(yōu)點(diǎn)。對于凸規(guī)劃,庫恩—塔克條件不但就是最優(yōu)點(diǎn)存在得必要條件,它同時也就是充分條件。某非線性規(guī)劃得可行解X(k),假定此處有兩個起作用約束,若X(k)就是極小點(diǎn),則必處于得夾角之間,否則,X(k)點(diǎn)處必存在可行下降方向,它就不會就是極小點(diǎn)。如右圖所示。庫恩—塔克條件得幾何解釋:且其梯度線性無關(guān)。三舉例例１求得極大值點(diǎn)。并驗(yàn)證其就是否為K-T點(diǎn)。說明理由。解:1如上圖所示,陰影部分為可行域R,紅色直線為目標(biāo)函數(shù)得等值線。顯然最大值點(diǎn)為(1,0)。R將原問題標(biāo)準(zhǔn)化x1x20大家學(xué)習(xí)辛苦了，還是要堅持繼續(xù)保持安靜K-T條件(1)(2)(3)(5)(4)(1)式為代入上式,得:故不就是K-T點(diǎn)。得起作用約束為線性相關(guān)不就是K-T點(diǎn)。自己驗(yàn)證就是F-J點(diǎn)。例2用K-T條件,求解非線性規(guī)劃解:1驗(yàn)證該問題為凸規(guī)劃原問題標(biāo)準(zhǔn)化為半正定,負(fù)定就是凸函數(shù)就是凹函數(shù)故該問題為凸規(guī)劃。所以2求K-T點(diǎn)該問題得K-T條件為(1)(2)(3)(4)就是K-T點(diǎn)(i)(ii)(5)討論(iii)將求出得帶入(6)式都不滿足故該問題有唯一得K-T點(diǎn)即為極小值點(diǎn),(iv)二次規(guī)劃得數(shù)學(xué)模型可表示為:二次規(guī)劃得數(shù)學(xué)模型變形為:(I)(II)二次規(guī)劃(5、2)其中:書中為行向量(III)例1

求解二次規(guī)劃問題(例5-3)解:寫出問題對應(yīng)得矩陣形式如下:這就形成了式(III)所需要得全部信息:(III