1、信息與通信工程學(xué)院 莊伯金 ,1,凸優(yōu)化理論與應(yīng)用,莊 伯 金 B,信息與通信工程學(xué)院 莊伯金 ,2,優(yōu)化理論概述,什么是優(yōu)化問題？,Objective function,Constraint functions,信息與通信工程學(xué)院 莊伯金 ,3,幾類經(jīng)典的優(yōu)化問題,線性規(guī)劃問題,最小二乘問題,凸優(yōu)化問題,凸優(yōu)化問題理論上有有效的方法進(jìn)行求解！,信息與通信工程學(xué)院 莊伯金 ,4,本課程的主要內(nèi)容,理論部分 凸集和凸函數(shù) 凸優(yōu)化問題 對(duì)偶問題 應(yīng)用部分 逼近與擬合 統(tǒng)計(jì)估計(jì) 幾何問題 算法部分 非約束優(yōu)化方法 等式約束優(yōu)化方法 內(nèi)點(diǎn)法,信息與通信工程學(xué)院 莊伯金 ,5,熟悉了解凸優(yōu)化理論的基本原

2、理和基本方法； 掌握實(shí)際問題轉(zhuǎn)化為凸優(yōu)化問題的基本方法； 掌握最優(yōu)化問題的經(jīng)典算法。,課程要求,信息與通信工程學(xué)院 莊伯金 ,6,參考書目,Stephen Boyd and Lieven Vandenberghe, “Convex Optimization”, Cambridge University Press. 袁亞湘、孫文瑜，“最優(yōu)化理論與方法”，科學(xué)出版社，1999。,信息與通信工程學(xué)院 莊伯金 ,7,凸優(yōu)化理論與應(yīng)用,第一章 凸集,信息與通信工程學(xué)院 莊伯金 ,8,仿射集(Affine sets),直線的表示：,線段的表示：,信息與通信工程學(xué)院 莊伯金 ,9,仿射集(Affine s

3、ets),仿射集的定義：過集合C內(nèi)任意兩點(diǎn)的直線均在集合C內(nèi)，則稱集合C為仿射集。 仿射集的例：直線、平面、超平面,信息與通信工程學(xué)院 莊伯金 ,10,仿射集,仿射包：包含集合C的最小的仿射集。,仿射維數(shù)：仿射包的維數(shù)。,信息與通信工程學(xué)院 莊伯金 ,11,仿射集,內(nèi)點(diǎn)（interior）：,相對(duì)內(nèi)點(diǎn)（relative interior）：,信息與通信工程學(xué)院 莊伯金 ,12,凸集(Convex Sets),凸集的定義：集合C內(nèi)任意兩點(diǎn)間的線段均在集合C內(nèi)，則稱集合C為凸集。,信息與通信工程學(xué)院 莊伯金 ,13,凸集,凸包的定義：包含集合C的最小的凸集。,信息與通信工程學(xué)院 莊伯金 ,14,錐

4、(Cones),錐的定義：,凸錐的定義：集合C既是凸集又是錐。,錐包的定義：集合C內(nèi)點(diǎn)的所有錐組合。,信息與通信工程學(xué)院 莊伯金 ,15,超平面和半空間,超平面(hyperplane) ：,半空間(Halfspace)：,信息與通信工程學(xué)院 莊伯金 ,16,歐氏球和橢球,歐氏球(euclidean ball):,橢球(ellipsoid):,信息與通信工程學(xué)院 莊伯金 ,17,范數(shù)球和范數(shù)錐,范數(shù)(norm)：,范數(shù)球(norm ball)：,范數(shù)錐(norm cone)：,信息與通信工程學(xué)院 莊伯金 ,18,多面體(Polyhedra),多面體：,單純形(simplex)：,信息與通信工程學(xué)

5、院 莊伯金 ,19,半正定錐(Positive semidefinite cone),n階對(duì)稱矩陣集：,n階半正定矩陣集：,n階正定矩陣集：,n階半正定矩陣集為凸錐！,信息與通信工程學(xué)院 莊伯金 ,20,保持凸性的運(yùn)算,集合交運(yùn)算 仿射變換 透視/投射函數(shù)(perspective function),信息與通信工程學(xué)院 莊伯金 ,21,保持凸性的運(yùn)算,線性分式函數(shù)(linear-fractional function),信息與通信工程學(xué)院 莊伯金 ,22,真錐(proper cone),真錐的定義：錐 滿足如下條件,K具有內(nèi)點(diǎn),K內(nèi)不含直線,信息與通信工程學(xué)院 莊伯金 ,23,廣義不等式,真錐

