ellalgo.oracles namespace

Submodules

ellalgo.oracles.ldlt_mgr module

LDLTMgr (LDLT Manager)

This code defines a class called LDLTMgr, which stands for LDLT Manager. The purpose of this class is to perform a special kind of matrix factorization called LDLT factorization on symmetric matrices. This factorization is useful in various mathematical and engineering applications, especially when dealing with linear systems and eigenvalue problems.

The main input for this class is a symmetric matrix, which can be provided either as a NumPy array or through a function that returns individual matrix elements. The primary output is a boolean value indicating whether the input matrix is positive definite (a special property of matrices). Additionally, the class can produce other outputs like a witness vector (if the matrix is not positive definite) and a square root of the matrix (if it is positive definite).

The LDLTMgr class achieves its purpose through several methods. The main method is ‘factor’, which performs the actual LDLT factorization. It does this by going through the matrix elements row by row, calculating and storing values in a special way. This process helps determine if the matrix is positive definite and allows for efficient calculations later.

An important aspect of this code is its use of “lazy evaluation”. This means it doesn’t need the entire matrix upfront but can work with just a function that provides matrix elements as needed. This can be more efficient for large matrices or when the matrix is defined by a formula rather than stored values.

The class also includes methods to check if the matrix is positive definite (‘is_spd’), calculate a witness vector if it’s not (‘witness’), and compute a symmetric quadratic form (‘sym_quad’). These additional functionalities make the class versatile for various matrix-related tasks.

One of the key transformations happening in this code is the factorization itself. It’s breaking down the original matrix into simpler parts (L, D, and L transpose), which can be used to solve problems more easily. This factorization is done in a way that avoids using square roots, which can be computationally expensive.

Overall, the LDLTMgr class provides a set of tools for working with symmetric matrices, with a focus on determining their properties (like positive definiteness) and performing useful calculations efficiently. It’s designed to be flexible and can handle both standard matrices and those defined by functions, making it useful in a variety of mathematical and engineering contexts.

class ellalgo.oracles.ldlt_mgr.LDLTMgr(ndim: int)

Bases: object

LDLT factorization (mainly for LMI oracles)

LDLTMgr is a class that performs the LDLT factorization for a given symmetric matrix. The LDLT factorization decomposes a symmetric matrix A into the product of a lower triangular matrix L, a diagonal matrix D, and the transpose of L. This factorization is useful for solving linear systems and eigenvalue problems. The class provides methods to perform the factorization, check if the matrix is positive definite, calculate a witness vector if it is not positive definite, and calculate the symmetric quadratic form.

• LDL^T square-root-free version

• Option allow semidefinite

• Cholesky-Banachiewicz style, row-based

• Lazy evaluation

• A matrix A in R^{m x m} is positive definite

  iff v^T A v > 0 for all v in R^n.

• O(p^3) per iteration, independent of ndim

Examples

>>> A = np.array([[1.0, 0.5, 0.5], [0.5, 1.25, 0.75], [0.5, 0.75, 1.5]])
>>> ldl = LDLTMgr(3)
>>> ldl.factorize(A)
True

factor(get_elem: Callable[[int, int], float]) → bool

The function performs LDLT Factorization on a symmetric matrix using lazy evaluation.

Parameters:

get_elem (Callable[[int, int], float]) – The get_elem parameter is a callable function that is used to access the elements of a symmetric matrix. It takes two integer arguments i and j and returns the value of the element at the (i, j) position in the matrix

Returns:

The function factor returns a boolean value indicating whether the matrix is symmetric positive definite (SPD).

Examples

>>> mat = np.array([[1.0, 0.5, 0.5], [0.5, 1.25, 0.75], [0.5, 0.75, 1.5]])
>>> ldl = LDLTMgr(3)
>>> ldl.factor(lambda i, j: mat[i, j])
True

factor_with_allow_semidefinite(get_elem: Callable[[int, int], float]) → bool

The function performs LDLT Factorization on a symmetric matrix using lazy evaluation and checks if the matrix is positive definite.

Parameters:

get_elem (Callable[[int, int], float]) – The get_elem parameter is a callable function that takes two integer arguments i and j and returns a float value. This function is used to access the elements of a symmetric matrix mat. The factor_with_allow_semidefinite method performs LDLT Factorization on

Returns:

The function factor_with_allow_semidefinite returns a boolean value indicating whether the matrix is symmetric positive definite (SPD).

Examples

>>> mat = np.array([[1.0, 0.5, 0.5], [0.5, 1.25, 0.75], [0.5, 0.75, 1.5]])
>>> ldl = LDLTMgr(3)
>>> ldl.factor_with_allow_semidefinite(lambda i, j: mat[i, j])
True

factorize(mat: ndarray) → bool

The function factorize performs LDLT Factorization on a symmetric matrix A and returns a boolean value indicating whether the factorization was successful.

If $A$ is positive definite, then $p$ is zero. If it is not, then $p$ is a positive integer, such that $v = R^{-1} e_p$ is a certificate vector to make $v^T*A[:p,:p]*v < 0$

Parameters:

A (np.ndarray) – A is a numpy array representing a symmetric matrix

Returns:

the result of calling the factor method with a lambda function as an argument.

Examples

>>> mat = np.array([[1.0, 0.5, 0.5], [0.5, 1.25, 0.75], [0.5, 0.75, 1.5]])
>>> ldl = LDLTMgr(3)
>>> ldl.factorize(mat)
True

is_spd()

The function is_spd checks if a matrix A is symmetric positive definite (spd) and returns True if it is.

Returns:

a boolean value. It returns True if the matrix A is symmetric positive definite (spd), and False otherwise.

Examples

>>> mat = np.array([[1.0, 0.5, 0.5], [0.5, 1.25, 0.75], [0.5, 0.75, 1.5]])
>>> ldl = LDLTMgr(3)
>>> ldl.factorize(mat)
True
>>> ldl.is_spd()
True

pos: Tuple[int, int]

sqrt() → ndarray

Return upper triangular matrix R where A = R^T * R

Raises:

AssertionError – [description]

Returns:

[description]

Return type:

np.ndarray

Examples

>>> mat = np.array([[1.0, 0.5, 0.5], [0.5, 1.25, 0.75], [0.5, 0.75, 1.5]])
>>> ldl = LDLTMgr(3)
>>> ldl.factorize(mat)
True
>>> ldl.sqrt()
array([[1. , 0.5, 0.5],
       [0. , 1. , 0.5],
       [0. , 0. , 1. ]])

sym_quad(mat: ndarray)

The sym_quad function calculates the quadratic form of a vector v with a symmetric matrix mat.

Parameters:

mat (np.ndarray) – mat is a numpy array

Returns:

The function sym_quad returns the result of the dot product between v and the matrix product of mat[start:ndim, start:ndim] and v.

Examples

>>> mat = np.array([[1.0, 2.0, 3.0], [2.0, 3.5, 5.0], [3.0, 5.0, 6.0]])
>>> ldl = LDLTMgr(3)
>>> ldl.factorize(mat)
False
>>> ldl.pos
(0, 2)
>>> ldl.witness() # call this before sym_quad()
0.5
>>> ldl.wit
array([-2.,  1.,  0.])
>>> mat_b = np.array([[1.0, 0.5, 0.5], [0.5, 1.25, 0.75], [0.5, 0.75, 1.5]])
>>> ldl.sym_quad(mat_b)
3.25

wit: ndarray

witness() → float

The function “witness” provides evidence that a matrix is not symmetric positive definite.

(square-root-free version)

evidence: v^T A v = -ep

Raises:

AssertionError – $A$ indeeds a spd matrix

Returns:

ep

Return type:

float

Examples

>>> mat = np.array([[1.0, 2.0, 3.0], [2.0, 3.5, 5.0], [3.0, 5.0, 6.0]])
>>> ldl = LDLTMgr(3)
>>> ldl.factorize(mat)
False
>>> ldl.witness()
0.5

ellalgo.oracles.lmi0_oracle module

class ellalgo.oracles.lmi0_oracle.LMI0Oracle(mat_f)

Bases: object

