第3講凸集、凸函數(shù)、凸規(guī)劃-全文預覽
【正文】 為 D 上的凸函數(shù) ， 則稱規(guī)劃問題 ? ?xfDx ?m in 為凸規(guī)劃問題． 例： ? ?xf若 為 nR 上的凸函數(shù)， ? ?xfnRx ?m i n則為無約束凸規(guī)劃問題． 例： 0 X bs .t .A X m i n ??CX線性規(guī)劃 凸規(guī)劃 凸規(guī)劃 例： ??????????????????????,...,1,0)( ,...,1,0)(..m i n( 3) ,...,1,0)(..m i n ( 2) ,...,1,0)(..m i n ( 1) , ),...,2,1(h),...,2,1(ljxhmixgtsf ( x)mixgtsf ( x) ljxhtsf ( x)RljSmigSfRSjiijnjin是凸規(guī)劃：則下面三個規(guī)劃問題都上的線性函數(shù)是上的凹函數(shù)，是上的凸函數(shù)，是為開凸集，設凸規(guī)劃 定理 (1)凸規(guī)劃問題的任一局部極小點是全局 極小點，且全體極小點的集合為凸集． (2) 若 ? ?xf 是凸集 nRD ? 上的嚴格凸函數(shù)， 且凸規(guī)劃問題 ? ?xfDx ?m in局部極小點 x*存在， 則 x*是唯一的全局極小點． 凸規(guī)劃的基本性質 定理 凸規(guī)劃的任一局部最優(yōu)解都是它的整體最優(yōu)解。,|)a(221121212211212121是凸集是凸集上的凸集，則是和設DxDxxxDDDxDxxxDDRDD n??????????推論 ： ??kiii D1?設 kiD i ,2,1, ?? 是凸集， 則 也是凸集， 其中 i?是實數(shù)． (4) S 是凸集當且僅當 S中任意有限個點的凸 組合仍然在 S中 . 凸集 性質 注： 和集 和 并集 有很大的區(qū)別，凸集的并集 未必是凸集，而凸集的和集是凸集． 例 ： ? ?? ?RxxDT ?? 0,1 表示 x 軸上的點． ? ?? ?RyyD T ?? ,02 表示 y 軸上的點． 則 21 DD ?表示兩個軸的所有點， 它不是凸集； 221 RDD ??而 凸集 ． 凸集 性質 定義 設 S 中任意有限個點的所有凸組合所構成的集合稱為 S的凸包，記為 H(S),即 ,nRS ?凸集 凸包 (Convex Hull) ?????? ?????? ????miiiimiii NmmiSxxSH11,1,...,2,1,0,)( ???定理 H(S)是 Rn 中所有包含 S 的凸集的交集 . H(S)是包含 S 的最小凸集 . 定義 錐、凸錐 .SS .xS ,Sxx,0Sx,000為凸錐則稱又是凸集，如果為頂點的錐以是則稱有及，如果對一切設????????SxRSn凸集 凸錐 (Convex Cone) 凸函數(shù) 凸函數(shù) (Convex Function) 定義 設 ? ?,: RSxf ?是非空凸集， nRD ?若對任意的 , Dyx ? 及任意的 ? ?1,0??都有： ? ?? ? ? ? ? ? ? ?yfxfyxf ???? ????? 11則稱函數(shù) ? ?xf 為 D 上的凸函數(shù)． 注： 將上述定義中的不等式反向，可以得到 凹函數(shù) 的定義 ． 凸函數(shù) 嚴格凸函數(shù) 設 ? ?,: RSxf ?是非空凸集， nRD ?若對任意的 , ( ) ,x y D x y?? 及任意的 ? ?0 ,1? ?都有： ? ?? ? ? ?
電大資料相關推薦
鄂ICP備17016276號-1