Code Documentation

This is the base module for all other objects of the package.

• LaTeX returns a LaTeX string out of an Irene object.

• base is the parent of all Irene objects.

Irene.base.LaTeX(obj)

Returns LaTeX representation of Irene’s objects.

class Irene.base.base

All the modules in Irene extend this class which perform some common tasks such as checking existence of certain software.

AvailableSDPSolvers()

find the existing sdp solvers.

static which(program)

Check the availability of the program system-wide. Returns the path of the program if exists and returns ‘None’ otherwise.

This module is responsible for conversion of a given symbolic optimization problem into semidefinite optimization problems. The main classes included in this module are:

• SDPRelaxations

• SDRelaxSol

• Mom

Irene.relaxations.Calpha_(expn, Mmnt)

Given an exponent expn, this function finds the corresponding \(C_{expn}\) matrix which can be used for parallel processing.

Irene.relaxations.Calpha__(expn, Mmnt, ii, q)

Given an exponent expn, this function finds the corresponding \(C_{expn}\) matrix which can be used for parallel processing.

class Irene.relaxations.Mom(expr)

This is a simple interface to define moment constraints to be used via SDPRelaxations.MomentConstraint. It takes a sympy expression as input and initiates an object which can be used to force particular constraints on the moment sequence.

Example: Force the moment of \(x^2f(x) + f(x)^2\) to be at least .5:

Mom(x**2 * f + f**2) >= .5
# OR
Mom(x**2 * f) + Mom(f**2) >= .5

class Irene.relaxations.SDPRelaxations(gens, relations=(), name='SDPRlx')

This class defines a function space by taking a family of sympy symbolic functions and relations among them. Simply, it initiates a commutative free real algebra on the symbolic functions and defines the function space as the quotient of the free algebra by the ideal generated by the given relations. It takes three arguments:

• gens which is a list of sympy symbols and function symbols,

• relations which is a set of sympy expressions in terms of gens that defines an ideal.

• name is a given name which is used to save the state of the instant at break.

AddConstraint(cnst)

Takes an (in)equality as an algebraic combination of the generating functions that defines the feasibility region. It reduces the defining (in)equalities according to the given relations.

Calpha(expn, Mmnt)

Given an exponent expn, this method finds the corresponding \(C_{expn}\) matrix.

Commit(blk, c, idx)

Sets the latest computed values for the final SDP and saves the current state.

Decompose()

Returns a dictionary that associates a list to every constraint, \(g_i\ge0\) for \(i=0,\dots,m\), where \(g_0=1\). Each list consists of elements of algebra whose sums of squares is equal to \(\sigma_i\) and \(f-f_*=\sum_{i=0}^m\sigma_ig_i\). Here, \(f_*\) is the output of the SDPRelaxation.Minimize().

ExponentsVec(deg)

Returns all the exponents that appear in the reduced basis of all monomials of the auxiliary symbols of degree at most deg.

InitSDP()

Initializes the SDP based on the value of self.Parallel. If it is True, it runs in parallel mode, otherwise in serial.

LocalizedMoment(p)

Computes the reduced symbolic moment generating matrix localized at p.

LocalizedMoment_(p)

Computes the reduced symbolic moment generating matrix localized at p.

Minimize()

Finds the minimum of the truncated moment problem which provides a lower bound for the actual minimum.

MomentConstraint(cnst)

Takes constraints on the moments. The input must be an instance of Mom class.

MomentMat()

Returns the numerical moment matrix resulted from solving the SDP.

MomentsOrd(ordr)

Sets the order of moments to be considered.

PolyCoefFullVec()

return the vector of coefficient of the reduced objective function as an element of the vector space of elements of degree up to the order of moments.

ReduceExp(expr)

Takes an expression expr, either in terms of internal free symbolic variables or generating functions and returns the reduced expression in terms of internal symbolic variables, if a relation among generators is present, otherwise it just substitutes generating functions with their corresponding internal symbols.

ReducedMonomialBase(deg)

Returns a reduce monomial basis up to degree d.

RelaxationDeg()

Finds the minimum required order of moments according to user’s request, objective function and constraints.

Resume()

Resumes the process of a previously saved program.

SaveState()

Saves the current state of the relaxation object to the file self.Name+’.rlx’.

SetMonoOrd(ordr)

Changes the default monomial order to ord which mustbe among lex, grlex, grevlex, ilex, igrlex, igrevlex.

SetNumCores(num)

