凸優(yōu)化理論與應(yīng)用歸納課件

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

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

則稱函數(shù)為準(zhǔn)凸函數(shù)。精選準(zhǔn)凸函數(shù)(quasiconvexfunction)準(zhǔn)凸精選準(zhǔn)凸函數(shù)的判定定理定理：函數(shù)為準(zhǔn)凸函數(shù)，當(dāng)且僅當(dāng)為凸集，且對，有定理：若函數(shù)一階可微，則為準(zhǔn)凸函數(shù)，當(dāng)且僅當(dāng)為凸集，且對，有 ，有定理：若函數(shù)二階可微，且滿足對 則函數(shù)準(zhǔn)凸函數(shù)。精選準(zhǔn)凸函數(shù)的判定定理定理：函數(shù)為準(zhǔn)凸函數(shù)，精選最小值函數(shù)非負(fù)權(quán)值函數(shù)的最大值函數(shù)保持準(zhǔn)凸性的算子復(fù)合函數(shù)精選最小值函數(shù)非負(fù)權(quán)值函數(shù)的最大值函數(shù)保持準(zhǔn)凸性的算子復(fù)合函精選準(zhǔn)凸函數(shù)的凸函數(shù)族表示若為準(zhǔn)凸函數(shù)，根據(jù)的任意下水平集，我們可以構(gòu)造一個凸函數(shù)族，使得性質(zhì)：若為準(zhǔn)凸函數(shù)的凸函數(shù)族表示，對每一個，若，則有精選準(zhǔn)凸函數(shù)的凸函數(shù)族表示若為準(zhǔn)凸函數(shù)，根精選對數(shù)凸函數(shù) 為凸集 為凸函數(shù)。定義：函數(shù)稱為對數(shù)凸函數(shù)，若函數(shù)滿足：定理：函數(shù)的定義域為凸集，且，則為對數(shù)凸函數(shù)，當(dāng)且僅當(dāng)對有對數(shù)凸函數(shù)的例精選對數(shù)凸函數(shù) 為凸集 為凸函數(shù)精選對數(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ù)。精選對數(shù)凸函數(shù)和凹函數(shù)的性質(zhì)性質(zhì)：對數(shù)凸性與凹性對函數(shù)乘積和精選對數(shù)凸函數(shù)和凹函數(shù)的性質(zhì)定理：函數(shù)為對數(shù)凹函數(shù)，則函數(shù)是對數(shù)凹函數(shù)。精選對數(shù)凸函數(shù)和凹函數(shù)的性質(zhì)定理：函數(shù)精選廣義不等式下的凸性廣義單調(diào)性的定義：設(shè)為真錐，函數(shù)稱為單調(diào)增，若函數(shù)滿足：廣義凸函數(shù)的定義：設(shè)為真錐，函數(shù)稱為凸，若函數(shù)滿足對 均有定理(對偶等價)：函數(shù)為凸函數(shù)，當(dāng)且僅當(dāng)對所有，為凸函數(shù)。精選廣義不等式下的凸性廣義單調(diào)性的定義：設(shè)精選作業(yè)(1)P1163.16P1163.21精選作業(yè)(1)P1163.16精選作業(yè)(2)P1213.41P1223.49(1)(2)精選作業(yè)(2)P1213.41精選凸優(yōu)化理論與應(yīng)用第三章凸優(yōu)化精選凸優(yōu)化理論與應(yīng)用第三章凸優(yōu)化精選優(yōu)化問題的基本形式優(yōu)化問題的基本描述：優(yōu)化變量不等式約束等式約束無約束優(yōu)化精選優(yōu)化問題的基本形式優(yōu)化問題的基本描述：優(yōu)化變量不等式約束精選優(yōu)化問題的基本形式最優(yōu)化值最優(yōu)化解優(yōu)化問題的域可行點(解)(feasible)滿足約束條件可行域(可解集)所有可行點的集合精選優(yōu)化問題的基本形式最優(yōu)化值最優(yōu)化解優(yōu)化問題的域精選局部最優(yōu)問題局部最優(yōu)問題精選局部最優(yōu)問題局部最優(yōu)問題精選優(yōu)化問題的等價形式(1)定理：若則原優(yōu)化問題與以下優(yōu)化問題等價精選優(yōu)化問題的等價形式(1)定理：若則原優(yōu)化問題與以下精選優(yōu)化問題的等價形式(2)定理：設(shè)為一一對應(yīng)，且則原優(yōu)化問題與以下優(yōu)化問題等價精選優(yōu)化問題的等價形式(2)定理：設(shè)精選優(yōu)化問題的等價形式(3)定理：設(shè)為嚴(yán)格單調(diào)增函數(shù)；滿足當(dāng)且僅當(dāng)；滿足當(dāng)且僅當(dāng)。則原優(yōu)化問題與以下優(yōu)化問題等價精選優(yōu)化問題的等價形式(3)定理：設(shè)精選優(yōu)化問題的等價形式(4)定理：原優(yōu)化問題與以下優(yōu)化問題等價稱為松弛變量精選優(yōu)化問題的等價形式(4)定理：原優(yōu)化問題與以下優(yōu)化問題等精選優(yōu)化問題的等價形式(5)定理：設(shè)滿足等式成立，當(dāng)且僅當(dāng)。則原優(yōu)化問題與以下優(yōu)化問題等價精選優(yōu)化問題的等價形式(5)定理：設(shè)精選可分離變量優(yōu)化問題性質(zhì)： 其中 可以分離變量定理：優(yōu)化問題精選可分離變量優(yōu)化問題性質(zhì)： 其中 可以分離變量定理：優(yōu)化問精選優(yōu)化問題的上半圖形式精選優(yōu)化問題的上半圖形式精選凸優(yōu)化問題的基本形式凸優(yōu)化問題的基本描述：為仿射函數(shù)為凸函數(shù)若為準(zhǔn)凸函數(shù)，則優(yōu)化問題稱為準(zhǔn)凸優(yōu)化問題。性質(zhì)：凸優(yōu)化問題的可行域是凸集。精選凸優(yōu)化問題的基本形式凸優(yōu)化問題的基本描述：精選凸優(yōu)化問題的例例： 等價于凸優(yōu)化問題精選凸優(yōu)化問題的例例： 等價于凸優(yōu)化問題精選凸優(yōu)化問題的局部最優(yōu)解定理：凸優(yōu)化問題的局部最優(yōu)解均是全局最優(yōu)解。精選凸優(yōu)化問題的局部最優(yōu)解定理：凸優(yōu)化問題的局部最優(yōu)解均是全精選凸優(yōu)化問題最優(yōu)解的微分條件定理：設(shè)為凸優(yōu)化問題的可行域，可微。則為最優(yōu)解當(dāng)且僅當(dāng)成立。定理：非約束凸優(yōu)化問題中，若可微。則為最優(yōu)解當(dāng)且僅當(dāng)成立。精選凸優(yōu)化問題最優(yōu)解的微分條件定理：設(shè)為凸優(yōu)化問題的精選凸優(yōu)化問題的等價形式 則為最優(yōu)解當(dāng)且僅當(dāng)，且存在向量滿足定理：設(shè)凸優(yōu)化問題僅有等式約束精選凸優(yōu)化問題的等價形式 則為最優(yōu)解當(dāng)且僅當(dāng)精選凸優(yōu)化問題的等價形式 則為最優(yōu)解當(dāng)且僅當(dāng)，且定理：設(shè)凸優(yōu)化問題精選凸優(yōu)化問題的等價形式 則為最優(yōu)解當(dāng)且僅當(dāng)精選凸優(yōu)化問題的等價形式 等價于

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

