SDPSL
Semidefinite Programming Specification Library
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Pages
Public Member Functions | List of all members
sdp::SDPSolutionAnalyzer Class Reference

Tools to analyze solutions of SDPs. More...

#include <analyzer.h>

Public Member Functions

 SDPSolutionAnalyzer (const SDPEnvironment &e=SDPEnvironment())
 Creates an analyzer given an environment.
 
double double_eigenvalues (const Matrix< double > &A, std::vector< double > &eigenvalues) const
 Computes eigenvalues of a symmetric matrix of doubles; see Computing eigenvalues.
 
double double_eigenvalues (const Matrix< double > &A, const MatrixMask &mask, std::vector< double > &eigenvalues) const
 Computes eigenvalues of a symmetric matrix of doubles with a mask; see Computing eigenvalues.
 
double double_eigenvalues (const Matrix< mpf_class > &A, std::vector< double > &eigenvalues) const
 Computes eigenvalues of a symmetric matrix of mpf_class; see Computing eigenvalues.
 
double double_eigenvalues (const Matrix< mpf_class > &A, const MatrixMask &mask, std::vector< double > &eigenvalues) const
 Computes eigenvalues of a symmetric matrix of mpf_class with a mask; see Computing eigenvalues.
 
double feasibility_measures (const std::initializer_list< const SDPConstraintContainer * > &containers, const SDPSolution< double > &solution, std::vector< double > &measures) const
 Computes the feasibility measures of a double solution; see Feasibility measures.
 
mpf_class feasibility_measures (const std::list< const SDPConstraintContainer * > &containers, const SDPSolution< mpf_class > &solution, std::vector< mpf_class > &measures) const
 Computes the feasibility measures of a mpf_class solution; see Feasibility measures.
 
mpf_class feasibility_measures (const std::initializer_list< const SDPConstraintContainer * > &containers, const SDPSolution< mpf_class > &solution, std::vector< mpf_class > &measures) const
 Computes the feasibility measures of a mpf_class solution; see Feasibility measures.
 
void project_solution (const std::initializer_list< const SDPConstraintContainer * > &containers, const SDPSolution< double > &solution, SDPSolution< double > &result) const
 Projects a double solution onto an affine subspace generated by equality constraints using double-precision arithmetic; see Projections.
 
void project_solution (const std::initializer_list< const SDPConstraintContainer * > &containers, const SDPSolution< mpf_class > &solution, SDPSolution< double > &result) const
 Projects a GMP solution onto an affine subspace generated by equality constraints using double-precision arithmetic; see Projections.
 
void project_solution (const std::initializer_list< const SDPConstraintContainer * > &containers, const SDPSolution< double > &solution, SDPSolution< mpf_class > &result) const
 Projects a double solution onto an affine subspace generated by equality constraints using arbitrary-precision arithmetic; see Projections.
 
void project_solution (const std::list< const SDPConstraintContainer * > &containers, const SDPSolution< mpf_class > &solution, SDPSolution< mpf_class > &result) const
 Projects a GMP solution onto an affine subspace generated by equality constraints using arbitrary-precision arithmetic; see Projections.
 
void project_solution (const std::initializer_list< const SDPConstraintContainer * > &containers, const SDPSolution< mpf_class > &solution, SDPSolution< mpf_class > &result) const
 Projects a GMP solution onto an affine subspace generated by equality constraints using arbitrary-precision arithmetic; see Projections.
 

Detailed Description

Tools to analyze solutions of SDPs.

This class provides tools that can be used to analyze solutions of semidefinite programming problems. These tools can be used to:

  • Compute the eigenvalues of symmetric matrices, what can be used to check that the matrices are positive semidefinite. Here we employ an LAPACK routine to compute the eigenvalues, so computations are done using double-precision arithmetic.
  • Compute feasibility measures of a solution, meaning that given some constraints, we compute how violated they are. This can be done using double-precision or arbitrary-precision arithmetic.
  • Project a given solution on a subspace generated by some constraints. This can be used to improve the feasibility measures of a solution. Computations can be carried out in double-precision arithmetic (using LAPACK), or in arbitrary precision arithmetic, using a custom routine.

Computing eigenvalues

Eigenvalues are computed using double-precision arithmetic, even if the matrix uses mpf_class. We use an LAPACK routine to compute eigenvalues, so numerical issues may arise.

Two different kinds of functions to compute eigenvalues are provided. Their prototypes are:

  • double double_eigenvalues(const Matrix<T>& A, std::vector<double>& eigenvalues) const
  • double double_eigenvalues(const Matrix<T>& A, const MatrixMask& mask, std::vector<double>& eigenvalues) const
Parameters
Ais the input matrix, with elements of type T (either double or mpf_class).
maskis an instance of MatrixMask which tells the positions where the matrix is to be considered nonzero.
eigenvaluesis the vector that is filled with the eigenvalues computed; it is resized if necessary.
Returns
The smallest eigenvalue of the matrix.
Exceptions
AnalyzerErrorif the computation fails.
ValueErrorif the matrix supplied is not square, of if the matrix and the mask have different sizes.
Note
Matrix A is assumed to be symmetric; in any case only the lower-diagonal part is used.

Feasibility measures

The measure of violation of a constraint depends on its type:

  • For == constraints, it equals the absolute value of the difference of the right-hand side and the left-hand side.
  • For <= constraints, it equals the maximum of zero and the left-hand side minus the right-hand side.
  • For >= constraints, it equals the maximum of zero and the right-hand side minus the left-hand side.