Sets the maximum number of workers which cannot be bigger than number of available cores.

SetObjective(obj)

Takes the objective function obj as an algebraic combination of the generating symbolic functions, replace the symbolic functions with corresponding auxiliary symbols and reduce them according to the given relations.

SetSDPSolver(solver)

Sets the default SDP solver. The followings are currently supported:

• CVXOPT

• DSDP

• SDPA

• CSDP

The selected solver must be installed otherwise it cannot be called. The default solver is CVXOPT which has an interface for Python. DSDP is called through the CVXOPT’s interface. SDPA and CSDP are called independently.

State()

Returns the latest state of the object at last break and save.

classmethod from_problem(optim_prob: OptimizationProblem, name='SDPRlx')

Creates an SDPRelaxations instance from an OptimizationProblem.

This method acts as an alternative constructor to bridge compatibility with problems defined using SemigroupAlgebra.

Parameters:

• optim_prob (OptimizationProblem) – The optimization problem defined with SemigroupAlgebra.

• name (str) – A name for the relaxation instance.

Returns:

An instance of SDPRelaxations.

getConstraint(idx)

Returns the constraint number idx of the problem after reduction modulo the relations, if given.

getMomentConstraint(idx)

Returns the moment constraint number idx of the problem after reduction modulo the relations, if given.

getObjective()

Returns the objective function of the problem after reduction modulo the relations, if given.

pInitSDP()

Initializes the semidefinite program (SDP), in parallel, whose solution is a lower bound for the minimum of the program.

sInitSDP()

Initializes the semidefinite program (SDP), in serial mode, whose solution is a lower bound for the minimum of the program.

class Irene.relaxations.SDRelaxSol(X, symdict={}, err_tol=1e-05)

Instances of this class carry information on the solution of the semidefinite relaxation associated to an optimization problem. It includes various pieces of information:

• SDRelaxSol.TruncatedMmntSeq a dictionary of resulted moments

• SDRelaxSol.MomentMatrix the resulted moment matrix

• SDRelaxSol.Primal the value of the SDP in primal form

• SDRelaxSol.Dual the value of the SDP in dual form

• SDRelaxSol.RunTime the run time of the sdp solver

• SDRelaxSol.InitTime the total time consumed for initialization of the sdp

• SDRelaxSol.Solver the name of sdp solver

• SDRelaxSol.Status final status of the sdp solver

• SDRelaxSol.RelaxationOrd order of relaxation

• SDRelaxSol.Message the message that maybe returned by the sdp solver

• SDRelaxSol.ScipySolver the scipy solver to extract solutions

• SDRelaxSol.err_tol the minimum value which is considered to be nonzero

• SDRelaxSol.Support the support of discrete measure resulted from SDPRelaxation.Minimize()

• SDRelaxSol.Weights corresponding weights for the Dirac measures

ExtractSolution(mthd='LH', card=0)

Extract support of the solution measure from SDPRelaxations:

-mthd should be either ‘LH’ or ‘Scipy’, where ‘LH’ stands for ‘Lasserre-Henrion’ and ‘Scipy’ employs a Scipy solver to find points matching the moments,

-card restricts the number of points of the support.

ExtractSolutionLH(card=0)

Extract solutions based on Lasserre–Henrion’s method.

ExtractSolutionScipy(card=0)

This method tries to extract the corresponding values for generators of the SDPRelaxation class. Number of points is the rank of the moment matrix which is computed numerically according to the size of its eigenvalues. Then the points are extracted as solutions of a system of polynomial equations using a scipy solver. The following solvers are currently acceptable by scipy:

• hybr,

• lm (default),

• broyden1,

• broyden2,

• anderson,

• linearmixing,

• diagbroyden,

• excitingmixing,

• krylov,

• df-sane.

NumericalRank()

Finds the rank of the moment matrix based on the size of its eigenvalues. It considers those with absolute value less than self.err_tol to be zero.

Pivot(arr)

Get the leading term of each column.

SetScipySolver(solver)

Sets the scipy.optimize.root solver to solver.

StblRedEch(A)

Compute the stabilized row reduced echelon form.

Term2Mmnt(trm, rnk, X)

Converts a moment object into an algebraic equation.

class Irene.sdp.sdp(solver='cvxopt', solver_path=None)

This is the class which intends to solve semidefinite programs in primal format:

