凸優(yōu)化理論和常見的應(yīng)用

1、凸優(yōu)化理論和常見的應(yīng)用1優(yōu)化理論概述什么是優(yōu)化問題？Objective functionConstraint functions2幾類經(jīng)典的優(yōu)化問題線性規(guī)劃問題最小二乘問題凸優(yōu)化問題凸優(yōu)化問題理論上有有效的方法進(jìn)行求解！3本課程的主要內(nèi)容理論部分凸集和凸函數(shù)凸優(yōu)化問題對偶問題應(yīng)用部分逼近與擬合統(tǒng)計(jì)估計(jì)幾何問題算法部分非約束優(yōu)化方法等式約束優(yōu)化方法內(nèi)點(diǎn)法4熟悉了解凸優(yōu)化理論的基本原理和基本方法；掌握實(shí)際問題轉(zhuǎn)化為凸優(yōu)化問題的基本方法；掌握最優(yōu)化問題的經(jīng)典算法。課程要求5參考書目Stephen Boyd and Lieven Vandenberghe, “Convex Optimization”,

2、 Cambridge University Press.袁亞湘、孫文瑜，“最優(yōu)化理論與方法”，科學(xué)出版社，1999。 6凸優(yōu)化理論與應(yīng)用第一章凸集7仿射集(Affine sets)直線的表示：線段的表示：8仿射集(Affine sets)仿射集的定義：過集合C內(nèi)任意兩點(diǎn)的直線均在集合C內(nèi)，則稱集合C為仿射集。仿射集的例：直線、平面、超平面9仿射集仿射包：包含集合C的最小的仿射集。仿射維數(shù)：仿射包的維數(shù)。10仿射集內(nèi)點(diǎn)（interior）：相對內(nèi)點(diǎn)（relative interior）：11凸集(Convex Sets)凸集的定義：集合C內(nèi)任意兩點(diǎn)間的線段均在集合C內(nèi)，則稱集合C為凸集。12凸集

3、凸包的定義：包含集合C的最小的凸集。13錐(Cones)錐的定義：凸錐的定義：集合C既是凸集又是錐。錐包的定義：集合C內(nèi)點(diǎn)的所有錐組合。14超平面和半空間超平面(hyperplane) ：半空間(Halfspace)：15歐氏球和橢球歐氏球(euclidean ball):橢球(ellipsoid):16范數(shù)球和范數(shù)錐范數(shù)(norm)：范數(shù)球(norm ball)：范數(shù)錐(norm cone)：17多面體(Polyhedra)多面體：單純形(simplex)：18半正定錐(Positive semidefinite cone)n階對稱矩陣集：n階半正定矩陣集：n階正定矩陣集：n階半正定矩陣集為

4、凸錐！19保持凸性的運(yùn)算集合交運(yùn)算仿射變換透視/投射函數(shù)(perspective function)20保持凸性的運(yùn)算線性分式函數(shù)(linear-fractional function)21真錐(proper cone)真錐的定義：錐 滿足如下條件K具有內(nèi)點(diǎn)K內(nèi)不含直線22廣義不等式真錐 下的偏序關(guān)系：例：逐項(xiàng)不等式矩陣不等式廣義不等式嚴(yán)格廣義不等式23廣義不等式的性質(zhì)24嚴(yán)格廣義不等式的性質(zhì)25最值和極值最小元的定義：設(shè) ，對 ，都有 成立，則稱 為 的最小元。極小元的定義：設(shè) ，對于 ，若 ，則 成立，則稱 為 的極小元。26分割超平面(separating hyperplane)定理：設(shè)

5、 和 為兩不相交凸集，則存在超平面將 和 分離。即：27支撐超平面(supporting hyperplane)定義：設(shè)集合 ， 為 邊界上的點(diǎn)。若存在 ，滿足對任意 ，都有 成立，則稱超平面 為集合 在點(diǎn) 處的支撐超平面。定理：凸集邊界上任意一點(diǎn)均存在支撐超平面。定理：若一個(gè)閉的非中空集合，在邊界上的任意一點(diǎn)存在支撐超平面，則該集合為凸集。28對偶錐(dual cone)對偶錐的定義：設(shè) 為錐，則集合 稱為對偶錐。對偶錐的性質(zhì)：真錐的對偶錐仍然是真錐！29對偶廣義不等式廣義不等式與對偶等價(jià)性質(zhì)最小元的對偶特性：30對偶廣義不等式極小元的對偶特性反過來不一定成立！31作業(yè)P62 32凸優(yōu)化理論