This means that the measure of violation is always a nonnegative number, and the more positive it is the more violated the constraint is.

Notice that we have described the measure of violation of a linear constraint. Polynomial constraints are transformed into linear equality constraints (see Polynomial constraints and Polynomials and polynomial constraints), so measures of violation can also be applied to them.

There are two functions that can be used to compute feasibility measures, depending on the type of the solution provided. Their prototypes are:

  • double feasibility_measures(const std::initializer_list<const SDPConstraintContainer *>& containers, const SDPSolution<T>& solution, std::vector<T>& measures) const
Parameters
containersis a list of pointers to constraint containers, containing the constraints that are going to be tested.
solutionis the solution to be tested.
measuresis a vector that will contain the measure of violation of each constraint (in the order the constraints are provided); the vector will be resized if necessary.
Returns
The largest violation.

When T is double, computations are done with double-precision arithmetic. When T is mpf_class, computations use arbitrary-precision arithmetic via GMP.

Projections

Solvers use numerical methods and return solutions that are not truly feasible. One way to improve the feasibility measures of a solution for some given set of constraints is to project the solution onto the affine subspace generated by the constraints. This means that we find the closest point to the solution lying on the affine subspace.

SDPSolutionAnalyzer allows for the projection of solutions onto the affine subspace generated by linear equality constraints. These are specified by a constraint container, and might come from a polynomial constraint for instance.

Suppose we have a semidefinite programming problem with variables \(X_1, \ldots, X_r\) and also some linear constraints

\[ \sum_{j=1}^r \langle A_{ij}, X_j\rangle = b_i\quad\text{for $i = 1, \ldots, m$}. \]

Recall that the variable matrices are symmetric. Say \(X_j\) is an \(n_j \times n_j\) matrix, and let

\[ N = \sum_{j=1}^r \frac{n_j (n_j + 1)}{2}. \]

Notice \(N\) is the sum of the number of diagonal and upper-diagonal entries in the matrices \(X_j\). So \((X_1, \ldots, X_r)\) can be naturally identified with a vector \(x \in \mathbb{R}^N\). This means that the system above can be represented as \(F x = b\), where \(F \in \mathbb{R}^{m \times N}\) and \(b \in \mathbb{R}^m\).

We assume that the system \(F x = b\) is under-determined, that is, that \(m \leq N\). We use two different approaches to compute the projection, depending on whether double-precision or arbitrary-precision computations are desired; we will go into details below.

There are four different functions provided to compute projections; their prototypes are of the form:

  • void project_solution(const std::initializer_list<const SDPConstraintContainer *>& containers, const SDPSolution<T>& solution, SDPSolution<U>& result) const

Here, both T and U can be either double or mpf_class.

Parameters
containersis a list of pointers to constraint containers holding the constraints that will define the system giving the affine subspace onto which the projection will be made. Only the equality constraints contained in the container will be considered for the projection.
solutioncontains the solution to be projected.
resultwill contain the result of the projection. This instance of SDPSolution will be adapted to contain the projected solution. Namely, variables in the projection that do not occur in result will be created (without masks), and variables in result will be reset. If a mask is specified for some matrix in result, then it will be set by project_solution. For this, environment parameter output_eps is used: only numbers whose absolute value is at least output_eps are considered nonzero. Notice that it is usually not a good idea to specify masks for the projection, because it is not a priori clear how sparse it is.
Exceptions
ValueErrorif the system provided is over-determined (see above) or empty.
AnalyzerErrorif a call do LAPACK fails, or if the system given by the constraints is infeasible.

Finally, notice also that the projection satisfies all constraints with equality by definition. Since however we use floating-point computations, even after the projection the constraints are not exactly satisfied, but their violations will be very small — one would hope orders of magnitude smaller than the violations of the original solution.

Note
The parameter that determines which method is used for the projection is U. When U is double, then LAPACK is used for the projection. When U is mpf_class, a custom routine is used, as we explain now.

Double-precision projections using LAPACK

To project a given point \(z\) onto the affine subspace given by \(F x = b\), we first find a minimum-norm \(x^*\) such that \(F x^* = b - Fz\), and then the projection is \(\overline{x} = z + x^*\).

LAPACK is used to find this minimum-norm solution. If the solution to be projected is given using mpf_class, then the system is computed using arbitrary-precision arithmetic, but at the end it is converted to a double-precision system for LAPACK to be called. It is possible that there is a gain in precision during the computation of the system, however.

Arbitrary-precision projections with GMP

If result is of type SDPSolution<mpf_class> then the projection is made using arbitrary-precision arithmetic. To project a point \(z\) onto the afine subspace given by \(Fx = b\) we:

  1. Find a point \(x_0\) such that \(Fx_0 = b\);

  2. Project \(z - x_0\) onto the linear subspace given by \(Fx = 0\). This we do by finding the optimal solution \(v^*\) to the least-squares problem \(\min_v \| F^{\sf T} v - (z - x_0) \|^2\); then the projection is \(u = (z - x_0) - F^{\sf T} v^*\);

  3. The projection of \(z\) is then \(u + x_0 = z - F^{\sf T} v^*\).

To execute the above steps, we use the QR decomposition of \(F\).

The documentation for this class was generated from the following file: