“Cone-free” primal-dual path-following and potential-reduction polynomial time interior-point methods

We present a framework for designing and analyzing primal-dual interior-point methods for convex optimization. We assume that a self-concordant barrier for the convex domain of interest and the Legendre transformation of the barrier are both available to us. We directly apply the theory and techniques of interior-point methods to the given good formulation of the problem (as is, without a conic reformulation) using the very usual primal central path concept and a less usual version of a dual path concept. We show that many of the advantages of the primal-dual interior-point techniques are available to us in this framework and therefore, they are not intrinsically tied to the conic reformulation and the logarithmic homogeneity of the underlying barrier function.Part of the research was done while the author was a Visiting Professor at the University of Waterloo.Research of this author is supported in part by a PREA from Ontario and by a NSERC Discovery Grant. Tel: (519) 888-4567 ext.5598, Fax: (519) 725-5441Mathematics Subject Classification (2000): 90C51, 90C25, 65Y20,90C28, 49D49     

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.     

A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming

We present a unified analysis for a class of long-step primal-dual path-following algorithms for semidefinite programming whose search directions are obtained through linearization of the symmetrized equation of the central pathH _P (XS) [PXSP ^–1 + (PXSP ^–1) ^T ]/2 = I, introduced by Zhang. At an iterate (X,S), we choose a scaling matrixP from the class of nonsingular matricesP such thatPXSP ^–1 is symmetric. This class of matrices includes the three well-known choices, namely:P = S ^1/2 andP = X ^–1/2 proposed by Monteiro, and the matrixP corresponding to the Nesterov—Todd direction. We show that within the class of algorithms studied in this paper, the one based on the Nesterov—Todd direction has the lowest possible iteration-complexity bound that can provably be derived from our analysis. More specifically, its iteration-complexity bound is of the same order as that of the corresponding long-step primal-dual path-following algorithm for linear programming introduced by Kojima, Mizuno and Yoshise. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.This author's research is supported in part by the National Science Foundation under grants INT-9600343 and CCR-9700448 and the Office of Naval Research under grant N00014-94-1-0340.This author's research was supported in part by DOE DE-FG02-93ER25171-A001.     

Exploiting sparsity in primal-dual interior-point methods for semidefinite programming

The Helmberg-Rendl-Vanderbei-Wolkowicz/Kojima-Shindoh-Hara/Monteiro and Nesterov-Todd search directions have been used in many primal-dual interior-point methods for semidefinite programs. This paper proposes an efficient method for computing the two directions when the semidefinite program to be solved is large scale and sparse.     

Implementation of warm-start strategies in interior-point methods for linear programming in fixed dimension

We implement several warm-start strategies in interior-point methods for linear programming (LP). We study the situation in which both the original LP instance and the perturbed one have exactly the same dimensions. We consider different types of perturbations of data components of the original instance and different sizes of each type of perturbation. We modify the state-of-the-art interior-point solver PCx in our implementation. We evaluate the effectiveness of each warm-start strategy based on the number of iterations and the computation time in comparison with “cold start” on the NETLIB test suite. Our experiments reveal that each of the warm-start strategies leads to a reduction in the number of interior-point iterations especially for smaller perturbations and for perturbations of fewer data components in comparison with cold start. On the other hand, only one of the warm-start strategies exhibits better performance than cold start in terms of computation time. Based on the insight gained from the computational results, we discuss several potential improvements to enhance the performances of such warm-start strategies. This research was supported in part by NSF through CAREER grant DMI-0237415.     

Local analysis of the feasible primal-dual interior-point method

In this paper we analyze the rate of local convergence of the Newton primal-dual interior-point method when the iterates are kept strictly feasible with respect to the inequality constraints. It is shown under the classical conditions that the rate is q-quadratic when the functions associated to the binding inequality constraints are concave. In general, the q-quadratic rate is achieved provided the step in the primal variables does not become asymptotically orthogonal to any of the gradients of the binding inequality constraints.     

Quadratic interior-point methods in statistical disclosure control

