minima

Type Members

1. class BGSimplex extends MinimizerLP

   

   This class solves Linear Programming (LP) problems using the Bartels-Golub (BG) Simplex Algorithm.

   This class solves Linear Programming (LP) problems using the Bartels-Golub (BG) Simplex Algorithm. Given a constraint matrix 'a', constant vector 'b' 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) = c x subject to a x <= b, x >= 0

   The BG Simplex Algorithm performs LU Fractorization/Decomposition of the basis-matrix ('ba' = 'B') rather than computing inverses ('b_inv'). It has benefits over the (Revised) Simplex Algorithm (less runtime, less memory, and much reduced chance of round off errors).

2. class CheckLP extends Error

   

   This class checks the solution to Linear Programming (LP) problems.

   This class checks the solution to Linear Programming (LP) problems. Given a constraint matrix 'a', limit/RHS vector 'b' and cost vector 'c', determine if the values for the solution/decision vector 'x' minimizes the objective function f(x), while satisfying all of the constraints, i.e.,

   minimize f(x) = c x subject to a x <= b, x >= 0

   Check the feasibility and optimality of the solution.

3. class ConjGradient extends Minimizer with Error

   

   Polak-Ribiere Conjugate Gradient (PR-CG) Algorithm for solving Non-Linear Programming (NLP) problems.

   Polak-Ribiere Conjugate Gradient (PR-CG) Algorithm for solving Non-Linear Programming (NLP) problems. PR-CG determines a search direction as a weighted combination of the steepest descent direction (-gradient) and the previous direction. The weighting is set by the beta function, which for this implementation used the Polak-Ribiere technique.

   dir_k = -gradient (x) + beta * dir_k-1

   minimize f(x) subject to g(x) <= 0 [ optionally g(x) == 0 ]

4. class DualSimplex extends MinimizerLP

   

   This class solves Linear Programming (LP) problems using a tableau based Dual Simplex Algorithm.

   This class solves Linear Programming (LP) problems using a tableau based Dual Simplex Algorithm. It is particularly useful when re-optimizing after a constraint has been added. The algorithm starts with an infeasible super-optimal solution and moves toward (primal) feasibility and optimality.

   Given a constraint matrix 'a', limit/RHS vector 'b' 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) = c x subject to a x <= b, x >= 0

   Creates an MM-by-NN simplex tableau with -- [0..M-1, 0..N-1] = a (constraint matrix) -- [0..M-1, N..M+N-1] = s (slack/surplus variable matrix) -- [0..M-1, NN-1] = b (limit/RHS vector) -- [M, 0..NN-2] = c (cost vector)

5. class GeneticAlgorithm extends AnyRef

   

   This class performs local search to find minima of functions defined on integer vector domains (z^n).

   This class performs local search to find minima of functions defined on integer vector domains (z^n).

   minimize f(x) subject to g(x) <= 0, x in Z^n

6. class GoldenSectionLS extends LineSearch

   

   This class performs a line search on f(x) to find a minimal value for f.

   This class performs a line search on f(x) to find a minimal value for f. It requires no derivatives and only one functional evaluation per iteration. A search is conducted from x1 (often 0) to xmax. A guess for xmax must be given, but can be made larger during the expansion phase, that occurs before the recursive golden section search is called. It works on scalar functions (see GoldenSectionLSTest). If starting with a vector function f(x), simply define a new function g(y) = x0 + direction * y (see GoldenSectionLSTest2).

7. class IntegerGoldenSectionLS extends AnyRef

   

   This class performs a line search on f(x) to find a minimal value for f.

   This class performs a line search on f(x) to find a minimal value for f. It requires no derivatives and only one functional evaluation per iteration. A search is conducted from x1 (often 0) to xmax. A guess for xmax must be given, but can be made larger during the expansion phase, that occurs before the recursive golden section search is called. It works on scalar functions (see IntegerGoldenSectionLSTest). If starting with a vector function f(x), simply define a new function g(y) = x0 + direction * y (see IntegerGoldenSectionLSTest2).

8. class IntegerLP extends AnyRef

   

   This class solves Integer Linear Programming (ILP) and Mixed Integer Linear Programming (MILP) problems recursively using the Simplex algorithm.

   This class solves Integer Linear Programming (ILP) and Mixed Integer Linear Programming (MILP) problems recursively using the Simplex algorithm. First, an LP problem is solved. If the optimal solution vector x is entirely integer valued, the ILP is solved. If not, pick the first x_j that is not integer valued. Define two new LP problems which bound x_j to the integer below and above, respectively. Branch by solving each of these LP problems in turn. Prune by not exploring branches less optimal than the currently best integer solution. This technique is referred to as Branch and Bound. An exclusion set may be optionally provided for MILP problems. TODO: Use the Dual Simplex Algorithm for better performance.

   Given a constraint matrix 'a', limit/RHS vector 'b' and cost vector 'c', find values for the solution/decision vector 'x' that minmize the objective function f(x), while satisfying all of the constraints, i.e.,

   minimize f(x) = c x subject to a x <= b, x >= 0, some x_i must be integer valued

   Make b_i negative to indicate a ">=" constraint

