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.
base.LaTeX(obj)[source]

Returns LaTeX representation of Irene’s objects.

class base.base[source]

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

AvailableSDPSolvers()[source]

find the existing sdp solvers.

which(program)[source]

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
relaxations.Calpha_(expn, Mmnt)[source]

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

relaxations.Calpha__(expn, Mmnt, ii, q)[source]

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

class relaxations.Mom(expr)[source]

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 relaxations.SDPRelaxations(gens, relations=(), name='SDPRlx')[source]

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 two 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)[source]

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)[source]

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

Commit(blk, c, idx)[source]

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

Decompose()[source]

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)[source]

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

InitSDP()[source]

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

LocalizedMoment(p)[source]

Computes the reduced symbolic moment generating matrix localized at p.

LocalizedMoment_(p)[source]

Computes the reduced symbolic moment generating matrix localized at p.

Minimize()[source]

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

MomentConstraint(cnst)[source]

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

MomentMat()[source]

Returns the numerical moment matrix resulted from solving the SDP.

MomentsOrd(ordr)[source]

Sets the order of moments to be considered.

PolyCoefFullVec()[source]

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)[source]

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)[source]

Returns a reduce monomial basis up to degree d.

RelaxationDeg()[source]

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

Resume()[source]

Resumes the process of a previously saved program.

SaveState()[source]

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

SetMonoOrd(ord)[source]

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

SetNumCores(num)[source]

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

SetObjective(obj)[source]

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)[source]
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()[source]

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

getConstraint(idx)[source]

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

getMomentConstraint(idx)[source]

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

getObjective()[source]

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

pInitSDP()[source]

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

sInitSDP()[source]

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

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

Instances of this class carry information on the solution of the semidefinite relaxation associated to a optimization problem. It include 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)[source]

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)[source]

Extract solutions based on Lasserre–Henrion’s method.

ExtractSolutionScipy(card=0)[source]

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 followin solvers are currently acceptable by scipy:

  • hybr,
  • lm (default),
  • broyden1,
  • broyden2,
  • anderson,
  • linearmixing,
  • diagbroyden,
  • excitingmixing,
  • krylov,
  • df-sane.
NumericalRank()[source]

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)[source]

Get the leading term of each column.

SetScipySolver(solver)[source]

Sets the scipy.optimize.root solver to solver.

StblRedEch(A)[source]

Compute the stabilized row reduced echelon form.

Term2Mmnt(trm, rnk, X)[source]

Converts a moment object into an algebraic equation.

class sdp.sdp(solver='cvxopt', solver_path={})[source]

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)[source]

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)[source]

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()[source]

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

Option(param, val)[source]

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)[source]

Takes the coefficients of the objective function.

VEC(M)[source]

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

csdp()[source]

Calls SDPA to solve the initiated semidefinite program.

parse_solution_matrix(iterator)[source]

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)[source]

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)[source]

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

sdpa()[source]

Calls SDPA to solve the initiated semidefinite program.

sdpa_param()[source]

Produces sdpa.param file from SolverOptions.

solve()[source]

Solves the initiated semidefinite program according to the requested solver.

write_sdpa_dat(filename)[source]

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

write_sdpa_dat_sparse(filename)[source]

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