\[\begin{split}\left\lbrace \begin{array}{lll} \min & \sum_{i=1}^m b_i x_i & \\ \textrm{subject to} & & \\ & \sum_{i=1}^m A_{ij}x_i - C_j \succeq 0 & j=1,\dots,k. \end{array}\right.\end{split}\]

For the argument solver following sdp solvers are supported (if they are installed):

• CVXOPT,

• CSDP,

• SDPA,

• DSDP.

AddConstantBlock(C)

C must be a list of numpy matrices that represent \(C_j\) for each j. This method sets the value for \(C=[C_1,\dots,C_k]\).

AddConstraintBlock(A)

This takes a list of square matrices which corresponds to coefficient of \(x_i\). Simply, \(A_i=[A_{i1},\dots,A_{ik}]\). Note that the \(i^{th}\) call of AddConstraintBlock fills the blocks associated with \(i^{th}\) variable \(x_i\).

CvxOpt()

This calls CVXOPT and DSDP to solve the initiated semidefinite program.

Option(param, val)

Sets the param option of the solver to val if the solver accepts such an option. The following options are supported by solvers:

• CVXOPT:

  • show_progress: True or False, turns the output to the screen on or off (default: True);

  • maxiters: maximum number of iterations (default: 100);

  • abstol: absolute accuracy (default: 1e-7);

  • reltol: relative accuracy (default: 1e-6);

  • feastol: tolerance for feasibility conditions (default: 1e-7);

  • refinement: number of iterative refinement steps when solving KKT equations (default: 0 if the problem has no second-order cone or matrix inequality constraints; 1 otherwise).

• SDPA:

  • maxIteration: Maximum number of iterations. The SDPA stops when the iteration exceeds maxIteration;

  • epsilonStar, epsilonDash: The accuracy of an approximate optimal solution of the SDP;

  • lambdaStar: This parameter determines an initial point;

  • omegaStar: This parameter determines the region in which the SDPA searches an optimal solution;

  • lowerBound: Lower bound of the minimum objective value of the primal problem;

  • upperBound: Upper bound of the maximum objective value of the dual problem;

  • betaStar: Parameter controlling the search direction when current state is feasible;

  • betaBar: Parameter controlling the search direction when current state is infeasible;

  • gammaStar: Reduction factor for the primal and dual step lengths; 0.0 < gammaStar < 1.0.

SetObjective(b)

Takes the coefficients of the objective function.

static VEC(M)

Converts the matrix M into a column vector acceptable by CVXOPT.

csdp()

Calls SDPA to solve the initiated semidefinite program.

static parse_solution_matrix(iterator)

Parses and returns the matrices and vectors found by SDPA solver. This was taken from ncpol2sdpa and customized for Irene.

read_csdp_out(filename, txt)

Takes a file name and a string that are the outputs of CSDP as a file and command line outputs of the solver and extracts the required information.

read_sdpa_out(filename)

Extracts information from SDPA’s output file filename. This was taken from ncpol2sdpa and customized for Irene.

sdpa()

Calls SDPA to solve the initiated semidefinite program.

sdpa_param()

Produces sdpa.param file from SolverOptions.

solve()

Solves the initiated semidefinite program according to the requested solver.

write_sdpa_dat(filename)

Writes the semidefinite program in the file filename with dense SDPA format.

write_sdpa_dat_sparse(filename)

Writes the semidefinite program in the file filename with sparse SDPA format. Uses sparse iteration over non-zero entries to avoid dense nested loops.

class Irene.program.OptimizationProblem(sga: SemigroupAlgebra | None = None, relations: list[SemigroupAlgebraElement] | None = None)

This class represents an optimization problem.

sga

The semigroup algebra of the optimization problem.

Type:

SemigroupAlgebra

relations

The relations of the optimization problem.

Type:

list[SemigroupAlgebraElement]

semigroup

The semigroup of the optimization problem.

Type:

CommutativeSemigroup

objective

The objective function of the optimization problem.

Type:

SemigroupAlgebraElement

constraints

The constraints of the optimization problem.

Type:

list[SemigroupAlgebraElement]

objective_degree

The degree of the objective function.

Type:

int

objective_half_degree

The half degree of the objective function.

Type:

int

constraints_degree

The degrees of the constraints.

Type:

list[int]

constraints_half_degree

The half degrees of the constraints.

Type:

list[int]

objective_trms_with_positive_coefficient

The terms of the objective function with positive coefficients.

Type:

list[SemigroupAlgebraElement]

objective_trms_with_negative_coefficient

The terms of the objective function with negative coefficients.

