mlpack
Public Member Functions | List of all members
FrankWolfe< LinearConstrSolverType, UpdateRuleType > Class Template Reference

Frank-Wolfe is a technique to minimize a continuously differentiable convex function $ f $ over a compact convex subset $ D $ of a vector space. More...

Public Member Functions

 FrankWolfe (const LinearConstrSolverType linearConstrSolver, const UpdateRuleType updateRule, const size_t maxIterations=100000, const double tolerance=1e-10)
 Construct the Frank-Wolfe optimizer with the given function and parameters. More...

 
const LinearConstrSolverType & LinearConstrSolver () const
 Get the linear constrained solver. More...

 
LinearConstrSolverType & LinearConstrSolver ()
 Modify the linear constrained solver. More...

 
size_t MaxIterations () const
 Get the maximum number of iterations (0 indicates no limit). More...

 
size_t & MaxIterations ()
 Modify the maximum number of iterations (0 indicates no limit). More...

 
template
<
typename
FunctionType
>
double Optimize (FunctionType &function, arma::mat &iterate)
 Optimize the given function using FrankWolfe. More...

 
double Tolerance () const
 Get the tolerance for termination. More...

 
double & Tolerance ()
 Modify the tolerance for termination. More...

 
const UpdateRuleType & UpdateRule () const
 Get the update rule. More...

 
UpdateRuleType & UpdateRule ()
 Modify the update rule. More...

 

Detailed Description


template
<
typename
LinearConstrSolverType
,
typename
UpdateRuleType
>

class mlpack::optimization::FrankWolfe< LinearConstrSolverType, UpdateRuleType >

Frank-Wolfe is a technique to minimize a continuously differentiable convex function $ f $ over a compact convex subset $ D $ of a vector space.

It is also known as conditional gradient method.

To find minimum of a function using Frank-Wolfe in each iteration $ k $:

  1. One optimize the linearized constrained problem, using LinearConstrSolver:

    \[ s_k:= arg\min_{s\in D} <s_k, \nabla f(x_k)> \]

  2. Update $ x $ using UpdateRule:

    \[ x_{k+1} := (1-\gamma) x_k + \gamma s_k \]

    for some $ \gamma \in (0, 1) $, or use Fully-Corrective Variant:

    \[ x_{k+1}:= arg\min_{x\in conv(s_0, \cdots, s_k)} f(x) \]

The algorithm continues until $ k $ reaches the maximum number of iterations, or when the duality gap is bounded by a certain tolerance $ \epsilon $. That is,

\[ g(x):= \max_{s\in D} <x-s, \nabla f(x)> \quad \leq \epsilon, \]

we also know that $ g(x) \geq f(x) - f(x^*) $, where $ x^* $ is the optimal solution.

The parameter $ \epsilon $ is specified by the tolerance parameter to the constructor.

For FrankWolfe to work, LinearConstrSolverType and UpdateRuleType template parameters are required. These classes must implement the following functions:

LinearConstrSolverType:

void Optimize(const arma::mat& gradient, arma::mat& s);

UpdateRuleType:

void Update(const arma::mat& old_coords, const arma::mat& s, arma::mat& new_coords, const size_t num_iter);

Template Parameters
LinearConstrSolverTypeSolver for the linear constrained problem.
UpdateRuleTypeRule to update the solution in each iteration.

Definition at line 81 of file frank_wolfe.hpp.

Constructor & Destructor Documentation

◆ FrankWolfe()

FrankWolfe ( const LinearConstrSolverType  linearConstrSolver,
const UpdateRuleType  updateRule,
const size_t  maxIterations = 100000,
const double  tolerance = 1e-10 
)

Construct the Frank-Wolfe optimizer with the given function and parameters.

Notice that the constraint domain $ D $ is input at the initialization of linear_constr_solver, the function to be optimized is stored in update_rule.

Parameters
linearConstrSolverSolver for linear constrained problem.
updateRuleRule for updating solution in each iteration.
maxIterationsMaximum number of iterations allowed (0 means no limit).
toleranceMaximum absolute tolerance to terminate algorithm.

Member Function Documentation

◆ LinearConstrSolver() [1/2]

const LinearConstrSolverType& LinearConstrSolver ( ) const
inline

Get the linear constrained solver.

Definition at line 121 of file frank_wolfe.hpp.

◆ LinearConstrSolver() [2/2]

LinearConstrSolverType& LinearConstrSolver ( )
inline

Modify the linear constrained solver.

Definition at line 124 of file frank_wolfe.hpp.

◆ MaxIterations() [1/2]

size_t MaxIterations ( ) const
inline

Get the maximum number of iterations (0 indicates no limit).

Definition at line 132 of file frank_wolfe.hpp.

◆ MaxIterations() [2/2]

size_t& MaxIterations ( )
inline

Modify the maximum number of iterations (0 indicates no limit).

Definition at line 134 of file frank_wolfe.hpp.

◆ Optimize()

double Optimize ( FunctionType &  function,
arma::mat &  iterate 
)

Optimize the given function using FrankWolfe.

The given starting point will be modified to store the finishing point of the algorithm, the final objective value is returned.

FunctionType template class must provide the following functions:

double Evaluate(const arma::mat& coordinates); void Gradient(const arma::mat& coordinates, arma::mat& gradient);

Parameters
functionFunction to be optimized.
iterateInput with starting point, and will be modified to save the output optimial solution coordinates.
Returns
Objective value at the final solution.

◆ Tolerance() [1/2]

double Tolerance ( ) const
inline

Get the tolerance for termination.

Definition at line 137 of file frank_wolfe.hpp.

◆ Tolerance() [2/2]

double& Tolerance ( )
inline

Modify the tolerance for termination.

Definition at line 139 of file frank_wolfe.hpp.

◆ UpdateRule() [1/2]

const UpdateRuleType& UpdateRule ( ) const
inline

Get the update rule.

Definition at line 127 of file frank_wolfe.hpp.

◆ UpdateRule() [2/2]

UpdateRuleType& UpdateRule ( )
inline

Modify the update rule.

Definition at line 129 of file frank_wolfe.hpp.

The documentation for this class was generated from the following file:
  • /home/ryan/src/mlpack.org/_src/mlpack-3.0.4/src/mlpack/core/optimizers/fw/frank_wolfe.hpp