电子科技
電子科技
전자과기
IT AGE
2015年
2期
1-3
,共3页
半定规划%宽邻域%可行内点算法%多项式复杂性
半定規劃%寬鄰域%可行內點算法%多項式複雜性
반정규화%관린역%가행내점산법%다항식복잡성
在半定规划的内点算法中,中心参数的选择对于算法的复杂性和有效性是尤为重要的.但以往半定规划的论文中,中心参数是固定的,这大幅增加了算法的复杂性并降低了有效性.文中基于宽邻域提出了一种有效可地行内点算法,使中心参数与步长成多项式的关系,这样中心参数会随着步长的变化而更新.从而每次迭代均取到最优参数,且在文中,基于NT方向,证明了该算法在理论上的复杂性和有效性均是最优的.
在半定規劃的內點算法中,中心參數的選擇對于算法的複雜性和有效性是尤為重要的.但以往半定規劃的論文中,中心參數是固定的,這大幅增加瞭算法的複雜性併降低瞭有效性.文中基于寬鄰域提齣瞭一種有效可地行內點算法,使中心參數與步長成多項式的關繫,這樣中心參數會隨著步長的變化而更新.從而每次迭代均取到最優參數,且在文中,基于NT方嚮,證明瞭該算法在理論上的複雜性和有效性均是最優的.
재반정규화적내점산법중,중심삼수적선택대우산법적복잡성화유효성시우위중요적.단이왕반정규화적논문중,중심삼수시고정적,저대폭증가료산법적복잡성병강저료유효성.문중기우관린역제출료일충유효가지행내점산법,사중심삼수여보장성다항식적관계,저양중심삼수회수착보장적변화이경신.종이매차질대균취도최우삼수,차재문중,기우NT방향,증명료해산법재이론상적복잡성화유효성균시최우적.