二阶锥规划两个新的预估-校正算法

基于不可行内点法和预估-校正算法的思想,提出两个新的求解二阶锥规划的内点预估-校正算法.其预估方向分别是Newton方向和Euler方向,校正方向属于Alizadeh-Haeberly-Overton(AHO)方向的范畴.算法对于迭代点可行或不可行的情形都适用.主要构造了一个更简单的中心路径的邻域,这是有别于其它内点预估-校正算法的关键.在一些假设条件下,算法具有全局收敛性、线性和二次收敛速度,并获得了O(rln(ε0/ε))的迭代复杂性界,其中r表示二阶锥规划问题所包含的二阶锥约束的个数.数值实验结果表明提出的两个算法是有效的.     

非线性互补问题的一种不可行非内点连续方法

基于 Chen- Mangasarian光滑函数的一个子类 ,针对单调非线性互补问题给出了一种不可行非内点连续方法预估校正算法 ,并在适当的条件下 ,证明了算法具有全局线性收敛性和局部二次收敛性。     

框式线性规划的多项式预估校正内点算法

本文研究带线性约束的框式线性规划问题,给出了一个预估校正内点算法,分析了该算法的多项式计算复杂性,并证明其迭代复杂度为Ο(nL).     

关于半定规划的一种宽邻域不可行内点算法的注记

针对半定规划的宽邻域不可行内点算法,将牛顿法和预估校正法进行结合,构造出适当的迭代方向,提出一个修正的半定规划宽邻域不可行内点算法,并在适当的假设条件下,证明了该算法具有O(n~(1/3)L)的迭代复杂界.最后利用Matlab编程,给出了基于KM方向和NT方向的数值实验结果.     

单调线性互补问题的Mehrotra型预估-校正算法的迭代复杂性

Mehrotra型预估-校正算法是很多内点算法软件包的算法基础,但它的多项式迭代复杂性直到2007年才被Salahi等人证明.通过选择一个固定的预估步长及与Salahi文中不同的校正方向,本文把Salahi等人的算法拓展到单调线性互补问题,使得新算法的迭代复杂性为O(n log((x0)T s0/ε)),同时,初步的数值实验证明了新算法是有效的.     

单调非线性互补问题的不可行内点算法

为了克服内点算法初始点不易给出的缺陷，本文给出了一个求解单调非线性互补问题的不可行内点算法，并证明了算法的收敛性。     

半定规划的一种非精确不可行内点法

本文给出了求解半定规划的一种基于KM方向的非精确不可行内点法 ,分析了其收敛性 ,结果表明 ,该算法最多可以在O(n2 ln( 1 /ε) )步内求出半定规划的一个ε 近似解 ,与YZhang所提出的精确不可行内点法有相同的界 .     

一类非凸区域的拟法锥构造方法及其在非凸规划求解中的应用

本文给出基于球形的一类满足拟法锥条件区域的拟法锥构造方法,基于该可行域的拟法锥,建立求解在该类非凸区域上的规划问题的K-K-T点的部分凝聚同伦组合方程,并证明了该同伦内点法的整体收敛性,给出实现同伦内点法的具体数值跟踪算法步骤,并通过数值例子证明算法是可行的和有效的．     

线性规划基于预-校正的组合同伦多项式算法

本文针对线性规划问题提出了一个新的内点方法——组合同伦内点方法，并采用预估校正算法来跟踪组合同伦路径从而得到问题的ε-解.最后讨论了该算法的收敛性，并证明了该算法为多项式算法。     

求解退化单调线性互补问题极大互补解的复杂性

本文考虑求解退化单调线性互补问题的一类不可行内点算法，其中嵌入一个恢复算法，给出了用这类算法产生所考虑问题的一个精确极大互补解的复杂性．     

A POLYNOMIAL PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING

This article presents a polynomial predictor-corrector interior-point algorithm for convex quadratic programming based on a modified predictor-corrector interior-point algorithm. In this algorithm, there is only one corrector step after each predictor step, where Step 2 is a predictor step and Step 4 is a corrector step in the algorithm. In the algorithm, the predictor step decreases the dual gap as much as possible in a wider neighborhood of the central path and the corrector step draws iteration points back to a narrower neighborhood and make a reduction for the dual gap. It is shown that the algorithm has O(n~(1/2)L) iteration complexity which is the best result for convex quadratic programming so far.     

A modified predictor-corrector method for linear programming

