c

scalation.minima

QuadraticSimplex

class QuadraticSimplex extends Error

The QuadraticSimplex class solves Quadratic Programming (QP) problems using the Quadratic Simplex Algorithm. Given a constraint matrix 'a', constant vector 'b', cost matrix 'q' and cost vector 'c', find values for the solution/decision vector 'x' that minimize the objective function 'f(x)', while satisfying all of the constraints, i.e.,

minimize f(x) = 1/2 x q x + c x subject to a x <= b, x >= 0

Creates an 'MM-by-NN' simplex tableau. This implementation is restricted to linear constraints 'a x <= b' and 'q' being a positive semi-definite matrix. Pivoting must now also handle non-linear complementary slackness.

See also

www.engineering.uiowa.edu/~dbricker/lp_stacks.html

Linear Supertypes
Error, AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. QuadraticSimplex
  2. Error
  3. AnyRef
  4. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. All

Instance Constructors

  1. new QuadraticSimplex(a: MatrixD, b: VectorD, q: MatrixD, c: VectorD, x_B: Array[Int] = null)

    a

    the M-by-N constraint matrix

    b

    the M-length constant/limit vector

    q

    the N-by-N cost/revenue matrix (second order component)

    c

    the N-length cost/revenue vector (first order component)

    x_B

    the initial basis (set of indices where x_i is in the basis)

Value Members

  1. final def !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##(): Int
    Definition Classes
    AnyRef → Any
  3. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  4. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  5. def clone(): AnyRef
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @native() @throws( ... )
  6. def comple(l: Int): Int

    Return l's complementary variable.

    Return l's complementary variable.

    l

    whose complement

  7. def dual: VectorD

    Return the dual solution vector (y).

  8. def entering(): Int

    Find a variable 'x_l' to enter the basis.

    Find a variable 'x_l' to enter the basis. Determine the index of entering variable corresponding to column l. Neither the variable nor its complement may be in the current basis. Return -1 to indicate no such column.

  9. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  10. def equals(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  11. def finalize(): Unit
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] )
  12. final def flaw(method: String, message: String): Unit
    Definition Classes
    Error
  13. final def getClass(): Class[_]
    Definition Classes
    AnyRef → Any
    Annotations
    @native()
  14. def hashCode(): Int
    Definition Classes
    AnyRef → Any
    Annotations
    @native()
  15. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  16. val k: Int
  17. val l: Int
  18. def leaving(l: Int): Int

    Find the best variable x_k to leave the basis given that x_l is entering.

    Find the best variable x_k to leave the basis given that x_l is entering. Determine the index of the leaving variable corresponding to row k using the Min-Ratio Rule. Return -1 to indicate no such row.

    l

    the entering variable (column)

  19. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  20. final def notify(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native()
  21. final def notifyAll(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native()
  22. def objValue(x: VectorD): Double

    Return the optimal objective function value (f(x) = 1/2 x q x + c x).

    Return the optimal objective function value (f(x) = 1/2 x q x + c x).

    x

    the primal solution vector

  23. def pivot(k: Int, l: Int): Unit

    Pivot on entry (k, l) using Gauss-Jordan elimination to replace variable x_k with x_l in the basis.

    Pivot on entry (k, l) using Gauss-Jordan elimination to replace variable x_k with x_l in the basis.

    k

    the leaving variable (row)

    l

    the entering variable (column)

  24. def primal: VectorD

    Return the primal solution vector 'x'.

  25. def setBasis(j: Int = N, l: Int = M): Array[Int]

    There are 'M+N' variables, 'N' decision and 'M' slack variables, of which, for each iteration, 'M' are chosen for a Basic Feasible Solution (BFS).

    There are 'M+N' variables, 'N' decision and 'M' slack variables, of which, for each iteration, 'M' are chosen for a Basic Feasible Solution (BFS). The variables not in the basis are set to zero. Setting 'j' to 'N' will start with the slack variables in the basis (only works if 'b >= 0').

    j

    the offset to start the basis

    l

    the size of the basis

  26. def showTableau(): Unit

    Show the current basis and tableau.

  27. def solve(): (VectorD, Double)

    Run the simplex algorithm starting from the initial BFS and iteratively find a non-basic variable to replace a variable in the current basis so long as the objective improves.

  28. final def synchronized[T0](arg0: ⇒ T0): T0
    Definition Classes
    AnyRef
  29. def tableau: MatrixD

    Return the tableau 't'.

  30. def toString(): String
    Definition Classes
    AnyRef → Any
  31. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  32. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  33. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @native() @throws( ... )
  34. var x_B: Array[Int]

Inherited from Error

Inherited from AnyRef

Inherited from Any

Ungrouped