Module qps_pypower

Quadratic Program Solver for PYPOWER.

A common wrapper function for various QP solvers. Solves the following QP (quadratic programming) problem:

   min 1/2 x'*H*x + c'*x
    x

subject to:

   l <= A*x <= u       (linear constraints)
   xmin <= x <= xmax   (variable bounds)

Inputs (all optional except H, c, A and l):

• H : matrix (possibly sparse) of quadratic cost coefficients
• c : vector of linear cost coefficients
• A, l, u : define the optional linear constraints. Default values for the elements of l and u are -Inf and Inf, respectively.
• xmin, xmax : optional lower and upper bounds on the x variables, defaults are -Inf and Inf, respectively.
• x0 : optional starting value of optimization vector x
• opt : optional options structure with the following fields, all of which are also optional (default values shown in parentheses)
  • alg (0) - determines which solver to use
    • 0 = automatic, first available of BPMPD_MEX, CPLEX, MIPS
    • 100 = BPMPD_MEX
    • 200 = MIPS, MATLAB Interior Point Solver pure MATLAB implementation of a primal-dual interior point method
    • 250 = MIPS-sc, a step controlled variant of MIPS
    • 300 = Optimization Toolbox, QUADPROG or LINPROG
    • 400 = IPOPT
    • 500 = CPLEX
    • 600 = MOSEK
  • verbose (0) - controls level of progress output displayed
    • 0 = no progress output
    • 1 = some progress output
    • 2 = verbose progress output
  • max_it (0) - maximum number of iterations allowed
    • 0 = use algorithm default
  • bp_opt - options vector for BP
  • cplex_opt - options dict for CPLEX
  • ipopt_opt - options dict for IPOPT
  • pips_opt - options dict for qps_pips
  • mosek_opt - options dict for MOSEK
  • ot_opt - options dict for QUADPROG/LINPROG
• problem : The inputs can alternatively be supplied in a single problem dict with fields corresponding to the input arguments described above: H, c, A, l, u, xmin, xmax, x0, opt

Outputs:

• x : solution vector
• f : final objective function value
• exitflag : exit flag
  • 1 = converged
  • 0 or negative values = algorithm specific failure codes
• output : output struct with the following fields:
  • alg - algorithm code of solver used
  • (others) - algorithm specific fields
• lmbda : dict containing the Langrange and Kuhn-Tucker multipliers on the constraints, with fields:
  • mu_l - lower (left-hand) limit on linear constraints
  • mu_u - upper (right-hand) limit on linear constraints
  • lower - lower bound on optimization variables
  • upper - upper bound on optimization variables

Example from http://www.uc.edu/sashtml/iml/chap8/sect12.htm:

>>> from numpy import array, zeros, Inf
>>> from scipy.sparse import csr_matrix
>>> H = csr_matrix(array([[1003.1,  4.3,     6.3,     5.9],
...                       [4.3,     2.2,     2.1,     3.9],
...                       [6.3,     2.1,     3.5,     4.8],
...                       [5.9,     3.9,     4.8,     10 ]]))
>>> c = zeros(4)
>>> A = csr_matrix(array([[1,       1,       1,       1   ],
...                       [0.17,    0.11,    0.10,    0.18]]))
>>> l = array([1, 0.10])
>>> u = array([1, Inf])
>>> xmin = zeros(4)
>>> xmax = None
>>> x0 = array([1, 0, 0, 1])
>>> solution = qps_pips(H, c, A, l, u, xmin, xmax, x0)
>>> round(solution["f"], 11) == 1.09666678128
True
>>> solution["converged"]
True
>>> solution["output"]["iterations"]
10