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.     

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

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

Primal-dual Interior-point Algorithms for Second-order Cone Optimization Based on a New Parametric Kernel Function

A class of polynomial primal-dual interior-point algorithms for second-order cone optimization based on a new parametric kernel function, with parameters p and q, is presented. Its growth term is between linear and quadratic. Some new tools for the analysis of the algorithms are proposed. The complexity bounds of O（√Nlog N log N/ε） for large-update methods and O（√Nlog N/ε） for smallupdate methods match the best known complexity bounds obtained for these methods. Numerical tests demonstrate the behavior of the algorithms for different results of the parameters p and q.     

A full-NT-step infeasible interior-point algorithm for SDP based on kernel functions

This paper proposes an infeasible interior-point algorithm with full Nesterov-Todd (NT) steps for semidefinite programming (SDP). The main iteration consists of a feasibility step and several centrality steps. First we present a full NT step infeasible interior-point algorithm based on the classic logarithmical barrier function. After that a specific kernel function is introduced. The feasibility step is induced by this kernel function instead of the classic logarithmical barrier function. This kernel function has a finite value on the boundary. The result of polynomial complexity, O(nlogn/ε), coincides with the best known one for infeasible interior-point methods.     

Primal-Dual Interior-Point Algorithms for Semidefinite Optimization Based on a Simple Kernel Function

Interior-point methods (IPMs) for semidefinite optimization (SDO) have been studied intensively, due to their polynomial complexity and practical efficiency. Recently, J. Peng et al. introduced so-called self-regular kernel (and barrier) functions and designed primal-dual interior-point algorithms based on self-regular proximities for linear optimization (LO) problems. They also extended the approach for LO to SDO. In this paper we present a primal-dual interior-point algorithm for SDO problems based on a simple kernel function which was first presented at the Proceedings of Industrial Symposium and Optimization Day, Australia, November 2002; the function is not self-regular. We derive the complexity analysis for algorithms based on this kernel function, both with large- and small-updates. The complexity bounds are and , respectively, which are as good as those in the linear case. Mathematics Subject Classifications (2000) 90C22, 90C31.     

An infeasible interior-point algorithm with full-Newton step for linear optimization

Recently, Roos (SIAM J Optim 16(4):1110–1136, 2006) presented a primal-dual infeasible interior-point algorithm that uses full-Newton steps and whose iteration bound coincides with the best known bound for infeasible interior-point algorithms. In the current paper we use a different feasibility step such that the definition of the feasibility step in Mansouri and Roos (Optim Methods Softw 22(3):519–530, 2007) is a special case of our definition, and show that the same result on the order of iteration complexity can be obtained.      

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.     

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.     

一个解半正定规划问题的基于广义对数障碍函数的原始对偶内点算法

本文对经典对数障碍函数推广,给出了一个广义对数障碍函数.基于这个广义对数障碍函数设计了解半正定规划问题的原始-对偶内点算法.分析了该算法的复杂性,得到了一个理论迭代界,它与已有的基于经典对数障碍函数的算法的理论迭代界一致.同时,并给出了一个数值算例,阐明了函数的参数对算法运行时间的影响.     

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

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

Convergence of the homotopy path for a full-Newton step infeasible interior-point method

Roos [C. Roos, A full-Newton step O(n) infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16 (4) (2006) 1110-1136 (electronic)] proposed a new primal-dual infeasible interior-point method for linear optimization. This new method can be viewed as a homotopy method. In this work, we show that the homotopy path has precisely one accumulation point in the optimal set. Moreover, this accumulation point is the analytic center of a subset of the optimal set and depends on the starting point of the infeasible interior-point method.     

一个新的求解二阶锥规划的非内部连续化算法

基于光滑Fischer-Burmeister函数,本文给出一个新的求解二阶锥规划的非内部连续化算法.算法对初始点的选取没有任何限制,并且在每一步迭代只需求解一个线性方程组并进行一次线性搜索.在不需要满足严格互补条件下,证明了算法是全局收敛且是局部超线性收敛的.数值试验表明算法是有效的.     

基于局部self-concordant障碍函数的全牛顿步多项式时间算法

由Nesterov和Nemirovski[4]创立的self-concordant障碍函数理论为解线性和凸优化问题提供了多项式时间内点算法.根据self-concordant障碍函数的参数,就可以分析内点算法的复杂性.在这篇文章中,我们介绍了基于核函数的局部self-concordant障碍函数,它在线性优化问题的中心路径及其邻域内满足self-concordant性质.通过求解此障碍函数的局部参数值,我们得到了求解线性规划问题的基于此局部Self-concordant障碍函数的纯牛顿步内点算法的理论迭代界.此迭代界与目前已知的最好的理论迭代界是一致的.     

二次锥规划的光滑牛顿法

在光滑Fischer-Burmeister函数的基础上,本文给出了二次锥规划的一种新的光滑牛顿法.该方法所采用的系统不是等价于中心路径条件,而是等价于最优性条件本身.算法对初始点没有任何限制,且具有Q-二阶收敛速度.     

一个求解半正定规划问题的新原始一对偶内点算法

在原始对偶内点算法的设计和分析中,障碍函数对算法的搜索方法和复杂性起着重要的作用。本文由核函数来确定障碍函数,设计了一个求解半正定规划问题的原始。对偶内点算法。这个障碍函数即可以定义算法新的搜索方向,又度量迭代点与中心路径的距离,同时对算法的复杂性分析起着关键的作用。我们计算了算法的迭代界,得出了关于大步校正法和小步校正法的迭代界,它们分别是O（√n log n log n/c）和O（√n log n/ε）,这里n是半正定规划问题的维数。最后,我们根据一个算例,说明了算法的有效性以及对核函数的参数的敏感性。     

A New Filled Function Method for Global Optimization

A novel filled function is suggested in this paper for identifying a global minimum point for a general class of nonlinear programming problems with a closed bounded domain. Theoretical and numerical properties of the proposed filled function are investigated and a solution algorithm is proposed. The implementation of the algorithm on several test problems is reported with satisfactory numerical results.     

Convergence Analysis of a Class of Penalty Methods for Vector Optimization Problems with Cone Constraints

In this paper, we consider convergence properties of a class of penalization methods for a general vector optimization problem with cone constraints in infinite dimensional spaces. Under certain assumptions, we show that any efficient point of the cone constrained vector optimization problem can be approached by a sequence of efficient points of the penalty problems. We also show, on the other hand, that any limit point of a sequence of approximate efficient solutions to the penalty problems is a weekly efficient solution of the original cone constrained vector optimization problem. Finally, when the constrained space is of finite dimension, we show that any limit point of a sequence of stationary points of the penalty problems is a KKT stationary point of the original cone constrained vector optimization problem if Mangasarian–Fromovitz constraint qualification holds at the limit point.This work is supported by the Postdoctoral Fellowship of Hong Kong Polytechnic University.     

A full-Newton step infeasible interior-point method for linear optimization based on a trigonometric kernel function

An infeasible interior-point method (IIPM) for solving linear optimization problems based on a kernel function with trigonometric barrier term is analysed. In each iteration, the algorithm involves a feasibility step and several centring steps. The centring step is based on classical Newton’s direction, while we used a kernel function with trigonometric barrier term in the algorithm to induce the feasibility step. The complexity result coincides with the best-known iteration bound for IIPMs. To our knowledge, this is the first full-Newton step IIPM based on a kernel function with trigonometric barrier term.