Long-step strategies in interior-point primal-dual methods

In this paper we analyze from a unique point of view the behavior of path-following and primal-dual potential reduction methods on nonlinear conic problems. We demonstrate that most interior-point methods with efficiency estimate can be considered as different strategies of minimizing aconvex primal-dual potential function in an extended primal-dual space. Their efficiency estimate is a direct consequence of large local norm of the gradient of the potential function along a central path. It is shown that the neighborhood of this path is a region of the fastest decrease of the potential. Therefore the long-step path-following methods are, in a sense, the best potential-reduction strategies. We present three examples of such long-step strategies. We prove also an efficiency estimate for a pure primal-dual potential reduction method, which can be considered as an implementation of apenalty strategy based on a functional proximity measure. Using the convex primal dual potential, we prove efficiency estimates for Karmarkar-type and Dikin-type methods as applied to a homogeneous reformulation of the initial primal-dual problem.     

Local Convergence of a Primal-Dual Method for Degenerate Nonlinear Programming

In recent work, the local convergence behavior of path-following interior-point methods and sequential quadratic programming methods for nonlinear programming has been investigated for the case in which the assumption of linear independence of the active constraint gradients at the solution is replaced by the weaker Mangasarian–Fromovitz constraint qualification. In this paper, we describe a stabilization of the primal-dual interior-point approach that ensures rapid local convergence under these conditions without enforcing the usual centrality condition associated with path-following methods. The stabilization takes the form of perturbations to the coefficient matrix in the step equations that vanish as the iterates converge to the solution.     

Parabolic target space and primal-dual interior-point methods

In this paper we develop new primal-dual interior-point methods for linear programming problems, which are based on the concept of parabolic target space. We show that such schemes work in the infinity-neighborhood of the primal-dual central path. Nevertheless, these methods possess the best known complexity estimate. We demonstrate that the adaptive-step path-following strategies can be naturally incorporated in such schemes.     

Existence, uniqueness, and convergence of the regularized primal-dual central path

In a recent work [J. Castro, J. Cuesta, Quadratic regularizations in an interior-point method for primal block-angular problems, Mathematical Programming, in press (doi:10.1007/s10107-010-0341-2)] the authors improved one of the most efficient interior-point approaches for some classes of block-angular problems. This was achieved by adding a quadratic regularization to the logarithmic barrier. This regularized barrier was shown to be self-concordant, thus fitting the general structural optimization interior-point framework. In practice, however, most codes implement primal-dual path-following algorithms. This short paper shows that the primal-dual regularized central path is well defined, i.e., it exists, it is unique, and it converges to a strictly complementary primal-dual solution.     

New Self-Concordant Barrier for the Hypercube

We introduce a new barrier function to build new interior-point algorithms to solve optimization problems with bounded variables. First, we show that this function is a (3/2)n-self-concordant barrier for the unitary hypercube [0,1] ⁿ , assuring thus the polynomial property of related algorithms. Second, using the Hessian metric of that barrier, we present new explicit algorithms from the point of view of Riemannian geometry applications. Third, we prove that the central path defined by the new barrier to solve a certain class of linearly constrained convex problems maintains most of the properties of the central path defined by the usual logarithmic barrier. We present also a primal long-step path-following algorithm with similar complexity to the classical barrier. Finally, we introduce a new proximal-point Bregman type algorithm to solve linear problems in [0,1] ⁿ and prove its convergence. P.R. Oliveira was partially supported by CNPq/Brazil.     

Convergence property of the Iri-Imai algorithm for some smooth convex programming problems

In this paper, the Iri-Imai algorithm for solving linear and convex quadratic programming is extended to solve some other smooth convex programming problems. The globally linear convergence rate of this extended algorithm is proved, under the condition that the objective and constraint functions satisfy a certain type of convexity, called the harmonic convexity in this paper. A characterization of this convexity condition is given. The same convexity condition was used by Mehrotra and Sun to prove the convergence of a path-following algorithm.The Iri-Imai algorithm is a natural generalization of the original Newton algorithm to constrained convex programming. Other known convergent interior-point algorithms for smooth convex programming are mainly based on the path-following approach.     