精選凸優(yōu)化問題的等價形式 等價于定理：設(shè)凸優(yōu)化問精選凸優(yōu)化問題的等價形式 等價于

定理：設(shè)凸優(yōu)化問題精選凸優(yōu)化問題的等價形式 等價于定理：設(shè)凸優(yōu)化問精選準(zhǔn)凸優(yōu)化問題 為準(zhǔn)凸函數(shù)，為凸函數(shù)。準(zhǔn)凸優(yōu)化問題的基本描述注：準(zhǔn)凸優(yōu)化問題的局部最優(yōu)解不一定是全局最優(yōu)解。精選準(zhǔn)凸優(yōu)化問題 為準(zhǔn)凸函數(shù)，精選準(zhǔn)凸優(yōu)化問題的上半圖形式設(shè)為準(zhǔn)凸函數(shù)的凸函數(shù)族表示，即則準(zhǔn)凸優(yōu)化問題的可行解問題為設(shè)為準(zhǔn)凸優(yōu)化問題的最優(yōu)解，若上述問題可解，則。否則。精選準(zhǔn)凸優(yōu)化問題的上半圖形式設(shè)為準(zhǔn)凸函數(shù)精選準(zhǔn)凸優(yōu)化問題二分法求解給定一個足夠小的和足夠大的，使得區(qū)間能包含最優(yōu)解。給定LOOP：令求解可行解問題；若可解，則令，否則令若，則結(jié)束，否則gotoLOOP。精選準(zhǔn)凸優(yōu)化問題二分法求解給定一個足夠小的和足夠大的精選線性規(guī)劃(linearprogram,LP)LP問題的一般描述精選線性規(guī)劃(linearprogram,LP)LP問題的精選LP問題的幾種類型標(biāo)準(zhǔn)LP問題不等式形式LP問題精選LP問題的幾種類型標(biāo)準(zhǔn)LP問題不等式形式LP問題精選標(biāo)準(zhǔn)LP問題的轉(zhuǎn)換精選標(biāo)準(zhǔn)LP問題的轉(zhuǎn)換精選LP問題的例ChebyshevcenterofapolyhedronPiecewise-linearminimizationLinear-fractionalprogramming精選LP問題的例Chebyshevcenterofa精選Chebyshevcenterofapolyhedron多面體Chebyshevcenter：到多面體邊界距離最大的內(nèi)點（最深的點）問題描述LP形式精選Chebyshevcenterofapolyhe精選Piecewise-linearminimization問題描述上半圖形式LP形式精選Piecewise-linearminimizatio精選Linear-fractionalprogramming問題描述LP形式精選Linear-fractionalprogrammin精選二次規(guī)劃(quadraticprogram,QP)QP問題的基本描述精選二次規(guī)劃(quadraticprogram,QP)QP精選二次約束二次規(guī)劃quadraticallyconstrainedquadraticprogram(QCQP)精選二次約束二次規(guī)劃quadraticallyconstr精選QP問題的例Least-squaresandregressionDistancebetweenpolyhedra精選QP問題的例Least-squaresandregr精選Least-squaresandregression問題描述精選Least-squaresandregression精選Distancebetweenpolyhedra問題描述QP形式精選Distancebetweenpolyhedra問題精選Second-orderconeprogram,SOCPSOCP問題的基本描述二次錐約束條件精選Second-orderconeprogram,S精選SOCP問題的例－Robustlinearprogramming問題描述 其中不是完全確定的常數(shù)。例：為確定的常數(shù)，為變量，其范圍滿足 SOCP形式精選SOCP問題的例－Robustlinearprogr精選幾何規(guī)劃(Geometricprogramming)單項式與多項式幾何規(guī)劃的基本描述精選幾何規(guī)劃(Geometricprogramming)單精選幾何規(guī)劃的凸形式轉(zhuǎn)換令幾何規(guī)劃的凸形式精選幾何規(guī)劃的凸形式轉(zhuǎn)換令幾何規(guī)劃的凸形式精選廣義不等式約束廣義不等式約束的優(yōu)化問題SOCP的描述精選廣義不等式約束廣義不等式約束的優(yōu)化問題SOCP的描述精選凸優(yōu)化理論與應(yīng)用第四章對偶問題精選凸優(yōu)化理論與應(yīng)用第四章對偶問題精選優(yōu)化問題的拉格朗日函數(shù)設(shè)優(yōu)化問題：拉格朗日(Lagrangian)函數(shù)：對固定的，拉格朗日函數(shù)為關(guān)于和的仿射函數(shù)。精選優(yōu)化問題的拉格朗日函數(shù)設(shè)優(yōu)化問題：拉格朗日(Lagran精選拉格朗日對偶函數(shù)拉格朗日對偶函數(shù)(lagrangedualfunction)：若拉格朗日函數(shù)沒有下界，則令拉格朗日對偶函數(shù)為凹函數(shù)。對和，若原最優(yōu)化問題有最優(yōu)值，則精選拉格朗日對偶函數(shù)拉格朗日對偶函數(shù)(lagrangedu精選對偶函數(shù)的例Least-squaressolutionoflinearequationsStandardformLPTwo-waypartitioningproblem精選對偶函數(shù)的例Least-squaressolution精選Least-squaressolutionoflinearequations原問題：拉格朗日函數(shù)：拉格朗日對偶函數(shù)：精選Least-squaressolutionofli精選StandardformLP原問題：拉格朗日函數(shù)：拉格朗日對偶函數(shù)：精選StandardformLP原問題：拉格朗日函數(shù)：拉精選Two-waypartitioningproblem原問題：拉格朗日函數(shù)：拉格朗日對偶函數(shù)：精選Two-waypartitioningproblem精選對偶函數(shù)與共軛函數(shù)共軛函數(shù)共軛函數(shù)與對偶函數(shù)存在密切聯(lián)系具有線性不等式約束和線性等式約束的優(yōu)化問題：對偶函數(shù)：精選對偶函數(shù)與共軛函數(shù)共軛函數(shù)共軛函數(shù)與對偶函數(shù)存在密切聯(lián)系精選Equalityconstrainednormminimization問題描述：共軛函數(shù)：對偶函數(shù)：精選Equalityconstrainednormmi精選Entropymaximization原始問題：共軛函數(shù)：對偶函數(shù)：精選Entropymaximization原始問題：共軛函精選Minimumvolumecoveringellipsoid原始問題：對偶函數(shù)：共軛函數(shù)：精選Minimumvolumecoveringelli精選拉格朗日對偶問題拉格朗日對偶問題的描述：對偶可行域最優(yōu)值最優(yōu)解精選拉格朗日對偶問題拉格朗日對偶問題的描述：對偶可行域最優(yōu)值精選LP問題的對偶問題標(biāo)準(zhǔn)LP問題對偶函數(shù)對偶問題等價描述精選LP問題的對偶問題標(biāo)準(zhǔn)LP問題對偶函數(shù)對偶問題等價描述精選弱對偶性定理（弱對偶性）：設(shè)原始問題的最優(yōu)值為，對偶問題的最優(yōu)值為，則成立。optimaldualitygap可以利用對偶問題找到原始問題最優(yōu)解的下界。精選弱對偶性定理（弱對偶性）：設(shè)原始問題的最優(yōu)值為精選強(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條件。精選強(qiáng)對偶性強(qiáng)對偶性并不是總是成立的。定義（強(qiáng)對偶性）：設(shè)精選強(qiáng)對偶性 存在，滿足弱化的Slater條件：若不等式約束條件的前個為線性不等式約束條件，則Slater條件可以弱化為：精選強(qiáng)對偶性 存在，滿足精選Least-squaressolutionoflinearequations原問題：對偶問題：具有強(qiáng)對偶性精選Least-squaressolutionofli精選LagrangedualofQCQPQCQP：拉格朗日函數(shù)：對偶函數(shù)：精選LagrangedualofQCQPQCQP：拉格精選LagrangedualofQCQP對偶問題：Slater條件：存在，滿足精選LagrangedualofQCQP對偶問題：Sl精選Entropymaximization原始問題：對偶函數(shù)：對偶問題：精選Entropymaximization原始問題：對偶函精選Entropymaximization弱化的Slater條件：存在，滿足精選Entropymaximization弱化的Slate精選Minimumvolumecoveringellipsoid原始問題：對偶函數(shù)：對偶問題：精選Minimumvolumecoveringelli精選Minimumvolumecoveringellipsoid弱化的Slater條件總成立，因此該優(yōu)化問題具有強(qiáng)對偶性。弱化的Slater條件：存在，滿足精選Minimumvolumecoveringelli精選對偶可行解的不等式對于一優(yōu)化問題，若為一可行解，為對偶問題可行解，則有如下不等式： 為次優(yōu)解，其中不等式可以用于對次優(yōu)解的精度估計精選對偶可行解的不等式對于一優(yōu)化問題，若為一可行解，精選互補(bǔ)松弛條件 所以設(shè)為原始優(yōu)化問題的最優(yōu)解，為對偶問題的最優(yōu)解，若兩者具有強(qiáng)對偶性，則 即精選互補(bǔ)松弛條件 所以設(shè)為原始優(yōu)化問題的最優(yōu)解，精選KKT優(yōu)化條件設(shè)優(yōu)化問題中，函數(shù)可微。設(shè)為原始優(yōu)化問題的最優(yōu)解，為對偶問題的最優(yōu)解，且兩者具有強(qiáng)對偶性，則滿足如下條件：KKT條件為必要條件！精選KKT優(yōu)化條件設(shè)優(yōu)化問題中，函數(shù)精選凸優(yōu)化問題的KKT條件 可微。設(shè)滿足KKT條件，則為原始問題的最優(yōu)解，而為對偶問題的最優(yōu)解，且兩者具有強(qiáng)對偶性。設(shè)原始問題為凸優(yōu)化問題中，函數(shù)精選凸優(yōu)化問題的KKT條件 可微。設(shè)精選例原始凸優(yōu)化問題

KKT條件精選例原始凸優(yōu)化問題 KKT條件精選例 其中

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

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

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

KKT系統(tǒng)：二次優(yōu)化：KKT系統(tǒng)可解，則二次優(yōu)化問題存在最優(yōu)解。系數(shù)矩陣稱為KKT矩陣。KKT矩陣非奇異當(dāng)且僅當(dāng)：精選例 KKT系統(tǒng)：二次優(yōu)化：KKT系統(tǒng)可解，則二次優(yōu)化問題精選消去等式約束方程組的解集：為方程組的一個特解，為的零空間范圍。無約束優(yōu)化形式：若為最優(yōu)解，則有精選消去等式約束方程組的解集：精選對偶問題對偶形式：精選對偶問題對偶形式：精選牛頓法牛頓減量為等式約束優(yōu)化的可行解，則在附近原問題的二次近似為：設(shè)和分別為該問題和對偶問題的最優(yōu)解，則滿足：精選牛頓法牛頓減量為等式約束優(yōu)化的可行解，則在精選性質(zhì)2：牛頓減量具有仿射不變性。牛頓減量牛頓減量牛頓減量的性質(zhì)：精選性質(zhì)2：牛頓減量具有仿射不變性。牛頓減量牛頓減量牛頓減量精選可行下降方向可行下降方向：設(shè)滿足方程組。若滿足方程組，則。稱為可行方向。若對于較小的，有，則為可行下降方向。精選可行下降方向可行下降方向：設(shè)滿足方程組精選等式約束的牛頓方法LOOP：計算及；若則終止退出；一維線性搜索：計算步長因子；迭代：初始化：給定初始解滿足，以及精選等式約束的牛頓方法LOOP：計算及精選消去等式約束的牛頓方法轉(zhuǎn)換為等式約束下的牛頓方法：初始值，第次迭代值；初始值：迭代值：精選消去等式約束的牛頓方法轉(zhuǎn)換為等式約束下的牛頓方法：初始值精選非可行解為初始點的牛頓法函數(shù)二階連續(xù)可微，因此有為等式約束優(yōu)化的非可行解，則增量應(yīng)盡可能使?jié)M足KKT條件，即：設(shè)和為KKT條件的解，即有：精選非可行解為初始點的牛頓法函數(shù)二階連續(xù)可精選非可行解為初始點的牛頓法則KKT條件可表示為：令設(shè)為不滿足KKT條件，則其迭代量需滿足： 即精選非可行解為初始點的牛頓法則KKT條件可表示為：令設(shè)精選當(dāng)且時，終止迭代。非可行解為初始點的牛頓法LOOP：計算和；回溯一維線性搜索：迭代：初始化：給定初始解及，以及令；While精選當(dāng)且精選 其中，且滿足。KKT系統(tǒng)的求解1.分解；2.若非奇異，則可消元：3.若奇異，則KKT系統(tǒng)可改寫為：KKT系統(tǒng)：精選 其中，且滿足精選凸優(yōu)化理論與應(yīng)用第9章內(nèi)點法精選凸優(yōu)化理論與應(yīng)用第9章內(nèi)點法精選則優(yōu)化問題具有強(qiáng)對偶性，其對偶問題亦可解。假設(shè)存在，滿足嚴(yán)格不等式條件不等式約束優(yōu)化問題問題描述：為凸函數(shù)，且二次連續(xù)可微，且假設(shè)最優(yōu)值存在；精選則優(yōu)化問題具有強(qiáng)對偶性，其對偶問題亦可解。假設(shè)存在精選不具備良好的連續(xù)可微性，考慮用對數(shù)閥函數(shù)來近似替代。不等式約束的消去示性函數(shù)消去不等式約束：精選不具備良好的連續(xù)可微性，考慮用對數(shù)閥精選令對數(shù)閥函數(shù)對于，是的光滑逼近。且當(dāng)時，有帶示性函數(shù)的優(yōu)化問題可近似為：精選令對數(shù)閥函數(shù)對于，精選對數(shù)閥函數(shù)二階連續(xù)可微，導(dǎo)數(shù)為：對數(shù)閥函數(shù)對數(shù)閥函數(shù)是凸函數(shù)精選對數(shù)閥函數(shù)二階連續(xù)可微，導(dǎo)數(shù)為：對數(shù)閥函數(shù)對數(shù)閥函數(shù)精選中心線對數(shù)閥近似問題的等價問題：最優(yōu)解為，則最優(yōu)解集稱為優(yōu)化問題的中心線。精選中心線對數(shù)閥近似問題的等價問題：最優(yōu)解為精選中心線的對偶點設(shè)，則存在滿足KKT條件：為對偶問題的可行解。令 則是拉格朗日函數(shù)的最小值解。精選中心線的對偶點設(shè)，則存在精選中心線的對偶點設(shè)為原始問題的最優(yōu)值，則有：因此，當(dāng)時，有。為原始問題的次優(yōu)解。精選中心線的對偶點設(shè)為原始問題的最優(yōu)值，則有：因此精選更新：閥方法初始化：給定嚴(yán)格可行解，，，及LOOP：中心步驟：以為初始點求解優(yōu)化問題，迭代：終止條件：若，則終止退出。精選更新：閥方法初始化：給定嚴(yán)格可行解，精選收斂性分析外層循環(huán)迭代次數(shù)：中心步驟實質(zhì)為一個無約束或等式約束優(yōu)化問題，其收斂性分析與相應(yīng)優(yōu)化問題的收斂性分析結(jié)果一致。精選收斂性分析外層循環(huán)迭代次數(shù)：中心步驟實質(zhì)為一個無約束或等精選例：LP問題：初始值：精選例：LP問題：初始值：精選當(dāng)時，原始問題不可解；當(dāng)時，無法準(zhǔn)確確定。第一階段方法對于不等式約束的優(yōu)化問題，如何尋找嚴(yán)格可行解或驗證不可解？求解優(yōu)化問題：該問題最優(yōu)解存在，假設(shè)最優(yōu)值為當(dāng)時，存在嚴(yán)格可行解；精選當(dāng)時，原始問題不可解；當(dāng)精選第一階段方法優(yōu)化目標(biāo)為逐項之和：對于固定的，精選第一階段方法優(yōu)化目標(biāo)為逐項之和：對于固定的，精選尋找嚴(yán)格可行解的方法牛頓法求解優(yōu)化問題：迭代終止條件：當(dāng)前解，即終止迭代，嚴(yán)格可行解為。精選尋找嚴(yán)格可行解的方法牛頓法求解優(yōu)化問題：迭代終止條件：當(dāng)精選凸優(yōu)化理論與應(yīng)用復(fù)習(xí)精選凸優(yōu)化理論與應(yīng)用復(fù)習(xí)精選凸集凸集與凸包的概念；幾種常見的凸集多面體、單純形、范數(shù)球、凸錐、真錐、范數(shù)錐、半正定錐等；保持凸集的運(yùn)算集合交運(yùn)算、仿射變換、透視函數(shù)、線性分式函數(shù)廣義不等式的概念支撐超平面、分割超平面的概念精選凸集凸集與凸包的概念；精選凸函數(shù)凸函數(shù)的概念及判定；常見凸函數(shù)；Jessen不等式；保持函數(shù)凸性的算子；共軛函數(shù)的概念、常見函數(shù)的共軛函數(shù)；向量凸函數(shù)（廣義不等式下的凸性）精選凸函數(shù)凸函數(shù)的概念及判定；精選優(yōu)化問題優(yōu)化問題的基本描述、等價形式；凸優(yōu)化問題的基本描述、等價形式；常見凸優(yōu)化問題。精選優(yōu)化問題優(yōu)化問題的基本描述、等價形式；精選對偶問題優(yōu)化問題的拉格朗日函數(shù)及對偶函數(shù)的概念和性質(zhì)；一些常見問題的對偶函數(shù)；對偶函數(shù)與共軛函數(shù)的關(guān)系；對偶問題的描述；強(qiáng)對偶性的概念及Slater條件；KKT條件。精選對偶問題優(yōu)化問題的拉格朗日函數(shù)及對偶函數(shù)的概念和性質(zhì)；精選常見應(yīng)用問題逼近問題的幾種基本描述；統(tǒng)計估計問題的基本描述。精選常見應(yīng)用問題逼近問題的幾種基本描述；精選常用算法無約束問題常用算法：下降法最速下降牛頓法等式約束問題的常用算法等式約束條件的消去牛頓法內(nèi)點法精選常用算法無約束問題常用算法：精選凸優(yōu)化理論與應(yīng)用莊伯金B(yǎng)jzhuang@精選凸優(yōu)化理論與應(yīng)用莊伯金精選優(yōu)化理論概述什么是優(yōu)化問題？ObjectivefunctionConstraintfunctions精選優(yōu)化理論概述什么是優(yōu)化問題？Objectivefunc精選幾類經(jīng)典的優(yōu)化問題線性規(guī)劃問題最小二乘問題凸優(yōu)化問題凸優(yōu)化問題理論上有有效的方法進(jìn)行求解！精選幾類經(jīng)典的優(yōu)化問題線性規(guī)劃問題最小二乘問題凸優(yōu)化問題凸優(yōu)精選本課程的主要內(nèi)容理論部分凸集和凸函數(shù)凸優(yōu)化問題對偶問題應(yīng)用部分逼近與擬合統(tǒng)計估計幾何問題算法部分非約束優(yōu)化方法等式約束優(yōu)化方法內(nèi)點法精選本課程的主要內(nèi)容理論部分精選熟悉了解凸優(yōu)化理論的基本原理和基本方法；掌握實際問題轉(zhuǎn)化為凸優(yōu)化問題的基本方法；掌握最優(yōu)化問題的經(jīng)典算法。課程要求精選熟悉了解凸優(yōu)化理論的基本原理和基本方法；課程要求精選參考書目StephenBoydandLievenVandenberghe,“ConvexOptimization”,CambridgeUniversityPress.袁亞湘、孫文瑜，“最優(yōu)化理論與方法”，科學(xué)出版社，1999。

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

則稱函數(shù)為準(zhǔn)凸函數(shù)。精選準(zhǔn)凸函數(shù)(quasiconvexfunction)準(zhǔn)凸精選準(zhǔn)凸函數(shù)的判定定理定理：函數(shù)為準(zhǔn)凸函數(shù)，當(dāng)且僅當(dāng)為凸集，且對，有定理：若函數(shù)一階可微，則為準(zhǔn)凸函數(shù)，當(dāng)且僅當(dāng)為凸集，且對，有 ，有定理：若函數(shù)二階可微，且滿足對 則函數(shù)準(zhǔn)凸函數(shù)。精選準(zhǔn)凸函數(shù)的判定定理定理：函數(shù)為準(zhǔn)凸函數(shù)，精選最小值函數(shù)非負(fù)權(quán)值函數(shù)的最大值函數(shù)保持準(zhǔn)凸性的算子復(fù)合函數(shù)精選最小值函數(shù)非負(fù)權(quán)值函數(shù)的最大值函數(shù)保持準(zhǔn)凸性的算子復(fù)合函精選準(zhǔn)凸函數(shù)的凸函數(shù)族表示若為準(zhǔn)凸函數(shù)，根據(jù)的任意下水平集，我們可以構(gòu)造一個凸函數(shù)族，使得性質(zhì)：若為準(zhǔn)凸函數(shù)的凸函數(shù)族表示，對每一個，若，則有精選準(zhǔn)凸函數(shù)的凸函數(shù)族表示若為準(zhǔn)凸函數(shù)，根精選對數(shù)凸函數(shù) 為凸集 為凸函數(shù)。定義：函數(shù)稱為對數(shù)凸函數(shù)，若函數(shù)滿足：定理：函數(shù)的定義域為凸集，且，則為對數(shù)凸函數(shù)，當(dāng)且僅當(dāng)對有對數(shù)凸函數(shù)的例精選對數(shù)凸函數(shù) 為凸集 為凸函數(shù)精選對數(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ù)