Type:

list[SemigroupAlgebraElement]

objective_terms_with_even_exponent

The terms of the objective function with even exponents.

Type:

list[SemigroupAlgebraElement]

objective_terms_with_odd_exponent

The terms of the objective function with odd exponents.

Type:

list[SemigroupAlgebraElement]

constraint_trms_with_positive_coefficient

The terms of the constraints with positive coefficients.

Type:

list[SemigroupAlgebraElement]

constraint_trms_with_negative_coefficient

The terms of the constraints with negative coefficients.

Type:

list[SemigroupAlgebraElement]

constraint_terms_with_even_exponent

The terms of the constraints with even exponents.

Type:

list[SemigroupAlgebraElement]

constraint_terms_with_odd_exponent

The terms of the constraints with odd exponents.

Type:

list[SemigroupAlgebraElement]

total_degree

The total degree of the optimization problem.

Type:

int

add_constraints(const: list[SemigroupAlgebraElement]) → None

Adds polynomial inequality or equality constraints to the optimization problem.

This method extends the optimization problem with additional constraints, typically representing feasibility conditions like bounds or domain restrictions. Each constraint is analyzed for its degree to assist in later relaxation construction.

Place in code structure: Complements set_objective() to fully define the constrained optimization problem. Called during problem setup before relaxation methods.

Parameters:

const (list[SemigroupAlgebraElement]) – List of polynomial constraint expressions, each represented as a SemigroupAlgebraElement.

Returns:

None

Side effects:

• Appends each constraint to self.constraints

• Updates self.semigroup if any constraint uses a different semigroup

• Computes and stores degree and half-degree for each constraint

analyse_program() → None

Performs structural analysis of the optimization problem’s polynomial terms.

This method categorizes all terms from the objective function and constraints based on two key properties: (1) sign of coefficients, and (2) parity of exponents. This analysis is essential for specialized polynomial optimization techniques like SONC (sums of non-negative circuit polynomials) and conditional relaxations.

Place in code structure: Called after problem setup to preprocess the polynomial structure. Populates classification lists used by relaxation algorithms (relaxations.py) and decomposition methods (sonc.py).

Returns:

None

Side effects:

Populates the following attributes: - objective_trms_with_positive/negative_coefficient: Objective terms by sign - constraint_trms_with_positive/negative_coefficient: Constraint terms by sign - objective_terms_with_even/odd_exponent: Objective terms by exponent parity - constraint_terms_with_even/odd_exponent: Constraint terms by exponent parity

convex_combination(point: Sequence[float]) → ndarray | None

Finds the representation of a point as a convex combination of Newton polytope vertices.

This method formulates and solves a linear program to express a point as a convex combination of the polytope vertices, enforcing both non-negativity of coefficients and that they sum to 1. This is more restrictive than linear_combination() but guarantees the point lies within the convex hull.

Place in code structure: Advanced geometric utility for Newton polytope analysis. Uses scipy.optimize to solve the constrained optimization problem. Results can guide sparse relaxation strategies by identifying how to express new terms using existing ones.

Parameters:

point – A numeric sequence representing coordinates in the exponent space that should be expressed as a convex combination of self.vertices.

Returns:

Array of non-negative coefficients summing to 1 that express the point

as a convex combination of vertices, or None if no such combination exists (i.e., point is outside the Newton polytope).

Return type:

numpy.ndarray

delta(xprsn: SemigroupAlgebraElement, deg: int) → dict[str, set]

Identifies problematic terms in polynomial expressions for relaxation construction.

The delta function categorizes terms that cannot be directly represented in a sum-of-squares (SOS) form: terms with odd exponents or negative coefficients. These terms are grouped by whether their total degree equals the target degree (‘=d’) or is less than it (‘<d’), which affects how they’re handled in relaxations.

Place in code structure: Core analysis method used by relaxation algorithms (relaxations.py) to identify which terms need special treatment through auxiliary variables or alternative decomposition strategies.

Parameters:

• xprsn (SemigroupAlgebraElement) – The polynomial expression to analyze.

• deg (int) – The target degree for comparison.

Returns:

Dictionary with two keys:

’=d’: Set of monomials with degree exactly equal to deg ‘<d’: Set of monomials with degree less than deg Both contain only non-square or negative coefficient terms.

Return type:

dict[str, set[SemigroupAlgebraElement]]

delta_vertex(xprsn: SemigroupAlgebraElement, vertices: list) → None

