信息與通信工程學(xué)院莊伯金bjzhuang@1凸優(yōu)化理論與應(yīng)用莊伯金B(yǎng)jzhuang@信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@2優(yōu)化理論概述什么是優(yōu)化問題？ObjectivefunctionConstraintfunctions信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@3幾類經(jīng)典的優(yōu)化問題線性規(guī)劃問題最小二乘問題凸優(yōu)化問題凸優(yōu)化問題理論上有有效的方法進(jìn)行求解！信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@4本課程的主要內(nèi)容理論部分凸集和凸函數(shù)凸優(yōu)化問題對偶問題應(yīng)用部分逼近與擬合統(tǒng)計估計幾何問題算法部分非約束優(yōu)化方法等式約束優(yōu)化方法內(nèi)點法信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@5熟悉了解凸優(yōu)化理論的基本原理和基本方法；掌握實際問題轉(zhuǎn)化為凸優(yōu)化問題的基本方法；掌握最優(yōu)化問題的經(jīng)典算法。課程要求信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@6參考書目StephenBoydandLievenVandenberghe,“ConvexOptimization”,CambridgeUniversityPress.袁亞湘、孫文瑜，“最優(yōu)化理論與方法”，科學(xué)出版社，1999。

信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@7凸優(yōu)化理論與應(yīng)用第一章凸集信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@8仿射集(Affinesets)直線的表示：線段的表示：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@9仿射集(Affinesets)仿射集的定義：過集合C內(nèi)任意兩點的直線均在集合C內(nèi)，則稱集合C為仿射集。仿射集的例：直線、平面、超平面信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@10仿射集仿射包：包含集合C的最小的仿射集。仿射維數(shù)：仿射包的維數(shù)。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@11仿射集內(nèi)點（interior）：相對內(nèi)點（relativeinterior）：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@12凸集(ConvexSets)凸集的定義：集合C內(nèi)任意兩點間的線段均在集合C內(nèi)，則稱集合C為凸集。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@13凸集凸包的定義：包含集合C的最小的凸集。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@14錐(Cones)錐的定義：凸錐的定義：集合C既是凸集又是錐。錐包的定義：集合C內(nèi)點的所有錐組合。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@15超平面和半空間超平面(hyperplane)：半空間(Halfspace)：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@16歐氏球和橢球歐氏球(euclideanball):橢球(ellipsoid):信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@17范數(shù)球和范數(shù)錐范數(shù)(norm)：范數(shù)球(normball)：范數(shù)錐(normcone)：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@18多面體(Polyhedra)多面體：單純形(simplex)：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@19半正定錐(Positivesemidefinitecone)n階對稱矩陣集：n階半正定矩陣集：n階正定矩陣集：n階半正定矩陣集為凸錐！信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@20保持凸性的運(yùn)算集合交運(yùn)算仿射變換透視/投射函數(shù)(perspectivefunction)信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@21保持凸性的運(yùn)算線性分式函數(shù)(linear-fractionalfunction)信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@22真錐(propercone)真錐的定義：錐滿足如下條件K具有內(nèi)點K內(nèi)不含直線信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@23廣義不等式真錐下的偏序關(guān)系：例：逐項不等式矩陣不等式廣義不等式嚴(yán)格廣義不等式信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@24廣義不等式的性質(zhì)信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@25嚴(yán)格廣義不等式的性質(zhì)信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@26最值和極值最小元的定義：設(shè)，對，都有成立，則稱為的最小元。極小元的定義：設(shè)，對于，若，則成立，則稱為的極小元。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@27分割超平面(separatinghyperplane)定理：設(shè)和為兩不相交凸集，則存在超平面將和分離。即：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@28支撐超平面(supportinghyperplane)定義：設(shè)集合，為邊界上的點。若存在，滿足對任意，都有成立，則稱超平面為集合在點處的支撐超平面。定理：凸集邊界上任意一點均存在支撐超平面。定理：若一個閉的非中空集合，在邊界上的任意一點存在支撐超平面，則該集合為凸集。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@29對偶錐(dualcone)對偶錐的定義：設(shè)為錐，則集合稱為對偶錐。對偶錐的性質(zhì)：真錐的對偶錐仍然是真錐！信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@30對偶廣義不等式廣義不等式與對偶等價性質(zhì)最小元的對偶特性：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@31對偶廣義不等式極小元的對偶特性反過來不一定成立！信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@32作業(yè)P602.8P602.10P602.14P622.16P622.18P642.30P642.31P642.33信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@33凸優(yōu)化理論與應(yīng)用第二章凸函數(shù)信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@34凸函數(shù)的定義1.定義域為凸集；2.，有凸函數(shù)的定義：函數(shù)，滿足凸函數(shù)的擴(kuò)展定義：若為凸函數(shù)，則可定義其擴(kuò)展函數(shù)為凸函數(shù)的擴(kuò)展函數(shù)也是凸函數(shù)！信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@35凸函數(shù)的一階微分條件若函數(shù)的定義域為開集，且函數(shù)一階可微，則函數(shù)為凸函數(shù)當(dāng)且僅當(dāng)為凸集，且對信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@36凸函數(shù)的二階微分條件若函數(shù)的定義域為開集，且函數(shù)二階可微，則函數(shù)為凸函數(shù)當(dāng)且僅當(dāng)為凸集，且對，其Hessian矩陣信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@37凸函數(shù)的例冪函數(shù)負(fù)對數(shù)函數(shù)負(fù)熵函數(shù)范數(shù)函數(shù)指數(shù)函數(shù)信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@38凸函數(shù)的例信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@39下水平集(sublevelset)定理：凸函數(shù)的任一下水平集均為凸集。任一下水平集均為凸集的函數(shù)不一定為凸函數(shù)。 稱為的下水平集。定義：集合信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@40函數(shù)上半圖(epigraph)定理：函數(shù)為凸函數(shù)當(dāng)且僅當(dāng)?shù)纳习雸D為凸集。 稱為函數(shù)的上半圖。定義：集合信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@41Jensen不等式為凸函數(shù)，則有：Jensen不等式的另外形式：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@42保持函數(shù)凸性的算子凸函數(shù)的逐點最大值凸函數(shù)與仿射變換的復(fù)合凸函數(shù)的非負(fù)加權(quán)和信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@43保持函數(shù)凸性的算子復(fù)合運(yùn)算最小值算子凸函數(shù)的透視算子信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@44共軛函數(shù)(conjugatefunction)定義：設(shè)函數(shù)，其共軛函數(shù)，定義為共軛函數(shù)的例共軛函數(shù)具有凸性！信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@45共軛函數(shù)的性質(zhì)Fenchel’sinequality性質(zhì)：若為凸函數(shù)，且的上半圖是閉集，則有性質(zhì)：設(shè)為凸函數(shù)，且可微，對于，若 則信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@46準(zhǔn)凸函數(shù)(quasiconvexfunction)準(zhǔn)凸函數(shù)的例定義：設(shè)函數(shù)，若函數(shù)的定義域和任意下水平集