6、 下的偏序關(guān)系：,例： 逐項(xiàng)不等式 矩陣不等式,廣義不等式,嚴(yán)格廣義不等式,信息與通信工程學(xué)院 莊伯金 ,24,廣義不等式的性質(zhì),信息與通信工程學(xué)院 莊伯金 ,25,嚴(yán)格廣義不等式的性質(zhì),信息與通信工程學(xué)院 莊伯金 ,26,最值和極值,最小元的定義：設(shè) ，對(duì) ，都有 成立，則稱 為 的最小元。,極小元的定義：設(shè) ，對(duì)于 ，若 ，則 成立，則稱 為 的極小元。,信息與通信工程學(xué)院 莊伯金 ,27,分割超平面(separating hyperplane),定理：設(shè) 和 為兩不相交凸集，則存在超平面將 和 分離。即：,信息與通信工程學(xué)院 莊伯金 ,28,支撐超平面(supporting hyperp

7、lane),定義：設(shè)集合 ， 為 邊界上的點(diǎn)。若存在 ，滿足對(duì)任意 ，都有 成立，則稱超平面 為集合 在點(diǎn) 處的支撐超平面。,定理：凸集邊界上任意一點(diǎn)均存在支撐超平面。 定理：若一個(gè)閉的非中空集合，在邊界上的任意一點(diǎn)存在支撐超平面，則該集合為凸集。,信息與通信工程學(xué)院 莊伯金 ,29,對(duì)偶錐(dual cone),對(duì)偶錐的定義：設(shè) 為錐，則集合 稱為對(duì)偶錐。,對(duì)偶錐的性質(zhì)：,真錐的對(duì)偶錐仍然是真錐！,信息與通信工程學(xué)院 莊伯金 ,30,對(duì)偶廣義不等式,廣義不等式與對(duì)偶等價(jià)性質(zhì),最小元的對(duì)偶特性：,信息與通信工程學(xué)院 莊伯金 ,31,對(duì)偶廣義不等式,極小元的對(duì)偶特性,反過來(lái)不一定成立！,信息與通

8、信工程學(xué)院 莊伯金 ,32,作業(yè),P60 2.8 P60 2.10 P60 2.14 P62 2.16 P62 2.18 P64 2.30 P64 2.31 P64 2.33,信息與通信工程學(xué)院 莊伯金 ,33,凸優(yōu)化理論與應(yīng)用,第二章 凸函數(shù),信息與通信工程學(xué)院 莊伯金 ,34,凸函數(shù)的定義,1.定義域 為凸集；,2. ，有,凸函數(shù)的定義：函數(shù) ，滿足,凸函數(shù)的擴(kuò)展定義：若 為凸函數(shù)，則可定義其擴(kuò)展函數(shù) 為,凸函數(shù)的擴(kuò)展函數(shù)也是凸函數(shù)！,信息與通信工程學(xué)院 莊伯金 ,35,凸函數(shù)的一階微分條件,若函數(shù) 的定義域 為開集，且函數(shù) 一階可微，則函數(shù) 為凸函數(shù)當(dāng)且僅當(dāng) 為凸集，且對(duì),信息與通信工程

9、學(xué)院 莊伯金 ,36,凸函數(shù)的二階微分條件,若函數(shù) 的定義域 為開集，且函數(shù) 二階可微，則函數(shù) 為凸函數(shù)當(dāng)且僅當(dāng) 為凸集，且對(duì) ，其Hessian矩陣,信息與通信工程學(xué)院 莊伯金 ,37,凸函數(shù)的例,冪函數(shù),負(fù)對(duì)數(shù)函數(shù),負(fù)熵函數(shù),范數(shù)函數(shù),指數(shù)函數(shù),信息與通信工程學(xué)院 莊伯金 ,38,凸函數(shù)的例,信息與通信工程學(xué)院 莊伯金 ,39,下水平集(sublevel set),定理：凸函數(shù)的任一下水平集均為凸集。,任一下水平集均為凸集的函數(shù)不一定為凸函數(shù)。,信息與通信工程學(xué)院 莊伯金 ,40,函數(shù)上半圖(epigraph),定理：函數(shù) 為凸函數(shù)當(dāng)且僅當(dāng) 的上半圖為凸集。,信息與通信工程學(xué)院 莊伯金 ,

10、41,Jensen不等式,為凸函數(shù)，則有：,Jensen不等式的另外形式：,信息與通信工程學(xué)院 莊伯金 ,42,保持函數(shù)凸性的算子,凸函數(shù)的逐點(diǎn)最大值,凸函數(shù)與仿射變換的復(fù)合,凸函數(shù)的非負(fù)加權(quán)和,信息與通信工程學(xué)院 莊伯金 ,43,保持函數(shù)凸性的算子,復(fù)合運(yùn)算,最小值算子,凸函數(shù)的透視算子,信息與通信工程學(xué)院 莊伯金 ,44,共軛函數(shù)(conjugate function),定義：設(shè)函數(shù) ，其共軛函數(shù) ，定義為,共軛函數(shù)的例,共軛函數(shù)具有凸性！,信息與通信工程學(xué)院 莊伯金 ,45,共軛函數(shù)的性質(zhì),Fenchels inequality,性質(zhì)：若 為凸函數(shù)，且 的上半圖是閉集，則有,信息與通信工

11、程學(xué)院 莊伯金 ,46,準(zhǔn)凸函數(shù)(quasiconvex function),準(zhǔn)凸函數(shù)的例,信息與通信工程學(xué)院 莊伯金 ,47,準(zhǔn)凸函數(shù)的判定定理,定理：函數(shù) 為準(zhǔn)凸函數(shù)，當(dāng)且僅當(dāng) 為凸集，且對(duì) ，有,定理：若函數(shù) 一階可微，則 為準(zhǔn)凸函數(shù)，當(dāng)且僅當(dāng) 為凸集，且對(duì) ，有,信息與通信工程學(xué)院 莊伯金 ,48,最小值函數(shù),非負(fù)權(quán)值函數(shù)的最大值函數(shù),保持準(zhǔn)凸性的算子,復(fù)合函數(shù),信息與通信工程學(xué)院 莊伯金 ,49,準(zhǔn)凸函數(shù)的凸函數(shù)族表示,若 為準(zhǔn)凸函數(shù)，根據(jù) 的任意 下水平集，我們可以構(gòu)造一個(gè)凸函數(shù)族 ，使得,性質(zhì)：若 為準(zhǔn)凸函數(shù) 的凸函數(shù)族表示，對(duì)每一個(gè) ，若 ，則有,信息與通信工程學(xué)院 莊伯金 ,

