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

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

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

Kuhn-Tucker條件

設(shè)x*是非線性規(guī)劃（I）的局部極小點有一階連續(xù)偏導而且X*處的所有起作用約束梯度線性無關(guān)，則存在數(shù)使得（7）成立第7頁，共28頁，2022年，5月20日，0點45分，星期五成立（3）（7）并令即得第8頁，共28頁，2022年，5月20日，0點45分，星期五

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

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

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