6、與應(yīng)用第二章 凸函數(shù)33凸函數(shù)的定義1.定義域 為凸集；2. ，有凸函數(shù)的定義：函數(shù) ，滿足凸函數(shù)的擴(kuò)展定義：若 為凸函數(shù)，則可定義其擴(kuò)展函數(shù) 為凸函數(shù)的擴(kuò)展函數(shù)也是凸函數(shù)！34凸函數(shù)的一階微分條件若函數(shù) 的定義域 為開集，且函數(shù) 一階可微，則函數(shù) 為凸函數(shù)當(dāng)且僅當(dāng) 為凸集，且對35凸函數(shù)的二階微分條件若函數(shù) 的定義域 為開集，且函數(shù) 二階可微，則函數(shù) 為凸函數(shù)當(dāng)且僅當(dāng) 為凸集，且對 ，其Hessian矩陣36凸函數(shù)的例冪函數(shù)負(fù)對數(shù)函數(shù)負(fù)熵函數(shù)范數(shù)函數(shù)指數(shù)函數(shù)37凸函數(shù)的例38下水平集(sublevel set)定理：凸函數(shù)的任一下水平集均為凸集。任一下水平集均為凸集的函數(shù)不一定為凸函數(shù)。稱為

7、 的 下水平集。定義：集合39函數(shù)上半圖(epigraph)定理：函數(shù) 為凸函數(shù)當(dāng)且僅當(dāng) 的上半圖為凸集。稱為函數(shù) 的上半圖。定義：集合40Jensen不等式 為凸函數(shù)，則有：Jensen不等式的另外形式：41保持函數(shù)凸性的算子凸函數(shù)的逐點(diǎn)最大值凸函數(shù)與仿射變換的復(fù)合凸函數(shù)的非負(fù)加權(quán)和42保持函數(shù)凸性的算子復(fù)合運(yùn)算最小值算子凸函數(shù)的透視算子43共軛函數(shù)(conjugate function)定義：設(shè)函數(shù) ，其共軛函數(shù) ，定義為共軛函數(shù)的例共軛函數(shù)具有凸性！44共軛函數(shù)的性質(zhì)Fenchels inequality性質(zhì)：若 為凸函數(shù)，且 的上半圖是閉集，則有性質(zhì)：設(shè) 為凸函數(shù)，且可微，對于 ，若則

8、45準(zhǔn)凸函數(shù)(quasiconvex function)準(zhǔn)凸函數(shù)的例定義：設(shè)函數(shù) ，若函數(shù)的定義域和任意下水平集則稱函數(shù) 為準(zhǔn)凸函數(shù)。46準(zhǔn)凸函數(shù)的判定定理定理：函數(shù) 為準(zhǔn)凸函數(shù)，當(dāng)且僅當(dāng) 為凸集，且對 ，有定理：若函數(shù) 一階可微，則 為準(zhǔn)凸函數(shù)，當(dāng)且僅當(dāng) 為凸集，且對 ，有 ，有定理：若函數(shù) 二階可微，且滿足對則函數(shù) 準(zhǔn)凸函數(shù)。47保持準(zhǔn)凸性的算子最小值函數(shù)非負(fù)權(quán)值函數(shù)的最大值函數(shù)復(fù)合函數(shù)48準(zhǔn)凸函數(shù)的凸函數(shù)族表示若 為準(zhǔn)凸函數(shù)，根據(jù) 的任意 下水平集，我們可以構(gòu)造一個(gè)凸函數(shù)族 ，使得性質(zhì)：若 為準(zhǔn)凸函數(shù) 的凸函數(shù)族表示，對每一個(gè) ，若 ，則有49對數(shù)凸函數(shù) 為凸集為凸函數(shù)。定義：函數(shù) 稱為