則稱函數(shù)為準(zhǔn)凸函數(shù)。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@47準(zhǔn)凸函數(shù)的判定定理定理：函數(shù)為準(zhǔn)凸函數(shù)，當(dāng)且僅當(dāng)為凸集，且對，有定理：若函數(shù)一階可微，則為準(zhǔn)凸函數(shù)，當(dāng)且僅當(dāng)為凸集，且對，有 ，有定理：若函數(shù)二階可微，且滿足對 則函數(shù)準(zhǔn)凸函數(shù)。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@48最小值函數(shù)非負(fù)權(quán)值函數(shù)的最大值函數(shù)保持準(zhǔn)凸性的算子復(fù)合函數(shù)信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@49準(zhǔn)凸函數(shù)的凸函數(shù)族表示若為準(zhǔn)凸函數(shù)，根據(jù)的任意下水平集，我們可以構(gòu)造一個凸函數(shù)族，使得性質(zhì)：若為準(zhǔn)凸函數(shù)的凸函數(shù)族表示，對每一個，若，則有信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@50對數(shù)凸函數(shù) 為凸集 為凸函數(shù)。定義：函數(shù)稱為對數(shù)凸函數(shù)，若函數(shù)滿足：定理：函數(shù)的定義域為凸集，且，則為對數(shù)凸函數(shù)，當(dāng)且僅當(dāng)對有對數(shù)凸函數(shù)的例信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@51對數(shù)凸函數(shù)和凹函數(shù)的性質(zhì)性質(zhì)：對數(shù)凸性與凹性對函數(shù)乘積和正數(shù)數(shù)乘運(yùn)算均保持封閉。定理：函數(shù)二階可微，則為對數(shù)凸函數(shù)當(dāng)且僅當(dāng)性質(zhì)：對數(shù)凸性對函數(shù)加運(yùn)算保持封閉。但對數(shù)凹性對函數(shù)加運(yùn)算不封閉。推論：函數(shù)對每一個在上對數(shù)凸，則函數(shù)也是對數(shù)凸函數(shù)。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@52對數(shù)凸函數(shù)和凹函數(shù)的性質(zhì)定理：函數(shù)為對數(shù)凹函數(shù)，則函數(shù)是對數(shù)凹函數(shù)。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@53廣義不等式下的凸性廣義單調(diào)性的定義：設(shè)為真錐，函數(shù)稱為單調(diào)增，若函數(shù)滿足：廣義凸函數(shù)的定義：設(shè)為真錐，函數(shù)稱為凸，若函數(shù)滿足對 均有定理(對偶等價)：函數(shù)為凸函數(shù)，當(dāng)且僅當(dāng)對所有，為凸函數(shù)。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@54作業(yè)(1)P1163.16P1163.21信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@55作業(yè)(2)P1213.41P1223.49(1)(2)信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@56凸優(yōu)化理論與應(yīng)用第三章凸優(yōu)化信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@57優(yōu)化問題的基本形式優(yōu)化問題的基本描述：優(yōu)化變量不等式約束等式約束無約束優(yōu)化信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@58優(yōu)化問題的基本形式最優(yōu)化值最優(yōu)化解優(yōu)化問題的域可行點(解)(feasible)滿足約束條件可行域(可解集)所有可行點的集合信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@59局部最優(yōu)問題局部最優(yōu)問題信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@60優(yōu)化問題的等價形式(1)定理：若則原優(yōu)化問題與以下優(yōu)化問題等價信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@61優(yōu)化問題的等價形式(2)定理：設(shè)為一一對應(yīng)，且則原優(yōu)化問題與以下優(yōu)化問題等價信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@62優(yōu)化問題的等價形式(3)定理：設(shè)為嚴(yán)格單調(diào)增函數(shù)；滿足當(dāng)且僅當(dāng)；滿足當(dāng)且僅當(dāng)。則原優(yōu)化問題與以下優(yōu)化問題等價信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@63優(yōu)化問題的等價形式(4)定理：原優(yōu)化問題與以下優(yōu)化問題等價稱為松弛變量信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@64優(yōu)化問題的等價形式(5)定理：設(shè)滿足等式成立，當(dāng)且僅當(dāng)。則原優(yōu)化問題與以下優(yōu)化問題等價信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@65可分離變量優(yōu)化問題性質(zhì)： 其中 可以分離變量定理：優(yōu)化問題信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@66優(yōu)化問題的上半圖形式信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@67凸優(yōu)化問題的基本形式凸優(yōu)化問題的基本描述：為仿射函數(shù)為凸函數(shù)若為準(zhǔn)凸函數(shù)，則優(yōu)化問題稱為準(zhǔn)凸優(yōu)化問題。性質(zhì)：凸優(yōu)化問題的可行域是凸集。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@68凸優(yōu)化問題的例例： 等價于凸優(yōu)化問題信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@69凸優(yōu)化問題的局部最優(yōu)解定理：凸優(yōu)化問題的局部最優(yōu)解均是全局最優(yōu)解。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@70凸優(yōu)化問題最優(yōu)解的微分條件定理：設(shè)為凸優(yōu)化問題的可行域，可微。則為最優(yōu)解當(dāng)且僅當(dāng)成立。定理：非約束凸優(yōu)化問題中，若可微。則為最優(yōu)解當(dāng)且僅當(dāng)成立。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@71凸優(yōu)化問題的等價形式 則為最優(yōu)解當(dāng)且僅當(dāng)，且存在向量滿足定理：設(shè)凸優(yōu)化問題僅有等式約束信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@72凸優(yōu)化問題的等價形式 則為最優(yōu)解當(dāng)且僅當(dāng)，且定理：設(shè)凸優(yōu)化問題信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@73凸優(yōu)化問題的等價形式 等價于

