Interfaces with solvers

inflation.sdp.sdp_utils.solveSDP_MosekFUSION(mask_matrices: Dict | None = None, objective: Dict | None = None, known_vars: Dict | None = None, semiknown_vars: Dict | None = None, inequalities: List[Dict] | None = None, equalities: List[Dict] | None = None, solve_dual: bool = True, default_non_negative: bool = False, feas_as_optim: bool = False, verbose: int = 0, solverparameters: Dict = {}, process_constraints: bool = True) → Dict[str, Any][source]

Internal function to solve the SDP with the MOSEK Fusion API.

Now follows an extended description of how the SDP is encoded. In general, it is preferred to solve using the dual formulation, which is the default.

The primal is written as follows:

\[\begin{split}\text{max}\quad & c_0 + c\cdot x\\ \text{s.t.}\quad & F_0 + \sum F_i x_i \succeq 0\end{split}\]

\(F_0\) is the constant entries of the moment matrix, and \(F_i\) is the matrix whose entry \((n,m)\) stores the value of the coefficient of the moment \(x_i\) at position \((n,m)\) in the moment matrix.

The dual of the equation above is:

\[\begin{split}\text{min}\quad & c_0+\text{Tr}(Z\cdot F_0)\\ \text{s.t.}\quad & \text{Tr}(Z\cdot F_i) = - c_i \,\forall\, i,\\ &Z \succeq 0.\end{split}\]

Typically, all the probability information is stored in \(F_0\), and the coefficients \(F_i\) do not depend on the probabilities. However, if we use LPI constraints (see, e.g., arXiv:2203.16543), then \(F_i\) can depend on the probabilities. The form of the SDP does not change, in any case.

If we have a constant objective function, then we have a feasibility problem. It can be rewritten into the following optimization problem:

\[\begin{split}\text{max}\quad&\lambda\\ \text{s.t.}\quad& F_0 + \sum F_i x_i - \lambda \cdot 1 \succeq 0,\end{split}\]

which achieves \(\lambda\geq 0\) if the original problem is feasible and \(\lambda<0\) otherwise. The dual of this problem is:

\[\begin{split}\text{min}\quad & \text{Tr}(Z\cdot F_0) \\ \text{s.t.}\quad & \text{Tr}(Z\cdot F_i) = 0 \,\forall\, i,\\ & Z \succeq 0,\,\text{Tr} Z = 1.\end{split}\]

This still allows for the extraction of certificates. If we use a \(Z_{P_1}\) obtained from running the problem above on the probability distribution \(P_1\), and we find that \(\text{Tr}[Z_{P_1}\cdot F_0(P_2)] < 0\), then clearly this is an upper bound of the optimal value of the problem, and thus we can certify that the optimisation will be negative when using \(P_2\).

If we have upper and lower bounds on the variables, the problems change as follows:

\[\begin{split}\text{max}\quad & c_0 + c\cdot x \\ \text{s.t.}\quad & F_0 + \sum F_i x_i \succeq 0,\\ & x_i - l_i \geq 0,\\ & u_i - x_i \geq 0,\end{split}\]

with dual:

\[\begin{split}\text{min}\quad & \text{Tr}(Z\cdot F_0 - L\cdot l + U\cdot u) \\ \text{s.t.}\quad & \text{Tr}(Z \cdot F_i) = -c_i+U_i-L_i\,\forall\,i,\\ & Z \succeq 0,\,L \geq 0,\,U \geq 0.\end{split}\]

The relaxed feasibility problems change accordingly.

Parameters:

mask_matrices (dict) – A dictionary with keys as monomials and values as scipy sparse arrays indicating the locations of the monomial in the moment matrix.
objective (dict, optional) – Dictionary with keys as monomials and as values the monomial’s coefficient in the objective function.
known_vars (dict, optional) – Dictionary of values for monomials (keys).
semiknown_vars (dict, optional) – Dictionary encoding proportionality constraints between different monomials.
inequalities (list, optional) – List of inequalities encoded as dictionaries of coefficients.
equalities (list, optional) – List of equalities encoded as dictionaries of coefficients.
solve_dual (bool, optional) – Whether to solve the dual (True) or primal (False) formulation. By default True.
default_non_negative (bool, optional) – Whether to set default primal variables as non-negative (True) or not (False). By default, False.
feas_as_optim (bool, optional) – Whether to treat feasibility problems, where the objective is, constant, as an optimisation problem. By default False.
verbose (int, optional) – How much information to display to the user. By default 0.
solverparameters (dict, optional) – Dictionary of parameters to pass to the MOSEK solver, see MOSEK’s documentation.
process_constraints (bool, optional) – Whether to remove the simple equalities constraints contained in the semiknown_vars arguments by eliminating variables (True) or pass them to the solver as equality constraints (False). By default True.

