A New Second-Order Infeasible Primal-Dual Path-Following Algorithm for Symmetric Optimization

In this article, we propose a new second-order infeasible primal-dual path-following algorithm for symmetric cone optimization. The algorithm further improves the complexity bound of a wide infeasible primal-dual path-following algorithm. The theory of Euclidean Jordan algebras is used to carry out our analysis. The convergence is shown for a commutative class of search directions. In particular, the complexity bound is 𝒪(r^5/4log ?^?1) for the Nesterov-Todd direction, and 𝒪(r^7/4log ?^?1) for the xs and sx directions, where r is the rank of the associated Euclidean Jordan algebra and ? is the required precision. If the starting point is strictly feasible, then the corresponding bounds can be reduced by a factor of r^3/4. Some preliminary numerical results are provided as well.     

New Interior-Point Algorithm for Symmetric Optimization Based on a Positive-Asymptotic Barrier Function

Abstract

We define a new interior-point method (IPM), which is suitable for solving symmetric optimization (SO) problems. The proposed algorithm is based on a new search direction. In order to obtain this direction, we apply the method of algebraically equivalent transformation on the centering equation of the central path. We prove that the associated barrier cannot be derived from a usual kernel function. Therefore, we introduce a new notion, namely the concept of the positive-asymptotic kernel function. We conclude that this algorithm solves the problem in polynomial time and has the same complexity as the best known IPMs for SO.     

基于全牛顿步长求解凸二次规划问题的不可行内点算法

借助于全牛顿步长对凸二次规划问题提出了一种新的不可行内点算法.算法主要迭代由可行迭代步和中心路径邻域迭代步组成.其优点是线性搜寻方向是不需要的.最后证明算法迭代复杂性为O(nlogn/ε),与目前最好的不可行内点算法复杂性一致.     

A Full-Newton Step Infeasible Interior-Point Algorithm Based on Darvay Directions for Linear Optimization

We present a full-Newton step primal-dual infeasible interior-point algorithm based on Darvay’s search directions. These directions are obtained by an equivalent algebraic transformation of the centering equation. The algorithm decreases the duality gap and the feasibility residuals at the same rate. During this algorithm we construct strictly feasible iterates for a sequence of perturbations of the given problem and its dual problem. Each main iteration of the algorithm consists of a feasibility step and some centering steps. The starting point in the first iteration of the algorithm depends on a positive number ξ and it is strictly feasible for a perturbed pair, and feasibility steps find strictly feasible iterate for the next perturbed pair. By using centering steps for the new perturbed pair, we obtain strictly feasible iterate close to the central path of the new perturbed pair. The algorithm finds an ?-optimal solution or detects infeasibility of the given problem. The iteration bound coincides with the best known iteration bound for linear optimization problems.     

基于核函数求解LCPs的全-Newton步不可行内点算法

本文对P_*(κ)线性互补问题设计了一种基于核函数的全-Newton步不可行内点算法,是对Mansouri等人提出的单调线性互补问题全-Newton步不可行内点算法的改进与推广.算法的主迭代由一个可行步和几个中心步构成且可行步采用小步校正.通过建立和应用一些新的技术性结果,证明了算法的多项式复杂性为O((1+2κ)~(3/2)(1og_2log_264(1+2κ))nlogmax{(x0)Ts0,||r0||}/ε),当k=0时,与当前单调线性互补问题的不可行内点算法最好的迭代复杂性界一致.最后,用Matlab数值实验验证了算法的可行性.     

A New Complexity Analysis for Full-Newton Step Infeasible Interior-Point Algorithm for Horizontal Linear Complementarity Problems

In this paper, we first present a full-Newton step feasible interior-point algorithm for solving horizontal linear complementarity problems. We prove that the full-Newton step to the central path is quadratically convergent. Then, we generalize an infeasible interior-point method for linear optimization to horizontal linear complementarity problems based on new search directions. This algorithm starts from strictly feasible iterates on the central path of a perturbed problem that is produced by a suitable perturbation in the horizontal linear complementarity problem. We use the so-called feasibility steps that find strictly feasible iterates for the next perturbed problem. By using centering steps for the new perturbed problem, we obtain a strictly feasible iterate close enough to the central path of the new perturbed problem. The complexity of the algorithm coincides with the best known iteration bound for infeasible interior-point methods.     

Convergence Analysis of the Inexact Infeasible Interior-Point Method for Linear Optimization

We present the convergence analysis of the inexact infeasible path-following (IIPF) interior-point algorithm. In this algorithm, the preconditioned conjugate gradient method is used to solve the reduced KKT system (the augmented system). The augmented system is preconditioned by using a block triangular matrix. The KKT system is solved approximately. Therefore, it becomes necessary to study the convergence of the interior-point method for this specific inexact case. We present the convergence analysis of the inexact infeasible path-following (IIPF) algorithm, prove the global convergence of this method and provide complexity analysis. Communicated by Y. Zhang.     

