【关於凸二次规划的几种内点算法】.pdf

目录英文摘要中文摘要前言第一章关于凸二次规划的-个具有多项式计算复杂性和局部超线性收敛的预估一校正算法 1引言.1预估一校正算法.1算法的设定性1算法的计算复杂性.1算法的收敛性第二章关于凸二次规划的一个位势函数下降算法 2引言算法的提出和多项式时间的i明 2下降方向的注释第三章关于凸二次规划的原始对偶非可行内点算法 3引言.

摘要印度数学家Karmarkar在1984年对线性规化问题提出了个具有多项式时间内点新算法后。内点算法引起了广大研究者的注意,成为近年来研究数学规划领域的一强有力手段。各种形式的内点算法不断出现,有路径跟踪算法、位势函数下降法、原仿射算法等等.本文对凸二次规划作了一些研究,并给出一些结果.本文共分三章:第一章:介绍了二次规划的一个原始-对偶路径跟踪算法之后,提出了一个预估-校正的路径跟踪算法。该算法在每次迭代的预估阶段,使用仿射方向,步长参数6的选取是可变的,该阶段产生的点列在该点中心路径的较大范围内。

(dLemke五补转轴法:此法用于约素季件S={x1 Ax=b x20,Q是对称短阵},由优化理沦的k-T条件得下到方轻组 μ-Gx+ATy=c V-Ax q-= μx=0 vy = 0 μ,v,x,y≥o 从于是条件可写成:W-M2= W,wz=0 用主元消去法找此互补问影,选主元时需注意山若W;(或:)离基,则(或w)进基,按匹单纯形方生中的最小北值规则确定离基变量.线埋约来的凸二次规划与浅性规划问题有着担同的结构,二者半出担关 1949年,美国科学家anti年提出了用素求非浅性知划问题的一种有效方法—单纯形方结。1959年P.