- Generated by
1.8.13
|
Turi Create
4.0
|
#include <ml/optimization/constraint_interface.hpp>
Public Member Functions | |
| virtual | ~constraint_interface () |
| virtual void | project (DenseVector &point) const =0 |
| virtual void | project_block (DenseVector &point, const size_t block_start, const size_t block_size) const =0 |
| virtual bool | is_satisfied (const DenseVector &point) const =0 |
| virtual double | first_order_optimality_conditions (const DenseVector &point, const DenseVector &gradient) const =0 |
Interface for constraints for Gradient Projection solvers. See chapter 12 of (1) for an intro to constrained optimization.
Some implementations are based on Section 16.7 of (1).
Gradient project methods are methods for solving bound constrained optimization problems.
Traditionally, in unconstrained optimization, we solve the problem f(x) using a gradient descent method as follows:
x_{k+1} = x_{k} - \alpha_k \grad f(x_k) (G)
where is a step size.
The gradient-projection framework performs solves the problem: {x C} f(x) using a slight modification to the gradient step in (G)
x_{k+1} = P_C(x_{k} - \alpha_k \grad f(x_k)) (PG)
where P_C is the projection of a point on to the convex set.
P_C(z) = \min_{x \in z} ||x-z||^2
which works out to be the closest point to the set in C.
In solving bound constrained optimization problems, active set methods face criticism because the working set changes slowly; at each iteration, at most one constraint is added to or dropped from the working set. If there are k0 constraints active at the initial W0, but kθ constraints active at the solution, then at least |kθ−k0| iterations are required for convergence. This property can be a serious disadvantage in large problems if the working set at the starting point is vastly different from the active set at the solution.
The gradient-projection method is guaranteed to identify the active set at a solution in a finite number of iterations. After it has identified the correct active set, the gradient-projection algorithm reduces to the steepest-descent algorithm on the subspace of free variables.
References:
(1) Wright S.J and J. Nocedal. Numerical optimization. Vol. 2. New York: Springer, 1999. (Chapter 12)
Definition at line 93 of file constraint_interface.hpp.
|
inlinevirtual |
Default desctuctor.
Definition at line 100 of file constraint_interface.hpp.
|
pure virtual |
A measure of the first order optimality conditions.
| [in] | point | Point which we are querying. |
| [in] | gradient | Gradient at that point for a given function |
If you don't know what to do, then use ||P_C(x - grad) - x|| where x is the point, grad is the gradient and P_C is the projection to the set in consideration.
Implemented in turi::optimization::box_constraints.
|
pure virtual |
Boolean function to determine if a dense point is present in a constraint space.
| [in] | point | Point which we are querying. |
Implemented in turi::optimization::box_constraints.
|
pure virtual |
Project a dense point into the constraint space.
| [in,out] | point | Point which we are using to project the point. |
Given a convex set X, the projection operator is given by
P(y) = \min_{x \in X} || x - y ||^2
Implemented in turi::optimization::box_constraints.
|
pure virtual |
Project a dense a block of co-ordinates point into the constraint space.
| [in,out] | point | A block project the point. |
| [in] | block_start | Start index of the block |
| [in] | block_size | Size of the block |
Given a convex set X, the projection operator is given by
P(y) = \min_{x \in X} || x - y ||^2
Implemented in turi::optimization::box_constraints.
1.8.13