Computes delta relative to Newton polytope vertices (currently unimplemented).

This method is intended to analyze terms based on their relationship to the vertices of the Newton polytope, likely for geometric programming or sparsity exploitation.

Place in code structure: Placeholder for advanced geometric analysis that would work with the newton() and related polytope methods for exploiting problem structure.

Parameters:

• xprsn (SemigroupAlgebraElement) – The expression to analyze.

• vertices (list) – List of vertices from the Newton polytope.

Returns:

None (not yet implemented)

static has_symbol(symb: str, mono: SemigroupAlgebraElement) → tuple[bool, int]

Searches for a specific variable (symbol) in a monomial and returns its position.

This method determines whether a given variable name appears in a monomial’s factorization, which is useful for variable-specific operations like substitution, elimination, or targeted relaxation strategies.

Place in code structure: Static utility method for monomial inspection. Used by various algorithms that need to check variable presence or extract variable-specific information from polynomial terms.

Parameters:

• symb (str) – The name of the variable/symbol to search for (e.g., ‘x’, ‘y’).

• mono (SemigroupAlgebraElement) – The monomial to search within.

Returns:

A tuple where the first element is True if the symbol is found,

False otherwise. The second element is the index of the symbol in the monomial’s array form if found, or -1 if not found.

Return type:

tuple[bool, int]

in_newton(point: Sequence[float]) → bool

Tests whether a point lies inside the Newton polytope.

This method uses Delaunay triangulation to efficiently determine if a given point (typically representing a monomial’s exponents) is within the convex hull of the problem’s support. This is useful for determining which monomials are representable as convex combinations of existing terms.

Place in code structure: Geometric query method that depends on newton() being called first. Used in sparsity analysis and to determine valid monomial spaces for relaxations.

Parameters:

point – A numeric sequence (tuple, list, or array) representing exponent coordinates to test for inclusion in the Newton polytope.

Returns:

True if the point is inside or on the boundary of the Newton polytope,

False otherwise.

Return type:

bool

Raises:

ValueError – If vertices are empty or if Delaunay triangulation fails due to degenerate geometry.

linear_combination(point: Sequence[float]) → ndarray

Expresses a point as a linear combination of Newton polytope vertices.

This method solves a linear system to find coefficients that express the given point as a linear combination of polytope vertices. Note that unlike convex_combination(), this method doesn’t enforce non-negativity or that coefficients sum to 1, so it’s suitable for affine (not necessarily convex) combinations.

Place in code structure: Geometric utility for expressing points in terms of vertices. Complements convex_combination() but with less restrictive constraints. Used when affine relationships are needed rather than strictly convex ones.

Parameters:

point – A numeric sequence representing coordinates to express in terms of vertices.

Returns:

Array of coefficients for the linear combination. Note that these

coefficients may be negative or sum to values other than 1.

Return type:

numpy.ndarray

Note

Excludes the origin vertex [0, 0, …] if present to avoid singularity issues.

mono2ord_tuple(mono: Any) → tuple[int, ...]

Converts a monomial from semigroup representation to a tuple of exponents.

This method transforms a symbolic monomial into a numeric tuple where each position corresponds to a generator in the semigroup, containing that generator’s exponent. This standardized format is essential for numerical computations like convex hull calculations and geometric analysis.

Place in code structure: Conversion utility used by newton() and related geometric methods to transform symbolic polynomial data into numeric arrays suitable for scipy geometric algorithms.

Parameters:

mono (SemigroupAlgebraElement) – The monomial to convert. Can also be a scalar (int or float) representing a constant term.

Returns:

A tuple of integers representing the exponents of each generator in order.

For constants, returns a tuple of zeros.

Return type:

tuple

newton() → None

Computes the Newton polytope of the optimization problem.

The Newton polytope is the convex hull of all exponent vectors appearing in the objective function and constraints. This geometric object encodes the sparsity structure of the problem and can be exploited to construct more efficient relaxations.

Place in code structure: Geometric analysis method that should be called after problem setup. Its results (stored in newton_polytope and vertices) are used by in_newton(), convex_combination(), and potentially specialized relaxation strategies.

Returns:

None

Side effects:

• Collects all exponent tuples from objective and constraints

• Computes and stores the convex hull in self.newton_polytope

• Extracts and stores sorted vertex list in self.vertices

• Raises ValueError if polytope is degenerate (insufficient points or dimension mismatch)

