A new infeasible interior-point method based on Darvay’s technique for symmetric optimization

We present a full Nesterov and Todd step primal-dual infeasible interior-point algorithm for symmetric optimization based on Darvay’s technique by using Euclidean Jordan algebras. The search 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. The feasibility steps find strictly feasible iterates for the next perturbed pair. By using centering steps for the new perturbed pair, we obtain strictly feasible iterates close to the central path of the new perturbed pair. The algorithm finds an ?-optimal solution or detects infeasibility of the given problem. Moreover, we derive the currently best known iteration bound for infeasible interior-point methods.     

An infeasible interior-point algorithm based on modified Nesterov and Todd directions for symmetric linear complementarity problem

We present an infeasible interior-point algorithm for symmetric linear complementarity problem based on modified Nesterov–Todd directions by using Euclidean Jordan algebras. The algorithm decreases the duality gap and the feasibility residual at the same rate. In this algorithm, we construct strictly feasible iterates for a sequence of perturbations of the given problem. Each main iteration of the algorithm consists of a feasibility step and a number of centring steps. The starting point in the first iteration is strictly feasible for a perturbed problem. The feasibility steps lead to a strictly feasible iterate for the next perturbed problem. By using centring steps for the new perturbed problem, a strictly feasible iterate is obtained to be close to the central path of the new perturbed problem. Furthermore, giving a complexity analysis of the algorithm, we derive the currently best-known iteration bound for infeasible interior-point methods.     

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.     

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 new full-Newton step <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis>) infeasible interior-point algorithm for semidefinite optimization

Interior-point methods for semidefinite optimization have been studied intensively, due to their polynomial complexity and practical efficiency. Recently, the second author designed a primal-dual infeasible interior-point algorithm with the currently best iteration bound for linear optimization problems. Since the algorithm uses only full Newton steps, it has the advantage that no line-searches are needed. In this paper we extend the algorithm to semidefinite optimization. The algorithm constructs strictly feasible iterates for a sequence of perturbations of the given problem and its dual problem, close to their central paths. Two types of full-Newton steps are used, feasibility steps and (ordinary) centering steps, respectively. The algorithm starts from strictly feasible iterates of a perturbed pair, on its central path, and feasibility steps find strictly feasible iterates for the next perturbed pair. By using centering steps for the new perturbed pair, we obtain strictly feasible iterates close enough to the central path of the new perturbed pair. The starting point depends on a positive number ζ. The algorithm terminates either by finding an ε-solution or by detecting that the primal-dual problem pair has no optimal solution (X ^*,y ^*,S ^*) with vanishing duality gap such that the eigenvalues of X ^* and S ^* do not exceed ζ. The iteration bound coincides with the currently best iteration bound for semidefinite optimization problems.     

Improved Full-Newton Step <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">nL</Emphasis>) Infeasible Interior-Point Method for Linear Optimization

We present several improvements of the full-Newton step infeasible interior-point method for linear optimization introduced by Roos (SIAM J. Optim. 16(4):1110–1136, 2006). Each main step of the method consists of a feasibility step and several centering steps. We use a more natural feasibility step, which targets the μ ⁺-center of the next pair of perturbed problems. As for the centering steps, we apply a sharper quadratic convergence result, which leads to a slightly wider neighborhood for the feasibility steps. Moreover, the analysis is much simplified and the iteration bound is slightly better.     

A full step infeasible interior-point method for Cartesian $$P_{*}(\kappa )$$-SCLCP

In this paper, a new full Nesterov–Todd step infeasible interior-point method for Cartesian \(P_*(\kappa )\) linear complementarity problem over symmetric cone is considered. Our algorithm starts from a strictly feasible point of a perturbed problem, after a full Nesterov–Todd step for the new perturbed problem the obtained strictly feasible iterate is close to the central path of it, where closeness is measured by some merit function. Furthermore, the complexity bound of the algorithm is the best available for infeasible interior-point methods.     

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.     

On the Rate of Local Convergence of High-Order-Infeasible-Path-Following Algorithms for P*-Linear Complementarity Problems

A simple and unified analysis is provided on the rate of local convergence for a class of high-order-infeasible-path-following algorithms for the P_*-linear complementarity problem (P_*-LCP). It is shown that the rate of local convergence of a -order algorithm with a centering step is + 1 if there is a strictly complementary solution and ( + 1)/2 otherwise. For the -order algorithm without the centering step the corresponding rates are and /2, respectively. The algorithm without a centering step does not follow the fixed traditional central path. Instead, at each iteration, it follows a new analytic path connecting the current iterate with an optimal solution to generate the next iterate. An advantage of this algorithm is that it does not restrict iterates in a sequence of contracting neighborhoods of the central path.     

A primal-dual large-update interior-point algorithm for <Emphasis Type="Italic">P</Emphasis><Subscript>*</Subscript>(<Emphasis Type="Italic">κ</Emphasis>)-LCP based on a new class of kernel functions