9、對數(shù)凸函數(shù)，若函數(shù) 滿足：定理：函數(shù) 的定義域?yàn)橥辜?，則 為對數(shù)凸函數(shù)，當(dāng)且僅當(dāng)對 有對數(shù)凸函數(shù)的例50對數(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ù) 對每一個(gè) 在 上對數(shù)凸，則函數(shù) 也是對數(shù)凸函數(shù)。51對數(shù)凸函數(shù)和凹函數(shù)的性質(zhì)定理：函數(shù) 為對數(shù)凹函數(shù)，則函數(shù) 是對數(shù)凹函數(shù)。52廣義不等式下的凸性廣義單調(diào)性的定義：設(shè) 為真錐，函數(shù) 稱為 單調(diào)增，若函數(shù) 滿足：廣義凸函數(shù)的定義：設(shè) 為真錐，函數(shù) 稱為 凸，若函數(shù) 滿足對 均有定理(對偶

10、等價(jià))：函數(shù) 為 凸函數(shù)，當(dāng)且僅當(dāng)對所有 ， 為凸函數(shù)。53作業(yè)(1)54作業(yè)(2)P122 3.49 (1)(2)55凸優(yōu)化理論與應(yīng)用第三章 凸優(yōu)化56優(yōu)化問題的基本形式優(yōu)化問題的基本描述：優(yōu)化變量不等式約束等式約束無約束優(yōu)化57優(yōu)化問題的基本形式最優(yōu)化值最優(yōu)化解 優(yōu)化問題的域 可行點(diǎn)(解) (feasible) 滿足約束條件 可行域(可解集) 所有可行點(diǎn)的集合58局部最優(yōu)問題局部最優(yōu)問題59優(yōu)化問題的等價(jià)形式(1)定理：若 則原優(yōu)化問題與以下優(yōu)化問題等價(jià)60優(yōu)化問題的等價(jià)形式(2)定理：設(shè) 為一一對應(yīng)，且 則原優(yōu)化問題與以下優(yōu)化問題等價(jià)61優(yōu)化問題的等價(jià)形式(3)定理：設(shè) 為嚴(yán)格單調(diào)增函數(shù)

11、； 滿足 當(dāng)且僅當(dāng) ； 滿足 當(dāng)且僅當(dāng) 。則原優(yōu)化問題與以下優(yōu)化問題等價(jià)62優(yōu)化問題的等價(jià)形式(4)定理：原優(yōu)化問題與以下優(yōu)化問題等價(jià) 稱為松弛變量63優(yōu)化問題的等價(jià)形式(5)定理：設(shè) 滿足等式 成立，當(dāng)且僅當(dāng) 。則原優(yōu)化問題與以下優(yōu)化問題等價(jià)64可分離變量優(yōu)化問題性質(zhì)：其中可以分離變量定理：優(yōu)化問題65優(yōu)化問題的上半圖形式66凸優(yōu)化問題的基本形式凸優(yōu)化問題的基本描述： 為仿射函數(shù) 為凸函數(shù) 若 為準(zhǔn)凸函數(shù)，則優(yōu)化問題稱為準(zhǔn)凸優(yōu)化問題。 性質(zhì)：凸優(yōu)化問題的可行域是凸集。67凸優(yōu)化問題的例例：等價(jià)于凸優(yōu)化問題68凸優(yōu)化問題的局部最優(yōu)解定理：凸優(yōu)化問題的局部最優(yōu)解均是全局最優(yōu)解。69凸優(yōu)化問題最優(yōu)