定理：設(shè)凸優(yōu)化問題 其中

信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@74凸優(yōu)化問題的等價形式 等價于

定理：設(shè)凸優(yōu)化問題信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@75準(zhǔn)凸優(yōu)化問題 為準(zhǔn)凸函數(shù)，為凸函數(shù)。準(zhǔn)凸優(yōu)化問題的基本描述注：準(zhǔn)凸優(yōu)化問題的局部最優(yōu)解不一定是全局最優(yōu)解。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@76準(zhǔn)凸優(yōu)化問題的上半圖形式設(shè)為準(zhǔn)凸函數(shù)的凸函數(shù)族表示，即則準(zhǔn)凸優(yōu)化問題的可行解問題為設(shè)為準(zhǔn)凸優(yōu)化問題的最優(yōu)解，若上述問題可解，則。否則。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@77準(zhǔn)凸優(yōu)化問題二分法求解給定一個足夠小的和足夠大的，使得區(qū)間能包含最優(yōu)解。給定LOOP：令求解可行解問題；若可解，則令，否則令若，則結(jié)束，否則gotoLOOP。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@78線性規(guī)劃(linearprogram,LP)LP問題的一般描述信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@79LP問題的幾種類型標(biāo)準(zhǔn)LP問題不等式形式LP問題信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@80標(biāo)準(zhǔn)LP問題的轉(zhuǎn)換信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@81LP問題的例ChebyshevcenterofapolyhedronPiecewise-linearminimizationLinear-fractionalprogramming信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@82Chebyshevcenterofapolyhedron多面體Chebyshevcenter：到多面體邊界距離最大的內(nèi)點（最深的點）問題描述LP形式信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@83Piecewise-linearminimization問題描述上半圖形式LP形式信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@84Linear-fractionalprogramming問題描述LP形式信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@85二次規(guī)劃(quadraticprogram,QP)QP問題的基本描述信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@86二次約束二次規(guī)劃quadraticallyconstrainedquadraticprogram(QCQP)信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@87QP問題的例Least-squaresandregressionDistancebetweenpolyhedra信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@88Least-squaresandregression問題描述信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@89Distancebetweenpolyhedra問題描述QP形式信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@90Second-orderconeprogram,SOCPSOCP問題的基本描述二次錐約束條件信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@91SOCP問題的例－Robustlinearprogramming問題描述 其中不是完全確定的常數(shù)。例：為確定的常數(shù)，為變量，其范圍滿足 SOCP形式信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@92幾何規(guī)劃(Geometricprogramming)單項式與多項式幾何規(guī)劃的基本描述信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@93幾何規(guī)劃的凸形式轉(zhuǎn)換令幾何規(guī)劃的凸形式信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@94廣義不等式約束廣義不等式約束的優(yōu)化問題SOCP的描述信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@95凸優(yōu)化理論與應(yīng)用第四章對偶問題信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@96優(yōu)化問題的拉格朗日函數(shù)設(shè)優(yōu)化問題：拉格朗日(Lagrangian)函數(shù)：對固定的，拉格朗日函數(shù)為關(guān)于和的仿射函數(shù)。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@97拉格朗日對偶函數(shù)拉格朗日對偶函數(shù)(lagrangedualfunction)：若拉格朗日函數(shù)沒有下界，則令拉格朗日對偶函數(shù)為凹函數(shù)。對和，若原最優(yōu)化問題有最優(yōu)值，則信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@98對偶函數(shù)的例Least-squaressolutionoflinearequationsStandardformLPTwo-waypartitioningproblem信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@99Least-squaressolutionoflinearequations原問題：拉格朗日函數(shù)：拉格朗日對偶函數(shù)：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@100StandardformLP原問題：拉格朗日函數(shù)：拉格朗日對偶函數(shù)：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@101Two-waypartitioningproblem原問題：拉格朗日函數(shù)：拉格朗日對偶函數(shù)：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@102對偶函數(shù)與共軛函數(shù)共軛函數(shù)共軛函數(shù)與對偶函數(shù)存在密切聯(lián)系具有線性不等式約束和線性等式約束的優(yōu)化問題：對偶函數(shù)：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@103Equalityconstrainednormminimization問題描述：共軛函數(shù)：對偶函數(shù)：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@104Entropymaximization原始問題：共軛函數(shù)：對偶函數(shù)：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@105Minimumvolumecoveringellipsoid原始問題：對偶函數(shù)：共軛函數(shù)：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@106拉格朗日對偶問題拉格朗日對偶問題的描述：對偶可行域最優(yōu)值最優(yōu)解信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@107LP問題的對偶問題標(biāo)準(zhǔn)LP問題對偶函數(shù)對偶問題等價描述信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@108弱對偶性定理（弱對偶性）：設(shè)原始問題的最優(yōu)值為，對偶問題的最優(yōu)值為，則成立。optimaldualitygap可以利用對偶問題找到原始問題最優(yōu)解的下界。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@109強(qiáng)對偶性強(qiáng)對偶性并不是總是成立的。定義（強(qiáng)對偶性）：設(shè)原始問題的最優(yōu)值為，對偶問題的最優(yōu)值為。若成立，則稱原始問題和對偶問題之間具有強(qiáng)對偶性。凸優(yōu)化問題通常（但并不總是）具有強(qiáng)對偶性。Slater定理：若凸優(yōu)化問題存在嚴(yán)格可行解，即存在，滿足 則優(yōu)化問題具有強(qiáng)對偶性。該條件稱為Slater條件。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@110強(qiáng)對偶性 存在，滿足弱化的Slater條件：若不等式約束條件的前個為線性不等式約束條件，則Slater條件可以弱化為：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@111Least-squaressolutionoflinearequations原問題：對偶問題：具有強(qiáng)對偶性信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@112LagrangedualofQCQPQCQP：拉格朗日函數(shù)：對偶函數(shù)：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@113LagrangedualofQCQP對偶問題：Slater條件：存在，滿足信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@114Entropymaximization原始問題：對偶函數(shù)：對偶問題：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@115Entropymaximization弱化的Slater條件：存在，滿足信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@116Minimumvolumecoveringellipsoid原始問題：對偶函數(shù)：對偶問題：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@117Minimumvolumecoveringellipsoid弱化的Slater條件總成立，因此該優(yōu)化問題具有強(qiáng)對偶性。弱化的Slater條件：存在，滿足信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@118對偶可行解的不等式對于一優(yōu)化問題，若為一可行解，為對偶問題可行解，則有如下不等式： 為次優(yōu)解，其中不等式可以用于對次優(yōu)解的精度估計信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@119互補(bǔ)松弛條件 所以設(shè)為原始優(yōu)化問題的最優(yōu)解，為對偶問題的最優(yōu)解，若兩者具有強(qiáng)對偶性，則 即信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@120KKT優(yōu)化條件設(shè)優(yōu)化問題中，函數(shù)可微。設(shè)為原始優(yōu)化問題的最優(yōu)解，為對偶問題的最優(yōu)解，且兩者具有強(qiáng)對偶性，則滿足如下條件：KKT條件為必要條件！信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@121凸優(yōu)化問題的KKT條件 可微。設(shè)滿足KKT條件，則為原始問題的最優(yōu)解，而為對偶問題的最優(yōu)解，且兩者具有強(qiáng)對偶性。設(shè)原始問題為凸優(yōu)化問題中，函數(shù)信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@122例原始凸優(yōu)化問題

