  


Interiorpoint solver for convex separable blockangular problems
Jordi Castro (jordi.castroupc.edu) Abstract: Constraints matrices with blockangular structures are pervasive in Optimization. Interiorpoint methods have shown to be competitive for these structured problems by exploiting the linear algebra. One of these approaches solved the normal equations using sparse Cholesky factorizations for the block constraints, and a preconditioned conjugate gradient (PCG) for the linking constraints. The preconditioner is based on a power series expansion which approximates the inverse of the matrix of the linking constraints system. In this work we present an efficient solver based on this algorithm. Some of its features are: it solves linearly constrained convex separable problems (linear, quadratic or nonlinear); both Newton and secondorder predictorcorrector directions can be used, either with the Cholesky+PCG scheme or with a Cholesky factorization of normal equations; the preconditioner may include any number of terms of the power series; for any number of these terms, it estimates the spectral radius of the matrix in the power series (which is instrumental for the quality of the preconditioner). The solver has been hooked to SML, a structureconveying modelling language based on the popular AMPL modeling language. Computational results are reported for some large and/or difficult instances in the literature: (1) multicommodity flow problems; (2) minimum congestion problems; (3) statistical data protection problems using $\ell_1$ and $\ell_2$ distances (which are linear and quadratic problems, respectively), and the pseudoHuber function, a nonlinear approximation to $\ell_1$ which improves the preconditioner. In the largest instances, of up to 25 millions of variables and 300000 constraints, this approach is from two to three orders of magnitude faster than stateoftheart linear and quadratic optimization solvers. Keywords: interiorpoint methods; structured problems; normal equations; preconditioned conjugate gradient; largescale optimization; optimization software Category 1: Optimization Software and Modeling Systems Category 2: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: J. Castro, Interiorpoint solver for convex separable blockangular problems, Research Report DR 2014/03, Dept. of Statistics and Operations Research, Universitat Politècnica de Catalunya, Barcelona, 2014. Download: [PDF] Entry Submitted: 10/08/2014 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  