The safe dissemination of statistical tabular data is one of the main concerns of National Statistical Institutes (NSIs). Although each cell of the tables is made up of the aggregated information of several individuals, the statistical confidentiality can be violated. NSIs must guarantee that no individual information can be derived from the released tables. One widely used type of methods to reduce the disclosure risk is based on the perturbation of the cell values. We consider a new controlled perturbation method which, given a set of tables to be protected, finds the closest safe ones - thus reducing the information loss while preserving confidentiality. This approach means solving a quadratic optimization problem with a much larger number of variables than constraints. Real instances can provide problems with millions of variables. We show that interior-point methods are an effective choice for that model, and, also, that specialized algorithms which exploit the problem structure can be faster than state-of-the art general solvers. Computational results are presented for instances of up to 1000000 variables.AMS Subject Classification: 90C06, 90C20, 90C51, 90C90Jordi Castro: Partially supported by the EU IST-2000-25069 CASC project and by the Spanish MCyT project TIC2003-00997.     

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.     

On self-concordant barrier functions for conic hulls and fractional programming

Given a self-concordant barrier function for a convex set , we determine a self-concordant barrier function for the conic hull of . As our main result, we derive an “optimal” barrier for based on the barrier function for . Important applications of this result include the conic reformulation of a convex problem, and the solution of fractional programs by interior-point methods. The problem of minimizing a convex-concave fraction over some convex set can be solved by applying an interior-point method directly to the original nonconvex problem, or by applying an interior-point method to an equivalent convex reformulation of the original problem. Our main result allows to analyze the second approach showing that the rate of convergence is of the same order in both cases.     

Potential-reduction methods in mathematical programming

We provide a survey of interior-point methods for linear programming and its extensions that are based on reducing a suitable potential function at each iteration. We give a fairly complete overview of potential-reduction methods for linear programming, focusing on the possibility of taking long steps and the properties of the barrier function that are necessary for the analysis. We then describe briefly how the methods and results can be extended to certain convex programming problems, following the approach of Nesterov and Todd. We conclude with some open problems. Research supported in part by NSF, AFOSR and ONR through NSF Grant DMS-8920550. Some of this work was done while the author was on a sabbatical leave from Cornell University visiting the Department of Mathematics at the University of Washington.     

General primal-dual penalty/barrier path-following Newton methods for nonlinear programming

In the present article rather general penalty/barrier-methods are considered, that define a local continuously differentiable primal-dual path. The class of penalty/barrier terms includes most of the usual techniques like logarithmic barriers, SUMT, quadratic loss functions as well as exponential penalties, and the optimization problem which may contain inequality as well as equality constraints. The convergence of the corresponding general primal-dual path-following method is shown for local minima that satisfy strong second-order sufficiency conditions with linear independence constraint qualification (LICQ) and strict complementarity. A basic tool in the analysis of these methods is to estimate the radius of convergence of Newton's method depending on the penalty/barrier-parameter. Without using self-concordance properties convergence bounds are derived by direct estimations of the solutions of the Newton equations. Parameter selection rules are proposed which guarantee the local convergence of the considered penalty/barrier-techniques with only a finite number of Newton steps at each parameter level. Numerical examples illustrate the practical behavior of the proposed class of methods.     

Long-step primal-dual target-following algorithms for linear programming

In this paper we propose a long-step target-following methodology for linear programming. This is a general framework, that enables us to analyze various long-step primal-dual algorithms in the literature in a short and uniform way. Among these are long-step central and weighted path-following methods and algorithms to compute a central point or a weighted center. Moreover, we use it to analyze a method with the property that starting from an initial noncentral point, generates iterates that simultaneously get closer to optimality and closer to centrality.This work is completed with the support of a research grant from SHELL.The first author is supported by the Dutch Organization for Scientific Research (NWO), grant 611-304-028.The fourth author is supported by the Swiss National Foundation for Scientific Research, grant 12-34002.92.     

On the convergence of primal-dual interior-point methods with wide neighborhoods

We study primal-dual interior-point methods for linear programs. After proposing a new primaldual potential function we describe a new potential reduction algorithm. We make connections between the new potential function and primal-dual interior-point algorithms with wide neighborhoods. Then we describe an algorithm that is a slightly modified version of existing primal-dual algorithms using wide neighborhoods. Assuming the optimal solution is non-degenerate, the algorithm is 1-step Q-quadratically convergent. We also study the degenerate case and show that the neighborhoods of the central path stay large as the iterates approach the optimal solutions.Research performed while the author was a Ph.D. student at Cornell University and was supported in part by the United States Army Research Office through the Army Center of Excellence for Symbolic Methods in Algorithmic Mathematics (ACSyAM), Mathematical Sciences Institute of Cornell University, Contract DAAL03-91-C-0027 and also by NSF, AFOSR and ONR through NSF Grant DMS-8920550.     

