An interior-point solver for large block-angular problems and applications

Abstract: Interior point methods (IPMs) have shown to behave very well in some classes of large-scale structured optimization problems. We will discuss a successful approach for block-angular structures that relies on the combination of Cholesky factorizations and preconditioned conjugate gradients for the normal equations. In the first part of the talk we will outline such specialized IPM, which is implemented in a solver named BlockIP (coded in C/C++). In the second part of the talk we will overview a set of applications where this algorithm outperformed some of the most efficient alternative state-of-the-art codes. The list of applications includes:

(1) statistical tabular data confidentiality;
(2) support vector machines;
(3) minimum convex cost flows in bipartite networks;
(4) and multiperiod facility location (a mixed integer linear optimization problem).
Computational results showing the efficiency of the method will be reported for instances of up to 1000 million variables and 5 million constraints.