最適化アルゴリズム

詳細説明

このセクションのアルゴリズムは、指定された制約の下で、または制約なしで、関数値を最小化または最大化する。

クラス
class	cv::ConjGradSolver
	このクラスは、勾配が既知の関数に対する非線形・非制約の最小化を行うために使用する。 続きを読む...
class	cv::DownhillSolver
	このクラスは、関数に対する非線形・非制約の最小化を行うために使用する。 続きを読む...
class	cv::MinProblemSolver
	すべてのソルバーのための基本インターフェース。 続きを読む...

列挙型
enum	cv::SolveLPResult {   cv::SOLVELP_LOST = -3 ,   cv::SOLVELP_UNBOUNDED = -2 ,   cv::SOLVELP_UNFEASIBLE = -1 ,   cv::SOLVELP_SINGLE = 0 ,   cv::SOLVELP_MULTI = 1 }
	cv::solveLP()関数の戻りコード 詳細...

関数
int	cv::solveLP (InputArray Func, InputArray Constr, OutputArray z)
int	cv::solveLP (InputArray Func, InputArray Constr, OutputArray z, double constr_eps)
	シンプレックス Algorithm（シンプレックス法）を用いて、与えられた（非整数の）線形計画問題を解く。

列挙型詳解

SolveLPResult

enum cv::SolveLPResult

#include <opencv2/core/optim.hpp>

cv::solveLP()関数の戻りコード

列挙値
SOLVELP_LOST  Python: cv.SOLVELP_LOST	問題は実行可能だが、ソルバーが浮動小数点演算の誤差により解を失った
SOLVELP_UNBOUNDED  Python: cv.SOLVELP_UNBOUNDED	問題は非有界である（目的関数が任意に大きな値を取りうる）
SOLVELP_UNFEASIBLE  Python: cv.SOLVELP_UNFEASIBLE	問題は実行不可能である（課されたすべての制約を満たす点が存在しない）
SOLVELP_SINGLE  Python: cv.SOLVELP_SINGLE	目的関数の最大値は1つだけ存在する
SOLVELP_MULTI  Python: cv.SOLVELP_MULTI	目的関数の最大値が複数存在する。そのうちの任意の1つが返される

関数詳解

solveLP() [1/2]

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

Python:
	cv.solveLP(	Func, Constr, constr_eps[, z]	) ->	retval, z
	cv.solveLP(	Func, Constr[, z]	) ->	retval, z

#include <opencv2/core/optim.hpp>

これは利便性のために提供されているオーバーロードされたメンバ関数である。上記の関数とは、受け取る引数のみが異なる。

solveLP() [2/2]

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

Python:
	cv.solveLP(	Func, Constr, constr_eps[, z]	) ->	retval, z
	cv.solveLP(	Func, Constr[, z]	) ->	retval, z

#include <opencv2/core/optim.hpp>

与えられた（整数でない）線形計画問題を単体法 Algorithm（シンプレックス法）で解く。

ここで「線形計画問題」（略してLP問題）と呼ぶものは、次のように定式化できる:

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

ここで \(c\) は固定の 1×n 行ベクトル、\(A\) は固定の m×n 行列、\(b\) は固定の m×1 列ベクトル、\(x\) は制約を満たす任意の n×1 列ベクトルである。

シンプレックス法は、この種の問題を効率的に扱うために設計された多くのアルゴリズムの1つである。理論的には最適ではない（上記のように記述できる任意の問題を多項式時間で解けるアルゴリズムが存在する一方、シンプレックス法は特殊なケースでは指数時間に退化する）が、よく研究されており、実装が容易で、実用的な目的では十分に機能することが示されている。

この実装は、T. H. Cormen、C. E. Leiserson、R. L. Rivest、Clifford Stein による Introduction to Algorithms, third edition からほぼそのまま引用している。特に、循環を防ぐためにブランドの規則 http://en.wikipedia.org/wiki/Bland%27s_rule を使用している。

引数

Func	この行ベクトルは、LP問題の定式化における\(c\)に対応する（上記参照）。32ビットまたは64ビットの浮動小数点数を含む必要がある。便宜上、列ベクトルを与えることもでき、その場合は\(c^T\)に対応するものとみなされる。
Constr	m行n+1列の行列。最右列は上記の定式化における\(b\)に対応し、残りの列は\(A\)に対応する。32ビットまたは64ビットの浮動小数点数を含む必要がある。
z	解はここに列ベクトルとして返される。上記の定式化における\(c\)に対応する。64ビットの浮動小数点数を含む。
constr_eps	制約に対して許容される数値的な視差

戻り値

cv::SolveLPResult のいずれか