12、解的微分條件定理：設(shè) 為凸優(yōu)化問題的可行域， 可微。則 為最優(yōu)解當(dāng)且僅當(dāng) 成立。定理：非約束凸優(yōu)化問題中，若 可微。則 為最優(yōu)解當(dāng)且僅當(dāng) 成立。70凸優(yōu)化問題的等價(jià)形式則 為最優(yōu)解當(dāng)且僅當(dāng) ，且存在向量 滿足 定理：設(shè)凸優(yōu)化問題僅有等式約束71凸優(yōu)化問題的等價(jià)形式則 為最優(yōu)解當(dāng)且僅當(dāng) ，且 定理：設(shè)凸優(yōu)化問題72凸優(yōu)化問題的等價(jià)形式等價(jià)于 定理：設(shè)凸優(yōu)化問題其中 73凸優(yōu)化問題的等價(jià)形式等價(jià)于 定理：設(shè)凸優(yōu)化問題74準(zhǔn)凸優(yōu)化問題 為準(zhǔn)凸函數(shù)， 為凸函數(shù)。準(zhǔn)凸優(yōu)化問題的基本描述注：準(zhǔn)凸優(yōu)化問題的局部最優(yōu)解不一定是全局最優(yōu)解。75準(zhǔn)凸優(yōu)化問題的上半圖形式設(shè) 為準(zhǔn)凸函數(shù) 的凸函數(shù)族表示，即 則準(zhǔn)凸優(yōu)

13、化問題的可行解問題為設(shè) 為準(zhǔn)凸優(yōu)化問題的最優(yōu)解，若上述問題可解，則 。否則 。76準(zhǔn)凸優(yōu)化問題二分法求解給定一個(gè)足夠小的 和足夠大的 ，使得區(qū)間 能包含最優(yōu)解 。給定LOOP：令求解可行解問題；若可解，則令 ，否則令若 ，則結(jié)束，否則goto LOOP。 77線性規(guī)劃(linear program,LP)LP問題的一般描述78LP問題的幾種類型標(biāo)準(zhǔn)LP問題不等式形式LP問題79標(biāo)準(zhǔn)LP問題的轉(zhuǎn)換80LP問題的例Chebyshev center of a polyhedronPiecewise-linear minimizationLinear-fractional programming81C

14、hebyshev center of a polyhedron多面體Chebyshev center：到多面體邊界距離最大的內(nèi)點(diǎn)（最深的點(diǎn)）問題描述LP形式82Piecewise-linear minimization問題描述上半圖形式LP形式83Linear-fractional programming問題描述LP形式84二次規(guī)劃(quadratic program,QP)QP問題的基本描述85二次約束二次規(guī)劃quadratically constrained quadratic program (QCQP)86QP問題的例Least-squares and regressionDistan

15、ce between polyhedra87Least-squares and regression問題描述88Distance between polyhedra問題描述QP形式89Second-order cone program, SOCPSOCP問題的基本描述二次錐約束條件90SOCP問題的例Robust linear programming問題描述其中 不是完全確定的常數(shù)。例： 為確定的常數(shù)， 為變量，其范圍滿足SOCP形式91幾何規(guī)劃(Geometric programming)單項(xiàng)式與多項(xiàng)式幾何規(guī)劃的基本描述92幾何規(guī)劃的凸形式轉(zhuǎn)換令幾何規(guī)劃的凸形式93廣義不等式約束廣義不等式約

16、束的優(yōu)化問題SOCP的描述94凸優(yōu)化理論與應(yīng)用第四章 對偶問題95優(yōu)化問題的拉格朗日函數(shù)設(shè)優(yōu)化問題：拉格朗日(Lagrangian)函數(shù)：對固定的 ，拉格朗日函數(shù) 為關(guān)于 和 的仿射函數(shù)。96拉格朗日對偶函數(shù)拉格朗日對偶函數(shù)(lagrange dual function) ：若拉格朗日函數(shù)沒有下界，則令拉格朗日對偶函數(shù)為凹函數(shù)。對 和 ，若原最優(yōu)化問題有最優(yōu)值 ，則97對偶函數(shù)的例Least-squares solution of linear equationsStandard form LPTwo-way partitioning problem98Least-squares soluti

