Documentation

sdplr(C, As, b, r)
sdplr(C, As, b, r; kwargs...)

These functions tackle the following semidefinite program

\[\begin{aligned} \text{minimize}_{X \succeq 0} \quad &\langle C , X \rangle \\ \text{subject to}\quad &\langle A_i, X \rangle = b_i, \quad \forall i \in [m]\\ & X \in \mathbb{R}^{n \times n} \end{aligned}\]

by factorizing the solution matrix $X$ as $YY^T$ and solve the following nonlinear program instead.

\[\begin{aligned} \text{minimize}\quad &\langle C , YY^T \rangle \\ \text{subject to}\quad &\langle A_i, YY^T \rangle = b_i, \quad \forall i \in [m]\\ & Y \in \mathbb{R}^{n \times r} \end{aligned}\]

Arguments

• As is a vector of $m$ constraint matrices $A_i$ of size $n \times n$. There are four types of constraint matrices supported:
  • SparseMatrixCSC for sparse constraints with nnz $\Theta (n)$.
  • SparseMatrixCOO for super sparse constraints with nnz $o(n)$.
  • SymLowRankMatrix for low-rank constraints with form $BDB^T$.
  • Diagonal for diagonal constraints. Consider using SparseMatrixCOO instead if the diagonal matrix is super sparse.
• C is the cost matrix $C$ of size $n \times n$. Currently we support four types mentioned above.
• b is a vector of m right-hand side values $b_i$.
• r is the initial rank of the solution matrix $Y$.

Optional arguments

• ptol: Tolerance for relative primal infeasibility, i.e.

\[\|\mathcal{A}(YY^T) - b\| / (1 + \|b\|_2).\]

The default value is $10^{-2}$.

• objtol: Tolerance for relative suboptimality, i.e.

\[\langle C, YY^T \rangle - \langle C, X^* \rangle / (1 + |\langle C, YY^T \rangle|).\]

The default value is $10^{-2}$.

• numberlbfgsvecs: Number of L-BFGS vectors. The default value is $4$.
• fprec: Break one major iteration if the relative change of the Lagrangian value is smaller than fprec * eps(). The default value is $10^8$, which is for moderate-accuracy solutions (ptol = objtol = $10^{-2}$).
• prior_trace_bound: A trace bound priorly known or estimated. For example, it is $n$ for max cut. The default value is $10^{18}$.
• σfac: Factor for increasing the smoothing factor $\sigma$ in the augmented Lagrangian. The default value is $2.0$.
• rankupd_tol: Rank update tolerance. After primal infeasibility reaches ptol and objtol is not reached for rankupd_tol major iterations, the rank of the solution matrix $Y$ is doubled. The default value is $4$.
• maxtime: Maximum time in seconds for the optimization. The default value is $3600.0$. There may be some postprocessing overhead so the program will not stop exactly at maxtime. If you want to achieve a hard time limit, use terminal tools.
• printlevel: Print level. The default value is $1$.
• printfreq: How often to print in seconds. The default value is $60.0$.
• maxmajoriter: Maximum number of major iterations. The default value is $10^5$.
• maxiter: Maximum number of total iterations. The default value is $10^7$.
• dataset: Dataset name for better tracking progress, especially when executed parallely. The default value is "".
• eval_DIMACS_errs: Whether to evaluate DIMACS errors. The default value is false.

SymLowRankMatrix{T} <: AbstractMatrix{T}

Symmetric low-rank matrix of the form $BDB^T$ with elements of type T. Besides the diagonal matrix $D$ and the thin matrix $B$, we also store $B^T$ as Bt. It's because usually B is really thin, storing Bt doesn't cost too much more storage but will save allocation during computation.