BlockIPPlatform

BlockIP implements a specialized primaldual longstep pathfollowing 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 NgPeyton'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