KKT條件信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@123例 其中

解得信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@124凸優(yōu)化問題的對偶求解 存在唯一解。若為原始問題的可行解，則即為原始問題的最優(yōu)解；若不是原始問題的可行解，則原始問題不存在最優(yōu)解。設(shè)原始優(yōu)化問題與對偶問題具有強(qiáng)對偶性，且為對偶問題的最優(yōu)解。存在唯一的最小解，即信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@125擾動問題擾動問題：當(dāng)時即為原始問題。若為正，則第個不等式約束被放寬；若為負(fù)，則第個不等式約束被收緊。記為擾動問題的最優(yōu)解。若擾動問題無最優(yōu)解，則記信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@126靈敏度分析設(shè)對偶問題存在最優(yōu)解，且與原始問題具有強(qiáng)對偶性，若非干擾問題的最優(yōu)對偶解為，則有若在處可微，則信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@127定義（弱選擇性）：若兩個不等式（等式）系統(tǒng)，至多有一個可解，則稱這兩個系統(tǒng)具有弱選擇性。選擇定理對偶不等式組設(shè)原始問題的約束條件：對偶問題原始問題的約束條件與對偶不等式組具有弱選擇性。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@128選擇定理對偶不等式組設(shè)原始問題的嚴(yán)格不等式約束條件：原始問題的嚴(yán)格不等式約束條件與對偶不等式組具有弱選擇性。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@129定義（強(qiáng)選擇性）：若兩個不等式（等式）系統(tǒng)，恰有一個可解，則稱這兩個系統(tǒng)具有強(qiáng)選擇性。選擇定理對偶不等式組設(shè)原始問題為凸優(yōu)化問題，其嚴(yán)格不等式約束條件為：若存在，滿足，則上述兩不等式約束系統(tǒng)具有強(qiáng)選擇性。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@130選擇定理對偶不等式組設(shè)原始問題為凸優(yōu)化問題，其不等式約束條件為： 則原始問題的不等式約束條件與對偶不等式組具有強(qiáng)選擇性。若存在，滿足，且下述優(yōu)化問題存在最優(yōu)解信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@131罰函數(shù)的例范數(shù)：死區(qū)線性罰函數(shù)：對數(shù)門限罰函數(shù)信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@132魯棒的罰函數(shù)若大到一定程度時，罰函數(shù)為的線性函數(shù)，則稱該罰函數(shù)為魯棒的罰函數(shù)。Huber罰函數(shù)信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@133最小范數(shù)問題問題描述： 其中為方程組的解?？梢韵サ仁郊s束將其轉(zhuǎn)換為范數(shù)逼近問題：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@134最小范數(shù)問題最小平方范數(shù)問題：范數(shù)，最優(yōu)解滿足：最小罰問題：絕對值和最小問題：范數(shù)，原問題可轉(zhuǎn)換為LP問題：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@135正則逼近二元矢量優(yōu)化問題描述：正則化問題： 最優(yōu)解描述了兩分量的一條折中曲線。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@136正則逼近Tikhonov正則化問題： 為二次優(yōu)化問題： 最優(yōu)解的形式：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@137正則逼近Tikhonov光滑正則化問題： 為二階差分算子：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@138信號復(fù)原已知加噪信號： 信號復(fù)原問題的描述： 函數(shù)為正則函數(shù)或光滑函數(shù)。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@139信號復(fù)原信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@140信號復(fù)原信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@141信號復(fù)原信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@142魯棒逼近問題描述：隨機(jī)魯棒逼近：為隨機(jī)變量，逼近問題轉(zhuǎn)換為最小化期望例： 隨機(jī)魯棒逼近為： 轉(zhuǎn)換為：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@143隨機(jī)魯棒逼近為隨機(jī)變量： 最小平方隨機(jī)魯棒逼近為： 轉(zhuǎn)換為： 其中信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@144最壞情況魯棒逼近考慮，最壞情況魯棒逼近為：例： 隨機(jī)魯棒逼近為： 轉(zhuǎn)換為：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@145凸優(yōu)化理論與應(yīng)用第6章統(tǒng)計估計信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@146概率分布的參數(shù)估計隨機(jī)變量的概率密度為，其中為概率分布的參數(shù)，且參數(shù)未知。參數(shù)估計的目標(biāo)就是通過一些已知樣本估計獲得參數(shù)的最優(yōu)近似值。問題描述為樣本觀測值；為對數(shù)似然函數(shù)；若似然函數(shù)為凹函數(shù)，則優(yōu)化問題為凸優(yōu)化問題。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@147具有獨立同分布噪聲的線性測量線性測量模型：為觀測值或測量值；為未知參數(shù)向量；獨立同分布噪聲，其概率密度為。似然函數(shù)為最大似然估計問題為：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@148例高斯白噪聲 對數(shù)似然函數(shù)：區(qū)間上均勻分布的噪聲： 對數(shù)似然函數(shù)：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@149邏輯回歸隨機(jī)變量的概率分布為：為參數(shù)；為可觀測的解釋變量；為觀察值。 對數(shù)似然函數(shù)：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@150假定測驗隨機(jī)變量，有種可能（假定）的分布；假定：的概率分布為假定測驗的目標(biāo)：由觀察值猜測隨機(jī)變量最有可能服從哪種假定的分布。當(dāng)時，稱為二元假定測驗。隨機(jī)檢測子：非負(fù)元素矩陣信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@151假定測驗為當(dāng)實際服從第1種假定分布而猜測為第2種假定分布的概率；為當(dāng)實際服從第2種假定分布而猜測為第1種假定分布的概率；多目標(biāo)優(yōu)化形式：檢測概率矩陣信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@152假定測驗最小最大值形式尺度優(yōu)化形式：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@153例

