cutting_plane.hpp File Reference

Cutting-plane methods for convex feasibility and optimization. More...

#include <cassert>
#include <cmath>
#include <tuple>
#include <type_traits>
#include "ell_config.hpp"
#include "half_nonnegative.hpp"

Include dependency graph for cutting_plane.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	OptimQState< A >
	State machine for the discrete cutting-plane method. More...
class	BSearchAdaptor< Oracle, Space >
	Binary search adaptor wrapping a cutting-plane feasibility oracle. More...

Typedefs
template<typename S >
using	CuttingPlaneArrayType = typename std::remove_reference_t< S >::ArrayType

Functions
template<typename T > requires std::is_floating_point_v<T>
auto	invalid_value () -> T
	Return an invalid/sentinel value for type T.
template<typename T >
auto	invalid_value () -> T requires(!std::is_floating_point_v< T >)
	Return an invalid/sentinel value for non-floating-point types.
template<typename O , typename S > requires OracleFeas<O, typename S::ArrayType> && SearchSpace<S>
auto	cutting_plane_feas (O &omega, S &space, const Options &options=Options()) -> std::tuple< CuttingPlaneArrayType< S >, size_t >
	Find a point in a convex set (defined through a cutting-plane oracle).
template<typename O , typename S , typename N > requires OracleOptim<O, typename S::ArrayType, N> && SearchSpace<S>
auto	cutting_plane_optim (O &omega, S &space, N &gamma, const Options &options=Options()) -> std::tuple< CuttingPlaneArrayType< S >, size_t >
	Cutting-plane method for solving convex problem.
template<typename O , typename S , typename N > requires OracleOptimQ<O, typename S::ArrayType, N> && SearchSpace<S>
auto	cutting_plane_optim_q (O &omega, S &space_q, N &gamma, const Options &options=Options()) -> std::tuple< CuttingPlaneArrayType< S >, size_t >
	Cutting-plane method for solving convex discrete optimization problem.
template<typename O , typename T > requires OracleBS<O, T>
auto	bsearch (O &omega, const std::pair< T, T > &intvl, const Options &options=Options()) -> std::tuple< T, size_t >
	Binary search using a cutting-plane oracle.

Detailed Description

Cutting-plane methods for convex feasibility and optimization.

Typedef Documentation

CuttingPlaneArrayType

template<typename S >

using CuttingPlaneArrayType = typename std::remove_reference_t<S>::ArrayType

Function Documentation

bsearch()

template<typename O , typename T >
requires OracleBS<O, T>

auto bsearch ( O &  omega, const std::pair< T, T > &  intvl, const Options &  options = Options()  ) -> std::tuple<T, size_t>

inline

Binary search using a cutting-plane oracle.

Assumes monotone feasibility: if gamma is feasible, all larger values are also feasible. Narrows the interval [lower, upper] containing the threshold value.

Template Parameters

O	Oracle type satisfying OracleBS concept
T	Numeric type for the search parameter

Parameters

[in,out]	omega	Oracle for feasibility assessment
[in]	intvl	Initial interval [lower, upper] containing the threshold
[in]	options	Maximum iterations and tolerance

Returns

Tuple (threshold, num_iterations)

cutting_plane_feas()

template<typename O , typename S >
requires OracleFeas<O, typename S::ArrayType> && SearchSpace<S>

auto cutting_plane_feas ( O &  omega, S &  space, const Options &  options = Options()  ) -> std::tuple<CuttingPlaneArrayType<S>, size_t>

inline

Find a point in a convex set (defined through a cutting-plane oracle).

The cutting_plane_feas function implements the cutting-plane method for solving a convex feasibility problem:

\[ \mathop{\text{find}} x \quad \text{s.t.} \quad f(x) \le 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.

Note

Strategy pattern: cutting_plane_feas is the algorithm Context; the separation oracle O is the Strategy, injected as a template parameter and constrained by the OracleFeas concept. Swap oracles without touching this driver. The Context drives the Strategy via omega.assess_feas(space.xc()) and the Space side via space.update_bias_cut(*cut).

Template Parameters

OracleFeas
SearchSpace

Parameters

[in,out]	omega	perform assessment on x0
[in,out]	space	search Space containing x*
[in]	options	maximum iteration and error tolerance etc.

Returns

Information of Cutting-plane method

cutting_plane_optim()

template<typename O , typename S , typename N >
requires OracleOptim<O, typename S::ArrayType, N> && SearchSpace<S>

auto cutting_plane_optim ( O &  omega, S &  space, N &  gamma, const Options &  options = Options()  ) -> std::tuple<CuttingPlaneArrayType<S>, size_t>

inline

Cutting-plane method for solving convex problem.

The cutting_plane_optim function implements the cutting-plane method for solving a convex optimization problem:

\[ \min \; \gamma \quad \text{s.t.} \quad f(x, \gamma) \le 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.

Template Parameters

OracleOptim
SearchSpace
Num

Parameters

[in,out]	omega	perform assessment on x0
[in,out]	space	search Space containing x*
[in,out]	gamma	best-so-far optimal sol'n
[in]	options	maximum iteration and error tolerance etc.

Returns

Information of Cutting-plane method

cutting_plane_optim_q()

template<typename O , typename S , typename N >
requires OracleOptimQ<O, typename S::ArrayType, N> && SearchSpace<S>

auto cutting_plane_optim_q ( O &  omega, S &  space_q, N &  gamma, const Options &  options = Options()  ) -> std::tuple<CuttingPlaneArrayType<S>, size_t>

inline

Cutting-plane method for solving convex discrete optimization problem.

The cutting_plane_optim_q function implements the cutting-plane method for solving a discrete convex optimization problem:

\[ \min \; \gamma \quad \text{s.t.} \quad f(x, \gamma) \le 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 Parameters

OracleOptimQ
SearchSpaceQ
Num

Parameters

[in,out]	omega	perform assessment on x0
[in,out]	space_q	search Space containing x*
[in,out]	gamma	best-so-far optimal sol'n
[in]	options	maximum iteration and error tolerance etc.

Returns

Information of Cutting-plane method

invalid_value() [1/2]

template<typename T >
requires std::is_floating_point_v<T>

auto invalid_value ( ) -> T

inline

Return an invalid/sentinel value for type T.

For floating-point types, returns NaN. For non-floating-point types, returns a default-constructed T.

Template Parameters

T	The type of the invalid value

Returns

T The sentinel invalid value

invalid_value() [2/2]

template<typename T >

auto invalid_value ( ) -> T requires(!std::is_floating_point_v<T>)

inline

Return an invalid/sentinel value for non-floating-point types.

Template Parameters

T	The type (must not be floating-point)

Returns

T Default-constructed T{}