Simplified infeasible interior-point algorithm for SDO using full Nesterov-Todd step

Interior-point methods for semidefinite optimization problems have been studied frequently, due to their polynomial complexity and practical implications. In this paper we propose a primal-dual infeasible interior-point algorithm that uses full Nesterov-Todd (NT) steps with a different feasibility step. We obtain the currently best known iteration bound for semidefinite optimization problems.     

Full Nesterov-Todd step infeasible interior-point method for symmetric optimization

Euclidean Jordan algebras were proved more than a decade ago to be an indispensable tool in the unified study of interior-point methods. By using it, we generalize the full-Newton step infeasible interior-point method for linear optimization of Roos [Roos, C., 2006. A full-Newton step O(n) infeasible interior-point algorithm for linear optimization. SIAM Journal on Optimization. 16 (4), 1110-1136 (electronic)] to symmetric optimization. This unifies the analysis for linear, second-order cone and semidefinite optimizations.     

New complexity analysis of a full-Newton step feasible interior-point algorithm for $$P_*(\kappa )$$-LCP

In this paper, we consider a full-Newton step feasible interior-point algorithm for \(P_*(\kappa )\)-linear complementarity problem. The perturbed complementarity equation \(xs=\mu e\) is transformed by using a strictly increasing function, i.e., replacing \(xs=\mu e\) by \(\psi (xs)=\psi (\mu e)\) with \(\psi (t)=\sqrt{t}\), and the proposed interior-point algorithm is based on that algebraic equivalent transformation. Furthermore, we establish the currently best known iteration bound for \(P_*(\kappa )\)-linear complementarity problem, namely, \(O((1+4\kappa )\sqrt{n}\log \frac{n}{\varepsilon })\), which almost coincides with the bound derived for linear optimization, except that the iteration bound in the \(P_{*}(\kappa )\)-linear complementarity problem case is multiplied with the factor \((1+4\kappa )\).     

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.     

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.     

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.      

Simplified analysis for full-Newton step infeasible interior-point algorithm for semidefinite programming

We present an analysis of the full-Newton step infeasible interior-point algorithm for semidefinite optimization, which is an extension of the algorithm introduced by Roos [C. Roos, A full-Newton step 𝒪(n) infeasible interior-point algorithm for linear optimization, SIAM J. Optim. 16 (2006), pp. 1110–1136] for the linear optimization case. We use the proximity measure σ(V)?=?‖I???V ²‖ to overcome the difficulty of obtaining an upper bound of updated proximity after one full-Newton step, where I is an identity matrix and V is a symmetric positive definite matrix. It turns out that the complexity analysis of the algorithm is simplified and the iteration bound obtained is improved slightly.     

A full-Newton step infeasible interior-point algorithm for monotone LCP based on a locally-kernel function

We propose a new full-Newton step infeasible interior-point algorithm for monotone linear complementarity problems based on a simple locally-kernel function. The algorithm uses the simple locally-kernel function to determine the search directions and define the neighborhood of central path. Two types of full-Newton steps are used, feasibility step and centering step. The algorithm starts from strictly feasible iterates of a perturbed problem, on its central path, and feasibility steps find strictly feasible iterates for the next perturbed problem. By using centering steps for the new perturbed problem, we obtain strictly feasible iterates close enough to the central path of the new perturbed problem. The procedure is repeated until an ?-approximate solution is found. We analyze the algorithm and obtain the complexity bound, which coincides with the best-known result for monotone linear complementarity problems.     

A full-Newton step feasible interior-point algorithm for P_*(\kappa )-linear complementarity problems

In this paper, a full-Newton step feasible interior-point algorithm is proposed for solving $P_*(\kappa )$ -linear complementarity problems. We prove that the full-Newton step to the central path is local quadratically convergent and the proposed algorithm has polynomial iteration complexity, namely, $O\left( (1+4\kappa )\sqrt{n}\log {\frac{n}{\varepsilon }}\right) $ , which matches the currently best known iteration bound for $P_*(\kappa )$ -linear complementarity problems. Some preliminary numerical results are provided to demonstrate the computational performance of the proposed algorithm.     

半定规划的一个新的宽邻域非可行内点算法

基于一种新的宽邻域,提出一个求解半定规划的新的非可行内点算法．在适当的假设条件下,证明了该算法具有较好的迭代复杂界O（√nL）,优于目前此类算法的最好的复杂性O（n√nL）,等同于可行内点算法．     

Polynomial convergence of two higher order interior-point methods for $$P_*(\kappa )$$-LCP in a wide neighborhood of the central path

In this paper, we propose two interior-point methods for solving \(P_*(\kappa )\)-linear complementarity problems (\(P_*(\kappa )\)-LCPs): a high order large update path following method and a high order corrector–predictor method. Both algorithms generate sequences of iterates in the wide neighborhood \((\mathcal {N}_{2,\tau }^-(\alpha ))\) of the central path introduced by Ai and Zhang. The methods do not depend on the handicap \(\kappa \) of the problem so that they work for any \(P_*(\kappa )\)-LCP . They have \(O((1 +\kappa )\sqrt{n}L)\) iteration complexity, the best-known iteration complexity obtained so far by any interior-point method for solving \(P_*(\kappa )\)-LCP. The high order corrector–predictor algorithm is superlinearly convergent with Q-order \((m_p+1)\) for problems that admit a strict complementarity solution and \((m_p+1)/2\) for general problems, where \(m_p\) is the order of the predictor step.     

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.     

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.     

An infeasible interior-point arc-search algorithm for nonlinear constrained optimization

Numerical Algorithms - In this paper, we propose an infeasible arc-search interior-point algorithm for solving nonlinear programming problems. Most algorithms based on interior-point methods are...     

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

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

Two computationally efficient polynomial-iteration infeasible interior-point algorithms for linear programming

The present work considers the numerical solution of differential equations that are obtained by space discretization (method of lines) of parabolic evolution equations. Main emphasis is put on the presence of mixed derivatives in the elliptic operator. An extension of the alternating-direction-implicit (ADI) approach to this situation is presented. Our stability analysis is based on a scalar test equation that is relevant to the considered class of problems. The novel treatment of mixed derivatives is implemented in third-order W-methods. Numerical experiments and comparisons with standard methods show the efficiency of the new approach. An extension of our treatment of mixed derivatives to 3D and higher dimensional problems is outlined at the end of the article.