17、on of linear equations原問題：拉格朗日函數(shù)：拉格朗日對偶函數(shù)：99Standard form LP原問題：拉格朗日函數(shù)：拉格朗日對偶函數(shù)：100Two-way partitioning problem原問題：拉格朗日函數(shù)：拉格朗日對偶函數(shù)：101對偶函數(shù)與共軛函數(shù)共軛函數(shù)共軛函數(shù)與對偶函數(shù)存在密切聯(lián)系具有線性不等式約束和線性等式約束的優(yōu)化問題： 對偶函數(shù)：102Equality constrained norm minimization問題描述：共軛函數(shù)：對偶函數(shù)：103Entropy maximization原始問題：共軛函數(shù)：對偶函數(shù)：104Minimum volum

18、e covering ellipsoid原始問題：對偶函數(shù)：共軛函數(shù)：105拉格朗日對偶問題拉格朗日對偶問題的描述：對偶可行域最優(yōu)值最優(yōu)解106LP問題的對偶問題標(biāo)準(zhǔn)LP問題對偶函數(shù)對偶問題等價(jià)描述107弱對偶性定理（弱對偶性） ：設(shè)原始問題的最優(yōu)值為 ，對偶問題的最優(yōu)值為 ，則 成立。optimal duality gap可以利用對偶問題找到原始問題最優(yōu)解的下界。108強(qiáng)對偶性強(qiáng)對偶性并不是總是成立的。定義（強(qiáng)對偶性） ：設(shè)原始問題的最優(yōu)值為 ，對偶問題的最優(yōu)值為 。若 成立，則稱原始問題和對偶問題之間具有強(qiáng)對偶性。凸優(yōu)化問題通常（但并不總是）具有強(qiáng)對偶性。Slater定理：若凸優(yōu)化問題存在

19、嚴(yán)格可行解，即存在 ，滿足則優(yōu)化問題具有強(qiáng)對偶性。該條件稱為Slater條件。109強(qiáng)對偶性存在 ，滿足弱化的Slater條件：若不等式約束條件的前 個(gè)為線性不等式約束條件，則Slater條件可以弱化為：110Least-squares solution of linear equations原問題：對偶問題：具有強(qiáng)對偶性111Lagrange dual of QCQPQCQP：拉格朗日函數(shù)：對偶函數(shù)：112Lagrange dual of QCQP對偶問題：Slater條件：存在 ，滿足113Entropy maximization原始問題：對偶函數(shù)：對偶問題：114Entropy maxi

20、mization弱化的Slater條件：存在 ，滿足115Minimum volume covering ellipsoid原始問題：對偶函數(shù)：對偶問題：116Minimum volume covering ellipsoid弱化的Slater條件總成立，因此該優(yōu)化問題具有強(qiáng)對偶性。弱化的Slater條件：存在 ，滿足117對偶可行解的不等式對于一優(yōu)化問題，若 為一可行解， 為對偶問題可行解，則有如下不等式： 為 次優(yōu)解，其中不等式可以用于對次優(yōu)解的精度估計(jì)118互補(bǔ)松弛條件所以設(shè) 為原始優(yōu)化問題的最優(yōu)解， 為對偶問題的最優(yōu)解，若兩者具有強(qiáng)對偶性，則即119KKT優(yōu)化條件設(shè)優(yōu)化問題中，函數(shù) 可

21、微。設(shè) 為原始優(yōu)化問題的最優(yōu)解， 為對偶問題的最優(yōu)解，且兩者具有強(qiáng)對偶性，則 滿足如下條件：KKT條件為必要條件！120凸優(yōu)化問題的KKT條件可微。設(shè) 滿足KKT條件，則 為原始問題的最優(yōu)解，而 為對偶問題的最優(yōu)解，且兩者具有強(qiáng)對偶性。設(shè)原始問題為凸優(yōu)化問題中，函數(shù)121例原始凸優(yōu)化問題KKT條件122例其中解得123凸優(yōu)化問題的對偶求解存在唯一解 。若 為原始問題的可行解，則 即為原始問題的最優(yōu)解；若 不是原始問題的可行解，則原始問題不存在最優(yōu)解。設(shè)原始優(yōu)化問題與對偶問題具有強(qiáng)對偶性，且 為對偶問題的最優(yōu)解。 存在唯一的最小解，即124擾動問題擾動問題：當(dāng) 時(shí)即為原始問題。若 為正，則第 個(gè)

