运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2009年
3期
67-82
,共16页
运筹学%半正定规划%原始-对偶内点算法%大步-小步校正法%迭代界
運籌學%半正定規劃%原始-對偶內點算法%大步-小步校正法%迭代界
운주학%반정정규화%원시-대우내점산법%대보-소보교정법%질대계
在原始对偶内点算法的设计和分析中,障碍函数对算法的搜索方法和复杂性起着重要的作用.本文由核函数来确定障碍函数,设计了一个求解半正定规划问题的原始-对偶内点算法.这个障碍函数即可以定义算法新的搜索方向,又度量迭代点与中心路径的距离,同时对算法的复杂性分析起着关键的作用.我们计算了算法的迭代界,得出了关于大步校正法和小步校正法的迭代界,它们分别是O(√n log n 10g n/ε)和O(√n log n/ε),这里n是半正定规划问题的维数.最后,我们根据一个算例,说明了算法的有效性以及对核函数的参数的敏感性.
在原始對偶內點算法的設計和分析中,障礙函數對算法的搜索方法和複雜性起著重要的作用.本文由覈函數來確定障礙函數,設計瞭一箇求解半正定規劃問題的原始-對偶內點算法.這箇障礙函數即可以定義算法新的搜索方嚮,又度量迭代點與中心路徑的距離,同時對算法的複雜性分析起著關鍵的作用.我們計算瞭算法的迭代界,得齣瞭關于大步校正法和小步校正法的迭代界,它們分彆是O(√n log n 10g n/ε)和O(√n log n/ε),這裏n是半正定規劃問題的維數.最後,我們根據一箇算例,說明瞭算法的有效性以及對覈函數的參數的敏感性.
재원시대우내점산법적설계화분석중,장애함수대산법적수색방법화복잡성기착중요적작용.본문유핵함수래학정장애함수,설계료일개구해반정정규화문제적원시-대우내점산법.저개장애함수즉가이정의산법신적수색방향,우도량질대점여중심로경적거리,동시대산법적복잡성분석기착관건적작용.아문계산료산법적질대계,득출료관우대보교정법화소보교정법적질대계,타문분별시O(√n log n 10g n/ε)화O(√n log n/ε),저리n시반정정규화문제적유수.최후,아문근거일개산례,설명료산법적유효성이급대핵함수적삼수적민감성.
