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.     

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.      

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.     

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.     

An O（rL） Infeasible Interior-point Algorithm for Symmetric Cone LCP via CHKS Function

In this paper, we propose a theoretical framework of an infeasible interior-point algorithm for solving monotone linear cornplementarity problems over symmetric cones （SCLCP）. The new algorithm gets Newton-like directions from the Chen-Harker-Kanzow-Smale （CHKS） smoothing equation of the SCLCP. It possesses the following features： The starting point is easily chosen; one approximate Newton step is computed and accepted at each iteration; the iterative point with unit stepsize automatically remains in the neighborhood of central path; the iterative sequence is bounded and possesses （9（rL） polynomial-time complexity under the monotonicity and solvability of the SCLCP.     

An Infeasible Mizuno–Todd–Ye Type Algorithm for Convex Quadratic Programming with Polynomial Complexity

Infeasible interior point methods have been very popular and effective. In this paper, we propose a predictor–corrector infeasible interior point algorithm for convex quadratic programming, and we prove its convergence and analyze its complexity. The algorithm has the polynomial numerical complexity with O(nL)-iteration.     

Simplified infeasible interior-point algorithm for linear optimization based on a simple function

Based on a similar kernel function, we present an infeasible version of the interior-point algorithm for linear optimization introduced by Wang et al. (2016). The property of exponential convexity is still important to simplify the analysis of the algorithm. The iteration bound coincides with the currently best iteration bound for infeasible interior-point algorithms.     

Complexity of convex optimization using geometry-based measures and a reference point

Our concern lies in solving the following convex optimization problem:where P is a closed convex subset of the n-dimensional vector space X. We bound the complexity of computing an almost-optimal solution of G_P in terms of natural geometry-based measures of the feasible region and the level-set of almost-optimal solutions, relative to a given reference point x^r that might be close to the feasible region and / or the almost-optimal level set. This contrasts with other complexity bounds for convex optimization that rely on data-based condition numbers or algebraic measures, and that do not take into account any a priori reference point information. Mathematics Subject Classification (2000):90C, 90C05, 90C60This research has been partially supported through the Singapore-MIT Alliance. Portions of this research were undertaken when the author was a Visiting Scientist at Delft University of Technology.Received: 1, October 2001     

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

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

A new kernel function yielding the best known iteration bounds for primal-dual interior-point algorithms

Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm for solving linear optimization problems. In this paper we present a new kernel function which yields an algorithm with the best known complexity bound for both large- and small-update methods.     

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 primal-dual interior-point algorithm for symmetric optimization based on a new method for finding search directions

We introduce an interior-point method for symmetric optimization based on a new method for determining search directions. In order to accomplish this, we use a new equivalent algebraic transformation on the centring equation of the system which characterizes the central path. In this way, we obtain a new class of directions. We analyse a special case of this class, which leads to the new interior-point algorithm mentioned before. Another way to find the search directions is using barriers derived from kernel functions. We show that in our case the corresponding direction cannot be deduced from a usual kernel function. In spite of this fact, we prove the polynomial complexity of the proposed algorithm.     

A primal-dual interior-point algorithm for second-order cone optimization with full Nesterov–Todd step

In this paper we propose a primal-dual path-following interior-point algorithm for second-order cone optimization. The algorithm is based on a new technique for finding the search directions and the strategy of the central path. At each iteration, we use only full Nesterov–Todd step. Moreover, we derive the currently best known iteration bound for the algorithm with small-update method, namely, , where N denotes the number of second-order cones in the problem formulation and ε the desired accuracy.     

A large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function

In this paper, we present a large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function. The proposed function is strongly convex. It is not self-regular function and also the usual logarithmic function. The goal of this paper is to investigate such a kernel function and show that the algorithm has favorable complexity bound in terms of the elegant analytic properties of the kernel function. The complexity bound is shown to be $O\left( {\sqrt n \left( {\log n} \right)^2 \log \frac{n} {\varepsilon }} \right)$ . This bound is better than that by the classical primal-dual interior-point methods based on logarithmic barrier function and recent kernel functions introduced by some authors in optimization fields. Some computational results have been provided.