12、50,對(duì)數(shù)凸函數(shù),對(duì)數(shù)凸函數(shù)的例,信息與通信工程學(xué)院 莊伯金 ,51,對(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ù)。,信息與通信工程學(xué)院 莊伯金 ,52,對(duì)數(shù)凸函數(shù)和凹函數(shù)的性質(zhì),定理：函數(shù) 為對(duì)數(shù)凹函數(shù)，則函數(shù) 是對(duì)數(shù)凹函數(shù)。,信息與通信工程學(xué)院 莊伯金 ,53,廣義不等式下的凸性,廣義單調(diào)性的定義：設(shè) 為真錐，函數(shù) 稱為 單調(diào)增，若函數(shù) 滿足：,定理(對(duì)偶等價(jià))：函數(shù) 為 凸函數(shù)

13、，當(dāng)且僅當(dāng)對(duì)所有 ， 為凸函數(shù)。,信息與通信工程學(xué)院 莊伯金 ,54,作業(yè)(1),P116 3.16 P116 3.21,信息與通信工程學(xué)院 莊伯金 ,55,作業(yè)(2),P121 3.41 P122 3.49 (1)(2),信息與通信工程學(xué)院 莊伯金 ,56,凸優(yōu)化理論與應(yīng)用,第三章 凸優(yōu)化,信息與通信工程學(xué)院 莊伯金 ,57,優(yōu)化問題的基本形式,優(yōu)化問題的基本描述：,優(yōu)化變量,不等式約束,等式約束,無(wú)約束優(yōu)化,信息與通信工程學(xué)院 莊伯金 ,58,優(yōu)化問題的基本形式,最優(yōu)化值,最優(yōu)化解,優(yōu)化問題的域,可行點(diǎn)(解) (feasible) 滿足約束條件,可行域(可解集) 所有可行點(diǎn)的集合,信息與通

14、信工程學(xué)院 莊伯金 ,59,局部最優(yōu)問題,局部最優(yōu)問題,信息與通信工程學(xué)院 莊伯金 ,60,優(yōu)化問題的等價(jià)形式(1),信息與通信工程學(xué)院 莊伯金 ,61,優(yōu)化問題的等價(jià)形式(2),信息與通信工程學(xué)院 莊伯金 ,62,優(yōu)化問題的等價(jià)形式(3),定理：設(shè) 為嚴(yán)格單調(diào)增函數(shù)； 滿足 當(dāng)且僅當(dāng) ； 滿足 當(dāng)且僅當(dāng) 。則原優(yōu)化問題與以下優(yōu)化問題等價(jià),信息與通信工程學(xué)院 莊伯金 ,63,優(yōu)化問題的等價(jià)形式(4),定理：原優(yōu)化問題與以下優(yōu)化問題等價(jià),稱為松弛變量,信息與通信工程學(xué)院 莊伯金 ,64,優(yōu)化問題的等價(jià)形式(5),定理：設(shè) 滿足等式 成立，當(dāng)且僅當(dāng) 。則原優(yōu)化問題與以下優(yōu)化問題等價(jià),信息與通信工程

15、學(xué)院 莊伯金 ,65,可分離變量?jī)?yōu)化問題,信息與通信工程學(xué)院 莊伯金 ,66,優(yōu)化問題的上半圖形式,信息與通信工程學(xué)院 莊伯金 ,67,凸優(yōu)化問題的基本形式,凸優(yōu)化問題的基本描述：,為仿射函數(shù),為凸函數(shù),若 為準(zhǔn)凸函數(shù)，則優(yōu)化問題稱為準(zhǔn)凸優(yōu)化問題。,性質(zhì)：凸優(yōu)化問題的可行域是凸集。,信息與通信工程學(xué)院 莊伯金 ,68,凸優(yōu)化問題的例,例：,等價(jià)于凸優(yōu)化問題,信息與通信工程學(xué)院 莊伯金 ,69,凸優(yōu)化問題的局部最優(yōu)解,定理：凸優(yōu)化問題的局部最優(yōu)解均是全局最優(yōu)解。,信息與通信工程學(xué)院 莊伯金 ,70,凸優(yōu)化問題最優(yōu)解的微分條件,定理：設(shè) 為凸優(yōu)化問題的可行域， 可微。則 為最優(yōu)解當(dāng)且僅當(dāng) 成立。,

16、定理：非約束凸優(yōu)化問題中，若 可微。則 為最優(yōu)解當(dāng)且僅當(dāng) 成立。,信息與通信工程學(xué)院 莊伯金 ,71,凸優(yōu)化問題的等價(jià)形式,信息與通信工程學(xué)院 莊伯金 ,72,凸優(yōu)化問題的等價(jià)形式,信息與通信工程學(xué)院 莊伯金 ,73,凸優(yōu)化問題的等價(jià)形式,信息與通信工程學(xué)院 莊伯金 ,74,凸優(yōu)化問題的等價(jià)形式,等價(jià)于,定理：設(shè)凸優(yōu)化問題,信息與通信工程學(xué)院 莊伯金 ,75,準(zhǔn)凸優(yōu)化問題,注：準(zhǔn)凸優(yōu)化問題的局部最優(yōu)解不一定是全局最優(yōu)解。,信息與通信工程學(xué)院 莊伯金 ,76,準(zhǔn)凸優(yōu)化問題的上半圖形式,設(shè) 為準(zhǔn)凸函數(shù) 的凸函數(shù)族表示，即,則準(zhǔn)凸優(yōu)化問題的可行解問題為,設(shè) 為準(zhǔn)凸優(yōu)化問題的最優(yōu)解，若上述問題可解，則