Returns:

The first element of the tuple is a dictionary containing the optimisation information such as the 1) primal objective value, 2) the moment matrix, 3) the dual values, 4) the certificate and a 5) dictionary of values for the monomials, in the following keys in the same order: 1) sol, 2) G, 3) Z, 4) dual_certificate, 5) xi. The second element is the objective value and the last is the problem status.

Return type:

Tuple[Dict, float, str]

inflation.lp.lp_utils.solveLP_sparse(objective: ~scipy.sparse._coo.coo_array = <0x0 sparse array of type '<class 'numpy.int8'>' with 0 stored elements in COOrdinate format>, known_vars: ~scipy.sparse._coo.coo_array = <0x0 sparse array of type '<class 'numpy.int8'>' with 0 stored elements in COOrdinate format>, inequalities: ~scipy.sparse._coo.coo_array = <0x0 sparse array of type '<class 'numpy.int8'>' with 0 stored elements in COOrdinate format>, equalities: ~scipy.sparse._coo.coo_array = <0x0 sparse array of type '<class 'numpy.int8'>' with 0 stored elements in COOrdinate format>, lower_bounds: ~scipy.sparse._coo.coo_array = <0x0 sparse array of type '<class 'numpy.int8'>' with 0 stored elements in COOrdinate format>, upper_bounds: ~scipy.sparse._coo.coo_array = <0x0 sparse array of type '<class 'numpy.int8'>' with 0 stored elements in COOrdinate format>, solve_dual: bool = False, default_non_negative: bool = True, relax_known_vars: bool = False, relax_inequalities: bool = False, verbose: int = 0, solverparameters: ~typing.Dict | None = None, variables: ~typing.List | None = None) → Dict[source]

Internal function to solve an LP with the Mosek Optimizer API using sparse matrices. Columns of each matrix correspond to a fixed order of variables in the LP.

Parameters:

objective (coo_array, optional) – Objective function with coefficients as matrix entries.
known_vars (coo_array, optional) – Known values of the monomials with values as matrix entries.
inequalities (coo_array, optional) – Inequality constraints in matrix form.
equalities (coo_array, optional) – Equality constraints in matrix form.
lower_bounds (coo_array, optional) – Lower bounds of variables with bounds as matrix entries.
upper_bounds (coo_array, optional) – Upper bounds of variables with bounds as matrix entries.
solve_dual (bool, optional) – Whether to solve the dual (True) or primal (False) formulation. By default, False.
default_non_negative (bool, optional) – Whether to set default primal variables as non-negative. By default, True.
relax_known_vars (bool, optional) – Do feasibility as optimization where each known value equality becomes two relaxed inequality constraints. E.g., P(A) = 0.7 becomes P(A) + lambda >= 0.7 and P(A) - lambda <= 0.7, where lambda is a slack variable. By default, False.
relax_inequalities (bool, optional) – Do feasibility as optimization where each inequality is relaxed by the non-negative slack variable lambda. By default, False.
verbose (int, optional) – Verbosity. Higher means more messages. By default, 0.
solverparameters (dict, optional) – Parameters to pass to the MOSEK solver. For example, to control whether presolve is applied before optimization, set mosek.iparam.presolve_use to mosek.presolvemode.on or mosek.presolvemode.off. Or, control which optimizer is used by setting an optimizer type to mosek.iparam.optimizer. See MOSEK’s documentation for more details.
variables (list) – Monomials by name in same order as column indices of all other solver arguments

Returns:

Primal objective value, dual objective value, problem status, success status, dual certificate (as dictionary and sparse matrix), x values, and response code.

Return type:

dict