凸二次规划基于新的核函数的大步校正原始-对偶内点算法

A Large-update Primal-dual Interior-point Algorithm for Convex Quadratic Programming Based on a New Kernel Function

本文对凸二次规划提出了一种基于新的核函数的大步校正原始-对偶内点算法.这种核函数构造新的障碍函数不仅可以定义新的搜索方向,而且可以控制内迭代的过程,使得对凸二次规划提出的大步校正原始-对偶内点算法的多项式复杂性阶改善到O(槡n(logn)2log(n/ε)),优于基于经典对数障碍函数的相应算法的复杂性阶.

A primal-dual interior-point algorithm for convex quadratic programming（CQP） based on a new kernel function is presented. We use the kernel function to construct a new barrier function. It not only can difine a new search direction,but also can control the process of inner iteration. These properties enable to improve the polynomial complexity bound of a large-update primal-dual interior-point method for （CQP） to O（√n（logn）2log（n/ε））,which is better than the complexity bound of the corresponding algorithm based on the classical logarithmic barrier function.