Product-form Cholesky factorization in interior point methods for second-order cone programming

Second-order cone programming (SOCP) problems are typically solved by interior point methods. As in linear programming (LP), interior point methods can, in theory, solve SOCPs in polynomial time and can, in practice, exploit sparsity in the problem data. Specifically, when cones of large dimension are present, the density that results in the normal equations that are solved at each iteration can be remedied in a manner similar to the treatment of dense columns in an LP. Here we propose a product-form Cholesky factorization (PFCF) approach, and show that it is more numerically stable than the alternative Sherman-Morrison-Woodbury approach. We derive several PFCF variants and compare their theoretical perfomance. Finally, we prove that the elements of L in the Cholesky factorizations LDL^T that arise in interior point methods for SOCP are uniformly bounded as the duality gap tends to zero as long as the iterates remain is some conic neighborhood of the cental path.Mathematics Subject Classification (1991): 90C25, 90C51, 15A23Research supported in part by NSF Grants CDA 97-26385, DMS 01-04282, ONR Grant N000140310514 and DOE Grant GE-FG01-92ER-25126     

Regularization techniques in interior point methods

Regularization techniques, i.e., modifications on the diagonal elements of the scaling matrix, are considered to be important methods in interior point implementations. So far, regularization in interior point methods has been described for linear programming problems, in which case the scaling matrix is diagonal. It was shown that by regularization, free variables can be handled in a numerically stable way by avoiding column splitting that makes the set of optimal solutions unbounded. Regularization also proved to be efficient for increasing the numerical stability of the computations during the solutions of ill-posed linear programming problems. In this paper, we study the factorization of the augmented system arising in interior point methods. In our investigation, we generalize the methods developed and used in linear programming to the case when the scaling matrix is positive semidefinite, but not diagonal. We show that regularization techniques may be applied beyond the linear programming case.     

对称锥规划的邻域跟踪算法

本文把艾文宝的邻域跟踪算法推广到对称锥规划, 定义中心路径的宽邻域N(τ, β), 并证明该邻域的一个重要性质, 该性质在算法的复杂性分析中起到关键作用. 取宽邻域N(τ, β) 中一点为初始点并采用Nesterov-Todd (NT) 搜索方向, 则该算法的迭代复杂界为O(√r logε^-1), 其中, r是EuclidJordan 代数的秩, ε是允许误差. 这是对称锥规划的宽邻域内点算法最好的复杂界.     

Extension of primal-dual interior point methods to diff-convex problems on symmetric cones

We consider the extension of primal dual interior point methods for linear programming on symmetric cones, to a wider class of problems that includes approximate necessary optimality conditions for functions expressible as the difference of two convex functions of a special form. Our analysis applies the Jordan-algebraic approach to symmetric cones. As the basic method is local, we apply the idea of the filter method for a globalization strategy.     

Efficient solution of two-stage stochastic linear programs using interior point methods

Solving deterministic equivalent formulations of two-stage stochastic linear programs using interior point methods may be computationally difficult due to the need to factorize quite dense search direction matrices (e.g., AA ^T ). Several methods for improving the algorithmic efficiency of interior point algorithms by reducing the density of these matrices have been proposed in the literature. Reformulating the program decreases the effort required to find a search direction, but at the expense of increased problem size. Using transpose product formulations (e.g., A ^T A) works well but is highly problem dependent. Schur complements may require solutions with potentially near singular matrices. Explicit factorizations of the search direction matrices eliminate these problems while only requiring the solution to several small, independent linear systems. These systems may be distributed across multiple processors. Computational experience with these methods suggests that substantial performance improvements are possible with each method and that, generally, explicit factorizations require the least computational effort.     

Symmetric indefinite systems for interior point methods

