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.
Value parameters
a
the M-by-N constraint matrix
b
the M-length constant/limit vector
c
the N-length cost/revenue vector (first order component)
q
the N-by-N cost/revenue matrix (second order component)
x_B
the initial basis (set of indices where x_i is in 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.
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.
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.
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.
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).
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).
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.
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.