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

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

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

則稱(chēng)函數(shù)為準(zhǔn)凸函數(shù)。精選準(zhǔn)凸函數(shù)(quasiconvexfunction)準(zhǔn)凸精選準(zhǔn)凸函數(shù)的判定定理定理：函數(shù)為準(zhǔn)凸函數(shù)，當(dāng)且僅當(dāng)為凸集，且對(duì)，有定理：若函數(shù)一階可微，則為準(zhǔn)凸函數(shù)，當(dāng)且僅當(dāng)為凸集，且對(duì)，有 ，有定理：若函數(shù)二階可微，且滿足對(duì) 則函數(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)造一個(gè)凸函數(shù)族，使得性質(zhì)：若為準(zhǔn)凸函數(shù)的凸函數(shù)族表示，對(duì)每一個(gè)，若，則有精選準(zhǔn)凸函數(shù)的凸函數(shù)族表示若為準(zhǔn)凸函數(shù)，根精選對(duì)數(shù)凸函數(shù) 為凸集 為凸函數(shù)。定義：函數(shù)稱(chēng)為對(duì)數(shù)凸函數(shù)，若函數(shù)滿足：定理：函數(shù)的定義域?yàn)橥辜?，且，則為對(duì)數(shù)凸函數(shù)，當(dāng)且僅當(dāng)對(duì)有對(duì)數(shù)凸函數(shù)的例精選對(duì)數(shù)凸函數(shù) 為凸集 為凸函數(shù)精選對(duì)數(shù)凸函數(shù)和凹函數(shù)的性質(zhì)性質(zhì)：對(duì)數(shù)凸性與凹性對(duì)函數(shù)乘積和正數(shù)數(shù)乘運(yùn)算均保持封閉。定理：函數(shù)二階可微，則為對(duì)數(shù)凸函數(shù)當(dāng)且僅當(dāng)性質(zhì)：對(duì)數(shù)凸性對(duì)函數(shù)加運(yùn)算保持封閉。但對(duì)數(shù)凹性對(duì)函數(shù)加運(yùn)算不封閉。推論：函數(shù)對(duì)每一個(gè)在上對(duì)數(shù)凸，則函數(shù)也是對(duì)數(shù)凸函數(shù)。精選對(duì)數(shù)凸函數(shù)和凹函數(shù)的性質(zhì)性質(zhì)：對(duì)數(shù)凸性與凹性對(duì)函數(shù)乘積和精選對(duì)數(shù)凸函數(shù)和凹函數(shù)的性質(zhì)定理：函數(shù)為對(duì)數(shù)凹函數(shù)，則函數(shù)是對(duì)數(shù)凹函數(shù)。精選對(duì)數(shù)凸函數(shù)和凹函數(shù)的性質(zhì)定理：函數(shù)精選廣義不等式下的凸性廣義單調(diào)性的定義：設(shè)為真錐，函數(shù)稱(chēng)為單調(diào)增，若函數(shù)滿足：廣義凸函數(shù)的定義：設(shè)為真錐，函數(shù)稱(chēng)為凸，若函數(shù)滿足對(duì) 均有定理(對(duì)偶等價(jià))：函數(shù)為凸函數(shù)，當(dāng)且僅當(dāng)對(duì)所有，為凸函數(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)化問(wèn)題的基本形式優(yōu)化問(wèn)題的基本描述：優(yōu)化變量不等式約束等式約束無(wú)約束優(yōu)化精選優(yōu)化問(wèn)題的基本形式優(yōu)化問(wèn)題的基本描述：優(yōu)化變量不等式約束精選優(yōu)化問(wèn)題的基本形式最優(yōu)化值最優(yōu)化解優(yōu)化問(wèn)題的域可行點(diǎn)(解)(feasible)滿足約束條件可行域(可解集)所有可行點(diǎn)的集合精選優(yōu)化問(wèn)題的基本形式最優(yōu)化值最優(yōu)化解優(yōu)化問(wèn)題的域精選局部最優(yōu)問(wèn)題局部最優(yōu)問(wèn)題精選局部最優(yōu)問(wèn)題局部最優(yōu)問(wèn)題精選優(yōu)化問(wèn)題的等價(jià)形式(1)定理：若則原優(yōu)化問(wèn)題與以下優(yōu)化問(wèn)題等價(jià)精選優(yōu)化問(wèn)題的等價(jià)形式(1)定理：若則原優(yōu)化問(wèn)題與以下精選優(yōu)化問(wèn)題的等價(jià)形式(2)定理：設(shè)為一一對(duì)應(yīng)，且則原優(yōu)化問(wèn)題與以下優(yōu)化問(wèn)題等價(jià)精選優(yōu)化問(wèn)題的等價(jià)形式(2)定理：設(shè)精選優(yōu)化問(wèn)題的等價(jià)形式(3)定理：設(shè)為嚴(yán)格單調(diào)增函數(shù)；滿足當(dāng)且僅當(dāng)；滿足當(dāng)且僅當(dāng)。則原優(yōu)化問(wèn)題與以下優(yōu)化問(wèn)題等價(jià)精選優(yōu)化問(wèn)題的等價(jià)形式(3)定理：設(shè)精選優(yōu)化問(wèn)題的等價(jià)形式(4)定理：原優(yōu)化問(wèn)題與以下優(yōu)化問(wèn)題等價(jià)稱(chēng)為松弛變量精選優(yōu)化問(wèn)題的等價(jià)形式(4)定理：原優(yōu)化問(wèn)題與以下優(yōu)化問(wèn)題等精選優(yōu)化問(wèn)題的等價(jià)形式(5)定理：設(shè)滿足等式成立，當(dāng)且僅當(dāng)。則原優(yōu)化問(wèn)題與以下優(yōu)化問(wèn)題等價(jià)精選優(yōu)化問(wèn)題的等價(jià)形式(5)定理：設(shè)精選可分離變量?jī)?yōu)化問(wèn)題性質(zhì)： 其中 可以分離變量定理：優(yōu)化問(wèn)題精選可分離變量?jī)?yōu)化問(wèn)題性質(zhì)： 其中 可以分離變量定理：優(yōu)化問(wèn)精選優(yōu)化問(wèn)題的上半圖形式精選優(yōu)化問(wèn)題的上半圖形式精選凸優(yōu)化問(wèn)題的基本形式凸優(yōu)化問(wèn)題的基本描述：為仿射函數(shù)為凸函數(shù)若為準(zhǔn)凸函數(shù)，則優(yōu)化問(wèn)題稱(chēng)為準(zhǔn)凸優(yōu)化問(wèn)題。性質(zhì)：凸優(yōu)化問(wèn)題的可行域是凸集。精選凸優(yōu)化問(wèn)題的基本形式凸優(yōu)化問(wèn)題的基本描述：精選凸優(yōu)化問(wèn)題的例例： 等價(jià)于凸優(yōu)化問(wèn)題精選凸優(yōu)化問(wèn)題的例例： 等價(jià)于凸優(yōu)化問(wèn)題精選凸優(yōu)化問(wèn)題的局部最優(yōu)解定理：凸優(yōu)化問(wèn)題的局部最優(yōu)解均是全局最優(yōu)解。精選凸優(yōu)化問(wèn)題的局部最優(yōu)解定理：凸優(yōu)化問(wèn)題的局部最優(yōu)解均是全精選凸優(yōu)化問(wèn)題最優(yōu)解的微分條件定理：設(shè)為凸優(yōu)化問(wèn)題的可行域，可微。則為最優(yōu)解當(dāng)且僅當(dāng)成立。定理：非約束凸優(yōu)化問(wèn)題中，若可微。則為最優(yōu)解當(dāng)且僅當(dāng)成立。精選凸優(yōu)化問(wèn)題最優(yōu)解的微分條件定理：設(shè)為凸優(yōu)化問(wèn)題的精選凸優(yōu)化問(wèn)題的等價(jià)形式 則為最優(yōu)解當(dāng)且僅當(dāng)，且存在向量滿足定理：設(shè)凸優(yōu)化問(wèn)題僅有等式約束精選凸優(yōu)化問(wèn)題的等價(jià)形式 則為最優(yōu)解當(dāng)且僅當(dāng)精選凸優(yōu)化問(wèn)題的等價(jià)形式 則為最優(yōu)解當(dāng)且僅當(dāng)，且定理：設(shè)凸優(yōu)化問(wèn)題精選凸優(yōu)化問(wèn)題的等價(jià)形式 則為最優(yōu)解當(dāng)且僅當(dāng)精選凸優(yōu)化問(wèn)題的等價(jià)形式 等價(jià)于

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

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

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

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

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

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

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

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

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

