the do / gr-peach-opencv-project

Opencv 3.1 project on GR-PEACH board

Fork of gr-peach-opencv-project by the do

Embed: (wiki syntax)

« Back to documentation index

Optimization Algorithms
Data Structures | Enumerations | Functions

Optimization Algorithms
[Core functionality]

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

Data Structures

class  MinProblemSolver
 Basic interface for all solvers. More...
class  DownhillSolver
 This class is used to perform the non-linear non-constrained minimization of a function,. More...
class  ConjGradSolver
 This class is used to perform the non-linear non-constrained minimization of a function with known gradient,. More...

Enumerations

enum  SolveLPResult { SOLVELP_UNBOUNDED = -2, SOLVELP_UNFEASIBLE = -1, SOLVELP_SINGLE = 0, SOLVELP_MULTI = 1 }
 

return codes for cv::solveLP() function

More...

Functions

CV_EXPORTS_W int solveLP (const Mat &Func, const Mat &Constr, Mat &z)
 Solve given (non-integer) linear programming problem using the Simplex Algorithm (Simplex Method).

Detailed Description

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

Enumeration Type Documentation

enum SolveLPResult

return codes for cv::solveLP() function

Enumerator:
SOLVELP_UNBOUNDED 

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

SOLVELP_UNFEASIBLE 

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

SOLVELP_SINGLE 

there is only one maximum for target function

SOLVELP_MULTI 

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

Definition at line 257 of file optim.hpp.

Function Documentation

int solveLP ( const Mat &  Func,
const Mat &  Constr,
Mat &  z 
)

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:

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

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:
FuncThis 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 containt 32- or 64-bit floating point numbers.
zThe 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.
Returns:
One of cv::SolveLPResult

Definition at line 94 of file lpsolver.cpp.

Generated on Tue Jul 12 2022 15:17:34 by  doxygen 1.7.2