Module qps_pips

Uses the Python Interior Point Solver (PIPS) to solve 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)

Note the calling syntax is almost identical to that of QUADPROG from MathWorks' Optimization Toolbox. The main difference is that the linear constraints are specified with A, L, U instead of A, B, Aeq, Beq.

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

All parameters are optional except H, c, A and l or u.

Parameters:

• H (csr_matrix) - Quadratic cost coefficients.
• c (array) - vector of linear cost coefficients
• A (csr_matrix) - Optional linear constraints.
• l (array) - Optional linear constraints. Default values are -Inf.
• u (array) - Optional linear constraints. Default values are Inf.
• xmin (array) - Optional lower bounds on the x variables, defaults are -Inf.
• xmax (array) - Optional upper bounds on the x variables, defaults are Inf.
• x0 (array) - Starting value of optimization vector x.
• opt (dict) - optional options dictionary with the following keys, all of which are also optional (default values shown in parentheses)
  • verbose (False) - Controls level of progress output displayed
  • feastol (1e-6) - termination tolerance for feasibility condition
  • gradtol (1e-6) - termination tolerance for gradient condition
  • comptol (1e-6) - termination tolerance for complementarity condition
  • costtol (1e-6) - termination tolerance for cost condition
  • max_it (150) - maximum number of iterations
  • step_control (False) - set to True to enable step-size control
  • max_red (20) - maximum number of step-size reductions if step-control is on
  • cost_mult (1.0) - cost multiplier used to scale the objective function for improved conditioning. Note: The same value must also be passed to the Hessian evaluation function so that it can appropriately scale the objective function term in the Hessian of the Lagrangian.

Returns: dict

The solution dictionary has the following keys:

• x - solution vector
• f - final objective function value
• converged - exit status
  • True = first order optimality conditions satisfied
  • False = maximum number of iterations reached
  • None = numerically failed
• output - output dictionary with keys:
  • iterations - number of iterations performed
  • hist - dictionary of arrays with trajectories of the following: feascond, gradcond, coppcond, costcond, gamma, stepsize, obj, alphap, alphad
  • message - exit message
• lmbda - dictionary containing the Langrange and Kuhn-Tucker multipliers on the constraints, with keys:
  • eqnonlin - nonlinear equality constraints
  • ineqnonlin - nonlinear inequality constraints
  • 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