22、不等式約束被放寬；若 為負(fù)，則第 個(gè)不等式約束被收緊。記 為擾動問題的最優(yōu)解。若擾動問題無最優(yōu)解，則記125靈敏度分析設(shè)對偶問題存在最優(yōu)解，且與原始問題具有強(qiáng)對偶性，若非干擾問題的最優(yōu)對偶解為 ，則有若 在 處可微，則126選擇定理定義（弱選擇性）：若兩個(gè)不等式（等式）系統(tǒng)，至多有一個(gè)可解，則稱這兩個(gè)系統(tǒng)具有弱選擇性。對偶不等式組設(shè)原始問題的約束條件：對偶問題原始問題的約束條件與對偶不等式組具有弱選擇性。127選擇定理對偶不等式組設(shè)原始問題的嚴(yán)格不等式約束條件：原始問題的嚴(yán)格不等式約束條件與對偶不等式組具有弱選擇性。128選擇定理定義（強(qiáng)選擇性）：若兩個(gè)不等式（等式）系統(tǒng)，恰有一個(gè)可解，則稱這

23、兩個(gè)系統(tǒng)具有強(qiáng)選擇性。對偶不等式組設(shè)原始問題為凸優(yōu)化問題，其嚴(yán)格不等式約束條件為：若存在 ，滿足 ，則上述兩不等式約束系統(tǒng)具有強(qiáng)選擇性。129選擇定理對偶不等式組設(shè)原始問題為凸優(yōu)化問題，其不等式約束條件為：則原始問題的不等式約束條件與對偶不等式組具有強(qiáng)選擇性。若存在 ，滿足 ，且下述優(yōu)化問題存在最優(yōu)解130罰函數(shù)的例 范數(shù)：死區(qū)線性罰函數(shù)：對數(shù)門限罰函數(shù)131魯棒的罰函數(shù)若 大到一定程度時(shí)，罰函數(shù)為 的線性函數(shù)，則稱該罰函數(shù)為魯棒的罰函數(shù)。Huber罰函數(shù)132最小范數(shù)問題問題描述：其中 為方程組 的解?？梢韵サ仁郊s束將其轉(zhuǎn)換為范數(shù)逼近問題：133最小范數(shù)問題最小平方范數(shù)問題：范數(shù) ，最優(yōu)解

24、滿足：最小罰問題：絕對值和最小問題：范數(shù) ，原問題可轉(zhuǎn)換為LP問題：134正則逼近二元矢量優(yōu)化問題描述：正則化問題：最優(yōu)解描述了兩分量的一條折中曲線。135正則逼近Tikhonov正則化問題：為二次優(yōu)化問題：最優(yōu)解的形式：136正則逼近Tikhonov光滑正則化問題： 為二階差分算子：137信號復(fù)原已知加噪信號：信號復(fù)原問題的描述：函數(shù) 為正則函數(shù)或光滑函數(shù)。138信號復(fù)原139信號復(fù)原140信號復(fù)原141魯棒逼近問題描述：隨機(jī)魯棒逼近： 為隨機(jī)變量，逼近問題轉(zhuǎn)換為最小化期望例：隨機(jī)魯棒逼近為：轉(zhuǎn)換為：142隨機(jī)魯棒逼近 為隨機(jī)變量：最小平方隨機(jī)魯棒逼近為：轉(zhuǎn)換為：其中143最壞情況魯棒逼近考

25、慮 ，最壞情況魯棒逼近為： 例：隨機(jī)魯棒逼近為：轉(zhuǎn)換為：144凸優(yōu)化理論與應(yīng)用第6章 統(tǒng)計(jì)估計(jì)145概率分布的參數(shù)估計(jì)隨機(jī)變量的概率密度為 ，其中 為概率分布的參數(shù)，且參數(shù)未知。參數(shù)估計(jì)的目標(biāo)就是通過一些已知樣本估計(jì)獲得參數(shù)的最優(yōu)近似值。問題描述 為樣本觀測值； 為對數(shù)似然函數(shù)；若似然函數(shù)為凹函數(shù)，則優(yōu)化問題為凸優(yōu)化問題。146具有獨(dú)立同分布噪聲的線性測量線性測量模型： 為觀測值或測量值； 為未知參數(shù)向量； 獨(dú)立同分布噪聲，其概率密度為 。似然函數(shù)為最大似然估計(jì)問題為：147例高斯白噪聲對數(shù)似然函數(shù)：區(qū)間 上均勻分布的噪聲：對數(shù)似然函數(shù)：148邏輯回歸隨機(jī)變量 的概率分布為： 為參數(shù)； 為可觀

