All Classes Files Functions Variables
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})


          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

Previous papers related to some features of the package are:

Some features of the implementation are:

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