An exact primal–dual penalty method approach to warmstarting interior-point methods for linear programming

One perceived deficiency of interior-point methods in comparison to active set methods is their inability to efficiently re-optimize by solving closely related problems after a warmstart. In this paper, we investigate the use of a primal–dual penalty approach to overcome this problem. We prove exactness and convergence and show encouraging numerical results on a set of linear and mixed integer programming problems. Research of the first author is sponsored by ONR grant N00014-04-1-0145. Research of the second author is supported by NSF grant DMS-0107450.     

A primal-dual interior-point algorithm for quadratic programming

In this paper we propose a primal-dual interior-point method for large, sparse, quadratic programming problems. The method is based on a reduction presented by Gonzalez-Lima, Wei, and Wolkowicz [14] in order to solve the linear systems arising in the primal-dual methods for linear programming. The main features of this reduction is that it is well defined at the solution set and it preserves sparsity. These properties add robustness and stability to the algorithm and very accurate solutions can be obtained. We describe the method and we consider different reductions using the same framework. We discuss the relationship of our proposals and the one used in the LOQO code. We compare and study the different approaches by performing numerical experimentation using problems from the Maros and Meszaros collection. We also include a brief discussion on the meaning and effect of ill-conditioning when solving linear systems.This work was partially supported by DID-USB (GID-001).     

Interior-point methods for nonconvex nonlinear programming: regularization and warmstarts

In this paper, we investigate the use of an exact primal-dual penalty approach within the framework of an interior-point method for nonconvex nonlinear programming. This approach provides regularization and relaxation, which can aid in solving ill-behaved problems and in warmstarting the algorithm. We present details of our implementation within the loqo algorithm and provide extensive numerical results on the CUTEr test set and on warmstarting in the context of quadratic, nonlinear, mixed integer nonlinear, and goal programming. Research of the first author is sponsored by ONR grant N00014-04-1-0145. Research of the second author is supported by NSF grant DMS-0107450.     

Primal Central Paths and Riemannian Distances for Convex Sets

In this paper, we study the Riemannian length of the primal central path in a convex set computed with respect to the local metric defined by a self-concordant function. Despite some negative examples, in many important situations, the length of this path is quite close to the length of a geodesic curve. We show that in the case of a bounded convex set endowed with a ν-self-concordant barrier, the length of the central path is within a factor O(ν ^1/4) of the length of the shortest geodesic curve. This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister’s Office, Science Policy Programming.     

A new primal-dual path-following interior-point algorithm for semidefinite optimization

In this paper we present a new primal-dual path-following interior-point algorithm for semidefinite optimization. The algorithm is based on a new technique for finding the search direction and the strategy of the central path. At each iteration, we use only full Nesterov-Todd step. Moreover, we obtain the currently best known iteration bound for the algorithm with small-update method, namely, , which is as good as the linear analogue.     

Newton-KKT interior-point methods for indefinite quadratic programming

Two interior-point algorithms are proposed and analyzed, for the (local) solution of (possibly) indefinite quadratic programming problems. They are of the Newton-KKT variety in that (much like in the case of primal-dual algorithms for linear programming) search directions for the “primal” variables and the Karush-Kuhn-Tucker (KKT) multiplier estimates are components of the Newton (or quasi-Newton) direction for the solution of the equalities in the first-order KKT conditions of optimality or a perturbed version of these conditions. Our algorithms are adapted from previously proposed algorithms for convex quadratic programming and general nonlinear programming. First, inspired by recent work by P. Tseng based on a “primal” affine-scaling algorithm (à la Dikin) [J. of Global Optimization, 30 (2004), no. 2, 285–300], we consider a simple Newton-KKT affine-scaling algorithm. Then, a “barrier” version of the same algorithm is considered, which reduces to the affine-scaling version when the barrier parameter is set to zero at every iteration, rather than to the prescribed value. Global and local quadratic convergence are proved under nondegeneracy assumptions for both algorithms. Numerical results on randomly generated problems suggest that the proposed algorithms may be of great practical interest. The work of the first author was supported in part by the School of Computational Science of Florida State University through a postdoctoral fellowship. Part of this work was done while this author was a Research Fellow with the Belgian National Fund for Scientific Research (Aspirant du F.N.R.S.) at the University of Liège. The work of the second author was supported in part by the National Science Foundation under Grants DMI9813057 and DMI-0422931 and by the US Department of Energy under Grant DEFG0204ER25655. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the National Science Foundation or those of the US Department of Energy.