In the predictor-corrector method of Mizuno, Todd and Ye [1], the duality gap is reduced only at the predictor step and is kept unchanged during the corrector step. In this paper, we modify the corrector step so that the duality gap is reduced by a constant fraction, while the predictor step remains unchanged. It is shown that this modified predictor-corrector method retains the iteration complexity as well as the local quadratic convergence property.     

A predictor-corrector interior-point algorithm for P ∗ ( κ ) -horizontal linear complementarity problem

We present a predictor-corrector path-following interior-point algorithm for \(P_*(\kappa )\) horizontal linear complementarity problem based on new search directions. In each iteration, the algorithm performs two kinds of steps: a predictor (damped Newton) step and a corrector (full Newton) step. The full Newton-step is generated from an algebraic reformulation of the centering equation, which defines the central path and seeks directions in a small neighborhood of the central path. While the damped Newton step is used to move in the direction of optimal solution and reduce the duality gap. We derive the complexity for the algorithm, which coincides with the best known iteration bound for \(P_*(\kappa )\) -horizontal linear complementarity problems.     

线性互补问题的宽邻域预估校正算法

对线性互补问题提出了一种新的宽邻域预估校正算法,算法是基于经典线性规划路径跟踪算法的思想,将Maziar Salahi关于线性规划预估校正算法推广到线性互补问题中,给出了算法的具体迭代步骤并讨论了算法迭代复杂性,最后证明了算法具有多项式复杂性为O(ηlog(X~0)~Ts~0/ε)。     

On polynomiality of the Mehrotra-type predictor—corrector interior-point algorithms

Recently, Mehrotra [3] proposed a predictor—corrector primal—dual interior-point algorithm for linear programming. At each iteration, this algorithm utilizes a combination of three search directions: the predictor, the corrector and the centering directions, and requires only one matrix factorization. At present, Mehrotra's algorithmic framework is widely regarded as the most practically efficient one and has been implemented in the highly successful interior-point code OB1 [2]. In this paper, we study the theoretical convergence properties of Mehrotra's interior-point algorithmic framework. For generality, we carry out our analysis on a horizontal linear complementarity problem that includes linear and quadratic programming, as well as the standard linear complementarity problem. Under the monotonicity assumption, we establish polynomial complexity bounds for two variants of the Mehrotra-type predictor—corrector interior-point algorithms. These results are summarized in the last section in a table.Research supported in part by NSF DMS-9102761, DOE DE-FG05-91ER25100 and DOE DE-FG02-93ER25171.Corresponding author.     

A New Noninterior Predictor–Corrector Method for the P0 LCP

In this paper a new predictor-corrector noninterior method for LCP is presented, in which the predictor step is generated by the Levenberg-Marquadt method, which is new in the predictor-corrector-type methods, and the corrector step is generated as in [3]. The method has the following merits: (i) any cluster point of the iteration sequence is a solution of the P₀ LCP; (ii) if the generalized Jacobian is nonsingular at a solution point, then the whole sequence converges to the (unique) solution of the P₀ LCP superlinearly; (iii) for the P₀ LCP, if an accumulation point of the iteration sequence satisfies the strict complementary condition, then the whole sequence converges to this accumulation point superlinearly. Preliminary numerical experiments are reported to show the efficiency of the algorithm.     

A PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING

The simplified Newton method, at the expense of fast convergence, reduces the work required by Newton method by reusing the initial Jacobian matrix. The composite Newton method attempts to balance the trade-off between expense and fast convergence by composing one Newton step with one simplified Newton step. Recently, Mehrotra suggested a predictor-corrector variant of primal-dual interior point method for linear programming. It is currently the interior-point method of the choice for linear programming. In this work we propose a predictor-corrector interior-point algorithm for convex quadratic programming. It is proved that the algorithm is equivalent to a level-1 perturbed composite Newton method. Computations in the algorithm do not require that the initial primal and dual points be feasible. Numerical experiments are made.     

P*(κ)阵线性互补问题一种新的宽邻域预估-校正内点算法

基于邻近度量函数的最小值,对P*(κ)阵线性互补问题提出了一种新的宽邻域预估-校正算法,在较一般的条件下,证明了算法的迭代复杂性为O(κ+1)23n log(x0ε)Ts0.算法既可视为Miao的P*(κ)阵线性互补问题Mizuno-Todd-Ye预估-校正内点算法的一种变形,也可以视为最近Zhao提出的线性规划基于邻近度量函数最小值的宽邻域内点算法的推广.