namespace referencePiiOptimization
Functions and operations for optimization.
This namespace contains functions for optimizing linear and non-linear functions with methods such as the bfgs.
Classes
| class |
An interface for functions that can be optimized. |
| class |
An interface for optimizable functions that are provided with gradient information. |
| class |
An interface for functions optimized with respect to residual values. |
Functions
|
template<class Matrix>
Matrix::value_type
|
Solves the linear assignment problem. |
|
PII_OPTIMIZATION_EXPORT PiiMatrix< double >
|
(
The Broyden-Fletcher-Goldfarb-Shanno (BFGS) method is a method to solve an unconstrained nonlinear optimization problem. |
|
PII_OPTIMIZATION_EXPORT PiiMatrix< double >
|
(
The Levenberg-Marquardt is a method of non-linear optimization. |
Function details
-
template<class Matrix>
Matrix::value_type assign
#include <PiiOptimization.h>Solves the linear assignment problem.
Wikipedia defines this problem as follows: "There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task in such a way that the total cost of the assignment is minimized." The problem is presented as a cost matrix that defines the cost of assigning agent i (row index) to task j (column index).
This implementation is an adaptation of Roy Jonker's original C++ implementation, which in turn is based on "A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems," Computing 38, 325-340, 1987 by R. Jonker and A. Volgenant. Specifically, the dense version of the algorithm is implemented.
Parameters
- cost
-
the cost matrix. This matrix must be square (the number of tasks and agents must be the same). If there is a different number of tasks and agents, dummy rows/columns can be added with constant cost.
- solution
-
an optional output value argument that will store the optimal assignment upon return. The size of the matrix will be 2-by-N, where N is the size of the input matrix. The first row of the matrix stores the indices of columns assigned to rows in the solution, and the second column the indices of rows assigned to columns. In other words, solution(0,0) determines the task to which agent 0 should be assigned, and solution(1,0) the agent to which task 0 should be assigned. It follows that
solution(0, solution(1,N)) = N. - duals
-
an optional output value argument that will store the dual variables of the solution (2-by-N). The first row stores the row reduction numbers, and the second row the column reduction numbers.
-
PII_OPTIMIZATION_EXPORT PiiMatrix< double > bfgsMinimize
(- const GradientFunction< double > * function
- const PiiMatrix< double > & initialParams
- double epsG = 1e-8
- double epsF = 1e-8
- double epsX = 1e-8
- int maxIterations = 100
#include <PiiOptimization.h>The Broyden-Fletcher-Goldfarb-Shanno (BFGS) method is a method to solve an unconstrained nonlinear optimization problem.
This function minimizes function F(X) of N arguments by using a quasi- Newton method which is optimized to use a minimum amount of memory.
The algorithm generates the approximation of an inverse Hessian matrix by using information about the last M steps of the algorithm (M <= N). It lessens a required amount of memory from a value of order N^2 to a value of order 2*N*M.
Parameters
- function
-
the function to be minimized
- initialParams
- epsG
-
iteration break rule 1:
,
where
is the value of the
parameter estimate at time instant t. The iteration will end once
the norm of the gradient vector goes below epsG. - epsF
-
iteration break rule 2:
.
- epsX
-
iteration break rule 3:
.
- maxIterations
-
iteration break rule 4: t > maxIterations. This is the maximum number of iterations the algorithm will run if none of the first three rules breaks it.
Returns
the parameter values that result in the minimum value for
function. -
PII_OPTIMIZATION_EXPORT PiiMatrix< double > lmMinimize
(- const ResidualFunction< double > * function
- const PiiMatrix< double > & initialParams
- int maxIterations = 100
- double ftol = 1.e-14
- double xtol = 1.e-14
- double gtol = 1.e-14
- double epsilon = 1.e-14
- double stepbound = 100.0
#include <PiiOptimization.h>The Levenberg-Marquardt is a method of non-linear optimization.
It minimizes the sum of the squares of M nonlinear functions in N arguments by using Jacobian and information about function values. If the optimized function is not provided with Jacobian, it is calculated automagically by a forward-difference approximation.
Such a minimization problem could be solved as a general non-linear optimization problem (for example, using the LBFGS algorithm), but it is reasonable to use the information about the function F structure to solve the problem more effectively.
An example of a suitable optimization problem is to fit a mathematically defined geometric model to a set of measurements. In such a case the M non-linear functions could be the distances of each point to the model. The N optimized parameters could be translation, rotation, and scaling of the model. Note that N cannot exceed M.
Parameters
- function
-
the function to be minimized
- initialParams
- maxIterations
-
maximum number of iterations
- ftol
-
desired relative error in the sum of squared residuals
- xtol
-
desired relative error between last two approximations
- gtol
-
desired orthogonality between fvec and its derivatives
- epsilon
-
approximation step used to estimate the Jacobian if it is not provided by the function.
- stepbound
-
a factor that limits the size of initial approximation steps. Acceptable values are about 0.1 - 100. The default value seldom needs to be changed.
Add a note
Not a single note added yet. Be the first, add yours.