static omega(xprsn: SemigroupAlgebraElement, deg: int) → list[tuple[float, Any]]

Extracts terms from a polynomial that don’t match a specific univariate degree pattern.

The omega function filters out univariate monomials of exactly the specified degree, keeping all multivariate terms, constant terms, and univariate terms of other degrees. This is used in conditional optimization where certain degree-specific terms need special treatment.

Place in code structure: Static helper method used by delta() to identify terms that require special handling in relaxation construction, particularly for conditional constraints and geometric programming.

Parameters:

• xprsn (SemigroupAlgebraElement) – The polynomial expression to filter.

• deg (int) – The specific univariate degree to exclude.

Returns:

List of (coefficient, monomial) tuples

representing terms that don’t match the degree criterion.

Return type:

list[tuple[int, SemigroupAlgebraElement]]

program_degree() → int

Computes the overall degree of the optimization problem.

This method determines the maximum degree among all polynomials (objective and constraints) in the problem, rounded up to the nearest even number. This degree is critical for determining the size of sum-of-squares (SOS) relaxations.

Place in code structure: Utility method used during relaxation construction to determine the appropriate degree for SOS decompositions and moment matrices.

Returns:

The maximum degree among all polynomials, adjusted to be even (adds 1 if odd).

This ensures compatibility with SOS relaxations which require even degrees.

Return type:

int

set_objective(obj: SemigroupAlgebraElement) → None

Sets the objective function for the optimization problem.

This method is central to defining the optimization problem. It assigns the objective function that will be minimized or maximized, and automatically updates the semigroup and computes the degree information needed for polynomial optimization.

Place in code structure: Core setup method that must be called before relaxation generation. Works with add_constraints() to fully specify the optimization problem.

Parameters:

obj (SemigroupAlgebraElement) – A polynomial expression to be optimized, represented as an element in a semigroup algebra.

Returns:

None

Side effects:

• Updates self.objective with the provided expression

• Updates self.semigroup if different from current

• Computes and stores objective_degree (total degree of the leading monomial)

• Computes and stores objective_half_degree (ceiling of degree/2)

static square_exponent(xpnt: Any) → bool

Determines if a monomial has only even exponents (is a perfect square).

This method checks whether all variables in a monomial appear with even powers, meaning the monomial can be expressed as a square of another monomial. This property is fundamental for identifying terms that are inherently non-negative and for constructing sum-of-squares decompositions.

Place in code structure: Static utility method used throughout analysis and relaxation construction. Called by analyse_program(), delta(), and other methods that need to identify square monomials for optimization techniques.

Parameters:

xpnt (SemigroupAlgebraElement) – A monomial whose exponents are to be checked.

Returns:

True if all exponents in the monomial are even (divisible by 2),

False if any exponent is odd.

Return type:

bool

to_sympy(expr: SemigroupAlgebraElement, sym_map: dict[str, Symbol])

Converts a SemigroupAlgebraElement polynomial to a SymPy symbolic expression.

This method provides interoperability with the SymPy computer algebra system, enabling use of SymPy’s extensive symbolic manipulation capabilities (differentiation, integration, simplification, etc.) on polynomials defined in the semigroup algebra framework.

Place in code structure: Interface method for exporting to SymPy. Useful for visualization, symbolic analysis, or interfacing with other tools that expect SymPy expressions. Complements the internal semigroup algebra representation.

Parameters:

• expr (SemigroupAlgebraElement) – The polynomial expression to convert.

• sym_map (dict) – Dictionary mapping generator name strings to SymPy Symbol objects, e.g., {‘x’: Symbol(‘x’), ‘y’: Symbol(‘y’)}.

Returns:

A SymPy expression algebraically equivalent to the input, using the

symbols provided in sym_map.

Return type:

sympy.Expr

tuple2mono(xpnt: Sequence[int])

Converts a tuple of exponents back to a monomial in semigroup representation.

This method performs the inverse operation of mono2ord_tuple, constructing a symbolic monomial from numeric exponents. Each position in the input tuple corresponds to the power of the respective generator in the semigroup.

Place in code structure: Inverse conversion utility that works with mono2ord_tuple to enable round-trip conversions between symbolic and numeric representations. Used when translating geometric analysis results back to polynomial terms.

Parameters:

xpnt – A sequence (tuple or list) of integers representing exponents for each generator in the semigroup, in the same order as semigroup.generators.

Returns:

The monomial product of generators raised to their

corresponding powers from xpnt.

Return type:

