本论文是通过设计和分析全牛顿步不可行内点算法来求解锥规划中的两类问题：线性规划问题和半正定规划问题。针对求解上述两类锥规划问题存在着多种算法，其中内点算法已经被证实为有效算法之一。内点算法根据迭代点的不同分为可行内点算法和不可行内点算法：可行内点算法的初始点和算法产生的迭代点始终严格可行，随着算法的运行，迭代点从可行域内部趋近于问题的最优解；不可行内点算法的初始点和算法产生的迭代点始终不可行，随着算法的运行，迭代点从可行域外部趋近于问题的最优解。在分析和总结可行内点算法和不可行内点算法的特点基础上，2fJfJ6年c Roos设计和分析了第一个求解线性规划问题的全牛顿步不可行内点算法。作者通过线性规划问题及其一个不可行初始点构造出一个线性规划问题的扰动问题。在求解该扰动问题的过程中，全牛顿步不可行内点算法产生的迭代点对于扰动问题始终严格可行，但是对于原规划问题却始终不可行。随着算法的运行，线性规划问题的对偶间隙和可行性残量按照相同的速率减少，在假设最优解存在的情况下，该算法具有O（nlogn）的算法复杂性，这也同迄今为止最好的不可行内点算法复杂性一致。该算法的另一个特点是只采用全牛顿步，从而不需要对步长进行线搜索。本论文在复杂性分析和设计新算法两方面对求解锥规划问题的全牛顿步不可行内点算法进行研究。首先我们通过借用一个经典的近似估计（proximity mea—sure）简化了c Roos给出的全牛顿步不可行内点算法的复杂性分析，并且得到了比原分析稍好的复杂性结果。进一步，我们将这种办法推广到求解半正定规划的全牛顿步不可行内点算法的复杂性分析中，也得到了同迄今为止最好的算法复杂性一致的结果。我们还通过应用一个简单的局部核函数来设计和分析全牛顿步不可行内点算法。在算法中，该简单局部核函数不但被用来构造搜索方向和定义二次收敛域，而且还被用来做为近似估计来估算迭代点到中心路径的距离。对该算法的分析表明其复杂性结果同迄今为止最好的不可行内点算法复杂性一致。进一步，我们将求解线性规划问题的基于简单局部核函数的全牛顿步不可行内点算法拓展到求解半正定规划问题中，并得到了同迄今为止最好的不可行内点算法复杂性一致的结果。