26、測的解釋變量； 為觀察值。對數(shù)似然函數(shù)：149假定測驗(yàn)隨機(jī)變量 ，有 種可能（假定）的分布；假定 ： 的概率分布為假定測驗(yàn)的目標(biāo)：由觀察值猜測隨機(jī)變量最有可能服從哪種假定的分布。當(dāng) 時(shí)，稱為二元假定測驗(yàn)。隨機(jī)檢測子：非負(fù)元素矩陣 150假定測驗(yàn) 為當(dāng) 實(shí)際服從第1種假定分布而猜測為第2種假定分布的概率； 為當(dāng) 實(shí)際服從第2種假定分布而猜測為第1種假定分布的概率；多目標(biāo)優(yōu)化形式：檢測概率矩陣151假定測驗(yàn)最小最大值形式尺度優(yōu)化形式：152例 在兩種假設(shè)下的概率分布為：153例154實(shí)驗(yàn)設(shè)計(jì)線性測量問題最大似然估計(jì)值： 獨(dú)立同分布高斯白噪聲，服從分布 。估計(jì)誤差 均值為0，方差為信賴橢圓為155實(shí)

27、驗(yàn)設(shè)計(jì)實(shí)驗(yàn)設(shè)計(jì)的目標(biāo)：尋找 ，使得誤差的方差矩陣最小。向量優(yōu)化形式：為整數(shù)問題，求解較困難。156實(shí)驗(yàn)設(shè)計(jì)當(dāng) 時(shí)，令 近似為一連續(xù)實(shí)數(shù)，原問題可松弛轉(zhuǎn)換為連續(xù)實(shí)數(shù)優(yōu)化：157凸優(yōu)化理論與應(yīng)用第7章 無約束優(yōu)化158無約束優(yōu)化問題問題描述：無約束問題求解的兩種方法：迭代逼近：求解梯度方程： 為凸函數(shù)，且二次可微。159例梯度方程二次優(yōu)化：160迭代起始點(diǎn)滿足條件2的幾種函數(shù)：起始點(diǎn) 滿足：函數(shù) 任意下水平集都是閉集；函數(shù)的定義域?yàn)楫?dāng) 時(shí)，161強(qiáng)凸性定義：函數(shù) 在 上具有強(qiáng)凸性，若 滿足若函數(shù) 具有強(qiáng)凸性，則有 為最優(yōu)值，則162強(qiáng)凸性則有 為最優(yōu)值，則若函數(shù) 在 上具有強(qiáng)凸性，則可以證明存在

28、，滿足 163強(qiáng)凸性對于 ，矩陣 的特征值從大到小依次為 。則有： 定義：矩陣 的條件數(shù)為最大特征值與最小特征值之比，即 。條件數(shù)的上界：164下降法下降法的基本原理：迭代 ，滿足 為下降方向， 為步長因子。對于凸函數(shù) ，當(dāng) 滿足 時(shí)，存在某個(gè) ，使得 。165下降法下降法的一般步驟：給出初始點(diǎn) ；循環(huán)迭代計(jì)算下降方向 ； 搜索步長因子 ； 迭代： 166步長因子搜索精確一維搜索：回溯一維搜索：給定參數(shù)循環(huán)迭代初始化：令 ； 若 ，則終止退出； 否則令 167步長因子搜索168梯度下降法算法簡單，但收斂速度較慢。下降方向：終止條件：收斂性：其中 。169收斂性分析則有：設(shè)函數(shù) 具有強(qiáng)凸性，則存