A Full-Newton Step Infeasible Interior-Point Algorithm for Linear Programming Based on a Kernel Function

This paper proposes an infeasible interior-point algorithm with full-Newton step for linear programming, which is an extension of the work of Roos (SIAM J. Optim. 16(4):1110–1136, 2006). The main iteration of the algorithm consists of a feasibility step and several centrality steps. We introduce a kernel function in the algorithm to induce the feasibility step. For parameter p∈[0,1], the polynomial complexity can be proved and the result coincides with the best result for infeasible interior-point methods, that is, O(nlog n/ε). This work was supported in part by the National Natural Science Foundation of China under Grant No. 10871098.     

A New Infeasible Interior-Point Method Based on a Non-Coercive Kernel Function with Improved Centering Steps for Second-Order Cone Optimization

In this article, we present a new full Nesterov-Todd step infeasible interior-point method for second-order cone optimization based on a non-coercive kernel function. The main iteration consists of a so-called feasibility step and one centering step, whereas the earlier versions, in [4 S. Bouali and S. Kabbaj ( 2014 ). Full-NT step infeasible interior-point method for SOCO based on a specific kernel function . Afr. Mat. 25 : 549 – 565 .[Crossref] , [Google Scholar], 21 M. Zangiabadi , G. Gu , and C. Roos ( 2013 ). A full Nesterov-Todd step infeasible interior-point method for second-order cone optimization . J. Optim. Theory Appl. 158 : 816 – 858 .[Crossref], [Web of Science ®] , [Google Scholar]], needed two additional centering steps. We use a kernel function to induce the feasibility step. The new algorithm reduces the searching steps in each iteration and tenders an interesting analysis for complexity bound.     

求解凸二次规划问题的一种加权路径跟踪内点算法

基于Darvay提出用加权路径跟踪内点算法解线性规划问题的相关工作,本文致力于将此算法推广于解凸二次规划问题,并证明此算法具有局部二次收敛速度和目前所知的最好的多项式时间算法复杂性.     

An Interior-Point Algorithm for Nonlinear Minimax Problems

We present a primal-dual interior-point method for constrained nonlinear, discrete minimax problems where the objective functions and constraints are not necessarily convex. The algorithm uses two merit functions to ensure progress toward the points satisfying the first-order optimality conditions of the original problem. Convergence properties are described and numerical results provided.     

An Interior-Point Algorithm for Nonconvex Nonlinear Programming

The paper describes an interior-point algorithm for nonconvex nonlinear programming which is a direct extension of interior-point methods for linear and quadratic programming. Major modifications include a merit function and an altered search direction to ensure that a descent direction for the merit function is obtained. Preliminary numerical testing indicates that the method is robust. Further, numerical comparisons with MINOS and LANCELOT show that the method is efficient, and has the promise of greatly reducing solution times on at least some classes of models.     

基于一个有限罚函数的二阶锥优化的原始-对偶内点算法

本文基于一个有限罚函数,设计了关于二阶锥优化问题的原始-对偶路径跟踪内点算法,由于该罚函数在可行域的边界取有限值,因而它不是常规的罚函数,尽管如此,它良好的解析性质使得我们能分析算法并得到基于大步校正和小步校正方法目前较好的多项式时间复杂性分别为O(N~(1/2)log N log N/ε)和O(N~(1/2)log N/ε),其中N为二阶锥的个数．     

求解凸二次规划问题的不可行内点算法

该文对一般的凸二次规划问题，给出了一个不可行内点算法，并证明了该算法经过犗（狀２犔）步迭代之后，要么得到问题的一个近似最优解，要么说明该问题在某个较大的区域内无解．     

An improved Interior-Point Algorithm for Large-Scale Shakedown Analysis

This work focuses on the calculation of shakedown load-factors of structures by using the lower-bound theorem of shakedown analysis. The resultant optimization problem is solved by an interior-point algorithm. In general, the application of shakedown analysis to practical problems leads to large-scale problems with large numbers of unknowns and constraints. Thus the solution turns out to be computationally intensive. For this reason it is important to reduce the dimension of the considered problem. Therefore, the major improvement of the presented algorithm consists of a problem-oriented reformulation of the problem reducing the size of the system to be solved. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

多行程车辆路径问题中变邻域搜索算法的应用

多行程车辆路径问题是标准车辆路径问题的一个变体,每个车辆在运行期间可以使用不止一次.对于这种NP-HARD问题,提出了一个改进变邻域搜索算法并设计了四个邻域结构用于求解和制定多行程路径问题的调度规划.算法测试了一组标准实例问题,获得的解决方法与文献中提出的三种不同数据集进行比较计算证明,算法提供了较高质量的求解结果.最后采用三个标准函数进行数值计算,与PSO和GA算法进行比较证明,提出的VNS算法虽然运行花费时间较长,但是达到全局收敛性的比率和全局收敛性都远超其他两种算法.     

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

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