ellalgo package

Subpackages

Submodules

ellalgo.conjugate_gradient module

ellalgo.conjugate_gradient.conjugate_gradient(A, b, x0=None, tol=1e-05, max_iter=1000)[source]

Solve the linear system Ax = b using the Conjugate Gradient method.

The Conjugate Gradient method is an iterative algorithm for solving symmetric positive definite linear systems. It is particularly efficient for large, sparse systems.

Parameters:

  • A (numpy.ndarray) – The coefficient matrix (must be symmetric and positive definite).

  • b (numpy.ndarray) – The right-hand side vector.

  • x0 (numpy.ndarray, optional) – Initial guess for the solution (default is zero vector).

  • tol (float, optional) – Tolerance for convergence (default is 1e-5).

  • max_iter (int, optional) – Maximum number of iterations (default is 1000).

Returns:

The solution vector.

Return type:

numpy.ndarray

Raises:

ValueError – If the Conjugate Gradient method does not converge after the maximum number of iterations.

ellalgo.cutting_plane module

Cutting Plane Algorithm Implementation

This code implements various cutting plane algorithms, which are optimization techniques used to solve convex optimization problems. The main purpose of these algorithms is to find optimal or feasible solutions within a given search space.

The code defines several functions that take different inputs:

  1. cutting_plane_feas: Takes an oracle (a function that assesses feasibility), a search space, and options.

  2. cutting_plane_optim: Takes an optimization oracle, a search space, an initial best value (gamma), and options.

  3. cutting_plane_optim_q: Similar to cutting_plane_optim, but for quantized discrete optimization problems.

  4. bsearch: Performs a binary search using an oracle and an interval.

These functions generally output a solution (if found), the best value achieved, and the number of iterations performed.

The algorithms work by iteratively refining the search space. They start with an initial point and ask the oracle to assess it. The oracle either confirms the point is feasible/optimal or provides a “cut” - information about how to improve the solution. The search space is then updated based on this cut, and the process repeats until a solution is found or the maximum number of iterations is reached.

An important concept in these algorithms is the “cut”. A cut is like a hint that tells the algorithm which parts of the search space to exclude, helping it focus on more promising areas. The search space is continuously shrunk based on these cuts until a solution is found or the space becomes too small.

The code also includes a BSearchAdaptor class, which adapts a feasibility oracle to work with the binary search algorithm. This allows the binary search to be used in solving certain types of optimization problems.

Throughout the code, there’s a focus on handling different types of problems (feasibility, optimization, discrete optimization) and different types of search spaces. The algorithms are designed to be flexible and work with various problem types.

In summary, this code provides a toolkit for solving different types of optimization problems using cutting plane methods. It’s designed to be adaptable to various problem types and to efficiently search for solutions by iteratively refining the search space based on feedback from problem-specific oracles.

class ellalgo.cutting_plane.BSearchAdaptor(omega: ~ellalgo.ell_typing.OracleFeas2, space: ~ellalgo.ell_typing.SearchSpace2, options=<ellalgo.ell_config.Options object>)[source]

Bases: OracleBS

assess_bs(gamma: float | int) → bool[source]

The function assess_bs checks if a given value is the best-so-far optimal value.

Parameters:

gamma (Num) – Gamma is a float value representing the best-so-far optimal value

Returns:

The function assess_bs returns a boolean value.

property x_best: ArrayType

The x_best property returns the current best solution in the space object. :return: The x_best property returns an object of type ArrayType.

ellalgo.cutting_plane.bsearch(omega: ~ellalgo.ell_typing.OracleBS, intrvl: ~typing.Tuple[~typing.Any, ~typing.Any], options=<ellalgo.ell_config.Options object>) → Tuple[Any, int][source]

The bsearch function performs a binary search to find the optimal solution within a given interval.

Parameters:

  • omega (OracleBS) – The parameter omega is an instance of the OracleBS class. It represents an oracle that provides information about the feasibility of a given solution. The OracleBS class likely has a method called assess_bs that takes a solution as input and returns a boolean value.

  • intrvl (Tuple[Any, Any]) – The intrvl parameter is a tuple representing the interval within which the binary search will be performed. It consists of two elements: the lower bound and the upper bound of the interval.

  • options – The options parameter is an instance of the Options class. It is optional and has default values if not provided.

Returns:

The function bsearch returns a tuple containing three elements:

ellalgo.cutting_plane.cutting_plane_feas(omega: ~ellalgo.ell_typing.OracleFeas[~ellalgo.ell_typing.ArrayType], space: ~ellalgo.ell_typing.SearchSpace[~ellalgo.ell_typing.ArrayType], options=<ellalgo.ell_config.Options object>) → Tuple[ArrayType | None, int][source]

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

Description:

A function f(x) is convex if there always exist a g(x) such that f(z) >= f(x) + g(x)^T * (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^T (x - xc) + beta is called a cutting-plane, or a “cut” for short. This algorithm solves the following feasibility problem:

find x s.t. f(x) <= 0,

A separation oracle asserts that an evalution point x0 is feasible, or provide a cut that separates the feasible region and x0.

┌────────────┐ ┌───────────┐┌──────────┐ │CuttingPlane│ │SearchSpace││OracleFeas│ └─────┬──────┘ └─────┬─────┘└────┬─────┘ │ │ │ │ request xc │ │ │────────────────>│ │ │ │ │ │ return xc │ │ │<────────────────│ │ │ │ │ │ assess_feas(xc) │ │────────────────────────────>│ │ │ │ │ return cut │ │<────────────────────────────│ │ │ │ │update by the cut│ │ │────────────────>│ │ ┌─────┴──────┐ ┌─────┴─────┐┌────┴─────┐ │CuttingPlane│ │SearchSpace││OracleFeas│ └────────────┘ └───────────┘└──────────┘
Parameters:

  • omega (OracleFeas[ArrayType]) – The parameter omega is an instance of the OracleFeas class, which is responsible for performing assessments on a given point xinit. It provides information about the feasibility of xinit and returns a cutting-plane (or a “cut”) if xinit is not

  • space (SearchSpace[ArrayType]) – The space parameter represents the search space in which the algorithm is looking for a feasible solution. It is an instance of the SearchSpace class, which contains information about the current state of the search space, such as the current evaluation point xc() and the current trust region radius.

  • options – The options parameter is an instance of the Options class, which contains various options for the cutting-plane feasibility algorithm. It is optional and has default values if not provided

Returns:

The function cutting_plane_feas returns a tuple containing two elements: 1. An optional array (Optional[ArrayType]) representing a feasible solution. If no feasible solution is found, it returns None. 2. An integer representing the number of iterations performed.

ellalgo.cutting_plane.cutting_plane_optim(omega: ~ellalgo.ell_typing.OracleOptim[~ellalgo.ell_typing.ArrayType], space: ~ellalgo.ell_typing.SearchSpace[~ellalgo.ell_typing.ArrayType], gamma, options=<ellalgo.ell_config.Options object>) → Tuple[ArrayType | None, float, int][source]

Cutting-plane method for solving convex optimization problem

Parameters:

  • omega (OracleOptim[ArrayType]) – The omega parameter is an instance of the OracleOptim class, which is responsible for performing assessments on the initial solution xinit

  • space (SearchSpace[ArrayType]) – The space parameter represents the search space for the optimization problem. It is an instance of the SearchSpace class, which contains information about the feasible region and the current solution

  • gamma – The parameter gamma represents the initial best-so-far value in the cutting-plane optimization algorithm. It is used to keep track of the current best objective value found during the optimization process

  • options – The options parameter is an instance of the Options class, which contains various options for the cutting-plane optimization algorithm. It is optional and has default values if not provided

Returns:

The function cutting_plane_optim returns a tuple containing the following elements:

ellalgo.cutting_plane.cutting_plane_optim_q(omega: ~ellalgo.ell_typing.OracleOptimQ[~ellalgo.ell_typing.ArrayType], space_q: ~ellalgo.ell_typing.SearchSpaceQ[~ellalgo.ell_typing.ArrayType], gamma, options=<ellalgo.ell_config.Options object>) → Tuple[ArrayType | None, float, int][source]

Cutting-plane method for solving convex quantized discrete optimization problem

Parameters:

  • omega (OracleOptimQ[ArrayType]) – The omega parameter is an instance of the OracleOptimQ class, which is responsible for performing assessments on the initial solution xinit

  • space_q (SearchSpaceQ[ArrayType]) – The space_q parameter represents the search space for the discrete optimization problem. It is an instance of the SearchSpaceQ class, which contains the necessary methods and attributes to define and manipulate the search space

  • gamma – The parameter gamma represents the initial best-so-far value in the cutting-plane optimization algorithm. It is used to keep track of the current best solution found during the iterations of the algorithm

  • options – The options parameter is an instance of the Options class, which contains various settings for the cutting-plane optimization algorithm. It is optional and has default values if not provided

Returns:

a tuple containing the following elements: 1. Optional[ArrayType]: The optimal solution to the convex discrete optimization problem. It can be None if no solution is found. 2. float: The final best-so-far value. 3. int: The number of iterations performed.

ellalgo.ell module

Ell Class

This code defines a class called Ell which represents an ellipsoidal search space. The purpose of this class is to provide methods for updating and manipulating an ellipsoid, which is a mathematical shape used in certain optimization algorithms.

The Ell class takes two main inputs when initialized: a value (which can be a number or a list of numbers) and an array xc. These inputs define the initial shape and position of the ellipsoid. The class doesn’t produce a specific output on its own, but rather provides methods that can be used to modify and query the ellipsoid’s state.

The class achieves its purpose by maintaining several internal attributes that represent the ellipsoid’s properties, such as its center (_xc), a matrix (_mq), and scaling factors (_kappa and _tsq). It then provides methods to update these properties based on different types of “cuts” to the ellipsoid.

The main functionality of the Ell class revolves around three update methods: update_bias_cut, update_central_cut, and update_q. These methods take a “cut” as input, which is essentially a direction and a value that determine how to modify the ellipsoid. The cuts are used to shrink or reshape the ellipsoid, which is a key operation in certain optimization algorithms.

The core logic of these update methods is implemented in the private _update_core method. This method applies the cut to the ellipsoid by performing a series of mathematical operations. It calculates new values for the ellipsoid’s center and shape based on the input cut and a specified cut strategy.

An important aspect of the code is its use of numpy, a library for numerical computations in Python. The class uses numpy arrays and matrix operations to efficiently perform the necessary calculations.

The class also includes some helper methods like xc() and tsq() that allow access to certain properties of the ellipsoid. These can be used to query the current state of the ellipsoid during an optimization process.

Overall, this code provides a flexible and efficient way to represent and manipulate an ellipsoidal search space, which is a crucial component in certain types of optimization algorithms. The class encapsulates the complex mathematics involved in these operations, providing a clean interface for users of the class to work with ellipsoids in their algorithms.

class ellalgo.ell.Ell(val, xc: ArrayType)[source]

Bases: SearchSpace2[ArrayType], SearchSpaceQ[ArrayType]

helper: EllCalc
no_defer_trick: bool = False
set_xc(xc: ArrayType) → None[source]

The function sets the value of the variable _xc to the input x.

Parameters:

x (ArrayType) – The parameter x is of type ArrayType

tsq() → float[source]

The function tsq returns the measure of the distance between xc and x*. :return: The method is returning a float value, which represents the measure of the distance between xc and x*.

update_bias_cut(cut) → CutStatus[source]

The function update_bias_cut is an implementation of the SearchSpace interface that updates the ellipsoid based on a given deep-cut.

Parameters:

cut – The cut parameter is of type _type_ and it represents some kind of cut

Returns:

a CutStatus object.

Examples

>>> ell = Ell(1.0, [1.0, 1.0, 1.0, 1.0])
>>> cut = (np.array([1.0, 1.0, 1.0, 1.0]), 1.0)
>>> status = ell.update_bias_cut(cut)
>>> print(status)
CutStatus.Success
update_central_cut(cut) → CutStatus[source]

The function update_central_cut is an implementation of the SearchSpace interface that updates the ellipsoid based on a given central-cut.

Parameters:

cut – The cut parameter is of type _type_ and it represents a cut

Returns:

a CutStatus object.

Examples

>>> ell = Ell(1.0, [1.0, 1.0, 1.0, 1.0])
>>> cut = (np.array([1.0, 1.0, 1.0, 1.0]), 0.0)
>>> status = ell.update_central_cut(cut)
>>> print(status)
CutStatus.Success
update_q(cut) → CutStatus[source]

The function update_q is an implementation of the SearchSpaceQ interface that updates the ellipsoid based on a given non-central cut (deep or shallow).

Parameters:

cut – The cut parameter is of type _type_ and it represents the cut that needs to be updated

Returns:

a CutStatus object.

Examples

>>> ell = Ell(1.0, [1.0, 1.0, 1.0, 1.0])
>>> cut = (np.array([1.0, 1.0, 1.0, 1.0]), -0.01)
>>> status = ell.update_q(cut)
>>> print(status)
CutStatus.Success
xc() → ArrayType[source]

The function xc returns the value of the _xc attribute. :return: The method xc is returning the value of the attribute _xc.

ellalgo.ell_calc module

EllCalc (Ellipsoid Calculator)

The EllCalc class is a tool designed to perform calculations related to ellipsoids, which are mathematical shapes similar to stretched spheres. This code is part of an algorithm used in optimization problems, specifically for a method called the ellipsoid method.

The main purpose of this code is to provide various functions that calculate how to adjust or “cut” an ellipsoid based on certain input parameters. These calculations are used to gradually refine the search space in optimization problems, helping to find optimal solutions more efficiently.

The primary input for this class is the dimension of the problem space, represented by the parameter ‘n’ in the constructor. Other inputs vary depending on the specific calculation method being used, but generally include values like ‘beta’ (which represents a cut point) and ‘tsq’ (which is related to the tolerance or precision of the cut).

The outputs of the various calculation methods are typically tuples containing a status (indicating whether the calculation was successful, had no solution, or had no effect) and, if successful, a set of three float values. These values (often named rho, sigma, and delta) represent parameters used to update the ellipsoid in the optimization algorithm.

The class achieves its purpose through a series of mathematical calculations. It uses concepts from linear algebra and geometry to determine how to shrink or reshape the ellipsoid based on the input parameters. The exact calculations are quite complex, but they essentially determine where to make a “cut” in the ellipsoid and how to reshape it accordingly.

Some important logic flows in the code include:

  1. Checking if the input parameters are valid and returning appropriate status codes if they’re not.

  2. Deciding between different types of cuts (single, parallel, central) based on the input.

  3. Performing specific calculations for each type of cut.

The code also includes a helper class (EllCalcCore) that likely handles some of the more complex mathematical operations.

Overall, this code serves as a crucial component in an optimization algorithm, providing the mathematical backbone for adjusting the search space as the algorithm progresses towards finding an optimal solution. While the underlying math is complex, the code encapsulates this complexity into methods that can be easily used by other parts of the optimization algorithm.

class ellalgo.ell_calc.EllCalc(n: int)[source]

Bases: object

The EllCalc class is used for calculating ellipsoid parameters and has attributes for storing constants and configuration options.

Examples

>>> from ellalgo.ell_calc import EllCalc
>>> calc = EllCalc(3)
calc_bias_cut(beta: float, tsq: float) → Tuple[CutStatus, Tuple[float, float, float] | None][source]

Deep Cut

The function calculates the deep cut based on the given beta and tsq values.

Parameters:

  • beta (float) – The parameter beta represents a float value

  • tsq (float) – tsq is the square of the value of tau

Returns:

The function calc_bias_cut returns a tuple of four values: CutStatus, float, float, float.

Examples

>>> from ellalgo.ell_calc import EllCalc
>>> calc = EllCalc(3)
>>> calc.calc_bias_cut(1.0, 4.0)
(<CutStatus.Success: 0>, (1.25, 0.8333333333333334, 0.84375))
>>> calc.calc_bias_cut(0.0, 4.0)
(<CutStatus.Success: 0>, (0.5, 0.5, 1.125))
>>> calc.calc_bias_cut(1.5, 2.0)
(<CutStatus.NoSoln: 1>, None)
calc_bias_cut_q(beta: float, tsq: float) → Tuple[CutStatus, Tuple[float, float, float] | None][source]

Deep Cut (discrete)

The function calc_bias_cut_q calculates the deep cut for a given beta and tsq value.

Parameters:

  • beta (float) – The parameter beta represents a float value

  • tsq (float) – tsq is the square of the threshold value. It is a float value that represents the threshold squared

Returns:

The function calc_bias_cut_q returns a tuple of four values: CutStatus, float, float, float.

Examples

>>> from ellalgo.ell_calc import EllCalc
>>> calc = EllCalc(3)
>>> calc.calc_bias_cut_q(0.0, 4.0)
(<CutStatus.Success: 0>, (0.5, 0.5, 1.125))
>>> calc.calc_bias_cut_q(1.5, 2.0)
(<CutStatus.NoSoln: 1>, None)
>>> calc.calc_bias_cut_q(-1.5, 4.0)
(<CutStatus.NoEffect: 2>, None)
calc_parallel(beta0: float, beta1: float, tsq: float) → Tuple[CutStatus, Tuple[float, float, float] | None][source]

parallel deep cut

The function calc_parallel calculates the parallel deep cut based on the given parameters.

Parameters:

  • beta0 (float) – The parameter beta0 represents a float value

  • beta1 (float) – The parameter beta1 represents a float value

  • tsq (float) – tsq is a float representing the value of tsq

Returns:

The function calc_parallel returns a tuple of type Tuple[CutStatus, Optional[Tuple[float, float, float]]].

calc_parallel_q(beta0: float, beta1: float, tsq: float) → Tuple[CutStatus, Tuple[float, float, float] | None][source]

Parallel deep cut (discrete)

The function calc_parallel_q calculates the parallel deep cut for a given set of parameters.

Parameters:

  • beta0 (float) – The parameter beta0 represents a float value

  • beta1 (float) – The parameter beta1 represents a float value

  • tsq (float) – tsq is a float value that represents the square of a variable

Returns:

The function calc_parallel_q returns a tuple of type Tuple[CutStatus, float, float, float].

calc_single_or_parallel(beta, tsq: float) → Tuple[CutStatus, Tuple[float, float, float] | None][source]

single deep cut or parallel cut

The calc_single_or_parallel function calculates either a single deep cut or a parallel cut based on the input parameters.

Parameters:

  • beta – The parameter beta can be of type int, float, or a list of two elements

  • tsq (float) – The tsq parameter is a floating-point number that represents the square of the tolerance for the ellipsoid algorithm. It is used in the calculations performed by the calc_single_or_parallel method

Returns:

The function calc_single_or_parallel returns a tuple containing the following elements:

Examples

>>> from ellalgo.ell_calc import EllCalc
>>> calc = EllCalc(3)
calc_single_or_parallel_central_cut(beta, tsq: float) → Tuple[CutStatus, Tuple[float, float, float] | None][source]

single central cut or parallel cut

The function calc_single_or_parallel_central_cut calculates either a single central cut or a parallel cut based on the input parameters.

Parameters:

  • beta – The parameter beta is of type _type_ and represents some value. The specific details of its purpose and usage are not provided in the code snippet

  • tsq (float) – tsq is a float value representing the squared tau-value

Returns:

a tuple containing the following elements: 1. CutStatus: The status of the cut calculation. 2. float: The calculated value. 3. float: The calculated value. 4. float: The calculated value.

Examples

>>> from ellalgo.ell_calc import EllCalc
>>> calc = EllCalc(4)
>>> calc.calc_single_or_parallel_central_cut([0, 0.11], 0.01)
(<CutStatus.Success: 0>, (0.01897790039191521, 0.3450527343984584, 1.0549907942519101))
calc_single_or_parallel_q(beta, tsq: float) → Tuple[CutStatus, Tuple[float, float, float] | None][source]

single deep cut or parallel cut (discrete)

The function calc_single_or_parallel_q calculates the deep cut or parallel cut based on the input parameters beta and tsq.

Parameters:

  • beta – The parameter beta can be either a single value (int or float) or a list of two values

  • tsq (float) – tsq is a float value representing the square of the threshold value

Returns:

The function calc_single_or_parallel_q returns a tuple containing four elements: CutStatus, float, float, and float.

helper: EllCalcCore
use_parallel_cut: bool = True

ellalgo.ell_calc_core module

This module contains the EllCalcCore class.

This code defines a class called EllCalcCore, which is designed to perform calculations related to ellipsoids in mathematics. An ellipsoid is a 3D shape that’s like a stretched or squashed sphere. The class provides methods to calculate various parameters of ellipsoids under different conditions.

The main purpose of this code is to provide a set of tools for working with ellipsoids in optimization problems. It takes in various numerical inputs representing different aspects of an ellipsoid or cuts through it, and produces output values that describe how the ellipsoid should be adjusted or analyzed.

The class is initialized with a single input ‘n_f’, which represents the dimension of the space the ellipsoid exists in. This value is used to set up several constant values that are used in later calculations.

The class provides several methods, each performing a different type of calculation:

  1. calc_central_cut: This calculates parameters for a cut through the center of the ellipsoid.

  2. calc_bias_cut and calc_bias_cut_fast: These calculate parameters for a cut that doesn’t go through the center.

  3. calc_parallel_central_cut and calc_parallel_central_cut_old: These handle cuts that are parallel to a central cut.

  4. calc_parallel_bias_cut, calc_parallel_bias_cut_fast, and calc_parallel_bias_cut_old: These deal with parallel cuts that don’t go through the center.

Each of these methods takes in one or more numerical inputs (like ‘tau’, ‘beta’, ‘tsq’) that represent different aspects of the cut or the ellipsoid. They then perform a series of mathematical calculations using these inputs and the constants set up during initialization. The calculations involve basic arithmetic, square roots, and some more complex formulas specific to ellipsoid geometry.

The output of each method is typically a tuple of three float values, often represented as (rho, sigma, delta). These values describe how the ellipsoid should be adjusted based on the cut that was calculated.

The code achieves its purpose by encapsulating all these complex mathematical calculations into easy-to-use methods. A programmer can create an instance of EllCalcCore and then call these methods as needed, without having to understand all the underlying mathematics.

The main logic flow in this code is from the input parameters, through the mathematical calculations, to the output tuple. The data transformations happening are primarily mathematical: converting the input parameters into the desired output parameters using the formulas of ellipsoid geometry.

This code is a tool for more complex algorithms that might be using these ellipsoid calculations as part of a larger optimization or analysis process. It provides a clean, object-oriented way to perform these specific mathematical operations.

class ellalgo.ell_calc_core.EllCalcCore(n_f: float)[source]

Bases: object

The EllCalcCore class is used for calculating ellipsoid parameters.

Examples

>>> calc = EllCalcCore(3)
calc_bias_cut(beta: float, tau: float) → Tuple[float, float, float][source]

Calculate deep cut values.

Calculates the deep cut values ρ, σ, δ for given β and τ.

Parameters:

  • beta (float) – beta is a float representing the value of beta

  • tau (float) – tau is a float representing the value of tau

Returns:

The function calc_bias_cut returns a tuple containing the following elements:

_.-'''''''-._ ,' | `. / | \ . | . | | | | | . | | | | :\ | /: | `._ | _.' | | '-.......-' | | | | "-τ" "-β" +τ η = τ + n ⋅ β η ϱ = ───── n + 1 2 ⋅ ϱ σ = ───── τ + β 2 2 2 n τ - β δ = ────── ⋅ ─────── 2 2 n - 1 τ

Examples

>>> calc = EllCalcCore(3)
>>> calc.calc_bias_cut(1.0, 2.0)
(1.25, 0.8333333333333334, 0.84375)
>>> calc.calc_bias_cut(0.0, 2.0)
(0.5, 0.5, 1.125)
calc_bias_cut_fast(beta: float, tau: float, eta: float) → Tuple[float, float, float][source]

Calculates the deep cut ellipsoid parameters using precomputed eta values.

Given the beta, tau, and eta values, this method calculates the deep cut ellipsoid parameters rho, sigma, and delta using a precomputed eta value. that avoids explicitly calculating the intermediate eta value. This allows the deep cut to be computed faster.

The rho, sigma, and delta values define the deep cut ellipsoid.

Parameters:

  • beta (float) – beta is a float representing the value of beta

  • tau (float) – tau is a float representing the value of tau

Returns:

The function calc_bias_cut returns a tuple containing the following elements:

_.-'''''''-._ ,' | `. / | \ . | . | | | | | . | | | | :\ | /: | `._ | _.' | | '-.......-' | | | | "-τ" "-β" +τ η ϱ = ───── n + 1 2 ⋅ ϱ σ = ───── τ + β 2 2 2 n τ - β δ = ────── ⋅ ─────── 2 2 n - 1 τ

Examples

>>> calc = EllCalcCore(3)
>>> calc.calc_bias_cut_fast(1.0, 2.0, 5.0)
(1.25, 0.8333333333333334, 0.84375)
>>> calc.calc_bias_cut_fast(0.0, 2.0, 2.0)
(0.5, 0.5, 1.125)
calc_central_cut(tau: float) → Tuple[float, float, float][source]

Calculate the central cut values.

The calc_central_cut method calculates the central cut values ρ, σ, δ based on the input tau value.

Parameters:

tau (float) – The tau value

Returns:

Tuple of (ρ, σ, δ)

Return type:

Tuple[float, float, float]

_.-'''''''-._ ,' | `. / | \ . | . | | | . | | | :\ | /: | `._ | _.' | | '-.......-' | | | | "-τ" 0 +τ 2 σ = ───── n + 1 τ ϱ = ───── n + 1 2 n δ = ────── 2 n - 1

Examples

>>> calc = EllCalcCore(3)
>>> calc.calc_central_cut(4.0)
(1.0, 0.5, 1.125)
calc_parallel_bias_cut(beta0: float, beta1: float, tsq: float) → Tuple[float, float, float][source]

Calculation Parallel Deep Cut (15 mul/div + 1 sqrt)

The calc_parallel_bias_cut function calculates various values based on the input parameters and returns them as a tuple.

Parameters:

  • beta0 (float) – The parameter beta0 represents a float value

  • beta1 (float) – The parameter beta1 represents a float value

  • tsq (float) – tsq is a float representing the square of the value tau

Returns:

a tuple with three elements.

_.-'''''''-._ ,' | `. / | | \ . | | . | | | | | | |. | | | | | :\ | | /: | `._ | _.' | | |'-.......-' | | | | | "-τ" "-β" "-β" +τ 1 0 2 η = τ + n ⋅ β ⋅ β 0 1 β + β 0 1 β = ─────── 2 1 ⎛ 2 ⎞ 2 h = ─ ⋅ ⎜τ + β ⋅ β ⎟ + n ⋅ β 2 ⎝ 0 1⎠ _____________________ ╱ 2 2 k = h + ╲╱ h - (n + 1) ⋅ η ⋅ β 1 η σ = ───── = ─ μ + 1 k 1 η ─ = ───── μ k - η ϱ = β ⋅ σ 2 2 1 ⎛ 2 ⎞ δ ⋅ τ = τ + ─ ⋅ ⎜β ⋅ σ - β ⋅ β ⎟ μ ⎝ 0 1⎠

Examples

>>> calc = EllCalcCore(4)
>>> calc.calc_parallel_bias_cut(0.01, 0.11, 0.01)
(0.027228509068282114, 0.45380848447136857, 1.0443438549074862)
>>> calc.calc_parallel_bias_cut(-0.25, 0.25, 1.0)
(0.0, 0.8, 1.25)
>>> calc.calc_parallel_bias_cut(0.0, 0.09, 0.01)
(0.020941836487980856, 0.46537414417735234, 1.082031295477563)
calc_parallel_bias_cut_fast(beta0: float, beta1: float, tsq: float, b0b1: float, eta: float) → Tuple[float, float, float][source]

Calculation Parallel Deep Cut (13 mul/div + 1 sqrt)

The calc_parallel_bias_cut_fast function calculates various values based on the input parameters and returns them as a tuple.

Parameters:

  • beta0 (float) – The parameter beta0 represents a float value

  • beta1 (float) – The parameter beta1 represents a float value

  • tsq (float) – tsq is a float representing the square of the value tau

  • b0b1 (float) – The parameter b0b1 represents a float value

  • eta (float) – The parameter eta represents a float value

Returns:

a tuple with three elements.

_.-'''''''-._ ,' | `. / | | \ . | | . | | | | | | |. | | | | | :\ | | /: | `._ | _.' | | |'-.......-' | | | | | "-τ" "-β" "-β" +τ 1 0 β + β 0 1 β = ─────── 2 1 ⎛ 2 ⎞ 2 h = ─ ⋅ ⎜τ + β ⋅ β ⎟ + n ⋅ β 2 ⎝ 0 1⎠ _____________________ ╱ 2 2 k = h + ╲╱ h - (n + 1) ⋅ η ⋅ β 1 η σ = ───── = ─ μ + 1 k 1 η ─ = ───── μ k - η ϱ = β ⋅ σ 2 2 1 ⎛ 2 ⎞ δ ⋅ τ = τ + ─ ⋅ ⎜β ⋅ σ - β ⋅ β ⎟ μ ⎝ 0 1⎠

Examples

>>> calc = EllCalcCore(4)
>>> calc.calc_parallel_bias_cut_fast(0.11, 0.01, 0.01, 0.0011, 0.0144)
(0.027228509068282114, 0.45380848447136857, 1.0443438549074862)
>>> calc.calc_parallel_bias_cut_fast(-0.25, 0.25, 1.0, -0.0625, 0.75)
(0.0, 0.8, 1.25)
calc_parallel_bias_cut_old(beta0: float, beta1: float, tsq: float) → Tuple[float, float, float][source]

Calculation Parallel Deep Cut

The calc_parallel_bias_cut function calculates various values based on the input parameters and returns them as a tuple.

Parameters:

  • beta0 (float) – The parameter beta0 represents a float value

  • beta1 (float) – The parameter beta1 represents a float value

  • tsq (float) – tsq is a float representing the square of the value tau

Returns:

a tuple with three elements.

_.-'''''''-._ ,' | `. / | | \ . | | . | | | | | | |. | | | | | :\ | | /: | `._ | _.' | | |'-.......-' | | | | | "-τ" "-β" "-β" +τ 1 0 2 2 ζ = τ - β 0 0 2 2 ζ = τ - β 1 1 __________________________ ╱ 2 ╱ ⎛ ⎛ 2 2⎞⎞ ╱ ⎜n ⋅ ⎜β - β ⎟⎟ ╱ ⎜ ⎝ 1 0⎠⎟ ξ = ╱ ζ ⋅ ζ + ⎜─────────────⎟ ╲╱ 0 1 ⎝ 2 ⎠ ⎛ 2 ⎞ 2 ⋅ ⎜τ + β ⋅ β - ξ⎟ n ⎝ 0 1 ⎠ σ = ───── + ────────────────────── n + 1 2 (n + 1) ⋅ ⎛β + β ⎞ <---- Oop!!! ⎝ 0 1⎠ σ ⋅ ⎛β + β ⎞ ⎝ 0 1⎠ ϱ = ───────────── 2 ⎛ζ + ζ ⎞ 2 ⎜ 0 1 ξ⎟ n ⋅ ⎜─────── + ─⎟ ⎝ 2 n⎠ δ = ────────────────── ⎛ 2 ⎞ 2 ⎝n - 1⎠ ⋅ τ

Examples

>>> calc = EllCalcCore(4)
>>> calc.calc_parallel_bias_cut_old(0.11, 0.01, 0.01)
(0.02722850906828212, 0.4538084844713687, 1.0443438549074862)
calc_parallel_central_cut(beta1: float, tsq: float) → Tuple[float, float, float][source]

Calculate Parallel Central Cut (7 mul/div + 1 sqrt)

The function calc_parallel_central_cut calculates the parallel central cut for given values of beta1 and tsq.

Parameters:

  • beta1 (float) – The parameter beta1 represents a float value. It is used in the calculation of the central cut

  • tsq (float) – The parameter tsq represents the square of a value

Returns:

The function calc_parallel_central_cut returns a tuple of four values: CutStatus, float, float, float.

_.-'''''''-._ ,' | `. / | | \ . | | . | | | | | . | | | | :\ | | /: | `._ | _.' | | |'-.......-' | | | | | "-τ" "-β" 0 +τ 1 2 2 2 α = β / τ n 2 k = ─ ⋅ α 2 ___________ ╱ 2 2 r = k + ╲╱ k + 1 - α β ϱ = ───── r + 1 2 σ = ───── r + 1 r δ = ───────── r - 1 / n

Examples

>>> calc = EllCalcCore(4)
>>> calc.calc_parallel_central_cut(0.09, 0.01)
(0.020941836487980856, 0.46537414417735234, 1.082031295477563)
calc_parallel_central_cut_old(beta1: float, tsq: float) → Tuple[float, float, float][source]

Calculate Parallel Central Cut

The function calc_parallel_central_cut calculates the parallel central cut for given values of beta1 and tsq.

Parameters:

  • beta1 (float) – The parameter beta1 represents a float value. It is used in the calculation of the central cut

  • tsq (float) – The parameter tsq represents the square of a value

Returns:

The function calc_parallel_central_cut returns a tuple of four values: CutStatus, float, float, float.

_.-'''''''-._ ,' | `. / | | \ . | | . | | | | | . | | | | :\ | | /: | `._ | _.' | | |'-.......-' | | | | | "-τ" "-β" 0 +τ 1 __________________________ ╱ 2 ╱ ⎛ 2⎞ ╱ ⎜n ⋅ β ⎟ ╱ ⎛ 2 2⎞ 2 ⎜ 1⎟ ξ = ╱ ⎜τ - β ⎟ ⋅ τ + ⎜──────⎟ ╲╱ ⎝ 1⎠ ⎝ 2 ⎠ ⎛ 2 ⎞ n 2 ⋅ ⎝τ - ξ⎠ σ = ───── + ──────────── n + 1 2 (n + 1) ⋅ β 1 σ ⋅ β 1 ϱ = ────── 2 ⎛ 2 ⎞ ⎜ β ⎟ 2 ⎜ 2 1 ξ⎟ n ⋅ ⎜τ - ── + ─⎟ ⎝ 2 n⎠ δ = ────────────────── ⎛ 2 ⎞ 2 ⎝n - 1⎠ ⋅ τ

Examples

>>> calc = EllCalcCore(4)
>>> calc.calc_parallel_central_cut_old(0.09, 0.01)
(0.02094183648798086, 0.46537414417735246, 1.082031295477563)

ellalgo.ell_config module

class ellalgo.ell_config.CutStatus(value)[source]

Bases: Enum

NoEffect = 2
NoSoln = 1
Success = 0
Unknown = 3
class ellalgo.ell_config.Options[source]

Bases: object

max_iters: int = 2000
tolerance: float = 1e-20

ellalgo.ell_stable module

class ellalgo.ell_stable.EllStable(val, xc: ArrayType)[source]

Bases: SearchSpace[ArrayType], SearchSpaceQ[ArrayType]

helper: EllCalc
no_defer_trick: bool = False
set_xc(x: ArrayType) → None[source]

The function sets the value of the variable _xc to the input x.

Parameters:

x (ArrayType) – The parameter x is of type ArrayType

tsq() → float[source]

The function tsq returns the measure of the distance between xc and x*. :return: The method is returning a float value, which represents the measure of the distance between xc and x*.

update_bias_cut(cut) → CutStatus[source]

The function update_bias_cut is an implementation of the SearchSpace interface that updates the cut status based on a given cut.

Parameters:

cut – The cut parameter is of type _type_ and it represents some kind of cut

Returns:

a CutStatus object.

Examples

>>> ell = EllStable(1.0, [1.0, 1.0, 1.0, 1.0])
>>> cut = (np.array([1.0, 1.0, 1.0, 1.0]), 1.0)
>>> status = ell.update_bias_cut(cut)
>>> print(status)
CutStatus.Success
update_central_cut(cut) → CutStatus[source]

The function update_central_cut is an implementation of the SearchSpace interface that updates the cut status based on a given cut.

Parameters:

cut – The cut parameter is of type _type_ and it represents a cut

Returns:

a CutStatus object.

Examples

>>> ell = EllStable(1.0, [1.0, 1.0, 1.0, 1.0])
>>> cut = (np.array([1.0, 1.0, 1.0, 1.0]), 0.0)
>>> status = ell.update_central_cut(cut)
>>> print(status)
CutStatus.Success
update_q(cut) → CutStatus[source]

The function update_q is an implementation of the SearchSpaceQ interface that updates the cut status based on a given cut.

Parameters:

cut – The cut parameter is of type _type_ and it represents the cut that needs to be updated

Returns:

a CutStatus object.

Examples

>>> ell = EllStable(1.0, [1.0, 1.0, 1.0, 1.0])
>>> cut = (np.array([1.0, 1.0, 1.0, 1.0]), -0.01)
>>> status = ell.update_q(cut)
>>> print(status)
CutStatus.Success
xc() → ArrayType[source]

The function xc returns the value of the _xc attribute. :return: The method xc is returning the value of the attribute _xc.

ellalgo.ell_typing module

class ellalgo.ell_typing.OracleBS[source]

Bases: ABC

abstractmethod assess_bs(gamma) → bool[source]

The assess_bs function is a binary search assessment function that takes a gamma value as input and returns a boolean value.

Parameters:

gamma – The gamma parameter is the value that we are searching for in the binary search

class ellalgo.ell_typing.OracleFeas[source]

Bases: Generic[ArrayType]

abstractmethod assess_feas(xc: ArrayType) → Tuple[ArrayType, float | MutableSequence] | None[source]

The assess_feas function assesses the feasibility of a given input and returns a cut if it is not feasible.

Parameters:

xc (ArrayType) – An array of type ArrayType

class ellalgo.ell_typing.OracleFeas2[source]

Bases: OracleFeas[ArrayType]

abstractmethod update(gamma) → None[source]

The update function updates a gamma object.

Parameters:

gamma – The gamma parameter is of type Any, which means it can accept any type of value. It is used as an argument to update the gamma object

class ellalgo.ell_typing.OracleOptim[source]

Bases: Generic[ArrayType]

abstractmethod assess_optim(xc: ArrayType, gamma) → Tuple[Tuple[ArrayType, float | MutableSequence], float | None][source]

The assess_optim function assesses the feasibility based on the given xc and gamma parameters.

Parameters:

  • xc (ArrayType) – An array of values that represents the current solution or point in the optimization process

  • gamma – The gamma parameter is the value that we are trying to optimize or minimize. It could be a numerical value, a function, or any other type of object that represents the optimization goal

class ellalgo.ell_typing.OracleOptimQ[source]

Bases: Generic[ArrayType]

abstractmethod assess_optim_q(xc: ArrayType, gamma, retry: bool) → Tuple[Tuple[ArrayType, float | MutableSequence], ArrayType, float | None, bool][source]

assessment of optimization (discrete)

The function assess_optim_q assesses the feasibility of a design variable and returns a tuple containing a cut, an array, an optional float, and a boolean value.

Parameters:

  • xc (ArrayType) – An array or list representing the current solution or configuration being assessed for optimization

  • gamma – The gamma parameter is the desired value or condition that the optimization algorithm is trying to achieve. It could be a specific value, a range of values, or a certain condition that needs to be satisfied

  • retry (bool) – A boolean flag indicating whether to retry the optimization if it fails

class ellalgo.ell_typing.SearchSpace[source]

Bases: Generic[ArrayType]

abstractmethod tsq() → float[source]

The function tsq returns the measure of the distance between xc and x*. :return: The method is returning a float value, which represents the measure of the distance between xc and x*.

abstractmethod update_bias_cut(cut: Tuple[ArrayType, float | MutableSequence]) → CutStatus[source]

The update_bias_cut function is an abstract method that takes a Cut object as input and returns a CutStatus object.

Parameters:

cut (Cut) – The cut parameter is an instance of the Cut class. It represents a deep-cut that needs to be updated

abstractmethod update_central_cut(cut: Tuple[ArrayType, float | MutableSequence]) → CutStatus[source]

The update_central_cut function is an abstract method that updates the central cut and returns the status of the cut.

Parameters:

cut (Cut) – The “cut” parameter is an instance of the Cut class. It represents the central cut that needs to be updated

abstractmethod xc() → ArrayType[source]

The function xc returns the value of the _xc attribute. :return: The method xc is returning the value of the attribute _xc.

class ellalgo.ell_typing.SearchSpace2[source]

Bases: SearchSpace[ArrayType]

abstractmethod set_xc(xc: ArrayType) → None[source]

The function sets the value of the variable _xc to the input x.

Parameters:

x (ArrayType) – The parameter x is of type ArrayType

class ellalgo.ell_typing.SearchSpaceQ[source]

Bases: Generic[ArrayType]

abstractmethod tsq() → float[source]

The function tsq returns the measure of the distance between xc and x*. :return: The method is returning a float value, which represents the measure of the distance between xc and x*.

abstractmethod update_q(cut: Tuple[ArrayType, float | MutableSequence]) → CutStatus[source]

The update_q function is an abstract method that updates a shadow cut and returns a CutStatus object.

Parameters:

cut (Cut) – The cut parameter is an object of type Cut

abstractmethod xc() → ArrayType[source]

The function xc returns the value of the _xc attribute. :return: The method xc is returning the value of the attribute _xc.

ellalgo.skeleton module

This is a skeleton file that can serve as a starting point for a Python console script. To run this script uncomment the following lines in the [options.entry_points] section in setup.cfg:

console_scripts =
     fibonacci = ellalgo.skeleton:run

Then run pip install . (or pip install -e . for editable mode) which will install the command fibonacci inside your current environment.

Besides console scripts, the header (i.e. until _logger…) of this file can also be used as template for Python modules.

Note

This file can be renamed depending on your needs or safely removed if not needed.

References

ellalgo.skeleton.fib(n)[source]

Fibonacci example function

Parameters:

n (int) – integer

Returns:

n-th Fibonacci number

Return type:

int

ellalgo.skeleton.main(args)[source]

Wrapper allowing fib() to be called with string arguments in a CLI fashion

Instead of returning the value from fib(), it prints the result to the stdout in a nicely formatted message.

Parameters:

args (List[str]) – command line parameters as list of strings (for example ["--verbose", "42"]).

ellalgo.skeleton.parse_args(args)[source]

Parse command line parameters

Parameters:

args (List[str]) – command line parameters as list of strings (for example ["--help"]).

Returns:

command line parameters namespace

Return type:

argparse.Namespace

ellalgo.skeleton.run()[source]

Calls main() passing the CLI arguments extracted from sys.argv

This function can be used as entry point to create console scripts with setuptools.

ellalgo.skeleton.setup_logging(loglevel)[source]

Setup basic logging

Parameters:

loglevel (int) – minimum loglevel for emitting messages

Module contents