对称锥规划是数学规划中较为活跃的一个分支,它在交通运输,经济管理,信息科学和控制理论等学科中有着广泛的应用.另外,线性规划,半定规划以及二阶锥规划都是对称锥规划的子问题,所以它是一类涵盖面较宽，内容较新,理论知识丰富,学术价值高的优化问题,吸引了众多专家和学者对其进行深入研究并取得丰硕的成果.求解对称锥规划问题有诸多方法,其中最为重要的一类是内点算法.众所周知，宽邻域算法与窄邻域算法各有优缺点，宽邻域算法具有数值效果好而理论复杂度相对较差的特点,相反,窄邻域算法具有数值效果相对较差而理论复杂度好的特点.本文的研究目的是设计出兼有两者优点的算法.为此,我们设计了几个复杂度较低的宽邻域内点算法,主要工作概括如下：　　1.基于负无穷宽邻域,提出线性规划的弧搜索内点算法.该算法沿中心路径的椭圆近似寻找最优解.通过分析,获得该算法的多项式复杂度为O(n3/4L),其中n是问题的维数，L是输入数据的长度.该算法不仅改进了宽邻域算法的复杂度而且数值实验表明它是有效的.　　2.首先,使用Schatten1-范数定义一个新的宽邻域.基于该邻域,设计半定规划的新的二阶Mehrotra-型预估-矫正算法.其次,证明了一个重要的不等式‖UV+ VU‖1≤2‖U‖F‖V‖F,这是分析算法的收敛性不可缺少的.基于该不等式，证明该算法对于一个可交换类是收敛的,其中取H..K..M方向时,算法的复杂度为O(√nlogε-1),取Nesterov-Todd方向时,算法的复杂度为O(√nlogε-1).最后,通过数值实验说明该算法在实践中也是有效的.　　3.推广艾文宝和张树中提出的宽邻域到对称锥上,获得一个新的宽邻域N(β,γ).使用该邻域，提出对称锥规划的基于一个新的宽邻域的不可行内点算法.以欧氏Jordan代数作为基本分析工具,证明了对于一个可交换类方向，算法是收敛的,其中包括Nesterov-Todd方向，xs和sx方向.获得的复杂度比Rangarajan减少了一个因子r0.5.特别地，Nesterov-Todd方向的复杂度与Zhang等中线性规划的复杂度一致.据我们所知,本章获得的宽邻域不可行内点算法的复杂度与小步长路径跟踪算法的当前最好的理论复杂度一致.最后,简要地分析了存在严格可行初始点时算法的复杂度.　　4.高阶矫正算法因具有精度高,数值效果好,复杂度低的特性而备受关注.二阶矫正算法作为高阶矫正算法的一种特殊情况,也引起研究者的兴趣.为进一步改进我们之前提出的宽邻域一阶不可行算法的复杂度,设计对称锥规划的宽邻域二阶不可行原-对偶路径跟踪算法,该算法也使用宽邻域N(β,γ),并证明对于一个可交换类方向算法具有多项式收敛性.特别地,对于Nesterov-Todd方向复杂度为O(r5/4logε-1),对于xs和sx方向复杂度均为O(r7/4 logε-1),其中r是欧氏Jordan代数的秩,ε是要求的精度.　　5.基于负无穷宽邻域,提出对称锥规划带自适应更新策略的Mehrotra-型预估-矫正不可行算法.为证明算法对于一个可交换类方向具有多项式收敛性,首先需要证明一个重要不等式‖xoy‖1≤√3‖x‖F‖y‖F,其中映射‖·‖1被定义为‖x‖1=∑ri=1|λi|,谱分解为x=∑ri=1λiCi.据我们所知,这个不等式是第一次在对称锥上被证明成立.使用该不等式，证明当取一个可交换类方向时算法是收敛的，其中对于Nesterov-Todd方向，算法的复杂度为O(r2logε-1),对于rs和sr方向,算法的复杂度都是O(r5/2logε-1).通过测试Netlib和Sdplib中的一些线性规划问题和半定规划问题表明该算法的数值效果较好.