17、 。否則 。,信息與通信工程學(xué)院 莊伯金 ,77,準(zhǔn)凸優(yōu)化問題二分法求解,給定一個(gè)足夠小的 和足夠大的 ，使得區(qū)間 能包含最優(yōu)解 。給定,LOOP： 令 求解可行解問題； 若可解，則令 ，否則令 若 ，則結(jié)束，否則goto LOOP。,信息與通信工程學(xué)院 莊伯金 ,78,線性規(guī)劃(linear program,LP),LP問題的一般描述,信息與通信工程學(xué)院 莊伯金 ,79,LP問題的幾種類型,標(biāo)準(zhǔn)LP問題,不等式形式LP問題,信息與通信工程學(xué)院 莊伯金 ,80,標(biāo)準(zhǔn)LP問題的轉(zhuǎn)換,信息與通信工程學(xué)院 莊伯金 ,81,LP問題的例,Chebyshev center of a polyhedron

18、,Piecewise-linear minimization,Linear-fractional programming,信息與通信工程學(xué)院 莊伯金 ,82,Chebyshev center of a polyhedron,多面體,Chebyshev center：到多面體邊界距離最大的內(nèi)點(diǎn)（最深的點(diǎn)）,問題描述,LP形式,信息與通信工程學(xué)院 莊伯金 ,83,Piecewise-linear minimization,問題描述,上半圖形式,LP形式,信息與通信工程學(xué)院 莊伯金 ,84,Linear-fractional programming,問題描述,LP形式,信息與通信工程學(xué)院 莊伯金 ,

19、85,二次規(guī)劃(quadratic program,QP),QP問題的基本描述,信息與通信工程學(xué)院 莊伯金 ,86,二次約束二次規(guī)劃,quadratically constrained quadratic program (QCQP),信息與通信工程學(xué)院 莊伯金 ,87,QP問題的例,Least-squares and regression,Distance between polyhedra,信息與通信工程學(xué)院 莊伯金 ,88,Least-squares and regression,問題描述,信息與通信工程學(xué)院 莊伯金 ,89,Distance between polyhedra,問題描述

20、,QP形式,信息與通信工程學(xué)院 莊伯金 ,90,Second-order cone program, SOCP,SOCP問題的基本描述,二次錐約束條件,信息與通信工程學(xué)院 莊伯金 ,91,SOCP問題的例Robust linear programming,例： 為確定的常數(shù)， 為變量，其范圍滿足,SOCP形式,信息與通信工程學(xué)院 莊伯金 ,92,幾何規(guī)劃(Geometric programming),單項(xiàng)式與多項(xiàng)式,幾何規(guī)劃的基本描述,信息與通信工程學(xué)院 莊伯金 ,93,幾何規(guī)劃的凸形式轉(zhuǎn)換,令,幾何規(guī)劃的凸形式,信息與通信工程學(xué)院 莊伯金 ,94,廣義不等式約束,廣義不等式約束的優(yōu)化問題,S

21、OCP的描述,信息與通信工程學(xué)院 莊伯金 ,95,凸優(yōu)化理論與應(yīng)用,第四章 對(duì)偶問題,信息與通信工程學(xué)院 莊伯金 ,96,優(yōu)化問題的拉格朗日函數(shù),設(shè)優(yōu)化問題：,拉格朗日(Lagrangian)函數(shù)：,對(duì)固定的 ，拉格朗日函數(shù) 為關(guān)于 和 的仿射函數(shù)。,信息與通信工程學(xué)院 莊伯金 ,97,拉格朗日對(duì)偶函數(shù),拉格朗日對(duì)偶函數(shù)(lagrange dual function) ：,若拉格朗日函數(shù)沒有下界，則令,拉格朗日對(duì)偶函數(shù)為凹函數(shù)。,對(duì) 和 ，若原最優(yōu)化問題有最優(yōu)值 ，則,信息與通信工程學(xué)院 莊伯金 ,98,對(duì)偶函數(shù)的例,Least-squares solution of linear equat

22、ions,Standard form LP,Two-way partitioning problem,信息與通信工程學(xué)院 莊伯金 ,99,Least-squares solution of linear equations,原問題：,拉格朗日函數(shù)：,拉格朗日對(duì)偶函數(shù)：,信息與通信工程學(xué)院 莊伯金 ,100,Standard form LP,原問題：,拉格朗日函數(shù)：,拉格朗日對(duì)偶函數(shù)：,信息與通信工程學(xué)院 莊伯金 ,101,Two-way partitioning problem,原問題：,拉格朗日函數(shù)：,拉格朗日對(duì)偶函數(shù)：,信息與通信工程學(xué)院 莊伯金 ,102,對(duì)偶函數(shù)與共軛函數(shù),共軛函數(shù),共

23、軛函數(shù)與對(duì)偶函數(shù)存在密切聯(lián)系,具有線性不等式約束和線性等式約束的優(yōu)化問題：,對(duì)偶函數(shù)：,信息與通信工程學(xué)院 莊伯金 ,103,Equality constrained norm minimization,問題描述：,共軛函數(shù)：,對(duì)偶函數(shù)：,信息與通信工程學(xué)院 莊伯金 ,104,Entropy maximization,原始問題：,共軛函數(shù)：,對(duì)偶函數(shù)：,信息與通信工程學(xué)院 莊伯金 ,105,Minimum volume covering ellipsoid,原始問題：,對(duì)偶函數(shù)：,共軛函數(shù)：,信息與通信工程學(xué)院 莊伯金 ,106,拉格朗日對(duì)偶問題,拉格朗日對(duì)偶問題的描述：,對(duì)偶可行域,最優(yōu)值,

24、最優(yōu)解,信息與通信工程學(xué)院 莊伯金 ,107,LP問題的對(duì)偶問題,標(biāo)準(zhǔn)LP問題,對(duì)偶函數(shù),對(duì)偶問題,等價(jià)描述,信息與通信工程學(xué)院 莊伯金 ,108,弱對(duì)偶性,定理（弱對(duì)偶性） ：設(shè)原始問題的最優(yōu)值為 ，對(duì)偶問題的最優(yōu)值為 ，則 成立。,optimal duality gap,可以利用對(duì)偶問題找到原始問題最優(yōu)解的下界。,信息與通信工程學(xué)院 莊伯金 ,109,強(qiáng)對(duì)偶性,強(qiáng)對(duì)偶性并不是總是成立的。,定義（強(qiáng)對(duì)偶性） ：設(shè)原始問題的最優(yōu)值為 ，對(duì)偶問題的最優(yōu)值為 。若 成立，則稱原始問題和對(duì)偶問題之間具有強(qiáng)對(duì)偶性。,凸優(yōu)化問題通常（但并不總是）具有強(qiáng)對(duì)偶性。,信息與通信工程學(xué)院 莊伯金 ,110,強(qiáng)對(duì)

25、偶性,存在 ，滿足,弱化的Slater條件：若不等式約束條件的前 個(gè)為線性不等式約束條件，則Slater條件可以弱化為：,信息與通信工程學(xué)院 莊伯金 ,111,Least-squares solution of linear equations,原問題：,對(duì)偶問題：,具有強(qiáng)對(duì)偶性,信息與通信工程學(xué)院 莊伯金 ,112,Lagrange dual of QCQP,QCQP：,拉格朗日函數(shù)：,對(duì)偶函數(shù)：,信息與通信工程學(xué)院 莊伯金 ,113,Lagrange dual of QCQP,對(duì)偶問題：,Slater條件：存在 ，滿足,信息與通信工程學(xué)院 莊伯金 ,114,Entropy maximiza

26、tion,原始問題：,對(duì)偶函數(shù)：,對(duì)偶問題：,信息與通信工程學(xué)院 莊伯金 ,115,Entropy maximization,弱化的Slater條件：存在 ，滿足,信息與通信工程學(xué)院 莊伯金 ,116,Minimum volume covering ellipsoid,原始問題：,對(duì)偶函數(shù)：,對(duì)偶問題：,信息與通信工程學(xué)院 莊伯金 ,117,Minimum volume covering ellipsoid,弱化的Slater條件總成立，因此該優(yōu)化問題具有強(qiáng)對(duì)偶性。,弱化的Slater條件：存在 ，滿足,信息與通信工程學(xué)院 莊伯金 ,118,對(duì)偶可行解的不等式,對(duì)于一優(yōu)化問題，若 為一可行解，

27、 為對(duì)偶問題可行解，則有如下不等式：,為 次優(yōu)解，其中,不等式可以用于對(duì)次優(yōu)解的精度估計(jì),信息與通信工程學(xué)院 莊伯金 ,119,互補(bǔ)松弛條件,所以,設(shè) 為原始優(yōu)化問題的最優(yōu)解， 為對(duì)偶問題的最優(yōu)解，若兩者具有強(qiáng)對(duì)偶性，則,即,信息與通信工程學(xué)院 莊伯金 ,120,KKT優(yōu)化條件,設(shè)優(yōu)化問題中，函數(shù) 可微。設(shè) 為原始優(yōu)化問題的最優(yōu)解， 為對(duì)偶問題的最優(yōu)解，且兩者具有強(qiáng)對(duì)偶性，則 滿足如下條件：,KKT條件為必要條件！,信息與通信工程學(xué)院 莊伯金 ,121,凸優(yōu)化問題的KKT條件,信息與通信工程學(xué)院 莊伯金 ,122,例,原始凸優(yōu)化問題,KKT條件,信息與通信工程學(xué)院 莊伯金 ,123,例,其中,

28、解得,信息與通信工程學(xué)院 莊伯金 ,124,凸優(yōu)化問題的對(duì)偶求解,信息與通信工程學(xué)院 莊伯金 ,125,擾動(dòng)問題,擾動(dòng)問題：,當(dāng) 時(shí)即為原始問題。,若 為正，則第 個(gè)不等式約束被放寬；若 為負(fù)，則第 個(gè)不等式約束被收緊。,記 為擾動(dòng)問題的最優(yōu)解。若擾動(dòng)問題無(wú)最優(yōu)解，則記,信息與通信工程學(xué)院 莊伯金 ,126,靈敏度分析,設(shè)對(duì)偶問題存在最優(yōu)解，且與原始問題具有強(qiáng)對(duì)偶性，若非干擾問題的最優(yōu)對(duì)偶解為 ，則有,若 在 處可微，則,信息與通信工程學(xué)院 莊伯金 ,127,定義（弱選擇性）：若兩個(gè)不等式（等式）系統(tǒng)，至多有一個(gè)可解，則稱這兩個(gè)系統(tǒng)具有弱選擇性。,選擇定理,對(duì)偶不等式組,設(shè)原始問題的約束條件：