在兩種假設(shè)下的概率分布為：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@154例信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@155實驗設(shè)計線性測量問題最大似然估計值：獨立同分布高斯白噪聲，服從分布。估計誤差均值為0，方差為 信賴橢圓為信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@156實驗設(shè)計實驗設(shè)計的目標(biāo)：尋找，使得誤差的方差矩陣最小。向量優(yōu)化形式：為整數(shù)問題，求解較困難。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@157實驗設(shè)計當(dāng)時，令近似為一連續(xù)實數(shù)，原問題可松弛轉(zhuǎn)換為連續(xù)實數(shù)優(yōu)化：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@158凸優(yōu)化理論與應(yīng)用第7章無約束優(yōu)化信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@159無約束優(yōu)化問題問題描述：無約束問題求解的兩種方法：迭代逼近：求解梯度方程：為凸函數(shù)，且二次可微。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@160例 梯度方程二次優(yōu)化：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@161迭代起始點滿足條件2的幾種函數(shù)：起始點滿足：函數(shù)任意下水平集都是閉集；函數(shù)的定義域為當(dāng)時，信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@162強(qiáng)凸性定義：函數(shù)在上具有強(qiáng)凸性，若滿足若函數(shù)具有強(qiáng)凸性，則有為最優(yōu)值，則信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@163強(qiáng)凸性 則有為最優(yōu)值，則若函數(shù)在上具有強(qiáng)凸性，則可以證明存在，滿足信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@164強(qiáng)凸性對于，矩陣的特征值從大到小依次為。則有：

