cutting_plane.hpp file
Classes
-
template<typename Oracle, typename Space>class BSearchAdaptor
Typedefs
-
template<typename SearchSpace>using CuttingPlaneArrayType = typename std::remove_reference<SearchSpace>::type::
ArrayType
Functions
-
template<typename T>auto invalid_value() -> typename std::enable_if< std::is_floating_point< T >::value, T >::type -> auto
-
template<typename OracleFeas, typename SearchSpace>auto cutting_plane_feas(OracleFeas& omega, SearchSpace& space, const Options& options = Options()) -> std::tuple< CuttingPlaneArrayType< SearchSpace >, size_t > -> auto
- Find a point in a convex set (defined through a cutting-plane oracle).
-
template<typename OracleOptim, typename SearchSpace, typename Num>auto cutting_plane_optim(OracleOptim& omega, SearchSpace& space, Num& gamma, const Options& options = Options()) -> std::tuple< CuttingPlaneArrayType< SearchSpace >, size_t > -> auto
- Cutting-plane method for solving convex problem.
-
template<typename OracleOptimQ, typename SearchSpaceQ, typename Num>auto cutting_plane_optim_q(OracleOptimQ& omega, SearchSpaceQ& space_q, Num& gamma, const Options& options = Options()) -> std::tuple< CuttingPlaneArrayType< SearchSpaceQ >, size_t > -> auto
- Cutting-plane method for solving convex discrete optimization problem.
-
template<typename Oracle, typename T>auto bsearch(Oracle& omega, const std::pair<T, T>& intvl, const Options& options = Options()) -> std::tuple< T, size_t > -> auto
Function documentation
template<typename OracleFeas, typename SearchSpace>
auto cutting_plane_feas(OracleFeas& omega,
SearchSpace& space,
const Options& options = Options()) -> std::tuple< CuttingPlaneArrayType< SearchSpace >, size_t >
Find a point in a convex set (defined through a cutting-plane oracle).
| Template parameters | |
|---|---|
| OracleFeas | |
| SearchSpace | |
| Parameters | |
| omega in/out | perform assessment on x0 |
| space in/out | search Space containing x* |
| options in | maximum iteration and error tolerance etc. |
| Returns | Information of Cutting-plane method |
The cutting_plane_feas function implements the cutting-plane method for solving a convex feasibility problem:
find x s.t. f(x) <= 0,
It takes a cutting-plane oracle omega, a search space space, and an options object as input. A function f(x) is convex if there always exist a g(x) such that f(z) >= f(x) + g(x)' * (z - x), forall z, x in dom f. Note that dom f does not need to be a convex set in our definition. The affine function g' (x - xc) + beta is called a cutting-plane, or a `‘cut’' for short.
A separation oracle asserts that an evalution point xc is feasible, or provide a cut that separates the feasible region and xc.
template<typename OracleOptim, typename SearchSpace, typename Num>
auto cutting_plane_optim(OracleOptim& omega,
SearchSpace& space,
Num& gamma,
const Options& options = Options()) -> std::tuple< CuttingPlaneArrayType< SearchSpace >, size_t >
Cutting-plane method for solving convex problem.
| Template parameters | |
|---|---|
| OracleOptim | |
| SearchSpace | |
| Num | |
| Parameters | |
| omega in/out | perform assessment on x0 |
| space in/out | search Space containing x* |
| gamma in/out | best-so-far optimal sol'n |
| options in | maximum iteration and error tolerance etc. |
| Returns | Information of Cutting-plane method |
The cutting_plane_optim function implements the cutting-plane method for solving a convex optimization problem:
min gamma s.t. f(x, gamma) <= 0, x \in R
It takes a cutting-plane oracle omega, a search space space, and an options object as input. A function f(x) is convex if there always exist a g(x) such that f(z) >= f(x) + g(x)' * (z - x), forall z, x in dom f. Note that dom f does not need to be a convex set in our definition. The affine function g' (x - xc) + beta is called a cutting-plane, or a `‘cut’' for short.
template<typename OracleOptimQ, typename SearchSpaceQ, typename Num>
auto cutting_plane_optim_q(OracleOptimQ& omega,
SearchSpaceQ& space_q,
Num& gamma,
const Options& options = Options()) -> std::tuple< CuttingPlaneArrayType< SearchSpaceQ >, size_t >
Cutting-plane method for solving convex discrete optimization problem.
| Template parameters | |
|---|---|
| OracleOptimQ | |
| SearchSpaceQ | |
| Num | |
| Parameters | |
| omega in/out | perform assessment on x0 |
| space_q | |
| gamma in/out | best-so-far optimal sol'n |
| options in | maximum iteration and error tolerance etc. |
| Returns | Information of Cutting-plane method |
The cutting_plane_optim_q function implements the cutting-plane method for solving a discrete convex optimization problem:
min gamma s.t. f(x, gamma) <= 0, x \in D
It takes a cutting-plane oracle omega, a search space space, and an options object as input. A function f(x) is convex if there always exist a g(x) such that f(z) >= f(x) + g(x)' * (z - x), forall z, x in dom f. Note that dom f does not need to be a convex set in our definition. The affine function g' (x - xc) + beta is called a cutting-plane, or a `‘cut’' for short.
template<typename Oracle, typename T>
auto bsearch(Oracle& omega,
const std::pair<T, T>& intvl,
const Options& options = Options()) -> std::tuple< T, size_t >
| Template parameters | |
|---|---|
| Oracle | |
| T | |
| Parameters | |
| omega in/out | perform assessment on x0 |
| intvl in/out | interval containing x* |
| options in | maximum iteration and error tolerance etc. |
| Returns | CInfo |