29、,對(duì)偶問題,原始問題的約束條件與對(duì)偶不等式組具有弱選擇性。,信息與通信工程學(xué)院 莊伯金 ,128,選擇定理,對(duì)偶不等式組,設(shè)原始問題的嚴(yán)格不等式約束條件：,原始問題的嚴(yán)格不等式約束條件與對(duì)偶不等式組具有弱選擇性。,信息與通信工程學(xué)院 莊伯金 ,129,定義（強(qiáng)選擇性）：若兩個(gè)不等式（等式）系統(tǒng)，恰有一個(gè)可解，則稱這兩個(gè)系統(tǒng)具有強(qiáng)選擇性。,選擇定理,對(duì)偶不等式組,設(shè)原始問題為凸優(yōu)化問題，其嚴(yán)格不等式約束條件為：,若存在 ，滿足 ，則上述兩不等式約束系統(tǒng)具有強(qiáng)選擇性。,信息與通信工程學(xué)院 莊伯金 ,130,選擇定理,對(duì)偶不等式組,設(shè)原始問題為凸優(yōu)化問題，其不等式約束條件為：,信息與通信工程學(xué)院 莊

30、伯金 ,131,罰函數(shù)的例,范數(shù)：,死區(qū)線性罰函數(shù)：,對(duì)數(shù)門限罰函數(shù),信息與通信工程學(xué)院 莊伯金 ,132,魯棒的罰函數(shù),若 大到一定程度時(shí)，罰函數(shù)為 的線性函數(shù)，則稱該罰函數(shù)為魯棒的罰函數(shù)。,Huber罰函數(shù),信息與通信工程學(xué)院 莊伯金 ,133,最小范數(shù)問題,問題描述：,其中 為方程組 的解。,可以消去等式約束將其轉(zhuǎn)換為范數(shù)逼近問題：,信息與通信工程學(xué)院 莊伯金 ,134,最小范數(shù)問題,最小平方范數(shù)問題：范數(shù) ，最優(yōu)解滿足：,最小罰問題：,絕對(duì)值和最小問題：范數(shù) ，原問題可轉(zhuǎn)換為L(zhǎng)P問題：,信息與通信工程學(xué)院 莊伯金 ,135,正則逼近,二元矢量?jī)?yōu)化問題描述：,正則化問題：,最優(yōu)解描述了兩

31、分量的一條折中曲線。,信息與通信工程學(xué)院 莊伯金 ,136,正則逼近,Tikhonov正則化問題：,為二次優(yōu)化問題：,最優(yōu)解的形式：,信息與通信工程學(xué)院 莊伯金 ,137,正則逼近,Tikhonov光滑正則化問題：,為二階差分算子：,信息與通信工程學(xué)院 莊伯金 ,138,信號(hào)復(fù)原,已知加噪信號(hào)：,信號(hào)復(fù)原問題的描述：,函數(shù) 為正則函數(shù)或光滑函數(shù)。,信息與通信工程學(xué)院 莊伯金 ,139,信號(hào)復(fù)原,信息與通信工程學(xué)院 莊伯金 ,140,信號(hào)復(fù)原,信息與通信工程學(xué)院 莊伯金 ,141,信號(hào)復(fù)原,信息與通信工程學(xué)院 莊伯金 ,142,魯棒逼近,問題描述：,隨機(jī)魯棒逼近： 為隨機(jī)變量，逼近問題轉(zhuǎn)換為最小

32、化期望,例：,隨機(jī)魯棒逼近為：,轉(zhuǎn)換為：,信息與通信工程學(xué)院 莊伯金 ,143,隨機(jī)魯棒逼近,為隨機(jī)變量：,最小平方隨機(jī)魯棒逼近為：,轉(zhuǎn)換為：,其中,信息與通信工程學(xué)院 莊伯金 ,144,最壞情況魯棒逼近,考慮 ，最壞情況魯棒逼近為：,例：,隨機(jī)魯棒逼近為：,轉(zhuǎn)換為：,信息與通信工程學(xué)院 莊伯金 ,145,凸優(yōu)化理論與應(yīng)用,第6章 統(tǒng)計(jì)估計(jì),信息與通信工程學(xué)院 莊伯金 ,146,概率分布的參數(shù)估計(jì),隨機(jī)變量的概率密度為 ，其中 為概率分布的參數(shù)，且參數(shù)未知。參數(shù)估計(jì)的目標(biāo)就是通過一些已知樣本估計(jì)獲得參數(shù)的最優(yōu)近似值。,問題描述,為樣本觀測(cè)值；,為對(duì)數(shù)似然函數(shù)；,若似然函數(shù)為凹函數(shù)，則優(yōu)化問題為

33、凸優(yōu)化問題。,信息與通信工程學(xué)院 莊伯金 ,147,具有獨(dú)立同分布噪聲的線性測(cè)量,線性測(cè)量模型：,為觀測(cè)值或測(cè)量值；,為未知參數(shù)向量；,獨(dú)立同分布噪聲，其概率密度為 。,似然函數(shù)為,最大似然估計(jì)問題為：,信息與通信工程學(xué)院 莊伯金 ,148,例,高斯白噪聲,對(duì)數(shù)似然函數(shù)：,區(qū)間 上均勻分布的噪聲：,對(duì)數(shù)似然函數(shù)：,信息與通信工程學(xué)院 莊伯金 ,149,邏輯回歸,隨機(jī)變量 的概率分布為：,為參數(shù)；,為可觀測(cè)的解釋變量； 為觀察值。,對(duì)數(shù)似然函數(shù)：,信息與通信工程學(xué)院 莊伯金 ,150,假定測(cè)驗(yàn),隨機(jī)變量 ，有 種可能（假定）的分布；,假定 ： 的概率分布為,假定測(cè)驗(yàn)的目標(biāo)：由觀察值猜測(cè)隨機(jī)變量最

