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

關(guān)于最優(yōu)性條件及二次規(guī)劃最優(yōu)性條件二次規(guī)劃重點(diǎn)：最優(yōu)性條件，二次規(guī)劃難點(diǎn):最優(yōu)性條件及應(yīng)用基本要求：理解可行方向、下降方向、有效約束等概念，掌握最優(yōu)性條件，并會(huì)用其求解有約束極值問題，掌握二次規(guī)劃模型及求解方法，理解序列二次規(guī)劃的原理和特點(diǎn)。第7講最優(yōu)性條件和二次規(guī)劃第2頁(yè),共28頁(yè)，2024年2月25日，星期天一、基本概念1起作用（緊）約束

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

Kuhn-Tucker條件

設(shè)x*是非線性規(guī)劃（I）的局部極小點(diǎn)有一階連續(xù)偏導(dǎo)而且X*處的所有起作用約束梯度線性無(wú)關(guān)，則存在數(shù)使得（7）成立第7頁(yè),共28頁(yè)，2024年2月25日，星期天成立（3）（7）并令即得第8頁(yè),共28頁(yè)，2024年2月25日，星期天

若x*是非線性規(guī)劃(II)的局部極小點(diǎn)，且x*點(diǎn)的所有起作用約束的梯度和線性無(wú)關(guān)。則存在向量使得（7）其中稱為廣義拉格朗日(Lagrange)乘子。第9頁(yè),共28頁(yè)，2024年2月25日，星期天庫(kù)恩—塔克條件是確定某點(diǎn)為最優(yōu)點(diǎn)的必要條件，只要是最優(yōu)點(diǎn)．且此處起作用約束的梯度線性無(wú)關(guān)。就必須滿足這個(gè)條件。但一般說(shuō)來(lái)它并不是充分條件，因而，滿足這個(gè)條件的點(diǎn)不一定就是最優(yōu)點(diǎn)。對(duì)于凸規(guī)劃，庫(kù)恩—塔克條件不但是最優(yōu)點(diǎn)存在的必要條件，它同時(shí)也是充分條件。第10頁(yè),共28頁(yè)，2024年2月25日，星期天某非線性規(guī)劃的可行解X(k)，假定此處有兩個(gè)起作用約束，若X（k）是極小點(diǎn)，則必處于的夾角之間，否則，X（k）點(diǎn)處必存在可行下降方向，它就不會(huì)是極小點(diǎn)。如右圖所示。庫(kù)恩—塔克條件的幾何解釋：且其梯度線性無(wú)關(guān)。第11頁(yè),共28頁(yè)，2024年2月25日，星期天三舉例例１求的極大值點(diǎn)。并驗(yàn)證其是否為K-T點(diǎn)。說(shuō)明理由。解：1如上圖所示，陰影部分為可行域R，紅色直線為目標(biāo)函數(shù)的等值線。顯然最大值點(diǎn)為（1，0）。R將原問題標(biāo)準(zhǔn)化x1x20第12頁(yè),共28頁(yè)，2024年2月25日，星期天K-T條件第13頁(yè),共28頁(yè)，2024年2月25日，星期天（1）（2）（3）（5）（4）（1）式為代入上式，得：故不是K-T點(diǎn)。第14頁(yè),共28頁(yè)，2024年2月25日，星期天的起作用約束為線性相關(guān)不是K-T點(diǎn)。自己驗(yàn)證是F-J點(diǎn)。第15頁(yè),共28頁(yè)，2024年2月25日，星期天例2用K-T條件，求解非線性規(guī)劃解：1驗(yàn)證該問題為凸規(guī)劃原問題標(biāo)準(zhǔn)化為半正定，負(fù)定是凸函數(shù)是凹函數(shù)故該問題為凸規(guī)劃。所以第16頁(yè),共28頁(yè)，2024年2月25日，星期天2求K-T點(diǎn)該問題的K-T條件為（1）（2）（3）（4）是K-T點(diǎn)(i)(ii)（5）討論第17頁(yè),共28頁(yè)，2024年2月25日，星期天(iii)將求出的帶入（6）式都不滿足故該問題有唯一的K-T點(diǎn)即為極小值點(diǎn)，(iv)第18頁(yè),共28頁(yè)，2024年2月25日，星期天二次規(guī)劃的數(shù)學(xué)模型可表示為：二次規(guī)劃的數(shù)學(xué)模型變形為：（I）（II）二次規(guī)劃(5.2)第19頁(yè),共28頁(yè)，2024年2月25日，星期天其中：書中為行向量第20頁(yè),共28頁(yè)，2024年2月25日，星期天（III）第21頁(yè),共28頁(yè)，2024年2月25日，星期天例1

求解二次規(guī)劃問題（例5-3）解：寫出問題對(duì)應(yīng)的矩陣形式如下：這就形成了式（III）所需要的全部信息：（III）第22頁(yè),共28頁(yè)，2024年2月25日，星期天為解此方程組，在第1個(gè)方程和第2個(gè)方程中引入人工變量R1和R2，目標(biāo)函數(shù)為maxz=-R1-R2，對(duì)應(yīng)的初始單純形表見表5-1。第23頁(yè),共28頁(yè)，2024年2月25日，星期天第24頁(yè),共28頁(yè)，2024年2月25日，星期天第25頁(yè),共28頁(yè)，2024年2月25日，星期天例2求解二次規(guī)劃（自己練習(xí)）第26頁(yè),共28頁(yè)，2024年2月25日，星期天序列二次規(guī)劃(5.3)

序列二次規(guī)劃的思路序列二次規(guī)劃（SQP）算法是將復(fù)雜的有約束極值問題轉(zhuǎn)化為比較簡(jiǎn)單的二次規(guī)劃（QP）問題求解的算法。利用泰勒展開把有約束極值問題的目標(biāo)函數(shù)在迭代點(diǎn)展開成二次函數(shù)，將約束條件在迭代點(diǎn)展開成線性函數(shù)得到如下二次規(guī)