29、在 和 ，滿足：若 采用精確一維搜索，則 ，收斂速度因子：若 采用回溯一維搜索，收斂速度因子：條件數(shù)越大，收斂速度越小。170例當(dāng) 時(shí)，算法收斂速度很慢。初始解為 ，采用精確一維搜索；迭代：171例步長因子采用回溯一維搜索。172最速下降法歸一化最速下降方向：非歸一化最速下降方向歐式范數(shù)：二次范數(shù) ： 范數(shù)：173最速下降法174收斂性分析范數(shù)界：收斂速度因子：175牛頓法設(shè)函數(shù) 二階可微，則在 附近， 的泰勒展式為：泰勒展開可作為 在 附近的近似；下降方向：為二次范數(shù) 上的最速下降方向。176牛頓法177牛頓減量令 為 在 處的牛頓減量。牛頓減量的性質(zhì)1：性質(zhì)2：牛頓減量可作為迭代求解的誤差

30、估計(jì)。性質(zhì)3：牛頓減量具有仿射不變性。178牛頓方法初始化：給定初始解 以及LOOP：計(jì)算：若 則終止退出；一維線性搜索：計(jì)算步長因子 ；迭代：179收斂性分析定理：假設(shè) 二階連續(xù)可微，具有強(qiáng)凸性，即存在 ，滿足：則存在 ，且海森矩陣滿足Lipschitz條件，即存在 ，滿足：若 ，則 ；若 ，則 ，且180收斂性分析定理：假設(shè) 二階連續(xù)可微，具有強(qiáng)凸性，即存在 ，滿足：則存在 ，對于 ，有且海森矩陣滿足Lipschitz條件，即存在 ，滿足：181例182凸優(yōu)化理論與應(yīng)用第8章 等式約束優(yōu)化183等式約束優(yōu)化問題問題描述： 為凸函數(shù)，且二次連續(xù)可微，且假設(shè)最優(yōu)值 存在，則 為最優(yōu)解當(dāng)且僅當(dāng)存

31、在 ，滿足（KKT條件）：184例KKT系統(tǒng)：二次優(yōu)化：KKT系統(tǒng)可解，則二次優(yōu)化問題存在最優(yōu)解。系數(shù)矩陣稱為KKT矩陣。KKT矩陣非奇異當(dāng)且僅當(dāng)：185消去等式約束方程組 的解集： 為方程組的一個(gè)特解， 為 的零空間范圍。無約束優(yōu)化形式：若 為最優(yōu)解，則有186對偶問題對偶形式：187牛頓法牛頓減量 為等式約束優(yōu)化的可行解，則在 附近原問題的二次近似為：設(shè) 和 分別為該問題和對偶問題的最優(yōu)解，則滿足：188牛頓減量性質(zhì)2：牛頓減量具有仿射不變性。牛頓減量牛頓減量的性質(zhì)：189可行下降方向可行下降方向：設(shè) 滿足方程組 。若 滿足方程組 ，則 。 稱為可行方向。若對于較小的 ，有 ，則 為可行下

32、降方向。190等式約束的牛頓方法LOOP：計(jì)算 及 ；若 則終止退出；一維線性搜索：計(jì)算步長因子 ；迭代：初始化：給定初始解 滿足 ，以及191消去等式約束的牛頓方法轉(zhuǎn)換為等式約束下的牛頓方法：初始值 ，第 次迭代值 ；初始值：迭代值：192非可行解為初始點(diǎn)的牛頓法函數(shù) 二階連續(xù)可微，因此有 為等式約束優(yōu)化的非可行解，則增量 應(yīng)盡可能使 滿足KKT條件，即：設(shè) 和 為KKT條件的解，即有：193非可行解為初始點(diǎn)的牛頓法則KKT條件可表示為：令設(shè) 為不滿足KKT條件，則其迭代量需滿足：即194非可行解為初始點(diǎn)的牛頓法當(dāng) 且 時(shí)，終止迭代。LOOP：計(jì)算 和 ；回溯一維線性搜索：迭代：初始化：給定初始解 及 ，以及令 ；While 195KKT系統(tǒng)的求解其中 ，且滿足 。1. 分解；2.若