abstract positive semidefinite cone oracle

for the minimization of the maximum eigenvalue of affine matrix functions (see also implemention of a PSCOracle (PSCAffineFunction)) or, equivalently, Lagrangian relaxation of Linear Programs over the cone of positive semidefinite matrices More...


class  ConicBundle::PSCPrimalExtender
 Interface for extending PrimalData, e.g., in Lagrangian relaxation of column generation approaches. More...
class  ConicBundle::PSCOracle
 Oracle interface for minimization of the maximum eigenvalue of an affine matrix function or, equivalently, Lagrangian relaxation of semidefinite programs. More...
class  ConicBundle::PSCBundleParameters
 Bundle parameters for PSCModel, we recommend no to modify them. More...

Detailed Description

for the minimization of the maximum eigenvalue of affine matrix functions (see also implemention of a PSCOracle (PSCAffineFunction)) or, equivalently, Lagrangian relaxation of Linear Programs over the cone of positive semidefinite matrices

The oracle for the positive semidefinite cone is based on the observation, that the support function over the positive semidefinite matrices with trace 1 is the maximum eigenvalue function,

\[ \lambda_{\max}(C)=\max\{\langle C,X\rangle\colon \langle I,X\rangle=1,X\succeq 0\}\]

For (explicitly or implicitly given) symmetric matrices $C$ and $A_i$ of order $n$ for $i=1,\dots,m$, the abstract PSCOracle represents one of the following convex functions $\mathbf{R}^m\to\mathbf{R}$ depending on the selected parameter ConicBundle::FunctionTask and the scalar factor $\gamma>0$ when adding the function to the problem by MatrixCBsolver::add_function(),

\[ f_\gamma(y)=\gamma \lambda_{\max}(C+\sum y_iA_i), \]

\[ f^+_\gamma(y)=\gamma \max\{0,\lambda_{\max}(C+\sum y_iA_i)\}. \]

\[ f^+_\infty(y)=\gamma \max\{0,\lambda_{\max}(C+\sum y_iA_i)\} \mbox{ with }\gamma\to \infty. \]

While $\gamma$ is the fixed value given explicitly in MatrixCBsolver::add_function() in the first two cases, in the last case only the initial value is supplied and then solver and model successively determine new values so as to ensure (if feasible) that in the end solutions $y$ (almost) satisfy $\lambda_{\max}(C+\sum y_iA_i)\le 0$.

The solver exploits a PSCOracle by using a specialized PSCModel which implements the cutting model of the spectral bundle method, i.e., the cutting surface is determined by an approximation of the active eigenspace of the maximum eigenvalue successively constructed by requesting maximum eigenvalue/eigenvector evaluations via PSCOracle::evaluate(). The approach is explicitly intended for large scale matrices, therefore PSCOracle never supplies the coefficient matrices explicitly but provides access to computing their action on given vectors or matrices and to the evaluation of the mamximum eigenvalue/eigenvector for given $y$. In this sense it is a matrix free oracle. For an implementation that supports various special kinds of matrices (e.g. sparse and low rank matrices) see implemention of a PSCOracle (PSCAffineFunction). Of course special situations may allow for significantly more efficient eigenvalue/eigenvector computations than the general purpose iterative Lanczos method included there. In this case it is recommended to implement a corresponding specialized class derived from PSCOracle.

If in setting up groundset within MatrixCBSolver the $y$ variables are introduced with a linear cost vector $b$ and appropriate sign constraints, the three functions above may be interpreted as the Lagrangian dual to a primal semidefinite program of the form

\[ \mbox{maximize }\langle C,X\rangle \mbox{ subject to } \langle -A_i,X\rangle \begin{array}{c}\le\\=\\\ge\end{array} b_i, ~~ \langle I,X\rangle \begin{array}{c}\le\\=\end{array}\gamma, ~~ X\succeq 0 \]

The constraint $\langle I,X\rangle$ on the trace is always added implicitly and its type is guided by the choice of ConicBundle::FunctionTask in MatrixCBSolver::add_function(). In particular

In terms of the primal SDP view the sense of the constraints $\langle -A_i,X\rangle \begin{array}{c}\le\\=\\\ge\end{array} b_i$ is determined by the sign constraints on the dual variables $y_i$ and these must be encoded in the ConicBundle::Groundset of the y variables, these bounds and the right hand side are not provided by this oracle. The right hand side can be added e.g. as a linear cost term for the variables $y$ or alternatively via an AffineFunctionTransformation.

It is convenient to summarize the effect of the $A_i$ by introducing the mapping ( $\mathbf{S}^n$ refers to the set of real symmetric matrices of order $n$)

\[ \mbox{opA}\colon \mathbf{S}^n\to\mathbf{R}^m, X\mapsto \left[\begin{array}{@{}c@{}} \langle A_1,X\rangle\\[-1ex] \vdots\\[-.5ex] \langle A_m,X\rangle\end{array}\right] \]

The name $\mbox{opA}$ or of its adjoint

\[ \mbox{opAt}\colon \mathbf{R}^m\to\mathbf{S}^n, y\mapsto \sum_{i=1}^m y_iA_i \]

will appear frequently in the names of the members of PSCOracle and its derived classes.

The bundle method computes the cutting model by successively computing and collecting eingenvectors to the maximum eigenvalue of the maximum eigenvalue function. The proper convex/conic combination of these, not needed explicitly yet implicitly computed by the method, successively approximates an optimal solution $X$ to the primal SDP. As this primal approximation is often the central object of interest (e.g. it is the basis for cutting plane approaches) the method can be instructed to collect this primal information explicitly by supplying some PSCPrimal (similar to MatrixPrimal in MatrixFunctionOracle) in the implementation of PSCOracle::generate_minorant(). As the bundle method is designed for large scale matrices, collecting the full matrices (implemented in DensePSCPrimal) might be computationally too expensive, but other variants like collecting only the entries on some sparse support (e.g. in SparsePSCPrimal), sparse combined with a low rank dense part (e.g. in GramSparsePSCPrimal), or collecting each of these just on blocks (BlockPSCPrimal) can be realized by proper implementations of PSCPrimal.

For a concrete implementation of PSCOracle using Matrix Classes (namespace CH_Matrix_Classes) see implemention of a PSCOracle (PSCAffineFunction).

Internally, the SumBlockModel implementation of the spectral bundle model is PSCModel.