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

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

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

Kuhn-Tucker條件

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

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

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

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