ChebyshevOracle Class Reference

Oracle for the Chebyshev center of a polyhedron. More...

#include <chebyshev_oracle.hpp>

Public Types
using	Vec = std::valarray< double >
using	ArrayType = Vec
using	Cut = std::pair< Vec, double >

Public Member Functions
	ChebyshevOracle (const std::vector< Vec > &A, const Vec &b)
	Construct from halfspace data.
	ChebyshevOracle (const ChebyshevOracle &)=delete
auto	operator= (const ChebyshevOracle &) -> ChebyshevOracle &=delete
	ChebyshevOracle (ChebyshevOracle &&)=delete
auto	operator= (ChebyshevOracle &&) -> ChebyshevOracle &=delete
	~ChebyshevOracle ()=default
auto	assess_optim (const Vec &xc, double &gamma) -> std::tuple< Cut, bool >
	Assess feasibility and optimality at a candidate point.

Detailed Description

Oracle for the Chebyshev center of a polyhedron.

Given a polyhedron P = {u ∈ R^n : A u ≤ b}, find the largest Euclidean ball B(x, r) = {u : ‖u − x‖₂ ≤ r} contained in P:

max     r
s.t.    aᵢᵀx + ‖aᵢ‖₂ r ≤ bᵢ,   i = 1, …, m,

with design variables (x, r) ∈ R^{n+1}.

Every constraint is affine in (x, r) with a constant gradient (aᵢ, ‖aᵢ‖₂), so each violated halfspace yields a perfect cutting plane; the objective is linear, so the optimality cut is trivial. This makes the problem an ideal showcase for the cutting-plane method.

Note

Strategy pattern: constraints are scanned cyclically via a RoundRobin counter (mirroring ProfitOracle).

Member Typedef Documentation

ArrayType

using ChebyshevOracle::ArrayType = Vec

Cut

using ChebyshevOracle::Cut = std::pair<Vec, double>

Vec

using ChebyshevOracle::Vec = std::valarray<double>

Constructor & Destructor Documentation

ChebyshevOracle() [1/3]

ChebyshevOracle::ChebyshevOracle ( const std::vector< Vec > &  A, const Vec &  b  )

inline

Construct from halfspace data.

Parameters

[in]	A	m×n matrix; row i is the normal aᵢ.
[in]	b	offsets bᵢ (length m).

ChebyshevOracle() [2/3]

ChebyshevOracle::ChebyshevOracle ( const ChebyshevOracle &  )

delete

ChebyshevOracle() [3/3]

ChebyshevOracle::ChebyshevOracle ( ChebyshevOracle &&  )

delete

~ChebyshevOracle()

ChebyshevOracle::~ChebyshevOracle ( )

default

Member Function Documentation

assess_optim()

auto ChebyshevOracle::assess_optim ( const Vec &  xc, double &  gamma  ) -> std::tuple<Cut, bool>

inline

Assess feasibility and optimality at a candidate point.

Parameters

[in]	xc	candidate point (x, r); length n + 1.
[in,out]	gamma	best-so-far objective value (radius).

Returns

(cut, shrunk): the cutting plane, and whether gamma improved.

operator=() [1/2]

auto ChebyshevOracle::operator= ( ChebyshevOracle &&  ) -> ChebyshevOracle &=delete

delete

operator=() [2/2]

auto ChebyshevOracle::operator= ( const ChebyshevOracle &  ) -> ChebyshevOracle &=delete

delete

---

The documentation for this class was generated from the following file:

• ellalgo/oracles/chebyshev_oracle.hpp