34、有可能服從哪種假定的分布。,當(dāng) 時(shí)，稱為二元假定測(cè)驗(yàn)。,隨機(jī)檢測(cè)子：非負(fù)元素矩陣,信息與通信工程學(xué)院 莊伯金 ,151,假定測(cè)驗(yàn),為當(dāng) 實(shí)際服從第1種假定分布而猜測(cè)為第2種假定分布的概率；,為當(dāng) 實(shí)際服從第2種假定分布而猜測(cè)為第1種假定分布的概率；,多目標(biāo)優(yōu)化形式：,檢測(cè)概率矩陣,信息與通信工程學(xué)院 莊伯金 ,152,假定測(cè)驗(yàn),最小最大值形式,尺度優(yōu)化形式：,信息與通信工程學(xué)院 莊伯金 ,153,例,在兩種假設(shè)下的概率分布為：,信息與通信工程學(xué)院 莊伯金 ,154,例,信息與通信工程學(xué)院 莊伯金 ,155,實(shí)驗(yàn)設(shè)計(jì),線性測(cè)量問題,最大似然估計(jì)值：,獨(dú)立同分布高斯白噪聲，服從分布 。,估計(jì)誤差

35、均值為0，方差為,信賴橢圓為,信息與通信工程學(xué)院 莊伯金 ,156,實(shí)驗(yàn)設(shè)計(jì),實(shí)驗(yàn)設(shè)計(jì)的目標(biāo)：尋找 ，使得誤差的方差矩陣最小。,向量?jī)?yōu)化形式：,為整數(shù)問題，求解較困難。,信息與通信工程學(xué)院 莊伯金 ,157,實(shí)驗(yàn)設(shè)計(jì),當(dāng) 時(shí)，令 近似為一連續(xù)實(shí)數(shù)，原問題可松弛轉(zhuǎn)換為連續(xù)實(shí)數(shù)優(yōu)化：,信息與通信工程學(xué)院 莊伯金 ,158,凸優(yōu)化理論與應(yīng)用,第7章 無(wú)約束優(yōu)化,信息與通信工程學(xué)院 莊伯金 ,159,無(wú)約束優(yōu)化問題,問題描述：,無(wú)約束問題求解的兩種方法：,迭代逼近：,求解梯度方程：,為凸函數(shù)，且二次可微。,信息與通信工程學(xué)院 莊伯金 ,160,例,梯度方程,二次優(yōu)化：,信息與通信工程學(xué)院 莊伯金 ,1

36、61,迭代起始點(diǎn),滿足條件2的幾種函數(shù)：,起始點(diǎn) 滿足：,函數(shù) 任意下水平集都是閉集；,函數(shù)的定義域?yàn)?當(dāng) 時(shí)，,信息與通信工程學(xué)院 莊伯金 ,162,強(qiáng)凸性,定義：函數(shù) 在 上具有強(qiáng)凸性，若 滿足,若函數(shù) 具有強(qiáng)凸性，則有,為最優(yōu)值，則,信息與通信工程學(xué)院 莊伯金 ,163,強(qiáng)凸性,則有,為最優(yōu)值，則,若函數(shù) 在 上具有強(qiáng)凸性，則可以證明存在 ，滿足,信息與通信工程學(xué)院 莊伯金 ,164,強(qiáng)凸性,對(duì)于 ，矩陣 的特征值從大到小依次為 。則有：,定義：矩陣 的條件數(shù)為最大特征值與最小特征值之比，即 。,條件數(shù)的上界：,信息與通信工程學(xué)院 莊伯金 ,165,下降法,對(duì)于凸函數(shù) ，當(dāng) 滿足 時(shí)，存

37、在某個(gè) ，使得 。,信息與通信工程學(xué)院 莊伯金 ,166,下降法,下降法的一般步驟：,給出初始點(diǎn) ；,信息與通信工程學(xué)院 莊伯金 ,167,步長(zhǎng)因子搜索,精確一維搜索：,信息與通信工程學(xué)院 莊伯金 ,168,步長(zhǎng)因子搜索,信息與通信工程學(xué)院 莊伯金 ,169,梯度下降法,算法簡(jiǎn)單，但收斂速度較慢。,下降方向：,終止條件：,信息與通信工程學(xué)院 莊伯金 ,170,收斂性分析,若 采用精確一維搜索，則 ，收斂速度因子：,若 采用回溯一維搜索，收斂速度因子：,條件數(shù)越大，收斂速度越小。,信息與通信工程學(xué)院 莊伯金 ,171,例,當(dāng) 時(shí)，算法收斂速度很慢。,初始解為 ，采用精確一維搜索；,迭代：,信息與

38、通信工程學(xué)院 莊伯金 ,172,例,步長(zhǎng)因子采用回溯一維搜索。,信息與通信工程學(xué)院 莊伯金 ,173,最速下降法,歸一化最速下降方向：,非歸一化最速下降方向,歐式范數(shù)：,二次范數(shù) ：,范數(shù)：,信息與通信工程學(xué)院 莊伯金 ,174,最速下降法,信息與通信工程學(xué)院 莊伯金 ,175,收斂性分析,范數(shù)界：,收斂速度因子：,信息與通信工程學(xué)院 莊伯金 ,176,牛頓法,設(shè)函數(shù) 二階可微，則在 附近， 的泰勒展式為：,泰勒展開可作為 在 附近的近似；,下降方向：,為二次范數(shù) 上的最速下降方向。,信息與通信工程學(xué)院 莊伯金 ,177,牛頓法,信息與通信工程學(xué)院 莊伯金 ,178,牛頓減量,令,為 在 處的