Path-following and augmented Lagrangian methods for contact problems in linear elasticity

A certain regularization technique for contact problems leads to a family of problems that can be solved efficiently using infinite-dimensional semismooth Newton methods, or in this case equivalently, primal–dual active set strategies. We present two procedures that use a sequence of regularized problems to obtain the solution of the original contact problem: first-order augmented Lagrangian, and path-following methods. The first strategy is based on a multiplier-update, while path-following with respect to the regularization parameter uses theoretical results about the path-value function to increase the regularization parameter appropriately. Comprehensive numerical tests investigate the performance of the proposed strategies for both a 2D as well as a 3D contact problem.     

Elliptic cone optimization and primal–dual path-following algorithms

In elliptic cone optimization problems, we minimize a linear objective function over the intersection of an affine linear manifold with the Cartesian product of the so-called elliptic cones. We present some general classes of optimization problems that can be cast as elliptic cone programmes such as second-order cone programmes and circular cone programmes. We also describe some real-world applications of this class of optimization problems. We study and analyse the Jordan algebraic structure of the elliptic cones. Then, we present a glimpse of the duality theory associated with elliptic cone optimization. A primal–dual path-following interior-point algorithm is derived for elliptic cone optimization problems. We prove the polynomial convergence of the proposed algorithms by showing that the logarithmic barrier is a strongly self-concordant barrier. The numerical examples show the path-following algorithms are efficient.     

High Order Long-Step Methods for Solving Linear Complementarity Problems

The paper is concerned with methods for solving linear complementarity problems (LCP) that are monotone or at least sufficient in the sense of Cottle, Pang and Venkateswaran (1989). A basic concept of interior-point-methods is the concept of (perhaps weighted) feasible or infeasible interior-point paths. They converge to a solution of the LCP if a natural path parameter, usually the current duality gap, tends to 0.After reviewing some basic analyticity properties of these paths it is shown how these properties can be used to devise also long-step path-following methods (and not only predictor–corrector type methods) for which the duality gap converges Q-superlinearly to 0 with an arbitrarily high order.     

Self-regular functions and new search directions for linear and semidefinite optimization

In this paper, we introduce the notion of a self-regular function. Such a function is strongly convex and smooth coercive on its domain, the positive real axis. We show that any such function induces a so-called self-regular proximity function and a corresponding search direction for primal-dual path-following interior-point methods (IPMs) for solving linear optimization (LO) problems. It is proved that the new large-update IPMs enjoy a polynomial ?(n log) iteration bound, where q≥1 is the so-called barrier degree of the kernel function underlying the algorithm. The constant hidden in the ?-symbol depends on q and the growth degree p≥1 of the kernel function. When choosing the kernel function appropriately the new large-update IPMs have a polynomial ?(lognlog) iteration bound, thus improving the currently best known bound for large-update methods by almost a factor . Our unified analysis provides also the ?(log) best known iteration bound of small-update IPMs. At each iteration, we need to solve only one linear system. An extension of the above results to semidefinite optimization (SDO) is also presented. Received: March 2000 / Accepted: December 2001?Published online April 12, 2002     

Proximal Methods in View of Interior-Point Strategies

This paper deals with regularized penalty-barrier methods for convex programming problems. In the spirit of an iterative proximal regularization approach, an interior-point method is constructed, in which at each step a strongly convex function has to be minimized and the prox-term can be scaled by a variable scaling factor. The convergence of the method is studied for an axiomatically given class of barrier functions. According to the results, a wide class of barrier functions (in particular, logarithmic and exponential functions) can be applied to design special algorithms. For the method with a logarithmic barrier, the rate of convergence is investigated and assumptions that ensure linear convergence are given.     

Parallel Interior Point Schemes for Solving Multistage Convex Programming