則稱(chēng)函數(shù)為準(zhǔn)凸函數(shù)。精選準(zhǔn)凸函數(shù)(quasiconvexfunction)準(zhǔn)凸精選準(zhǔn)凸函數(shù)的判定定理定理：函數(shù)為準(zhǔn)凸函數(shù)，當(dāng)且僅當(dāng)為凸集，且對(duì)，有定理：若函數(shù)一階可微，則為準(zhǔn)凸函數(shù)，當(dāng)且僅當(dāng)為凸集，且對(duì)，有 ，有定理：若函數(shù)二階可微，且滿足對(duì) 則函數(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)造一個(gè)凸函數(shù)族，使得性質(zhì)：若為準(zhǔn)凸函數(shù)的凸函數(shù)族表示，對(duì)每一個(gè)，若，則有精選準(zhǔn)凸函數(shù)的凸函數(shù)族表示若為準(zhǔn)凸函數(shù)，根精選對(duì)數(shù)凸函數(shù) 為凸集 為凸函數(shù)。定義：函數(shù)稱(chēng)為對(duì)數(shù)凸函數(shù)，若函數(shù)滿足：定理：函數(shù)的定義域?yàn)橥辜?，且，則為對(duì)數(shù)凸函數(shù)，當(dāng)且僅當(dāng)對(duì)有對(duì)數(shù)凸函數(shù)的例精選對(duì)數(shù)凸函數(shù) 為凸集 為凸函數(shù)精選對(duì)數(shù)凸函數(shù)和凹函數(shù)的性質(zhì)性質(zhì)：對(duì)數(shù)凸性與凹性對(duì)函數(shù)乘積和正數(shù)數(shù)乘運(yùn)算均保持封閉。定理：函數(shù)二階可微，則為對(duì)數(shù)凸函數(shù)當(dāng)且僅當(dāng)性質(zhì)：對(duì)數(shù)凸性對(duì)函數(shù)加運(yùn)算保持封閉。但對(duì)數(shù)凹性對(duì)函數(shù)加運(yùn)算不封閉。推論：函數(shù)對(duì)每一個(gè)在上對(duì)數(shù)