Optimization Algorithms#

Detailed Description#

The algorithms in this section minimize or maximize function value within specified constraints or without any constraints.

Classes#

Name

Description

class cv::ConjGradSolver

This class is used to perform the non-linear non-constrained minimization of a function with known gradient,. View details

class cv::DownhillSolver

This class is used to perform the non-linear non-constrained minimization of a function,. View details

class cv::MinProblemSolver

Basic interface for all solvers. View details

Enumerations#

enum cv::SolveLPResult {
    cv::SOLVELP_LOST = -3,
    cv::SOLVELP_UNBOUNDED = -2,
    cv::SOLVELP_UNFEASIBLE = -1,
    cv::SOLVELP_SINGLE = 0,
    cv::SOLVELP_MULTI = 1
}

return codes for cv::solveLP() function View details

Enumeration Type Documentation#

SolveLPResult#

enum cv::SolveLPResult

#include <opencv2/core/optim.hpp>

return codes for cv::solveLP() function

Enumerator:

SOLVELP_LOST
Python: cv.SOLVELP_LOST

problem is feasible, but solver lost solution due to floating-point arithmetic errors

SOLVELP_UNBOUNDED
Python: cv.SOLVELP_UNBOUNDED

problem is unbounded (target function can achieve arbitrary high values)

SOLVELP_UNFEASIBLE
Python: cv.SOLVELP_UNFEASIBLE

problem is unfeasible (there are no points that satisfy all the constraints imposed)

SOLVELP_SINGLE
Python: cv.SOLVELP_SINGLE

there is only one maximum for target function

SOLVELP_MULTI
Python: cv.SOLVELP_MULTI

there are multiple maxima for target function - the arbitrary one is returned

Function Documentation#

solveLP() [1/2]#

int cv::solveLP(
InputArray Func,
InputArray Constr,
OutputArray z )

#include <opencv2/core/optim.hpp>

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

solveLP() [2/2]#

int cv::solveLP(
InputArray Func,
InputArray Constr,
OutputArray z,
double constr_eps )

#include <opencv2/core/optim.hpp>

Solve given (non-integer) linear programming problem using the Simplex Algorithm (Simplex Method).

What we mean here by “linear programming problem” (or LP problem, for short) can be formulated as:

\[\begin{split} \mbox{Maximize } c\cdot x\\ \mbox{Subject to:}\\ Ax\leq b\\ x\geq 0 \end{split}\]

Where \(c\) is fixed 1-by-n row-vector, \(A\) is fixed m-by-n matrix, \(b\) is fixed m-by-1 column vector and \(x\) is an arbitrary n-by-1 column vector, which satisfies the constraints.

Simplex algorithm is one of many algorithms that are designed to handle this sort of problems efficiently. Although it is not optimal in theoretical sense (there exist algorithms that can solve any problem written as above in polynomial time, while simplex method degenerates to exponential time for some special cases), it is well-studied, easy to implement and is shown to work well for real-life purposes.

The particular implementation is taken almost verbatim from Introduction to Algorithms, third edition by T. H. Cormen, C. E. Leiserson, R. L. Rivest and Clifford Stein. In particular, the Bland’s rule http://en.wikipedia.org/wiki/Bland%27s_rule is used to prevent cycling.

Parameters

  • Func — This row-vector corresponds to \(c\) in the LP problem formulation (see above). It should contain 32- or 64-bit floating point numbers. As a convenience, column-vector may be also submitted, in the latter case it is understood to correspond to \(c^T\).

  • Constr — m-by-n+1 matrix, whose rightmost column corresponds to \(b\) in formulation above and the remaining to \(A\). It should contain 32- or 64-bit floating point numbers.

  • z — The solution will be returned here as a column-vector - it corresponds to \(c\) in the formulation above. It will contain 64-bit floating point numbers.

  • constr_eps — allowed numeric disparity for constraints

Returns — One of cv::SolveLPResult