Oracle for Linear Matrix Inequality constraint

find x s.t. F * x ⪰ 0

assess_feas(x: ndarray) → Tuple[ndarray, float] | None

[summary]

Parameters:

x (np.ndarray) – [description]

Returns:

[description]

Return type:

Optional[Cut]

ellalgo.oracles.lmi_old_oracle module

class ellalgo.oracles.lmi_old_oracle.LMIOldOracle(mat_f, mat_b)

Bases: OracleFeas

Oracle for Linear Matrix Inequality constraint.

This oracle solves the following feasibility problem:

find x s.t. (B − F * x) ⪰ 0

assess_feas(x: ndarray) → Tuple[ndarray, float] | None

The assess_feas function assesses the feasibility of a given input array x and returns a Cut object if the feasibility is violated, otherwise it returns None.

Parameters:

x (np.ndarray) – An array of values that will be used in the calculation

Returns:

The function assess_feas returns an Optional[Cut].

ellalgo.oracles.lmi_oracle module

LMIOracle

This code defines a class called LMIOracle, which is designed to solve a specific type of mathematical problem known as a Linear Matrix Inequality (LMI) constraint. The purpose of this code is to determine if there exists a solution that satisfies the given constraint, and if not, to provide information about why it’s not feasible.

The LMIOracle class takes two inputs when it’s created: mat_f and mat_b. These are matrices that define the LMI constraint. mat_f is a list of numpy arrays, and mat_b is a single numpy array. These matrices represent the mathematical relationship that needs to be satisfied.

The main function in this class is called assess_feas, which takes a numpy array xc as input. This function tries to determine if xc is a feasible solution to the LMI constraint. If it is feasible, the function returns None. If it’s not feasible, it returns what’s called a “cut” - a tuple containing information about why the solution isn’t feasible.

To achieve its purpose, the code uses a technique called LDLT factorization. This is a way of breaking down a matrix into simpler parts, which can help determine if the matrix satisfies certain properties. The LDLTMgr class (which is used but not defined in this code snippet) handles this factorization.

The assess_feas function works by first creating a new matrix using the input xc and the original matrices mat_f and mat_b. It then tries to perform the LDLT factorization on this new matrix. If the factorization is successful, it means xc is a feasible solution, and the function returns None. If the factorization fails, it means xc is not feasible, and the function calculates and returns the “cut” information.

An important part of the logic is the get_elem function inside assess_feas. This function calculates each element of the new matrix based on the original matrices and the input xc. This is where the main mathematical operation of the LMI constraint is performed.

In summary, this code provides a way to check if a given solution satisfies a complex mathematical constraint, and if not, it provides information about why the solution doesn’t work. This could be useful in optimization problems where you’re trying to find a solution that satisfies certain mathematical conditions.

class ellalgo.oracles.lmi_oracle.LMIOracle(mat_f, mat_b)

Bases: OracleFeas

Oracle for Linear Matrix Inequality constraint.

This oracle solves the following feasibility problem:

find x

s.t. (B − F * x) ⪰ 0

assess_feas(xc: ndarray) → Tuple[ndarray, float] | None

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

Parameters:

x (np.ndarray) – An input array of type np.ndarray

Returns:

The function assess_feas returns an optional Cut object.

ellalgo.oracles.lowpass_oracle module

Lowpass Oracle

This code implements a Lowpass Oracle, which is used to design a low-pass filter for signal processing. A low-pass filter allows low-frequency signals to pass through while attenuating high-frequency signals. The main purpose of this code is to help optimize the design of such a filter by providing a way to assess whether a given set of filter coefficients meets certain specifications.

The code defines a class called LowpassOracle that takes several inputs when initialized:

1. ndim: The number of filter coefficients

2. wpass: The end of the passband (frequencies that should pass through)

3. wstop: The end of the stopband (frequencies that should be attenuated)

4. lp_sq: The lower bound for the squared magnitude response in the passband

5. up_sq: The upper bound for the squared magnitude response in the passband

6. sp_sq: The upper bound for the squared magnitude response in the stopband