39、牛頓減量。,牛頓減量的性質(zhì)1：,性質(zhì)2：,牛頓減量可作為迭代求解的誤差估計(jì)。,性質(zhì)3：牛頓減量具有仿射不變性。,信息與通信工程學(xué)院 莊伯金 ,179,牛頓方法,初始化：給定初始解 以及,LOOP：,計(jì)算：,若 則終止退出；,一維線性搜索：計(jì)算步長(zhǎng)因子 ；,迭代：,信息與通信工程學(xué)院 莊伯金 ,180,收斂性分析,定理：假設(shè) 二階連續(xù)可微，具有強(qiáng)凸性，即存在 ，滿足：,則存在 ，,且海森矩陣滿足Lipschitz條件，即存在 ，滿足：,若 ，則 ；,若 ，則 ，且,信息與通信工程學(xué)院 莊伯金 ,181,收斂性分析,定理：假設(shè) 二階連續(xù)可微，具有強(qiáng)凸性，即存在 ，滿足：,則存在 ，對(duì)于 ，有,且海

40、森矩陣滿足Lipschitz條件，即存在 ，滿足：,信息與通信工程學(xué)院 莊伯金 ,182,例,信息與通信工程學(xué)院 莊伯金 ,183,凸優(yōu)化理論與應(yīng)用,第8章 等式約束優(yōu)化,信息與通信工程學(xué)院 莊伯金 ,184,等式約束優(yōu)化問題,問題描述：,為凸函數(shù)，且二次連續(xù)可微，且,假設(shè)最優(yōu)值 存在，則 為最優(yōu)解當(dāng)且僅當(dāng)存在 ，滿足（KKT條件）：,信息與通信工程學(xué)院 莊伯金 ,185,例,KKT系統(tǒng)：,二次優(yōu)化：,KKT系統(tǒng)可解，則二次優(yōu)化問題存在最優(yōu)解。,系數(shù)矩陣稱為KKT矩陣。KKT矩陣非奇異當(dāng)且僅當(dāng)：,信息與通信工程學(xué)院 莊伯金 ,186,消去等式約束,方程組 的解集：,為方程組的一個(gè)特解， 為 的

41、零空間范圍。,無(wú)約束優(yōu)化形式：,若 為最優(yōu)解，則有,信息與通信工程學(xué)院 莊伯金 ,187,對(duì)偶問題,對(duì)偶形式：,信息與通信工程學(xué)院 莊伯金 ,188,牛頓法,牛頓減量,為等式約束優(yōu)化的可行解，則在 附近原問題的二次近似為：,設(shè) 和 分別為該問題和對(duì)偶問題的最優(yōu)解，則滿足：,信息與通信工程學(xué)院 莊伯金 ,189,性質(zhì)2：牛頓減量具有仿射不變性。,牛頓減量,牛頓減量,牛頓減量的性質(zhì)：,信息與通信工程學(xué)院 莊伯金 ,190,可行下降方向,可行下降方向：設(shè) 滿足方程組 。若 滿足方程組 ，則 。 稱為可行方向。若對(duì)于較小的 ，有 ，則 為可行下降方向。,信息與通信工程學(xué)院 莊伯金 ,191,等式約束的

42、牛頓方法,LOOP：,計(jì)算 及 ；,若 則終止退出；,一維線性搜索：計(jì)算步長(zhǎng)因子 ；,迭代：,初始化：給定初始解 滿足 ，以及,信息與通信工程學(xué)院 莊伯金 ,192,消去等式約束的牛頓方法,轉(zhuǎn)換為等式約束下的牛頓方法：,初始值 ，第 次迭代值 ；,初始值：,迭代值：,信息與通信工程學(xué)院 莊伯金 ,193,非可行解為初始點(diǎn)的牛頓法,函數(shù) 二階連續(xù)可微，因此有,為等式約束優(yōu)化的非可行解，則增量 應(yīng)盡可能使 滿足KKT條件，即：,設(shè) 和 為KKT條件的解，即有：,信息與通信工程學(xué)院 莊伯金 ,194,非可行解為初始點(diǎn)的牛頓法,則KKT條件可表示為：,令,設(shè) 為不滿足KKT條件，則其迭代量需滿足：,即,信息與通信工程學(xué)院 莊伯金 ,195,當(dāng) 且 時(shí)，終止迭代。,非可行解為初始點(diǎn)的牛頓法,LOOP：,計(jì)算 和 ；,回溯一維線性搜索：,迭代：,初始化：給定初始解 及 ，以及,令 ；,While,信息與通信工程學(xué)院 莊伯金 ,196,其中 ，且滿足 。,KKT系統(tǒng)的求解,1. 分解；,2.若 非奇異，則可消元：,3.若 奇異，則KKT系統(tǒng)可改寫為：,KKT系統(tǒng)：,信息與通信工程學(xué)院 莊伯金 ,197,凸優(yōu)化理論與應(yīng)用,第9章 內(nèi)點(diǎn)法,信息與通信工程學(xué)院 莊伯金 ,198,則優(yōu)化問題具有強(qiáng)對(duì)偶性，其對(duì)偶問題亦可解。,假設(shè)存在 ，滿足嚴(yán)