定義：矩陣的條件數(shù)為最大特征值與最小特征值之比，即。條件數(shù)的上界：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@165下降法下降法的基本原理： 迭代，滿足 為下降方向，為步長因子。對于凸函數(shù)，當(dāng)滿足時，存在某個，使得。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@166下降法下降法的一般步驟：給出初始點；循環(huán)迭代計算下降方向；搜索步長因子；迭代：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@167步長因子搜索精確一維搜索：回溯一維搜索：給定參數(shù)循環(huán)迭代初始化：令；若，則終止退出；否則令信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@168步長因子搜索信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@169梯度下降法算法簡單，但收斂速度較慢。下降方向：終止條件：收斂性： 其中。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@170收斂性分析 則有：設(shè)函數(shù)具有強(qiáng)凸性，則存在和，滿足：若采用精確一維搜索，則，收斂速度因子：若采用回溯一維搜索，收斂速度因子：條件數(shù)越大，收斂速度越小。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@171例當(dāng)時，算法收斂速度很慢。初始解為，采用精確一維搜索；迭代：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@172例步長因子采用回溯一維搜索。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@173最速下降法歸一化最速下降方向：非歸一化最速下降方向歐式范數(shù)：二次范數(shù)：范數(shù)：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@174最速下降法信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@175收斂性分析范數(shù)界：收斂速度因子：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@176牛頓法設(shè)函數(shù)二階可微，則在附近，的泰勒展式為：泰勒展開可作為在附近的近似；下降方向：為二次范數(shù)上的最速下降方向。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@177牛頓法信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@178牛頓減量令為在處的牛頓減量。牛頓減量的性質(zhì)1：性質(zhì)2： 牛頓減量可作為迭代求解的誤差估計。性質(zhì)3：牛頓減量具有仿射不變性。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@179牛頓方法初始化：給定初始解以及LOOP：計算：若則終止退出；一維線性搜索：計算步長因子；迭代：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@180收斂性分析定理：假設(shè)二階連續(xù)可微，具有強(qiáng)凸性，即存在，滿足： 則存在， 且海森矩陣滿足Lipschitz條件，即存在，滿足： 若，則； 若，則，且信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@181收斂性分析定理：假設(shè)二階連續(xù)可微，具有強(qiáng)凸性，即存在，滿足： 則存在，對于，有 且海森矩陣滿足Lipschitz條件，即存在，滿足：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@182例信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@183凸優(yōu)化理論與應(yīng)用第8章等式約束優(yōu)化信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@184等式約束優(yōu)化問題問題描述：為凸函數(shù)，且二次連續(xù)可微，且假設(shè)最優(yōu)值存在，則為最優(yōu)解當(dāng)且僅當(dāng)存在，滿足（KKT條件）：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@185例