9. class IntegerLocalSearch extends AnyRef

   

   This class performs local search to find minima of functions defined on integer vector domains (z^n).

   This class performs local search to find minima of functions defined on integer vector domains (z^n).

   minimize f(x) subject to g(x) <= 0, x in Z^n

10. class IntegerNLP extends AnyRef

    

    This class solves Integer Non-Linear Programming (INLP) and Mixed Integer Linear Non-Programming (MINLP) problems recursively using the Simplex algorithm.

    This class solves Integer Non-Linear Programming (INLP) and Mixed Integer Linear Non-Programming (MINLP) problems recursively using the Simplex algorithm. First, an NLP problem is solved. If the optimal solution vector x is entirely integer valued, the INLP is solved. If not, pick the first x_j that is not integer valued. Define two new NLP problems which bound x_j to the integer below and above, respectively. Branch by solving each of these NLP problems in turn. Prune by not exploring branches less optimal than the currently best integer solution. This technique is referred to as Branch and Bound. An exclusion set may be optionally provided for MINLP problems.

    Given an objective function f(x) and a constraint function g(x), find values for the solution/decision vector 'x' that minimize the objective function f(x), while satisfying the constraint function, i.e.,

    minimize f(x) subject to g(x) <= 0, some x_i must integer-valued

    Make b_i negative to indicate a ">=" constraint

11. class IntegerTabuSearch extends AnyRef

    

    This class performs tabu search to find minima of functions defined on integer vector domains (z^n). Tabu search will not re-visit points already deemed sub-optimal.

    This class performs tabu search to find minima of functions defined on integer vector domains (z^n). Tabu search will not re-visit points already deemed sub-optimal.

    minimize f(x) subject to g(x) <= 0, x in Z^n

12. trait LineSearch extends AnyRef

    

    This trait specifies the pattern for Line Search (LS) algorithms that perform line search on f(x) to find an x-value that minimizes a function f.

13. trait Minimizer extends AnyRef

    

    This trait sets the pattern for optimization algorithms for solving Non-Linear Programming (NLP) problems of the form:

    This trait sets the pattern for optimization algorithms for solving Non-Linear Programming (NLP) problems of the form:

    minimize f(x) subject to g(x) <= 0 [ optionally g(x) == 0 ]

    where f is the objective function to be minimized g is the constraint function to be satisfied, if any

    Classes mixing in this trait must implement a function (fg) that rolls the constraints into the objective functions as penalties for constraint violation, a one-dimensional Line Search (LS) algorithm (lineSearch) and an iterative method (solve) that searches for improved solutions (x-vectors with lower objective function values (f(x)).

14. trait MinimizerLP extends Error

    

    This trait sets the pattern for optimization algorithms for solving Linear Programming (NLP) problems of the form:

    This trait sets the pattern for optimization algorithms for solving Linear Programming (NLP) problems of the form:

    minimize c x subject to a x <= b, x >= 0

    where a is the constraint matrix b is the limit/RHS vector c is the cost vector

    Classes mixing in this trait must implement an objective function (objF) an iterative method (solve) that searches for improved solutions (x-vectors with lower objective function values.

15. class NelderMeadSimplex extends Minimizer with Error

    

    This class solves unconstrained Non-Linear Programming (NLP) problems using the Nelder-Mead Simplex algorithm.

    This class solves unconstrained Non-Linear Programming (NLP) problems using the Nelder-Mead Simplex algorithm. Given a function 'f' and its dimension 'n', the algorithm moves a simplex defined by n + 1 points in order to find an optimal solution. The algorithm is derivative-free.

    minimize f(x)

16. class NewtonRaphson extends AnyRef

    

    This class is used to find roots (zeros) for a one-dimensional (scalar) function f.

    This class is used to find roots (zeros) for a one-dimensional (scalar) function f. If f is the derivative of some other function g, then this technique can be used to find optima for g. Caveat: Use Conjugate Gradient or Quasi-Newton for complex optimizations.

17. class QuadraticSimplex extends Error

    

    This class solves Quadratic Programming (QP) problems using the Quadratic Simplex Algorithm.

    This 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 nonlinear complementary slackness

    See also

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

18. class QuasiNewton extends Minimizer with Error

    

    Broyden–Fletcher–Goldfarb–Shanno (BFGS) Quasi-Newton Algorithm for solving Non-Linear Programming (NLP) problems.

    Broyden–Fletcher–Goldfarb–Shanno (BFGS) Quasi-Newton Algorithm for solving Non-Linear Programming (NLP) problems. BFGS determines a search direction by deflecting the steepest descent direction vector (opposite the gradient) by multiplying it by a matrix that approximates the inverse Hessian. Note, this implementation may be set up to work with the matrix 'b' (approximate Hessian) or directly with the 'binv' matrix (the inverse of b).

    minimize f(x) subject to g(x) <= 0 [ optionally g(x) == 0 ]

19. class RevisedSimplex extends MinimizerLP

    

    This class solves Linear Programming (LP) problems using the Revised Simplex Algorithm.

    This class solves Linear Programming (LP) problems using the Revised Simplex Algorithm. Given a constraint matrix 'a', constant vector 'b' 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) = c x subject to a x <= b, x >= 0

    The Revised Simplex Algorithm operates on 'b_inv', which is the inverse of the basis-matrix ('ba' = 'B'). It has benefits over the Simplex Algorithm (less memory and reduced chance of round off errors).

20. class Simplex extends MinimizerLP

    

    This class solves Linear Programming (LP) problems using a tableau based Simplex Algorithm.

    This class solves Linear Programming (LP) problems using a tableau based Simplex Algorithm. Given a constraint matrix 'a', limit/RHS vector 'b' 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) = c x subject to a x <= b, x >= 0

    In case of "a_i x >= b_i", use -b_i as an indicator of a ">=" constraint. The program will flip such negative b_i back to positive as well as use a surplus variable instead of the usual slack variable, i.e., a_i x <= b_i => a_i x + s_i = b_i // use slack variable s_i with coeff 1 a_i x >= b_i => a_i x + s_i = b_i // use surplus variable s_i with coeff -1

    Creates an MM-by-NN simplex tableau with -- [0..M-1, 0..N-1] = a (constraint matrix) -- [0..M-1, N..M+N-1] = s (slack/surplus variable matrix) -- [0..M-1, NN-1] = b (limit/RHS vector) -- [M, 0..NN-2] = c (cost vector)