SemigroupAlgebraElement

A module for working with commutative semigroups and their differential algebras.

This module provides classes and functions for working with commutative semigroups and their differential algebras.

A semigroup is a set S together with an associative binary operation on S. A commutative semigroup is a semigroup in which the binary operation is commutative.

A semigroup algebra is a vector space over a field with a basis consisting of the elements of a semigroup equipped with multiplication compatible with the semigroup’s operation.

This module provides the following classes:

• CommutativeSemigroup: A class representing a commutative semigroup.

• AtomicSGElement: A class representing an atomic element of a semigroup algebra.

• SemigroupAlgebraElement: A class representing an element of a semigroup algebra.

• SemigroupAlgebra: A class representing a semigroup algebra.

This module also provides the following functions:

• _degree: Computes the degree of a given expression.

• diff: Computes the derivative of an expression in a semigroup algebra.

class Irene.grouprings.AtomicSGElement(semigroup: CommutativeSemigroup, element: str)

An atomic element of a semigroup algebra.

An atomic element is an element of the semigroup algebra that is not a sum of other elements.

semigroup

The semigroup of the element.

Type:

CommutativeSemigroup

symbol

The symbol of the element.

Type:

str

content

The content of the element.

Type:

list

LC() → float

Returns the leading coefficient of the element.

The leading coefficient of an element is the coefficient of the term with the highest degree.

Returns:

The leading coefficient of the element.

Return type:

float

LM() → Expr

Returns the leading monomial of the element.

The leading monomial of an element is the monomial with the highest degree.

Returns:

The leading monomial of the element.

Return type:

sympy.Expr

LT() → SemigroupAlgebraElement

Returns the leading term of the element.

The leading term of an element is the term with the highest degree.

Returns:

The leading term of the element.

Return type:

SemigroupAlgebraElement

divide(fs: list) → tuple[list, SemigroupAlgebraElement]

Divides the element by a list of elements or expressions.

Parameters:

fs (list) – The list of elements or expressions to divide by.

Returns:

A tuple containing the quotient and remainder of the division.

Return type:

tuple

lt_divisible_by(expr: Any) → bool

Checks if the leading term of the element is divisible by the leading term of another element or expression.

Parameters:

expr (int, float, AtomicSGElement, SemigroupAlgebraElement) – The element or expression to check divisibility by.

Returns:

True if the leading term of the element is divisible by the leading term of the other element or expression, False otherwise.

Return type:

bool

class Irene.grouprings.CommutativeSemigroup(gens: list, is_semigroup: bool = True, is_abelian: bool = True)

A class representing a commutative semigroup.

A semigroup is a set S together with an associative binary operation on S. A commutative semigroup is a semigroup in which the binary operation is commutative.

gens

The generators of the semigroup.

Type:

list

is_semigroup

True if the semigroup is a semigroup, False otherwise.

Type:

bool

is_abelian

True if the semigroup is abelian, False otherwise.

Type:

bool

rels

The relations of the semigroup.

Type:

list

aux_rels

The auxiliary relations of the semigroup.

Type:

list

inverses

The inverses of the generators of the semigroup.

Type:

dict

max_deg

The maximum degree of the relations of the semigroup.

Type:

int

edges

The edges of the lattice of the semigroup.

Type:

list

vertices

The vertices of the lattice of the semigroup.

Type:

dict

symbols

The symbols of the semigroup.

Type:

list

add_relations(rels: list)

Adds relations to the semigroup.

Parameters:

rels (list) – The relations to add to the semigroup.

degree(expr) → int

Computes the degree of an expression in the semigroup.

The degree of an expression is the sum of the absolute values of the exponents of its terms.

Parameters:

expr – The expression whose degree is to be computed.

Returns:

The degree of the expression.

Return type:

int

element_sub_lattice(elm: Expr, ex: set = None) → set

Computes the sublattice of the lattice of the semigroup generated by an element.

Parameters:

• elm (sympy.Expr) – The element of the semigroup to generate the sublattice from.

• ex (set) – The set of elements to exclude from the sublattice.

Returns:

The sublattice of the lattice of the semigroup generated by the element.

Return type:

set

lattice_edges(degree: int) → None

Computes the edges of the lattice of the semigroup.

Parameters:

degree (int) – The degree of the lattice.

lattice_vertices() → None

Computes the vertices of the lattice of the semigroup.

The vertices of the lattice are the elements of the semigroup that are generated by the edges of the lattice.

