/pypdas

Implementation of primal-dual active-set for quadratic optimization, with support of inexact subproblem solve.

Primary LanguagePython

--Introduction:
pypdas is an implementation of the primal-dual active-set (PDAS) method, with inexact subproblem solves and extensive enhancement, for convex quadratic optimization problems (QPs) of the form:
   min {1/2x'Hx + c'x | Aeq x = beq, bl <= Ax <= bu, l <= x <= u}.
Key features of this package is its:
- Unified interface for both dense and sparse problems; 
- Flexible control on the speed of identification of the optimal active-set;
- Customizable subproblem (linear equation system) iterative solve.

--Example:
    from pdas.toolbox import pdas,ipdas
    from pdas.randutil import sprandsym, sp_rand

    'Example to call pdas, with exact ssm solve.'
    n = 100  # number of variables
    m = 1    # number of equality
    mi = 1   # number of inequality
    # Generate some random data
    H    = sprandsym(n)
    c    = sp_rand(n,1,1)
    A    = sp_rand(mi,n,1)
    bl   = sp_rand(mi,1,1)
    bu   = bl + 1
    Aeq  = sp_rand(m,n,0.8)
    beq  = sp_rand(m,1,1)
    l    = sp_rand(n,1,1)
    u    = l + 1
    x0   = sp_rand(n,1,0.8)

    # Solve a general QP
    print('Solving a random QP with exact ssm solve:\n')
    pdas(H,c,Aeq,beq,A,bl,bu,l,u,x0)

    # Solve a bound constrained QP
    print('Solving a random bound-constrained QP with exact ssm solve:\n')
    pdas(H=H,c=c,l=l,u=u,x0=x0)

    'Example to call pdas, with inexact ssm solve.'
    n = 100  # number of variables
    m = 1    # number of equality
    mi = 1   # number of inequality
    # Generate some random data
    H    = sprandsym(n)
    c    = sp_rand(n,1,1)
    A    = sp_rand(mi,n,1)
    bl   = sp_rand(mi,1,1)
    bu   = bl + 1
    Aeq  = sp_rand(m,n,0.8)
    beq  = sp_rand(m,1,1)
    l    = sp_rand(n,1,1)
    u    = l + 1
    x0   = sp_rand(n,1,0.8)

    # Solve a general QP
    print('Solving a random QP with inexact ssm solve:\n')
    ipdas(H,c,Aeq,beq,A,bl,bu,l,u,x0)

    # Solve a bound constrained QP
    print('Solving a random QP with inexact ssm solve:\n')
    ipdas(H=H,c=c,l=l,u=u,x0=x0)

--Caveat:
Convergence is known for certain convex QPs arising in optimal control, most but not all convex QPs are solvable by pypdas.

--Prerequisites:
cvxopt (http://cvxopt.org/)
numpy (http://www.numpy.org/)
scipy (http://www.scipy.org/)
Set PYTHONPATH to include folder pdas/

--Design:
object-oriented
observer pattern heavily used