21. class Simplex2P extends MinimizerLP

    

    This class solves Linear Programming (LP) problems using a tableau based Simplex Algorithm.

    This class solves Linear Programming (LP) problems using a tableau based Simplex Algorithm. Given a constraint matrix 'a', limit/RHS vector 'b' 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) = c x subject to a x <= b, x >= 0

    In case of "a_i x >= b_i", use -b_i as an indicator of a ">=" constraint. The program will flip such negative b_i back to positive as well as use a surplus and artificial variable instead of the usual slack variable, i.e., a_i x <= b_i => a_i x + s_i = b_i // use slack variable s_i with coeff 1 a_i x >= b_i => a_i x + s_i = b_i // use surplus variable s_i with coeff -1 For each ">=" constraint, an artificial variable is introduced and put into the initial basis. These artificial variables must be removed from the basis during Phase I of the Two-Phase Simplex Algorithm. After this, or if there are no artificial variables, Phase II is used to find an optimal value for x and the optimum value for f.

    Creates an MM-by-nn simplex tableau with -- [0..M-1, 0..N-1] = a (constraint matrix) -- [0..M-1, N..M+N-1] = s (slack/surplus variable matrix) -- [0..M-1, M+N..nn-2] = r (artificial variable matrix) -- [0..M-1, nn-1] = b (limit/RHS vector) -- [M, 0..nn-2] = c (cost vector)

22. class SteepestDescent extends Minimizer with Error

    

    This class solves unconstrained Non-Linear Programming (NLP) problems using the Steepest Descent algorithm.

    This class solves unconstrained Non-Linear Programming (NLP) problems using the Steepest Descent algorithm. Given a function 'f' and a starting point 'x', the algorithm computes the gradient and takes steps in the opposite direction. The algorithm iterates until it converges. The class assumes that partial derivative functions are not availble unless explicitly given via the setDerivatives method.

    dir_k = -gradient (x)

    minimize f(x)

23. class WolfeLS extends LineSearch

    

    This class performs an inexact line search on f to find a point x that exhibits (1) sufficient decrease (f(x) enough less that f(0)) and (2) the slope at x is less steep than the slope at 0.

    This class performs an inexact line search on f to find a point x that exhibits (1) sufficient decrease (f(x) enough less that f(0)) and (2) the slope at x is less steep than the slope at 0. That is, the line search looks for a value for x satisfying the two Wolfe conditions.

    f(x) <= f(0) + c1 * f'(0) * x Wolfe condition 1 (Armijo condition) |f'(x)| <= |c2 * f'(0)| Wolfe condition 2 (Strong version) f'(x) >= c2 * f'(0) Wolfe condition 2 (Weak version, more robust)

    It works on scalar functions (see WolfeLSTest). If starting with a vector function f(x), simply define a new function g(y) = x0 + direction * y (see WolfeLSTest2).