【正文】 設(shè) 滿足 KKT條件，則 為原始問題的最優(yōu)解，而 為對偶問題的最優(yōu)解，且兩者具有強對偶性。 ? 弱化的 Slater條件：存在 ，滿足 1 , 1 , ...,Tiia Xa i m??nXS???信息與通信工程學(xué)院 莊伯金 118 對偶可行解的不等式 ? 對于一優(yōu)化問題，若 為一可行解， 為對偶問題可行解，則有如下不等式： x ( , )??*00( ) ( ) ( , )f x p f x g ??? ? ? 為 次優(yōu)解，其中 x ??0 ( ) ( , )f x g? ? ???? 不等式可以用于對次優(yōu)解的精度估計 信息與通信工程學(xué)院 莊伯金 119 互補松弛條件 所以 **( ) 0iiifx? ??? 設(shè) 為原始優(yōu)化問題的最優(yōu)解， 為對偶問題的最優(yōu)解，若兩者具有強對偶性，則 *x **( , )??* * *0**0* * * * *0*0( ) ( , ) inf ( ( ) ( ) ( ) ) ( ) ( ) ( ) ( )i i i ixiii i i iiif x gf x f x h xf x f x h xfx???????? ? ?? ? ?????? 即 **( ) 0 , 1 , ...,iif x i m? ??信息與通信工程學(xué)院 莊伯金 120 KKT優(yōu)化條件 ? 設(shè)優(yōu)化問題中，函數(shù) 可微。該條件稱為 Slater條件 。 *d **dp?*p? 凸優(yōu)化問題 通常（但并不總是） 具有強對偶性。 ? 定義（強對偶性） ：設(shè)原始問題的最優(yōu)值為 ，對偶問題的最優(yōu)值為 。 *d**dp?*p? optimal duality gap **pd?? 可以利用對偶問題找到原始問題最優(yōu)解的下界。 ( , , )Lx ??x ? ?信息與通信工程學(xué)院 莊伯金 97 拉格朗日對偶函數(shù) ? 拉格朗日對偶函數(shù) (lagrange dual function) ： 011( , ) i n f ( , , ) i n f ( ( ) ( ) ( ))pmi i i ix D x Diig L x f x f x h x? ? ? ? ? ??? ??? ? ? ???若拉格朗日函數(shù)沒有下界，則令 ( , )g ?? ? ??? 拉格朗日對偶函數(shù)為 凹函數(shù) 。 ( ) / 2t l u??ut? lt?ul ???信息與通信工程學(xué)院 莊伯金 78 線性規(guī)劃 (linear program,LP) ? LP問題的一般描述 m in im iz e s u b je c t to Tc x dG x hA x b???,m n p nGA ????RR信息與通信工程學(xué)院 莊伯金 79 LP問題的幾種類型 ? 標準 LP問題 m in im iz e s u b je c t to 0TcxA x bx??? 不等式形式 LP問題 m i ni m i z e su bj e c t t o Tc x dAx b??信息與通信工程學(xué)院 莊伯金 80 標準 LP問題的轉(zhuǎn)換 m inim iz e su bje c t to 0 , 0 , 0TTc x c x bG x G x s hA x A x bx x s??????????? ? ???? ? ?信息與通信工程學(xué)院 莊伯金 81 LP問題的例 ? Chebyshev center of a polyhedron ? Piecewiselinear minimization ? Linearfractional programming 信息與通信工程學(xué)院 莊伯金 82 Chebyshev center of a polyhedron { | }nP x R A x b? ? ?? 多面體 ? Chebyshev center：到多面體邊界距離最大的內(nèi)點（最深的點） 2( , ) { | }ccB x r x u u r? ? ?? 問題描述 m a x i m i z e s u b j e c t t o ( , )crB x r P?? LP形式 2m i n i m i z e 1 /s u b j e c t t o , 1 , . . . ,Ti c i ira x r a b i m? ? ?信息與通信工程學(xué)院 莊伯金 83 Piecewiselinear minimization ? 問題描述 1 , . . . ,m i n i m i z e ( ) m a x ( )Tiiimf x a x b???? 上半圖形式 1 , . . . ,m in im iz e s u b je c t to m a x ( )Tiiimta x b t???? LP形式 m inim iz e su b je c t to , 1 , ... ,Tiita x b t i m? ? ?信息與通信工程學(xué)院 莊伯金 84 Linearfractional programming ? 問題描述 00m in im iz e ( ) , d o m { | 0 }su b je c t to TTTc x df x f x e x fe x fG x hA x b?? ? ? ????? LP形式 m in im iz e s u b je c t to 0 0 1 0TTc y d zG y h zA y b ze y fzz????????1TTxye x fze x f????信息與通信工程學(xué)院 莊伯金 85 二次規(guī)劃 (quadratic program,QP) m inim iz e ( 1 / 2 )su b je c t to , ,TTn m n p nx P x q x rG x hA x bP S G R A R???????? ? ?? QP問題的基本描述 信息與通信工程學(xué)院 莊伯金 86 二次約束二次規(guī)劃 0 0 0m inim iz e ( 1 / 2)su bje c t to ( 1 / 2) 0 ,TTTTi i in p nix P x q x rx P x q x rA x bP S A R????? ? ????? quadratically constrained quadratic program (QCQP) 信息與通信工程學(xué)院 莊伯金 87 QP問題的例 ? Leastsquares and regression ? Distance between polyhedra 信息與通信工程學(xué)院 莊伯金 88 Leastsquares and regression ? 問題描述 22m i nim i z e Ax b?22 2T T T TA x b x A A x b A x b b? ? ? ?信息與通信工程學(xué)院 莊伯金 89 Distance between polyhedra ? 問題描述 1 2 1 2 1 1 2 2d i s t ( , ) i n f { | , }P P x x x P x P? ? ? ?1 1 1{ | }P x A x b?? 2 2 2{ | }P x A x b??? QP形式 212 21 1 2 2m in im ize su bj e c t to ,xxA x b A x b???信息與通信工程學(xué)院 莊伯金 90 Secondorder cone program, SOCP ? SOCP問題的基本描述 2m i n i m i z e s u b j e c t t o TTi i ifxA x b c x dF x g? ? ??? 二次錐約束條件 2TA x b c x d? ? ?信息與通信工程學(xué)院 莊伯金 91 SOCP問題的例 － Robust linear programming ? 問題描述 m in im iz e s u b je c t to TTiicxa x b? 其中 不是完全確定的常數(shù)。 *p*pt? *pt?信息與通信工程學(xué)院 莊伯金 77 準凸優(yōu)化問題二分法求解 ? 給定一個足夠小的 和足夠大的 ，使得區(qū)間 能包含最優(yōu)解 。 信息與通信工程學(xué)院 莊伯金 76 準凸優(yōu)化問題的上半圖形式 ? 設(shè) 為準凸函數(shù) 的凸函數(shù)族表示，即 0()fx()t x?0 ( ) ( ) 0tf x t x?? ? ? 則準凸優(yōu)化問題的可行解問題為 f i nd subj e c t to ( ) 0 , ( ) 0 , 1 , ..., tixxf x i mAx b? ????? 設(shè) 為準凸優(yōu)化問題的最優(yōu)解，若上述問題可解，則 。 0()fxx0 ( ) 0fx??信息與通信工程學(xué)院 莊伯金 71 凸優(yōu)化問題的等價形式 則 為最優(yōu)解當且僅當 ，且存在向量 滿足 ? 定理：設(shè)凸優(yōu)化問題僅有等式約束 x0 ( ) 0Tf x A v? ? ?0m inim iz e ( ) , su b je c t to nf x xA x b??RxX? v信息與通信工程學(xué)院 莊伯金 72 凸優(yōu)化問題的等價形式 則 為最優(yōu)解當且僅當 ，且 ? 定理：設(shè)凸優(yōu)化問題 x0 ( ) 0Tf x x??0m inim iz e ( ) , su b je c t to 0nf x xx??RxX?信息與通信工程學(xué)院 莊伯金 73 凸優(yōu)化問題的等價形式 0m in im iz e ( ) , s u b je c t to ( ) 0 , 1 , . . . , niTf x xf x i mA x b????R 等價于 ? 定理：設(shè)凸優(yōu)化問題 000m in im iz e ( ) , s u b je c t to ( ) 0 , 1 , . . . ,nif F z x xf F z x i m??? ? ?R 其中 0 TA x b x Fz x? ? ? ?信息與通信工程學(xué)院 莊伯金 74 凸優(yōu)化問題的等價形式 0m i n i m i z e ( ) , s u b j e c t t o , 1 , . . . ,nTiif x xa x b i m???R 等價于