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

-,1,凸優(yōu)化理論與應(yīng)用,莊伯金B(yǎng)jzhuang,-,2,優(yōu)化理論概述,什么是優(yōu)化問題？,Objectivefunction,Constraintfunctions,-,3,幾類經(jīng)典的優(yōu)化問題,線性規(guī)劃問題,最小二乘問題,凸優(yōu)化問題,凸優(yōu)化問題理論上有有效的方法進(jìn)行求解！,-,4,本課程的主要內(nèi)容,理論部分凸集和凸函數(shù)凸優(yōu)化問題對偶問題應(yīng)用部分逼近與擬合統(tǒng)計(jì)估計(jì)幾何問題算法部分非約束優(yōu)化方法等式約束優(yōu)化方法內(nèi)點(diǎn)法,-,5,熟悉了解凸優(yōu)化理論的基本原理和基本方法；掌握實(shí)際問題轉(zhuǎn)化為凸優(yōu)化問題的基本方法；掌握最優(yōu)化問題的經(jīng)典算法。,課程要求,-,6,參考書目,StephenBoydandLievenVandenberghe,“ConvexOptimization”,CambridgeUniversityPress.袁亞湘、孫文瑜，“最優(yōu)化理論與方法”，科學(xué)出版社，1999。,-,7,凸優(yōu)化理論與應(yīng)用,第一章凸集,-,8,仿射集(Affinesets),直線的表示：,線段的表示：,-,9,仿射集(Affinesets),仿射集的定義：過集合C內(nèi)任意兩點(diǎn)的直線均在集合C內(nèi)，則稱集合C為仿射集。仿射集的例：直線、平面、超平面,-,10,仿射集,仿射包：包含集合C的最小的仿射集。,仿射維數(shù)：仿射包的維數(shù)。,-,11,仿射集,內(nèi)點(diǎn)（interior）：,相對內(nèi)點(diǎn)（relativeinterior）：,-,12,凸集(ConvexSets),凸集的定義：集合C內(nèi)任意兩點(diǎn)間的線段均在集合C內(nèi)，則稱集合C為凸集。,-,13,凸集,凸包的定義：包含集合C的最小的凸集。,-,14,錐(Cones),錐的定義：,凸錐的定義：集合C既是凸集又是錐。,錐包的定義：集合C內(nèi)點(diǎn)的所有錐組合。,-,15,超平面和半空間,超平面(hyperplane)：,半空間(Halfspace)：,-,16,歐氏球和橢球,歐氏球(euclideanball):,橢球(ellipsoid):,-,17,范數(shù)球和范數(shù)錐,范數(shù)(norm)：,范數(shù)球(normball)：,范數(shù)錐(normcone)：,-,18,多面體(Polyhedra),多面體：,單純形(simplex)：,-,19,半正定錐(Positivesemidefinitecone),n階對稱矩陣集：,n階半正定矩陣集：,n階正定矩陣集：,n階半正定矩陣集為凸錐！,-,20,保持凸性的運(yùn)算,集合交運(yùn)算仿射變換透視/投射函數(shù)(perspectivefunction),-,21,保持凸性的運(yùn)算,線性分式函數(shù)(linear-fractionalfunction),-,22,真錐(propercone),真錐的定義：錐滿足如下條件,K具有內(nèi)點(diǎn),K內(nèi)不含直線,-,23,廣義不等式,真錐下的偏序關(guān)系：,例：逐項(xiàng)不等式矩陣不等式,廣義不等式,嚴(yán)格廣義不等式,-,24,廣義不等式的性質(zhì),-,25,嚴(yán)格廣義不等式的性質(zhì),-,26,最值和極值,最小元的定義：設(shè)，對，都有成立，則稱為的最小元。,極小元的定義：設(shè)，對于，若，則成立，則稱為的極小元。,-,27,分割超平面(separatinghyperplane),定理：設(shè)和為兩不相交凸集，則存在超平面將和分離。即：,-,28,支撐超平面(supportinghyperplane),定義：設(shè)集合，為邊界上的點(diǎn)。若存在，滿足對任意，都有成立，則稱超平面為集合在點(diǎn)處的支撐超平面。,定理：凸集邊界上任意一點(diǎn)均存在支撐超平面。定理：若一個(gè)閉的非中空集合，在邊界上的任意一點(diǎn)存在支撐超平面，則該集合為凸集。,-,29,對偶錐(dualcone),對偶錐的定義：設(shè)為錐，則集合稱為對偶錐。,對偶錐的性質(zhì)：,真錐的對偶錐仍然是真錐！,-,30,對偶廣義不等式,廣義不等式與對偶等價(jià)性質(zhì),最小元的對偶特性：,-,31,對偶廣義不等式,極小元的對偶特性,反過來不一定成立！,-,32,作業(yè),P602.8P602.10P602.14P622.16P622.18P642.30P642.31P642.33,-,33,凸優(yōu)化理論與應(yīng)用,第二章凸函數(shù),-,34,凸函數(shù)的定義,1.定義域?yàn)橥辜?2.，有,凸函數(shù)的定義：函數(shù)，滿足,凸函數(shù)的擴(kuò)展定義：若為凸函數(shù)，則可定義其擴(kuò)展函數(shù)為,凸函數(shù)的擴(kuò)展函數(shù)也是凸函數(shù)！,-,35,凸函數(shù)的一階微分條件,若函數(shù)的定義域?yàn)殚_集，且函數(shù)一階可微，則函數(shù)為凸函數(shù)當(dāng)且僅當(dāng)為凸集，且對,-,36,凸函數(shù)的二階微分條件,若函數(shù)的定義域?yàn)殚_集，且函數(shù)二階可微，則函數(shù)為凸函數(shù)當(dāng)且僅當(dāng)為凸集，且對，其Hessian矩陣,-,37,凸函數(shù)的例,冪函數(shù),負(fù)對數(shù)函數(shù),負(fù)熵函數(shù),范數(shù)函數(shù),指數(shù)函數(shù),-,38,凸函數(shù)的例,-,39,下水平集(sublevelset),定理：凸函數(shù)的任一下水平集均為凸集。,任一下水平集均為凸集的函數(shù)不一定為凸函數(shù)。,-,40,函數(shù)上半圖(epigraph),定理：函數(shù)為凸函數(shù)當(dāng)且僅當(dāng)?shù)纳习雸D為凸集。,-,41,Jensen不等式,為凸函數(shù)，則有：,Jensen不等式的另外形式：,-,42,保持函數(shù)凸性的算子,凸函數(shù)的逐點(diǎn)最大值,凸函數(shù)與仿射變換的復(fù)合,凸函數(shù)的非負(fù)加權(quán)和,-,43,保持函數(shù)凸性的算子,復(fù)合運(yùn)算,最小值算子,凸函數(shù)的透視算子,-,44,共軛函數(shù)(conjugatefunction),定義：設(shè)函數(shù)，其共軛函數(shù)，定義為,共軛函數(shù)的例,共軛函數(shù)具有凸性！,-,45,共軛函數(shù)的性質(zhì),Fenchelsinequality,性質(zhì)：若為凸函數(shù)，且的上半圖是閉集，則有,-,46,準(zhǔn)凸函數(shù)(quasiconvexfunction),準(zhǔn)凸函數(shù)的例,-,47,準(zhǔn)凸函數(shù)的判定定理,定理：函數(shù)為準(zhǔn)凸函數(shù)，當(dāng)且僅當(dāng)為凸集，且對，有,定理：若函數(shù)一階可微，則為準(zhǔn)凸函數(shù)，當(dāng)且僅當(dāng)為凸集，且對，有,-,48,最小值函數(shù),非負(fù)權(quán)值函數(shù)的最大值函數(shù),保持準(zhǔn)凸性的算子,復(fù)合函數(shù),-,49,準(zhǔn)凸函數(shù)的凸函數(shù)族表示,若為準(zhǔn)凸函數(shù)，根據(jù)的任意下水平集，我們可以構(gòu)造一個(gè)凸函數(shù)族，使得,性質(zhì)：若為準(zhǔn)凸函數(shù)的凸函數(shù)族表示，對每一個(gè)，若，則有,-,50,對數(shù)凸函數(shù),對數(shù)凸函數(shù)的例,-,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ù)對每一個(gè)在上對數(shù)凸，則函數(shù)也是對數(shù)凸函數(shù)。,-,52,對數(shù)凸函數(shù)和凹函數(shù)的性質(zhì),定理：函數(shù)為對數(shù)凹函數(shù)，則函數(shù)是對數(shù)凹函數(shù)。,-,53,廣義不等式下的凸性,廣義單調(diào)性的定義：設(shè)為真錐，函數(shù)稱為單調(diào)增，若函數(shù)滿足：,定理(對偶等價(jià))：函數(shù)為凸函數(shù)，當(dāng)且僅當(dāng)對所有，為凸函數(shù)。,-,54,作業(yè)(1),P1163.16P1163.21,-,55,作業(yè)(2),P1213.41P1223.49(1)(2),-,56,凸優(yōu)化理論與應(yīng)用,第三章凸優(yōu)化,-,57,優(yōu)化問題的基本形式,優(yōu)化問題的基本描述：,優(yōu)化變量,不等式約束,等式約束,無約束優(yōu)化,-,58,優(yōu)化問題的基本形式,最優(yōu)化值,最優(yōu)化解,優(yōu)化問題的域,可行點(diǎn)(解)(feasible)滿足約束條件,可行域(可解集)所有可行點(diǎn)的集合,-,59,局部最優(yōu)問題,局部最優(yōu)問題,-,60,優(yōu)化問題的等價(jià)形式(1),-,61,優(yōu)化問題的等價(jià)形式(2),-,62,優(yōu)化問題的等價(jià)形式(3),定理：設(shè)為嚴(yán)格單調(diào)增函數(shù)；滿足當(dāng)且僅當(dāng)；滿足當(dāng)且僅當(dāng)。則原優(yōu)化問題與以下優(yōu)化問題等價(jià),-,63,優(yōu)化問題的等價(jià)形式(4),定理：原優(yōu)化問題與以下優(yōu)化問題等價(jià),稱為松弛變量,-,64,優(yōu)化問題的等價(jià)形式(5),定理：設(shè)滿足等式成立，當(dāng)且僅當(dāng)。則原優(yōu)化問題與以下優(yōu)化問題等價(jià),-,65,可分離變量優(yōu)化問題,-,66,優(yōu)化問題的上半圖形式,-,67,凸優(yōu)化問題的基本形式,凸優(yōu)化問題的基本描述：,為仿射函數(shù),為凸函數(shù),若為準(zhǔn)凸函數(shù)，則優(yōu)化問題稱為準(zhǔn)凸優(yōu)化問題。,性質(zhì)：凸優(yōu)化問題的可行域是凸集。,-,68,凸優(yōu)化問題的例,例：,等價(jià)于凸優(yōu)化問題,-,69,凸優(yōu)化問題的局部最優(yōu)解,定理：凸優(yōu)化問題的局部最優(yōu)解均是全局最優(yōu)解。,-,70,凸優(yōu)化問題最優(yōu)解的微分條件,定理：設(shè)為凸優(yōu)化問題的可行域，可微。則為最優(yōu)解當(dāng)且僅當(dāng)成立。,定理：非約束凸優(yōu)化問題中，若可微。則為最優(yōu)解當(dāng)且僅當(dāng)成立。,-,71,凸優(yōu)化問題的等價(jià)形式,-,72,凸優(yōu)化問題的等價(jià)形式,-,73,凸優(yōu)化問題的等價(jià)形式,-,74,凸優(yōu)化問題的等價(jià)形式,等價(jià)于,定理：設(shè)凸優(yōu)化問題,-,75,準(zhǔn)凸優(yōu)化問題,注：準(zhǔn)凸優(yōu)化問題的局部最優(yōu)解不一定是全局最優(yōu)解。,-,76,準(zhǔn)凸優(yōu)化問題的上半圖形式,設(shè)為準(zhǔn)凸函數(shù)的凸函數(shù)族表示，即,則準(zhǔn)凸優(yōu)化問題的可行解問題為,設(shè)為準(zhǔn)凸優(yōu)化問題的最優(yōu)解，若上述問題可解，則。否則。,-,77,準(zhǔn)凸優(yōu)化問題二分法求解,給定一個(gè)足夠小的和足夠大的，使得區(qū)間能包含最優(yōu)解。給定,LOOP：令求解可行解問題；若可解，則令，否則令若，則結(jié)束，否則gotoLOOP。,-,78,線性規(guī)劃(linearprogram,LP),LP問題的一般描述,-,79,LP問題的幾種類型,標(biāo)準(zhǔn)LP問題,不等式形式LP問題,-,80,標(biāo)準(zhǔn)LP問題的轉(zhuǎn)換,-,81,LP問題的例,Chebyshevcenterofapolyhedron,Piecewise-linearminimization,Linear-fractionalprogramming,-,82,Chebyshevcenterofapolyhedron,多面體,Chebyshevcenter：到多面體邊界距離最大的內(nèi)點(diǎn)（最深的點(diǎn)）,問題描述,LP形式,-,83,Piecewise-linearminimization,問題描述,上半圖形式,LP形式,-,84,Linear-fractionalprogramming,問題描述,LP形式,-,85,二次規(guī)劃(quadraticprogram,QP),QP問題的基本描述,-,86,二次約束二次規(guī)劃,quadraticallyconstrainedquadraticprogram(QCQP),-,87,QP問題的例,Least-squaresandregression,Distancebetweenpolyhedra,-,88,Least-squaresandregression,問題描述,-,89,Distancebetweenpolyhedra,問題描述,QP形式,-,90,Second-orderconeprogram,SOCP,SOCP問題的基本描述,二次錐約束條件,-,91,SOCP問題的例Robustlinearprogramming,例：為確定的常數(shù)，為變量，其范圍滿足,SOCP形式,-,92,幾何規(guī)劃(Geometricprogramming),單項(xiàng)式與多項(xiàng)式,幾何規(guī)劃的基本描述,-,93,幾何規(guī)劃的凸形式轉(zhuǎn)換,令,幾何規(guī)劃的凸形式,-,94,廣義不等式約束,廣義不等式約束的優(yōu)化問題,SOCP的描述,-,95,凸優(yōu)化理論與應(yīng)用,第四章對偶問題,-,96,優(yōu)化問題的拉格朗日函數(shù),設(shè)優(yōu)化問題：,拉格朗日(Lagrangian)函數(shù)：,對固定的，拉格朗日函數(shù)為關(guān)于和的仿射函數(shù)。,-,97,拉格朗日對偶函數(shù),拉格朗日對偶函數(shù)(lagrangedualfunction)：,若拉格朗日函數(shù)沒有下界，則令,拉格朗日對偶函數(shù)為凹函數(shù)。,對和，若原最優(yōu)化問題有最優(yōu)值，則,-,98,對偶函數(shù)的例,Least-squaressolutionoflinearequations,StandardformLP,Two-waypartitioningproblem,-,99,Least-squaressolutionoflinearequations,原問題：,拉格朗日函數(shù)：,拉格朗日對偶函數(shù)：,-,100,StandardformLP,原問題：,拉格朗日函數(shù)：,拉格朗日對偶函數(shù)：,-,101,Two-waypartitioningproblem,原問題：,拉格朗日函數(shù)：,拉格朗日對偶函數(shù)：,-,102,對偶函數(shù)與共軛函數(shù),共軛函數(shù),共軛函數(shù)與對偶函數(shù)存在密切聯(lián)系,具有線性不等式約束和線性等式約束的優(yōu)化問題：,對偶函數(shù)：,-,103,Equalityconstrainednormminimization,問題描述：,共軛函數(shù)：,對偶函數(shù)：,-,104,Entropymaximization,原始問題：,共軛函數(shù)：,對偶函數(shù)：,-,105,Minimumvolumecoveringellipsoid,原始問題：,對偶函數(shù)：,共軛函數(shù)：,-,106,拉格朗日對偶問題,拉格朗日對偶問題的描述：,對偶可行域,最優(yōu)值,最優(yōu)解,-,107,LP問題的對偶問題,標(biāo)準(zhǔn)LP問題,對偶函數(shù),對偶問題,等價(jià)描述,-,108,弱對偶性,定理（弱對偶性）：設(shè)原始問題的最優(yōu)值為，對偶問題的最優(yōu)值為，則成立。,optimaldualitygap,可以利用對偶問題找到原始問題最優(yōu)解的下界。,-,109,強(qiáng)對偶性,強(qiáng)對偶性并不是總是成立的。,定義（強(qiáng)對偶性）：設(shè)原始問題的最優(yōu)值為，對偶問題的最優(yōu)值為。若成立，則稱原始問題和對偶問題之間具有強(qiáng)對偶性。,凸優(yōu)化問題通常（但并不總是）具有強(qiáng)對偶性。,-,110,強(qiáng)對偶性,存在，滿足,弱化的Slater條件：若不等式約束條件的前個(gè)為線性不等式約束條件，則Slater條件可以弱化為：,-,111,Least-squaressolutionoflinearequations,原問題：,對偶問題：,具有強(qiáng)對偶性,-,112,LagrangedualofQCQP,QCQP：,拉格朗日函數(shù)：,對偶函數(shù)：,-,113,LagrangedualofQCQP,對偶問題：,Slater條件：存在，滿足,-,114,Entropymaximization,原始問題：,對偶函數(shù)：,對偶問題：,-,115,Entropymaximization,弱化的Slater條件：存在，滿足,-,116,Minimumvolumecoveringellipsoid,原始問題：,對偶函數(shù)：,對偶問題：,-,117,Minimumvolumecoveringellipsoid,弱化的Slater條件總成立，因此該優(yōu)化問題具有強(qiáng)對偶性。,弱化的Slater條件：存在，滿足,-,118,對偶可行解的不等式,對于一優(yōu)化問題，若為一可行解，為對偶問題可行解，則有如下不等式：,為次優(yōu)解，其中,不等式可以用于對次優(yōu)解的精度估計(jì),-,119,互補(bǔ)松弛條件,所以,設(shè)為原始優(yōu)化問題的最優(yōu)解，為對偶問題的最優(yōu)解，若兩者具有強(qiáng)對偶性，則,即,-,120,KKT優(yōu)化條件,設(shè)優(yōu)化問題中，函數(shù)可微。設(shè)為原始優(yōu)化問題的最優(yōu)解，為對偶問題的最優(yōu)解，且兩者具有強(qiáng)對偶性，則滿足如下條件：,KKT條件為必要條件！,-,121,凸優(yōu)化問題的KKT條件,-,122,例,原始凸優(yōu)化問題,KKT條件,-,123,例,其中,解得,-,124,凸優(yōu)化問題的對偶求解,-,125,擾動問題,擾動問題：,當(dāng)時(shí)即為原始問題。,若為正，則第個(gè)不等式約束被放寬；若為負(fù)，則第個(gè)不等式約束被收緊。,記為擾動問題的最優(yōu)解。若擾動問題無最優(yōu)解，則記,-,126,靈敏度分析,設(shè)對偶問題存在最優(yōu)解，且與原始問題具有強(qiáng)對偶性，若非干擾問題的最優(yōu)對偶解為，則有,若在處可微，則,-,127,定義（弱選擇性）：若兩個(gè)不等式（等式）系統(tǒng)，至多有一個(gè)可解，則稱這兩個(gè)系統(tǒng)具有弱選擇性。,選擇定理,對偶不等式組,設(shè)原始問題的約束條件：,對偶問題,原始問題的約束條件與對偶不等式組具有弱選擇性。,-,128,選擇定理,對偶不等式組,設(shè)原始問題的嚴(yán)格不等式約束條件：,原始問題的嚴(yán)格不等式約束條件與對偶不等式組具有弱選擇性。,-,129,定義（強(qiáng)選擇性）：若兩個(gè)不等式（等式）系統(tǒng)，恰有一個(gè)可解，則稱這兩個(gè)系統(tǒng)具有強(qiáng)選擇性。,選擇定理,對偶不等式組,設(shè)原始問題為凸優(yōu)化問題，其嚴(yán)格不等式約束條件為：,若存在，滿足，則上述兩不等式約束系統(tǒng)具有強(qiáng)選擇性。,-,130,選擇定理,對偶不等式組,設(shè)原始問題為凸優(yōu)化問題，其不等式約束條件為：,-,131,罰函數(shù)的例,范數(shù)：,死區(qū)線性罰函數(shù)：,對數(shù)門限罰函數(shù),-,132,魯棒的罰函數(shù),若大到一定程度時(shí)，罰函數(shù)為的線性函數(shù)，則稱該罰函數(shù)為魯棒的罰函數(shù)。,Huber罰函數(shù),-,133,最小范數(shù)問題,問題描述：,其中為方程組的解。,可以消去等式約束將其轉(zhuǎn)換為范數(shù)逼近問題：,-,134,最小范數(shù)問題,最小平方范數(shù)問題：范數(shù)，最優(yōu)解滿足：,最小罰問題：,絕對值和最小問題：范數(shù)，原問題可轉(zhuǎn)換為LP問題：,-,135,正則逼近,二元矢量優(yōu)化問題描述：,正則化問題：,最優(yōu)解描述了兩分量的一條折中曲線。,-,136,正則逼近,Tikhonov正則化問題：,為二次優(yōu)化問題：,最優(yōu)解的形式：,-,137,正則逼近,Tikhonov光滑正則化問題：,為二階差分算子：,-,138,信號復(fù)原,已知加噪信號：,信號復(fù)原問題的描述：,函數(shù)為正則函數(shù)或光滑函數(shù)。,-,139,信號復(fù)原,-,140,信號復(fù)原,-,141,信號復(fù)原,-,142,魯棒逼近,問題描述：,隨機(jī)魯棒逼近：為隨機(jī)變量，逼近問題轉(zhuǎn)換為最小化期望,例：,隨機(jī)魯棒逼近為：,轉(zhuǎn)換為：,-,143,隨機(jī)魯棒逼近,為隨機(jī)變量：,最小平方隨機(jī)魯棒逼近為：,轉(zhuǎn)換為：,其中,-,144,最壞情況魯棒逼近,考慮，最壞情況魯棒逼近為：,例：,隨機(jī)魯棒逼近為：,轉(zhuǎn)換為：,-,145,凸優(yōu)化理論與應(yīng)用,第6章統(tǒng)計(jì)估計(jì),-,146,概率分布的參數(shù)估計(jì),隨機(jī)變量的概率密度為，其中為概率分布的參數(shù)，且參數(shù)未知。參數(shù)估計(jì)的目標(biāo)就是通過一些已知樣本估計(jì)獲得參數(shù)的最優(yōu)近似值。,問題描述,為樣本觀測值；,為對數(shù)似然函數(shù)；,若似然函數(shù)為凹函數(shù)，則優(yōu)化問題為凸優(yōu)化問題。,-,147,具有獨(dú)立同分布噪聲的線性測量,線性測量模型：,為觀測值或測量值；,為未知參數(shù)向量；,獨(dú)立同分布噪聲，其概率密度為。,似然函數(shù)為,最大似然估計(jì)問題為：,-,148,例,高斯白噪聲,對數(shù)似然函數(shù)：,區(qū)間上均勻分布的噪聲：,對數(shù)似然函數(shù)：,-,149,邏輯回歸,隨機(jī)變量的概率分布為：,為參數(shù)；,為可觀測的解釋變量；為觀察值。,對數(shù)似然函數(shù)：,-,150,假定測驗(yàn),隨機(jī)變量，有種可能（假定）的分布；,假定：的概率分布為,假定測驗(yàn)的目標(biāo)：由觀察值猜測隨機(jī)變量最有可能服從哪種假定的分布。,當(dāng)時(shí)，稱為二元假定測驗(yàn)。,隨機(jī)檢測子：非負(fù)元素矩陣,-,151,假定測驗(yàn),為當(dāng)實(shí)際服從第1種假定分布而猜測為第2種假定分布的概率；,為當(dāng)實(shí)際服從第2種假定分布而猜測為第1種假定分布的概率；,多目標(biāo)優(yōu)化形式：,檢測概率矩陣,-,152,假定測驗(yàn),最小最大值形式,尺度優(yōu)化形式：,-,153,例,在兩種假設(shè)下的概率分布為：,-,154,例,-,155,實(shí)驗(yàn)設(shè)計(jì),線性測量問題,最大似然估計(jì)值：,獨(dú)立同分布高斯白噪聲，服從分布。,估計(jì)誤差均值為0，方差為,信賴橢圓為,-,156,實(shí)驗(yàn)設(shè)計(jì),實(shí)驗(yàn)設(shè)計(jì)的目標(biāo)：尋找，使得誤差的方差矩陣最小。,向量優(yōu)化形式：,為整數(shù)問題，求解較困難。,-,157,實(shí)驗(yàn)設(shè)計(jì),當(dāng)時(shí)，令近似為一連續(xù)實(shí)數(shù)，原問題可松弛轉(zhuǎn)換為連續(xù)實(shí)數(shù)優(yōu)化：,-,158,凸優(yōu)化理論與應(yīng)用,第7章無約束優(yōu)化,-,159,無約束優(yōu)化問題,問題描述：,無約束問題求解的兩種方法：,迭代逼近：,求解梯度方程：,為凸函數(shù)，且二次可微。,-,160,例,梯度方程,二次優(yōu)化：,-,161,迭代起始點(diǎn),滿足條件2的幾種函數(shù)：,起始點(diǎn)滿足：,函數(shù)任意下水平集都是閉集；,函數(shù)的定義域?yàn)?當(dāng)時(shí)，,-,162,強(qiáng)凸性,定義：函數(shù)在上具有強(qiáng)凸性，若滿足,若函數(shù)具有強(qiáng)凸性，則有,為最優(yōu)值，則,-,163,強(qiáng)凸性,則有,為最優(yōu)值，則,若函數(shù)在上具有強(qiáng)凸性，則可以證明存在，滿足,-,164,強(qiáng)凸性,對于，矩陣的特征值從大到小依次為。則有：,定義：矩陣的條件數(shù)為最大特征值與最小特征值之比，即。,條件數(shù)的上界：,-,165,下降法,對于凸函數(shù)，當(dāng)滿足時(shí)，存在某個(gè)，使得。,-,166,下降法,下降法的一般步驟：,給出初始點(diǎn)；,-,167,步長因子搜索,精確一維搜索：,-,168,步長因子搜索,-,169,梯度下降法,算法簡單，但收斂速度較慢。,下降方向：,終止條件：,-,170,收斂性分析,若采用精確一維搜索，則，收斂速度因子：,若采用回溯一維搜索，收斂速度因子：,條件數(shù)越大，收斂速度越小。,-,171,例,當(dāng)時(shí)，算法收斂速度很慢。,初始解為，采用精確一維搜索；,迭代：,-,172,例,步長因子采用回溯一維搜索。,-,173,最速下降法,歸一化最速下降方向：,非歸一化最速下降方向,歐式范數(shù)：,二次范數(shù)：,范數(shù)：,-,174,最速下降法,-,175,收斂性分析,范數(shù)界：,收斂速度因子：,-,176,牛頓法,設(shè)函數(shù)二階可微，則在附近，的泰勒展式為：,泰勒展開可作為在附近的近似；,下降方向：,為二次范數(shù)上的最速下降方向。,-,177,牛頓法,-,178,牛頓減量,令,為在處的牛頓減量。,牛頓減量的性質(zhì)1：,性質(zhì)2：,牛頓減量可作為迭代求解的誤差估計(jì)。,性質(zhì)3：牛頓減量具有仿射不變性。,-,179,牛頓方法,初始化：給定初始解以及,LOOP：,計(jì)算：,若則終止退出；,一維線性搜索：計(jì)算步長因子；,迭代：,-,180,收斂性分析,定理：假設(shè)二階連續(xù)可微，具有強(qiáng)凸性，即存在，滿足：,則存在，,且海森矩陣滿足Lipschitz條件，即存在，滿足：,若，則；,若，則，且,-,181,收斂性分析,定理：假設(shè)二階連續(xù)可微，具有強(qiáng)凸性，即存在，滿足：,則存在，對于，有,且海森矩陣滿足Lipschitz條件，即存在，滿足：,-,182,例,-,183,凸優(yōu)化理論與應(yīng)用,第8章等式約束優(yōu)化,-,184,等式約束優(yōu)化問題,問題描述：,為凸函數(shù)，且二次連續(xù)可微，且,假設(shè)最優(yōu)值存在，則為最優(yōu)解當(dāng)且僅當(dāng)存在，滿足（KKT條件）：,-,185,例,KKT系統(tǒng)：,二次優(yōu)化：,KKT系統(tǒng)可解，則二次優(yōu)化問題存在最優(yōu)解。,系數(shù)矩陣稱為KKT矩陣。KKT矩陣非奇異當(dāng)且僅當(dāng)：,-,186,消去等式約束,方程組的解集：,為方程組的一個(gè)特解，為的零空間范圍。,無約束優(yōu)化形式：,若為最優(yōu)解，則有,-,187,對偶問題,對偶形式：,-,188,牛頓法,牛頓減量,為等式約束優(yōu)化的可行解，則在附近原問題的二次近似為：,設(shè)和分別為該問題和對偶問題的最優(yōu)解，則滿足：,-,189,性質(zhì)2：牛頓減量具有仿射不變性。,牛頓減量,牛頓減量,牛頓減量的性質(zhì)：,-,190,可行下降方向,可行下降方向：設(shè)滿足方程組。若滿足方程組，則。稱為可行方向。若對于較小的，有，則為可行下降方向。,-,191,等式約束的牛頓方法,LOOP：,計(jì)算及；,若則終止退出；,一維線性搜索：計(jì)算步長因子；,迭代：,初始化：給定初始解滿足，以及,-,192,消去等式約束的牛頓方法,轉(zhuǎn)換為等式約束下的牛頓方法：,初始值，第次迭代值；,初始值：,迭代值：,-,193,非可行解為初始點(diǎn)的牛頓法,函數(shù)二階連續(xù)可微，因此有,為等式約束優(yōu)化的非可行解，則增量應(yīng)盡可能使?jié)M足KKT條件，即：,設(shè)和為KKT條件的解，即有：,-,194,非可行解為初始點(diǎn)的牛頓法,則KKT條件可表示為：,令,設(shè)為不滿足KKT條件，則其迭代量需滿足：,即,-,195,當(dāng)且時(shí)，終止迭代。,非可行解為初始點(diǎn)的牛頓法,LOOP：,計(jì)算和；,回溯一維線性搜索：,迭代：,初始化：給定初始解及，以及,令；,While,-,196,其中，且滿足。,KKT系統(tǒng)的求解,1.分解；,2.若非奇異，則可消元：,3.若奇異，則KKT系統(tǒng)可改寫為：,KKT系統(tǒng)：,-,197,凸優(yōu)化理論與應(yīng)用,第9章內(nèi)點(diǎn)法,-,198,則優(yōu)化問題具有強(qiáng)對偶性，其對偶問題亦可解。,假設(shè)存在，滿足嚴(yán)格不等式條件,不等式約束優(yōu)化問題,問題描述：,為凸函數(shù)