BlockIPPlatform Documentation

BlockIP implements a specialized primal-dual long-step path-following interior point algorithm for linear, separable convex quadratic, or separable convex nonlinear problems with primal block structure.

Defining f(x) as either

          f(x)= c_1 x_1 + ...+ c_k x_k + c_{k+1} x_{k+1} +
            1/2 (x_1...x_k x_{k+1}) Q (x_1...x_k x_{k+1})

or

          f(x)= f(x_1, ..., x_k,x_{k+1})

the problem is

      min  f(x) 
      subj. to
         N_i x_i = b_i  i=1,...,k                       Block equations 
         (L_1*x_1 + ...+ L_k*x_k) + x_{k+1} = b_{k+1}   Linking constraints 
         0 <= x_i <= u_i   i=1,...,k+1                  Bounds 

where x_i i=1..k are the variables for each block and x_{k+1} are the slacks of the linking constraints

The normal equations for the dual direction is computed in two parts. The part associated to blocks is solved through k Cholesky factorizations. The part associated to linking constraints is computed with a PCG using a power series preconditioner. Cholesky factorizations are currently performed with Ng-Peyton's sprsblkllt; code is ready for others solvers.

A detailed description of BlockIP can be found in

• J. Castro, Interior-point solver for convex separable block-angular problems, Research Report DR 2014/03, Dept. of Statistics and Operations Research, Universitat Politecnica de Catalunya, 2014 (submitted).
  

Previous papers related to some features of the package are:

• J. Castro, A specialized interior-point algorithm for multicommodity network flows, SIAM Journal on Optimization, 10 (2000), 852-877.
  
• J. Castro, An interior-point approach for primal block-angular problems, Computational Optimization and Applications 36 (2007) 195-219.
  
• J. Castro, J. Cuesta, Quadratic regularizations in an interior-point method for primal block-angular problems, Mathematical Programming, 130 (2011) 415-445.
  

Some features of the implementation are:

• it can deal with any problem with primal block-angular structure
  
• it deals with quadratic costs of variables
  
• it considers linear and quadratic costs for slacks of linking constraints
  
• it considers lower and upper bounds for linking constraints
  
• rhs terms b_i and b_{k+1} can not be infinity.
• it can deal with convex separable nonlinear problems (i.e., with diagonal Hessian)
  
• both Newton and second-order predictor-corrector directions are available
  

The user can also solve the dual direction systems by the Cholesky factorization of the full system A*Theta*A' (A includes block and linking constraints).

Instances are created by the BlockIP() constructors. There are two variants of the constructor: one for problems in standard form (0 <= variables <= ub and constraints = rhs, and linking constraints contain slacks), another for general problems (lb <= variables <= ub and lhs <= constraints <= rhs).

See the constructors for information about the input parameters needed to define an instance.

Original idea and implementation: Jordi Castro
Other programmers: Xavi Jimenez

Jordi Castro, May 2014
Dept. of Statistics and Operations Research
Universitat Politecnica de Catalunya

Barcelona, Catalonia