We present a unified framework for solving linear and convex quadratic programs via interior point methods. At each iteration, this method solves an indefinite system whose matrix is instead of reducing to obtain the usualAD ² A ^T system. This methodology affords two advantages: (1) it avoids the fill created by explicitly forming the productAD ² A ^T whenA has dense columns; and (2) it can easily be used to solve nonseparable quadratic programs since it requires only thatD be symmetric. We also present a procedure for converting nonseparable quadratic programs to separable ones which yields computational savings when the matrix of quadratic coefficients is dense.     

A primal projective interior point method for linear programming

We present a new projective interior point method for linear programming with unknown optimal value. This algorithm requires only that an interior feasible point be provided. It generates a strictly decreasing sequence of objective values and within polynomial time, either determines an optimal solution, or proves that the problem is unbounded. We also analyze the asymptotic convergence rate of our method and discuss its relationship to other polynomial time projective interior point methods and the affine scaling method.This research was supported in part by NSF Grants DMS-85-12277 and CDR-84-21402 and ONR Contract N00014-87-K0214.     

A projection and contraction method for symmetric cone complementarity problem

ABSTRACT

This paper considers the symmetric cone complementarity problem. A new projection and contraction method is presented which only requires some projection calculations and functional computations. It is proved that the iteration sequence produced by the proposed method converges to a solution of the symmetric cone complementarity problem under the condition that the underlying transformation is monotone. Numerical experiments also show the effectiveness of this method.     

Direct solution of the normal equations in interior point methods for convex transportation problems

Recent research has shown that very large convex transportation problems can be solved efficiently with interior point methods by finding a good pre-conditioner for an iterative linear-equation solver. In this article, it is demonstrated that the specific structure of the constraints allows use of a direct method for solving those linear equations with the same order of worst-case time complexity.     

Inner solvers for interior point methods for large scale nonlinear programming

This paper deals with the solution of nonlinear programming problems arising from elliptic control problems by an interior point scheme. At each step of the scheme, we have to solve a large scale symmetric and indefinite system; inner iterative solvers, with an adaptive stopping rule, can be used in order to avoid unnecessary inner iterations, especially when the current outer iterate is far from the solution. In this work, we analyse the method of multipliers and the preconditioned conjugate gradient method as inner solvers for interior point schemes. We discuss the convergence of the whole approach, the implementation details and report the results of numerical experimentation on a set of large scale test problems arising from the discretization of elliptic control problems. A comparison with other interior point codes is also reported. This research was supported by the Italian Ministry for Education, University and Research (MIUR) projects: FIRB Project: “Parallel Nonlinear Numerical Optimization PN ² O” (grant n. RBAU01JYPN, ) and COFIN/PRIN04 Project “Numerical Methods and Mathematical Software for Applications” (grant n. 2004012559, ).     

On the coerciveness of some merit functions for complementarity problems over symmetric cones

One of the popular solution methods for the complementarity problem over symmetric cones is to reformulate it as the global minimization of a certain merit function. An important question to be answered for this class of methods is under what conditions the level sets of the merit function are bounded (the coerciveness of the merit function). In this paper, we introduce the generalized weak-coerciveness of a continuous transformation. Under this condition, we prove the coerciveness of some merit functions, such as the natural residual function, the normal map, and the Fukushima-Yamashita function for complementarity problems over symmetric cones. We note that this is a much milder condition than strong monotonicity, used in the current literature.     

A new efficient short-step projective interior point method for linear programming

In this paper, we are interested in the performance of Karmarkar’s projective algorithm for linear programming. We propose a new displacement step to accelerate and improve the convergence of this algorithm. This purpose is confirmed by numerical experimentations showing the efficiency and the robustness of the obtained algorithm over Schrijver’s one for small problem dimensions.     

Improving the rate of convergence of interior point methods for linear programming

This paper proposes a procedure for improving the rate of convergence of interior point methods for linear programming. If (x ^k ) is the sequence generated by an interior point method, the procedure derives an auxiliary sequence ( ). Under the suitable assumptions it is shown that the sequence ( ) converges superlinearly faster to the solution than (x ^k ). Application of the procedure to the projective and afflne scaling algorithms is discussed and some computational illustration is provided.     

