Examplesbfgs_search_strategy
This object represents a strategy for determining which direction a line search should be carried out along. This particular object is an implementation of the BFGS quasi-newton method for determining this direction.
This method uses an amount of memory that is quadratic in the number of variables to be optimized. It is generally very effective but if your problem has a very large number of variables then it isn't appropriate. Instead, you should try the lbfgs_search_strategy.
Specification: dlib/optimization/optimization_search_strategies_abstract.h
File to include: dlib/optimization.h
Code Examples: 1
cg_search_strategy
This object represents a strategy for determining which direction a line search should be carried out along. This particular object is an implementation of the Polak-Ribiere conjugate gradient method for determining this direction.
This method uses an amount of memory that is linear in the number of variables to be optimized. So it is capable of handling problems with a very large number of variables. However, it is generally not as good as the L-BFGS algorithm (see the lbfgs_search_strategy class).
Specification: dlib/optimization/optimization_search_strategies_abstract.h
File to include: dlib/optimization.h
Code Examples: 1
derivative
This is a function that takes another function as input and returns a function object that numerically computes the derivative of the input function.
Specification: dlib/optimization/optimization_abstract.h
File to include: dlib/optimization.h
find_max
Performs an unconstrained maximization of a nonlinear function using some search strategy (e.g. bfgs_search_strategy).
Specification: dlib/optimization/optimization_abstract.h
File to include: dlib/optimization.h
find_max_bobyqa
This function is identical to the find_min_bobyqa routine except that it negates the objective function before performing optimization. Thus this function will attempt to find the maximizer of the objective rather than the minimizer.
Note that BOBYQA only works on functions of two or more variables. So if you need to perform derivative-free optimization on a function of a single variable then you should use the find_max_single_variable function.
Specification: dlib/optimization/optimization_bobyqa_abstract.h
File to include: dlib/optimization.h
Code Examples: 1, 2
find_max_factor_graph_nmplp
This function is a tool for approximately solving the MAP problem in a graphical model or factor graph with pairwise potential functions. That is, it attempts to solve a certain kind of optimization problem which can be defined as follows:
maximize: f(X) where X is a set of integer valued variables and f(X) can be written as the sum of functions which each involve only two variables from X.
This function is an implementation of the NMPLP algorithm introduced in the following paper:
Fixing Max-Product: Convergent Message Passing Algorithms for MAP LP-Relaxations by Amir Globerson and Tommi Jaakkola
Specification: dlib/optimization/find_max_factor_graph_nmplp_abstract.h
File to include: dlib/optimization.h
find_max_factor_graph_viterbi
This function is a tool for exactly solving the MAP problem in a chain-structured graphical model or factor graph. In particular, it is an implementation of the classic Viterbi algorithm for finding the maximizing assignment. In addition to basic first order Markov models, this function is also capable of finding the MAP assignment for higher order Markov models.
Specification: dlib/optimization/find_max_factor_graph_viterbi_abstract.h
File to include: dlib/optimization.h
find_max_single_variable
Performs a bound constrained maximization of a nonlinear function. The function must be of a single variable. Derivatives are not required.
Specification: dlib/optimization/optimization_line_search_abstract.h
File to include: dlib/optimization.h
find_max_trust_region
Performs an unconstrained maximization of a nonlinear function using a trust region method.
Specification: dlib/optimization/optimization_trust_region_abstract.h
File to include: dlib/optimization.h
find_max_using_approximate_derivatives
Performs an unconstrained maximization of a nonlinear function using some search strategy (e.g. bfgs_search_strategy). This version doesn't take a gradient function but instead numerically approximates the gradient.
Specification: dlib/optimization/optimization_abstract.h
File to include: dlib/optimization.h
find_min
Performs an unconstrained minimization of a nonlinear function using some search strategy (e.g. bfgs_search_strategy).
Specification: dlib/optimization/optimization_abstract.h
File to include: dlib/optimization.h
Code Examples: 1
find_min_bobyqa
This function defines the dlib interface to the BOBYQA software developed by M.J.D Powell. BOBYQA is a method for optimizing a function in the absence of derivative information. Powell described it as a method that seeks the least value of a function of many variables, by applying a trust region method that forms quadratic models by interpolation. There is usually some freedom in the interpolation conditions, which is taken up by minimizing the Frobenius norm of the change to the second derivative of the model, beginning with the zero matrix. The values of the variables are constrained by upper and lower bounds.
The following paper, published in 2009 by Powell, describes the detailed working of the BOBYQA algorithm.
The BOBYQA algorithm for bound constrained optimization without derivatives by M.J.D. Powell
Note that BOBYQA only works on functions of two or more variables. So if you need to perform derivative-free optimization on a function of a single variable then you should use the find_min_single_variable function.
Specification: dlib/optimization/optimization_bobyqa_abstract.h
File to include: dlib/optimization.h
Code Examples: 1, 2
find_min_single_variable
Performs a bound constrained minimization of a nonlinear function. The function must be of a single variable. Derivatives are not required.
Specification: dlib/optimization/optimization_line_search_abstract.h
File to include: dlib/optimization.h
find_min_trust_region
Performs an unconstrained minimization of a nonlinear function using a trust region method.
Specification: dlib/optimization/optimization_trust_region_abstract.h
File to include: dlib/optimization.h
find_min_using_approximate_derivatives
Performs an unconstrained minimization of a nonlinear function using some search strategy (e.g. bfgs_search_strategy). This version doesn't take a gradient function but instead numerically approximates the gradient.
Specification: dlib/optimization/optimization_abstract.h
File to include: dlib/optimization.h
Code Examples: 1
gradient_norm_stop_strategy
This object represents a strategy for deciding if an optimization algorithm should terminate. This particular object looks at the norm (i.e. the length) of the current gradient vector and stops if it is smaller than a user given threshold.
Specification: dlib/optimization/optimization_stop_strategies_abstract.h
File to include: dlib/optimization.h
lagrange_poly_min_extrap
This function finds the second order polynomial that interpolates a set of points and returns you the minimum of that polynomial.
Specification: dlib/optimization/optimization_line_search_abstract.h
File to include: dlib/optimization.h
lbfgs_search_strategy
This object represents a strategy for determining which direction a line search should be carried out along. This particular object is an implementation of the L-BFGS quasi-newton method for determining this direction.
This method uses an amount of memory that is linear in the number of variables to be optimized. This makes it an excellent method to use when an optimization problem has a large number of variables.
Specification: dlib/optimization/optimization_search_strategies_abstract.h
File to include: dlib/optimization.h
Code Examples: 1
line_search
Performs a gradient based line search on a given function and returns the input that makes the function significantly smaller.
Specification: dlib/optimization/optimization_line_search_abstract.h
File to include: dlib/optimization.h
make_line_search_function
This is a function that takes another function f(x) as input and returns a function object l(z) = f(start + z*direction). It is useful for turning multi-variable functions into single-variable functions for use with the line_search routine.
Specification: dlib/optimization/optimization_line_search_abstract.h
File to include: dlib/optimization.h
max_cost_assignment
This function is an implementation of the Hungarian algorithm (also know as the Kuhn-Munkres algorithm). It solves the optimal assignment problem. For example, suppose you have an equal number of workers and jobs and you need to decide which workers to assign to which jobs. Some workers are better at certain jobs than others. So you would like to find out how to assign them all to jobs such that overall productivity is maximized. You can use this routine to solve this problem and others like it.
Note that dlib also contains a machine learning method for learning the cost function needed to use the Hungarian algorithm.
Specification: dlib/optimization/max_cost_assignment_abstract.h
File to include: dlib/optimization.h
max_sum_submatrix
This function finds the submatrix within a user supplied matrix which has the largest sum. It then zeros out that submatrix and repeats the process until no more maximal submatrices can be found.
Specification: dlib/optimization/max_sum_submatrix_abstract.h
File to include: dlib/optimization.h
negate_function
This is a function that takes another function as input and returns a function object that computes the negation of the input function.
Specification: dlib/optimization/optimization_abstract.h
File to include: dlib/optimization.h
newton_search_strategy
This object represents a strategy for determining which direction a line search should be carried out along. This particular routine is an implementation of the newton method for determining this direction. That means using it requires you to supply a method for creating hessian matrices for the problem you are trying to optimize.
Note also that this is actually a helper function for creating newton_search_strategy_obj objects.
Specification: dlib/optimization/optimization_search_strategies_abstract.h
File to include: dlib/optimization.h
objective_delta_stop_strategy
This object represents a strategy for deciding if an optimization algorithm should terminate. This particular object looks at the change in the objective function from one iteration to the next and bases its decision on how large this change is. If the change is below a user given threshold then the search stops.
Specification: dlib/optimization/optimization_stop_strategies_abstract.h
File to include: dlib/optimization.h
Code Examples: 1
oca
This object is a tool for solving the following optimization problem:
Minimize: f(w) == 0.5*dot(w,w) + C*R(w) Where R(w) is a user-supplied convex function and C > 0
For a detailed discussion you should consult the following papers from the Journal of Machine Learning Research:
Optimized Cutting Plane Algorithm for Large-Scale Risk Minimization by Vojtech Franc, Soren Sonnenburg; 10(Oct):2157--2192, 2009.
Bundle Methods for Regularized Risk Minimization by Choon Hui Teo, S.V.N. Vishwanthan, Alex J. Smola, Quoc V. Le; 11(Jan):311-365, 2010.
Specification: dlib/optimization/optimization_oca_abstract.h
File to include: dlib/optimization.h
poly_min_extrap
This function finds the 3rd degree polynomial that interpolates a set of points and returns you the minimum of that polynomial.
Specification: dlib/optimization/optimization_line_search_abstract.h
File to include: dlib/optimization.h
solve_least_squares
This is a function for solving non-linear least squares problems. It uses a method which combines the traditional Levenberg-Marquardt technique with a quasi-newton approach. It is appropriate for large residual problems (i.e. problems where the terms in the least squares function, the residuals, don't go to zero but remain large at the solution)
Specification: dlib/optimization/optimization_least_squares_abstract.h
File to include: dlib/optimization.h
Code Examples: 1
solve_least_squares_lm
This is a function for solving non-linear least squares problems. It uses the traditional Levenberg-Marquardt technique. It is appropriate for small residual problems (i.e. problems where the terms in the least squares function, the residuals, go to zero at the solution)
Specification: dlib/optimization/optimization_least_squares_abstract.h
File to include: dlib/optimization.h
Code Examples: 1
solve_qp2_using_smo
This function solves the following quadratic program:
Minimize: f(alpha) == 0.5*trans(alpha)*Q*alpha
subject to the following constraints:
sum(alpha) == nu*y.size()
0 <= min(alpha) && max(alpha) <= 1
trans(y)*alpha == 0
Where all elements of y must be equal to +1 or -1 and f is convex.
This means that Q should be symmetric and positive-semidefinite.
This object implements the strategy used by the LIBSVM tool. The following papers can be consulted for additional details:
- Chang and Lin, Training {nu}-Support Vector Classifiers: Theory and Algorithms
- Chih-Chung Chang and Chih-Jen Lin, LIBSVM : a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm
Specification: dlib/optimization/optimization_solve_qp2_using_smo_abstract.h
File to include: dlib/optimization.h
solve_qp3_using_smo
This function solves the following quadratic program:
Minimize: f(alpha) == 0.5*trans(alpha)*Q*alpha + trans(p)*alpha
subject to the following constraints:
for all i such that y(i) == +1: 0 <= alpha(i) <= Cp
for all i such that y(i) == -1: 0 <= alpha(i) <= Cn
trans(y)*alpha == B
Where all elements of y must be equal to +1 or -1 and f is convex.
This means that Q should be symmetric and positive-semidefinite.
This object implements the strategy used by the LIBSVM tool. The following papers can be consulted for additional details:
- Chih-Chung Chang and Chih-Jen Lin, LIBSVM : a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm
- Working Set Selection Using Second Order Information for Training Support Vector Machines by Fan, Chen, and Lin. In the Journal of Machine Learning Research 2005.
Specification: dlib/optimization/optimization_solve_qp3_using_smo_abstract.h
File to include: dlib/optimization.h
solve_qp_using_smo
This function solves the following quadratic program:
Minimize: f(alpha) == 0.5*trans(alpha)*Q*alpha - trans(alpha)*b
subject to the following constraints:
sum(alpha) == C
min(alpha) >= 0
Where f is convex. This means that Q should be symmetric and positive-semidefinite.
Specification: dlib/optimization/optimization_solve_qp_using_smo_abstract.h
File to include: dlib/optimization.h
solve_trust_region_subproblem
This function solves the following optimization problem:
Minimize: f(p) == 0.5*trans(p)*B*p + trans(g)*p subject to the following constraint: length(p) <= radius
Specification: dlib/optimization/optimization_trust_region_abstract.h
File to include: dlib/optimization.h