KKT系統(tǒng)：二次優(yōu)化：KKT系統(tǒng)可解，則二次優(yōu)化問題存在最優(yōu)解。系數(shù)矩陣稱為KKT矩陣。KKT矩陣非奇異當(dāng)且僅當(dāng)：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@186消去等式約束方程組的解集：為方程組的一個特解，為的零空間范圍。無約束優(yōu)化形式：若為最優(yōu)解，則有信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@187對偶問題對偶形式：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@188牛頓法牛頓減量為等式約束優(yōu)化的可行解，則在附近原問題的二次近似為：設(shè)和分別為該問題和對偶問題的最優(yōu)解，則滿足：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@189性質(zhì)2：牛頓減量具有仿射不變性。牛頓減量牛頓減量牛頓減量的性質(zhì)：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@190可行下降方向可行下降方向：設(shè)滿足方程組。若滿足方程組，則。稱為可行方向。若對于較小的，有，則為可行下降方向。信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@191等式約束的牛頓方法LOOP：計算及；若則終止退出；一維線性搜索：計算步長因子；迭代：初始化：給定初始解滿足，以及信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@192消去等式約束的牛頓方法轉(zhuǎn)換為等式約束下的牛頓方法：初始值，第次迭代值；初始值：迭代值：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@193非可行解為初始點的牛頓法函數(shù)二階連續(xù)可微，因此有為等式約束優(yōu)化的非可行解，則增量應(yīng)盡可能使?jié)M足KKT條件，即：設(shè)和為KKT條件的解，即有：信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@194非可行解為初始點的牛頓法則KKT條件可表示為：令設(shè)為不滿足KKT條件，則其迭代量需滿足： 即信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@195當(dāng)且時，終止迭代。非可行解為初始點的牛頓法LOOP：計算和；回溯一維線性搜索：迭代：初始化：給定初始解及，以及令；While信息與通信工程學(xué)院莊伯金bjzhuang@bupt.ed信息與通信工程學(xué)院莊伯金bjzhuang@196 其中，且滿足。KKT系