An interior point method, based on rank-1 updates, for linear programming

We propose a polynomial time primal—dual potential reduction algorithm for linear programming. The algorithm generates sequencesd ^k andv ^k rather than a primal—dual interior point (x ^k ,s ^k ), where and fori = 1, 2,,n. Only one element ofd ^k is changed in each iteration, so that the work per iteration is bounded by O(mn) using rank-1 updating techniques. The usual primal—dual iteratesx ^k ands ^k are not needed explicitly in the algorithm, whereasd ^k andv ^k are iterated so that the interior primal—dual solutions can always be recovered by aforementioned relations between (x ^k, s^k) and (d ^k, v^k) with improving primal—dual potential function values. Moreover, no approximation ofd ^k is needed in the computation of projection directions. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

An adaptation of the dual-affine interior point method for the surface flatness problem

This paper presents an adaptation of the dual-affine interior point method for the surface flatness problem. In order to determine how flat a surface is, one should find two parallel planes so that the surface is between them and they are as close together as possible. This problem is equivalent to the problem of solving inconsistent linear systems in terms of Tchebyshev’s norm. An algorithm is proposed and results are presented and compared with others published in the literature.     

A weighted least squaes study of robustness in interior point linear programming

This paper studies the robustness of interior point linear programming algorthims with respect to initial iterates that are too close to the boundary. Weighted least squares analysis is used in studying the near-boundary behavior of the affine scaling and Newton centering directions, which are often combined by interior point methods. This analysis leads to the develoment of a modified Newton centering direction exhibiting better near-boundary behavior than the two directions. Theoretical and computational results from the NETLIB test set are presented indicating that an approach which uses the modified newton direction is more robust than both the pure affine scaling approach and one which uses the Newton direction as the centering direction.     

Superlinear and quadratic convergence of some primal-dual interior point methods for constrained optimization

This paper proves local convergence rates of primal-dual interior point methods for general nonlinearly constrained optimization problems. Conditions to be satisfied at a solution are those given by the usual Jacobian uniqueness conditions. Proofs about convergence rates are given for three kinds of step size rules. They are: (i) the step size rule adopted by Zhang et al. in their convergence analysis of a primal-dual interior point method for linear programs, in which they used single step size for primal and dual variables; (ii) the step size rule used in the software package OB1, which uses different step sizes for primal and dual variables; and (iii) the step size rule used by Yamashita for his globally convergent primal-dual interior point method for general constrained optimization problems, which also uses different step sizes for primal and dual variables. Conditions to the barrier parameter and parameters in step size rules are given for each case. For these step size rules, local and quadratic convergence of the Newton method and local and superlinear convergence of the quasi-Newton method are proved. A preliminary version of this paper was presented at the conference “Optimization-Models and Algorithms” held at the Institute of Statistical Mathematics, Tokyo, March 1993.     

Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming

We propose to compute the search direction at each interior-point iteration for a linear program via a reduced augmented system that typically has a much smaller dimension than the original augmented system. This reduced system is potentially less susceptible to the ill-conditioning effect of the elements in the (1,1) block of the augmented matrix. A preconditioner is then designed by approximating the block structure of the inverse of the transformed matrix to further improve the spectral properties of the transformed system. The resulting preconditioned system is likely to become better conditioned toward the end of the interior-point algorithm. Capitalizing on the special spectral properties of the transformed matrix, we further proposed a two-phase iterative algorithm that starts by solving the normal equations with PCG in each IPM iteration, and then switches to solve the preconditioned reduced augmented system with symmetric quasi-minimal residual (SQMR) method when it is advantageous to do so. The experimental results have demonstrated that our proposed method is competitive with direct methods in solving large-scale LP problems and a set of highly degenerate LP problems. Research supported in parts by NUS Research Grant R146-000-076-112 and SMA IUP Research Grant.