Into

Modules

Documentation

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
(
  • const PiiRandomAccessMatrix & cost
  • PiiMatrix< int > * solution = 0
  • PiiMatrix< typename Matrix::value_type > * duals = 0
)

Solves the linear assignment problem.

PII_OPTIMIZATION_EXPORT PiiMatrix< double >
(
  • const GradientFunction< double > * function
  • const PiiMatrix< double > & initialParams
  • double epsG = 1e-8
  • double epsF = 1e-8
  • double epsX = 1e-8
  • int maxIterations = 100
)

The Broyden-Fletcher-Goldfarb-Shanno (BFGS) method is a method to solve an unconstrained nonlinear optimization problem.

PII_OPTIMIZATION_EXPORT PiiMatrix< double >
(
  • 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
)

The Levenberg-Marquardt is a method of non-linear optimization.

Function details

  • template<class Matrix>

    Matrix::value_type assign

    (
    • const PiiRandomAccessMatrix & cost
    • PiiMatrix< int > * solution = 0
    • PiiMatrix< typename Matrix::value_type > * duals = 0
    )

    #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.

Notes (0)

Add a note

Not a single note added yet. Be the first, add yours.