單純型算法的復(fù)雜性及改進途經(jīng)-在線瀏覽
2024-08-28 13:53本頁面
【正文】 是空集，或者都不是空集 2）只要 非空，就至少有一個頂點（ 列滿秩），其 所有頂點被 的橢球 包含，易 知 （后者是超立方體體積） 3）只要 非空，就成立 其中 ? ? ? ?? ? ? ?1?V o l V o l , 2 2 nLH X n? ?? ??? ? ???A? ? 2022 , 2 nLX B n n I?? 0E? ? ? ? 20V o l 2 2 nnLEn???結(jié)論：用橢球算法可解決 的判定問題 ??用橢球算法解決 判定問題的迭代次數(shù) ? ? ? ? ? ? 212 2 V o l 2 2nnL n Ln v V n?? ?? ? ? ? ? ?? ?3k O n L?? ? ? ? ? ?2 1 l n 2 1 l n ( ) l n ( )Vk n n V vv??? ? ? ? ?????? ? ? ?? ? ? ?110 . 5 1 1 2 nLnn? ???? ? ?? ?2Onk已知 ??迭代次數(shù) 為滿足下式的最小整數(shù) 由以上條件可得 每次迭代的計算量為 結(jié)論： 橢球算法計算復(fù)雜性為 ，多項式算法 ！ ? ?5O n L說明 1）如果求得的解屬于 但不屬于 ，采用恰當 的取整步驟可以得到屬于 的解 2）在確定 時我們簡單地用了 有的書中提到用阿達馬（ Hadamard）不等式 能給出各分量的上界為 ，最終復(fù)雜性就 是教材中給出的 3）嚴格說明算法復(fù)雜性還要討論中間數(shù)據(jù)大小和 開平方運算的復(fù)雜性等其他細節(jié)問題 ????? ?4O n L? ?2LO0E? ? ? ? ? ?? ?d e t ! 2 2 , d e t 1nj n L LA n n A? ? ?線性規(guī)劃的 Karmarkar算法（ 1984） 基本想法： 能否在可行集內(nèi)部搜索前進到最優(yōu)解 ？ 在任何內(nèi)點沿目標函數(shù)增加方向搜索一定到達邊界 目標函數(shù)梯度方向 最優(yōu)解 在靠近可行集的中間位置獲得較大改進的可能性大 設(shè)想： 每次搜索到一個新點后，設(shè)法用某種變換將可 行集變形，使新點靠近新可行集的中間位置 可能實現(xiàn)上述設(shè)想的集合與變換 考慮如下圖所示的二維空間的可行集及可行解 1x2x12 1xx??0 .7 5?0 .2 5X???????1y2y12 1yy?????????其中 ? ? ? ?? ? ? ?1 1111 1? 12 112? 0 .7 50 .7 5 0 .2 5?0 .2 5X TD X X xY T X x xxe D X X? ????????? ? ? ? ????? ? 11 1 12? 0??0xDXx??????????? ?? 0 .5? ? 0 .5XY T X ???? ????? ? 12? 0??0xDXx???????記 ? ?1 , 0nTn X R e X X? ? ? ? ? 是 維空間 個頂點的凸組合生成的 維單純型 1x3x? ?0,1,01x1?1x2x3?? ?1,0,0? ?1,0,0? ?1,02?? ?0,1??12xn? n n 1n?11, 1 , 0 ,nnnn i i i iiiX R X V i? ? ?????? ? ? ? ? ? ???????n?在 內(nèi)向任意方向移動都不會出 的最大步長： 1 1 1, Ten n n???????n? n?的 中心點 ： ? ?11rnn??rr 是中心點到 個頂點生成的 維單純型的距離 1n? 2n?是 的 內(nèi)點 （分量都大于零）！ 1|| ||dern d??01???n?r 的作用：對任何非零的 和 ，可保證 ndR?1en1en？ ? ? ? ?? ?1? 1?,? nXTD X XT X X Re D X X??? ? ? 上的 尺度變換 設(shè) 是 的任意內(nèi)點，即 n?定義尺度變換 ? 1 , 0 , 1T ie X x i n? ? ? ? ??Xn?其中 ? ?1??? nxDXx?????????? ?1111??? nxDXx?????????????如果 ，則 ? ??XY T X?11111? ,1? ?jjjnnxxy j nx x x x???? ? ? ???? ? ? ?? ?1???X TD X YX T Ye D X Y???1）有逆變換 尺度變換的性質(zhì) ?3） 111111?,? ?1jjjnnnxxyjx x x xxx???????? ? ?2） 11? ,? ?jjjnnxyxjx y x y????? ?? ?? ,n nnXY R Y T X X? ? ? ? ? ?11111? ,? ?jjjnnxxyjx x x x???????? 1 10,njyyyj? ? ???? ?? 1?XT X en?其中 ， Karmarkar標準型 m in. 010TTCXAXeXX???mnAR ??1） 行滿秩 2） 3）最優(yōu)目標值等于零 ? ?1 , 1 , , 1 T neR??A0Ae ? 1en 的中心點 是可行解 假設(shè)： m in . 0TnCXAXX????? n?? ??XY T X?Karmarkar算法的主要步驟 對原問題進行尺度變換，令 出發(fā)點：原問題的一個可行內(nèi)點 （分量都大于零） m in . 0TnCXAXX???? ?1?? ?XX T Y?? ??X考慮變換后的近似問題 ? ?? ??m in?s . t. 0 ,TnC D X YA D X Y Y? ? ??? ?? ?? ??m i
法律信息相關(guān)推薦
鄂ICP備17016276號-1