The main outputs of this code are produced by two methods: assess_feas and assess_optim. These methods take a set of filter coefficients as input and determine whether they meet the specified requirements or how close they are to meeting them.

The LowpassOracle achieves its purpose through a series of checks on the frequency response of the filter. It uses a pre-computed spectrum matrix to efficiently calculate the frequency response at different points. The code then checks if the response falls within the specified bounds for the passband and stopband.

The important logic flow in this code involves iterating through different frequency points and checking the filter’s response at each point. If any violations of the specifications are found, the code returns information about the violation, which can be used to adjust the filter coefficients.

A key data transformation happening in this code is the conversion from filter coefficients to frequency response. This is done using the pre-computed spectrum matrix, which allows for efficient calculation of the response at many frequency points.

The code also includes a helper function called create_lowpass_case, which sets up a specific instance of the LowpassOracle with predefined parameters. This function can be used to quickly create a standard test case for filter design.

Overall, this code provides a tool for iteratively designing and optimizing low-pass filters by giving feedback on how well a set of coefficients meets the desired specifications. It’s part of a larger optimization process where the coefficients would be adjusted based on the feedback from this oracle until a satisfactory filter design is achieved.

class ellalgo.oracles.lowpass_oracle.LowpassOracle(ndim: int, wpass: float, wstop: float, lp_sq: float, up_sq: float, sp_sq: float)

Bases: OracleOptim

assess_feas(x: ndarray) → Tuple[ndarray, float | Tuple[float, float]] | None

[summary]

Parameters:

• x (Arr) – coefficients of autocorrelation

• sp_sq (float) – the best-so-far stop_pass^2

Returns:

[description]

Return type:

[type]

assess_optim(x: ndarray, sp_sq: float)

[summary]

Parameters:

• x (Arr) – coefficients of autocorrelation

• sp_sq (float) – the best-so-far stop_pass^2

Returns:

[description]

Return type:

[type]

idx1: int = 0

ellalgo.oracles.lowpass_oracle.create_lowpass_case(ndim=48)

[summary]

Keyword Arguments:

mdim (int) – [description] (default: {48})

Returns:

[description]

Return type:

[type]

ellalgo.oracles.profit_oracle module

Profit Oracle

This code defines several classes that implement oracles for profit maximization problems. An oracle, in this context, is a function that helps solve optimization problems by providing information about the feasibility and optimality of potential solutions.

The main class, ProfitOracle, is designed to solve a specific type of profit maximization problem. It takes as input parameters related to production (like price, scale, and limits) and output elasticities. The goal is to find the optimal input quantities that maximize profit, given certain constraints.

The ProfitOracle class has methods to assess the feasibility of a solution (assess_feas) and to find the optimal solution (assess_optim). These methods take as input a vector y (representing input quantities in log scale) and a gamma value (representing the current best solution). They output “cuts”, which are linear constraints that help narrow down the search for the optimal solution.

The code also includes two variations of the profit oracle:

1. ProfitRbOracle: This is a robust version of the profit oracle that can handle some uncertainty in the input parameters.

2. ProfitQOracle: This version deals with discrete (integer) input quantities, as opposed to continuous ones.

The main logic flow in these classes involves calculating various economic functions (like Cobb-Douglas production functions) and their gradients. The code uses these calculations to determine if a given solution is feasible and to guide the search towards the optimal solution.

The output of these oracles is typically a “cut” (a linear constraint) and possibly an updated best solution (gamma). These outputs are used by an external optimization algorithm (not shown in this code) to iteratively improve the solution until the optimal one is found.

For beginners, it’s important to understand that this code is implementing mathematical optimization techniques. While the details might be complex, the basic idea is to efficiently search for the best solution to a profit maximization problem, given certain constraints and economic relationships.

class ellalgo.oracles.profit_oracle.ProfitOracle(params: Tuple[float, float, float], elasticities: ndarray, price_out: ndarray)

Bases: OracleOptim

Oracle for a profit maximization problem.

This example is taken from [Aliabadi and Salahi, 2013]

max p(A x1^α x2^β) − v1*x1 − v2*x2 s.t. x1 ≤ k

where:

p(A x1^α x2^β): Cobb-Douglas production function p: the market price per unit A: the scale of production α, β: the output elasticities x: input quantity v: output price k: a given constant that restricts the quantity of x1

assess_feas(y: ndarray, gamma: float) → Tuple[ndarray, float] | None

The assess_feas function takes in an input quantity y and a gamma value, and an optional Cut.

Parameters:

• y (Arr) – The parameter y is an array representing the input quantity in log scale

• gamma (float) – The gamma parameter is the best-so-far optimal value. It represents the gamma value that the optimization algorithm is trying to achieve or improve upon

Returns:

The function assess_feas returns an optional Cut. The Cut object represents a linear constraint in the form of a tuple (grad, fj), where grad is a numpy array representing the coefficients of the linear constraint and fj is a float representing the right-hand side of the constraint.

See also

cutting_plane_optim

assess_optim(y: ndarray, gamma: float) → Tuple[Tuple[ndarray, float], float | None]

The assess_optim function takes in an input quantity y and a gamma value, and returns a tuple containing a cut and an updated best-so-far value.

Parameters:

• y (Arr) – The parameter y is an array representing the input quantity in log scale

• gamma (float) – The gamma parameter is the best-so-far optimal value. It represents the gamma value that the optimization algorithm is trying to achieve or improve upon

Returns:

The function assess_optim returns a tuple containing a Cut object and an optional float value. The Cut object represents a linear constraint in the form of a tuple (g, fj), where g is a numpy array representing the coefficients of the linear constraint and fj is a float representing the right-hand side of the constraint.

See also

cutting_plane_optim

elasticities: ndarray

fn1(y: ndarray, _: float) → float

fn2(y: ndarray, gamma: float) → float

grad1(_: float) → ndarray

grad2(gamma: float) → ndarray

idx: int = -1

log_Cobb: float

log_k: float

log_pA: float

price_out: ndarray

q: ndarray

vx: float

class ellalgo.oracles.profit_oracle.ProfitQOracle(params, elasticities, price_out)

Bases: OracleOptimQ

Oracle for a discrete profit maximization problem.

max p(A x1^α x2^β) - v1*x1 - v2*x2 s.t. x1 ≤ k

where:

p(A x1^α x2^β): Cobb-Douglas production function p: the market price per unit A: the scale of production α, β: the output elasticities x: input quantity (must be integer value) v: output price k: a given constant that restricts the quantity of x1

Raises:

AssertionError – [description]

See also

ProfitOracle

assess_optim_q(y: ndarray, gamma: float, retry: bool) → Tuple[Tuple[ndarray, float], ndarray, float | None, bool]

The assess_optim_q function takes in an input quantity y in log scale, a gamma value, and a retry flag, and returns a tuple containing a cut, the gamma value, and the evaluation point.

Parameters:

• y (Arr) – An array representing the input quantity in log scale

• gamma (float) – The gamma parameter is the best-so-far optimal value. It represents the current best value that the optimization algorithm has found

• retry (bool) – A boolean flag indicating whether the optimization should be retried or not

Returns:

The function assess_optim_q returns a tuple containing the following elements:

See also

cutting_plane_optim_q

yd: ndarray

class ellalgo.oracles.profit_oracle.ProfitRbOracle(params: Tuple[float, float, float], elasticities: ndarray, price_out: ndarray, vparams: Tuple[float, float, float, float, float])

Bases: OracleOptim

Oracle for a robust profit maximization problem.

This example is taken from [Aliabadi and Salahi, 2013]:

See also

ProfitOracle

assess_optim(y: ndarray, gamma: float) → Tuple[Tuple[ndarray, float], float | None]

The assess_optim function takes in an input quantity y and a gamma value, and returns a tuple containing a cut and an updated best-so-far value.

Parameters:

• y (Arr) – The parameter y is an array representing the input quantity in log scale

• gamma (float) – The gamma parameter is the best-so-far optimal value. It represents the current best value that has been achieved in the optimization process

Returns:

The function assess_optim returns a tuple containing a Cut object and an optional float value.

See also

cutting_plane_optim