The predictor–corrector interior-point path-following algorithm is promising in solving multistage convex programming problems. Among many other general good features of this algorithm, especially attractive is that the algorithm allows possibility to parallelise the major computations. The dynamic structure of the multistage problems specifies a block-tridiagonal system at each Newton step of the algorithm. A wrap-around permutation is then used to implement the parallel computation for this step.     

An interior-point path-following algorithm for computing a Leontief economy equilibrium

In this paper, we present an interior-point path-following algorithm for computing a Leontief economy equilibrium, that is, an exchange market equilibrium with Leontief utility functions, which is known to be in the complexity class of PPAD-complete. It is known that an equilibrium corresponds to a solution of a system of complementarities, so we construct a smooth homotopy interior-point path to tackle this system. We prove that there always exists a continuously differentiable path leading to a complementary solution of the nonlinear system and at the same time to a Leontief economy equilibrium associated with the solution. We also report preliminary computational results to show effectiveness of the path-following Newton method.     

A wide neighborhood interior-point algorithm for linear optimization based on a specific kernel function

This paper presents an interior point algorithm for solving linear optimization problems in a wide neighborhood of the central path introduced by Ai and Zhang (SIAM J Optim 16:400–417, 2005). In each iteration, the algorithm computes the new search directions by using a specific kernel function. The convergence of the algorithm is shown and it is proved that the algorithm has the same iteration bound as the best short-step algorithms. We demonstrate the computational efficiency of the proposed algorithm by testing some Netlib problems in standard form. To best our knowledge, this is the first wide neighborhood path-following interior-point method with the same complexity as the best small neighborhood path-following interior-point methods that uses the kernel function.

     

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

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

Dual versus primal-dual interior-point methods for linear and conic programming

We observe a curious property of dual versus primal-dual path-following interior-point methods when applied to unbounded linear or conic programming problems in dual form. While primal-dual methods can be viewed as implicitly following a central path to detect primal infeasibility and dual unboundedness, dual methods can sometimes implicitly move away from the analytic center of the set of infeasibility/unboundedness detectors. Dedicated to Clovis Gonzaga on the occassion of his 60th birthday.     

Numerical Comparisons of Path-Following Strategies for a Primal-Dual Interior-Point Method for Nonlinear Programming

An important research activity in primal-dual interior-point methods for general nonlinear programming is to determine effective path-following strategies and their implementations. The objective of this work is to present numerical comparisons of several path-following strategies for the local interior-point Newton method given by El-Bakry, Tapia, Tsuchiya, and Zhang. We conduct numerical experimentation of nine strategies using two central regions, three notions of proximity measures, and three merit functions to obtain an optimal solution. Six of these strategies are implemented for the first time. The numerical results show that the best path-following strategy is that given by Argáez and Tapia.     

Interior-Point Algorithms,Penalty Methods and Equilibrium Problems

In this paper we consider the question of solving equilibrium problems—formulated as complementarity problems and, more generally, mathematical programs with equilibrium constraints (MPECs)—as nonlinear programs, using an interior-point approach. These problems pose theoretical difficulties for nonlinear solvers, including interior-point methods. We examine the use of penalty methods to get around these difficulties and provide substantial numerical results. We go on to show that penalty methods can resolve some problems that interior-point algorithms encounter in general. An erratum to this article is available at .     

An inexact interior point method for L 1-regularized sparse covariance selection

Sparse covariance selection problems can be formulated as log-determinant (log-det) semidefinite programming (SDP) problems with large numbers of linear constraints. Standard primal–dual interior-point methods that are based on solving the Schur complement equation would encounter severe computational bottlenecks if they are applied to solve these SDPs. In this paper, we consider a customized inexact primal–dual path-following interior-point algorithm for solving large scale log-det SDP problems arising from sparse covariance selection problems. Our inexact algorithm solves the large and ill-conditioned linear system of equations in each iteration by a preconditioned iterative solver. By exploiting the structures in sparse covariance selection problems, we are able to design highly effective preconditioners to efficiently solve the large and ill-conditioned linear systems. Numerical experiments on both synthetic and real covariance selection problems show that our algorithm is highly efficient and outperforms other existing algorithms.     

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.