In this paper, we propose a large-update primal-dual interior point algorithm for P_*(κ)-linear complementarity problem. The method is based on a new class of kernel functions which is neither classical logarithmic function nor self-regular functions. It is determines both search directions and the proximity measure between the iterate and the center path. We show that if a strictly feasible starting point is available, then the new algorithm has \(o\left( {(1 + 2k)p\sqrt n {{\left( {\frac{1}{p}\log n + 1} \right)}^2}\log \frac{n}{\varepsilon }} \right)\)iteration complexity which becomes \(o\left( {(1 + 2k)\sqrt n log{\kern 1pt} {\kern 1pt} n\log \frac{n}{\varepsilon }} \right)\)with special choice of the parameter p. It is matches the currently best known iteration bound for P_*(κ)-linear complementarity problem. Some computational results have been provided.     

A trust region affine scaling method for bound constrained optimization

We study a new trust region affine scaling method for general bound constrained optimization problems. At each iteration, we compute two trial steps. We compute one along some direction obtained by solving an appropriate quadratic model in an ellipsoidal region. This region is defined by an affine scaling technique. It depends on both the distances of current iterate to boundaries and the trust region radius. For convergence and avoiding iterations trapped around nonstationary points, an auxiliary step is defined along some newly defined approximate projected gradient. By choosing the one which achieves more reduction of the quadratic model from the two above steps as the trial step to generate next iterate, we prove that the iterates generated by the new algorithm are not bounded away from stationary points. And also assuming that the second-order sufficient condition holds at some nondegenerate stationary point, we prove the Q-linear convergence of the objective function values. Preliminary numerical experience for problems with bound constraints from the CUTEr collection is also reported.     

线性权互补问题的新全牛顿步可行内点算法

基于一个连续可微函数,通过等价变换中心路径,给出求解线性权互补问题的一个新全牛顿步可行内点算法.该算法每步迭代只需求解一个线性方程组,且不需要进行线搜索.通过适当选取参数,分析了迭代点的严格可行性,并证明算法具有线性优化最好的多项式时间迭代复杂度.数值结果验证了算法的有效性.     

Infeasible interior-point method for symmetric optimization using a positive-asymptotic barrier

We propose a new primal-dual infeasible interior-point method for symmetric optimization by using Euclidean Jordan algebras. Different kinds of interior-point methods can be obtained by using search directions based on kernel functions. Some search directions can be also determined by applying an algebraic equivalent transformation on the centering equation of the central path. Using this method we introduce a new search direction, which can not be derived from a usual kernel function. For this reason, we use the new notion of positive-asymptotic kernel function which induces the class of corresponding barriers. In general, the main iterations of the infeasible interior-point methods are composed of one feasibility and several centering steps. We prove that in our algorithm it is enough to take only one centering step in a main iteration in order to obtain a well-defined algorithm. Moreover, we conclude that the algorithm finds solution in polynomial time and has the same complexity as the currently best known infeasible interior-point methods. Finally, we give some numerical results.     

Postponing the choice of the barrier parameter in Mehrotra-type predictor–corrector algorithms

Recently Salahi et al. have considered a variant of Mehrotra’s celebrated predictor–corrector algorithm. By a numerical example they showed that this variant might make very small steps in order to keep the iterate in a certain neighborhood of the central path, that itself implies the inefficiency of the algorithm. This observation motivated them to incorporate a safeguard in their algorithmic scheme that gives a lower bound for the step size at each iteration and thus imply polynomial iteration complexity. In this paper we propose a different approach that enables us to have control on the iterates.     

A Solver for large-scale indefinite quadratic programs

Based on an active set strategy, a method for solving linearly constrained indefinite quadratic programs to solve the corresponding system of equations at each iteration is presented. The algorithm takes two descent directions to strictly decrease the value of objective function and obtains a suitable step to maintain feasibility. Computational results on a range of quadratic test problems are given.     

水平线性互补问题的广义中心路径跟踪算法

对水平线性互补问题提出了一种广义中心路径跟踪算法.任意的原始-对偶可行内点均可作为算法的初始点.每步迭代选择“仿射步”与“中心步”的凸组合为新的迭代方向,采用使对偶间隙尽可能减小的最大步长.算法的迭代复杂性为O(√nL).     

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 )\).     

A predictor-corrector algorithm for linear optimization based on a modified Newton direction

We present a predictor-corrector algorithm for linear optimization based on a modified Newton direction. In each main iteration, the algorithm operates two kinds of steps: a modified Newton step and a damped predictor step. The modified Newton step is generated from an equivalent reformulation of the centering equation from the system, which defines the central path, and move in the direction of a small neighborhood of the central path. While the damped predictor step is used to move in the direction of optimal solution and reduce the duality gap. The procedure is repeated until an ?-approximate solution is found. We derive the complexity for the algorithm, and obtain the best-known result for linear optimization.     

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.