positive_exp(expr: Expr) → bool

Checks if an expression in the semigroup has only positive exponents.

Parameters:

expr (sympy.Expr) – The expression to check.

Returns:

True if the expression has only positive exponents, False otherwise.

Return type:

bool

class Irene.grouprings.SemigroupAlgebra(semigroup: CommutativeSemigroup)

A semigroup algebra.

A semigroup algebra is a vector space over a field with a basis consisting of the elements of a semigroup.

gens

The generators of the semigroup.

Type:

list

semigroup

The semigroup of the algebra.

Type:

CommutativeSemigroup

derivatives

A list of dictionaries mapping the elements of the semigroup to their derivatives.

Type:

list

add_derivative(base_map: dict) → None

Adds a derivative to the algebra.

Parameters:

base_map (dict) – A dictionary mapping the elements of the semigroup to their derivatives.

derivative(expr: Any, idx: int)

Computes the derivative of an expression in the algebra.

Parameters:

• expr (SemigroupAlgebraElement, AtomicSGElement, int, float) – The expression to differentiate.

• idx (int) – The index of the derivative to use.

Returns:

The derivative of the expression.

Return type:

SemigroupAlgebraElement

diff(expr: Any, base_map: dict)

Computes the derivative of an expression in the algebra.

Parameters:

• expr (SemigroupAlgebraElement, AtomicSGElement, int, float) – The expression to differentiate.

• base_map (dict) – A dictionary mapping the elements of the semigroup to their derivatives.

Returns:

The derivative of the expression.

Return type:

SemigroupAlgebraElement

class Irene.grouprings.SemigroupAlgebraElement(terms: list, semigroup: CommutativeSemigroup)

An element of a semigroup algebra.

A semigroup algebra is a vector space over a field with a basis consisting of the elements of a semigroup.

content

The content of the element.

Type:

list

semigroup

The semigroup of the element.

Type:

CommutativeSemigroup

LC() → float

Returns the leading coefficient of the element.

The leading coefficient of an element is the coefficient of the term with the highest degree.

Returns:

The leading coefficient of the element.

Return type:

float

LM() → Expr

Returns the leading monomial of the element.

The leading monomial of an element is the monomial with the highest degree.

Returns:

The leading monomial of the element.

Return type:

sympy.Expr

LT() → SemigroupAlgebraElement

Returns the leading term of the element.

The leading term of an element is the term with the highest degree.

Returns:

The leading term of the element.

Return type:

SemigroupAlgebraElement

divide(fs: list) → tuple[list, SemigroupAlgebraElement]

Divides the element by a list of elements or expressions.

Parameters:

fs (list) – The list of elements or expressions to divide by.

Returns:

A tuple containing the quotient and remainder of the division.

Return type:

tuple

lt_divisible_by(expr: Any) → bool

Checks if the leading term of the element is divisible by the leading term of another element or expression.

Parameters:

expr (int, float, AtomicSGElement, SemigroupAlgebraElement) – The element or expression to check divisibility by.

Returns:

True if the leading term of the element is divisible by the leading term of the other element or expression, False otherwise.

Return type:

bool

This module provides a framework for polynomial optimization using the techniques introduced by Ghasemi, Lasserre, and Marshall, using Geometric Programming.

class Irene.geometric.GPRelaxations(prog: OptimizationProblem, **kwargs)

This class aims to provide a framework for polynomial optimization using the techniques introduced by Ghasemi, Lasserre, and Marshall, using Geometric Programming.

auto_transform_matrix() → ndarray

Compute the automatic transformation matrix H.

Returns:

The transformation matrix H.

static compare_diags(vec: list[float]) → tuple[int, list[float]]

Compare two vectors by the number of non-zero elements.

Parameters:

vec – The first vector.

Returns:

The number of non-zero elements in the vector.

h_plus(xprsn: Any, idn: Any = None) → float

Compute the h_plus function for a given expression.

Parameters:

• xprsn – The expression to evaluate.

• idn – The identity element of the semigroup.

Returns:

The value of h_plus(xprsn).

solve() → float

Form the geometric program relaxation.

Returns:

The optimal value of the relaxation.

transform_program() → None

Transform the program using the transformation matrix H.

class Irene.sonc.SONCRelaxations(prog: OptimizationProblem, **kwargs)

Framework for constrained SONC relaxations formulated as geometric programs.

solve(verbosity: int | None = None) → float

Build and solve the constrained SONC geometric program.