4

Suppose I have an SDP

\begin{align}\min_{X \in \mathbb{S}^{n}_{+}}&\quad f(X)\\\text{s.t.} &\quad X_{i,j} = c_{i,j} \quad \forall (i,j) \in I,\end{align} where $I \subseteq [n] \times [n]$ and $f$ is convex on the set of positive semidefinite matrices. Are there any methods for solving SDPs which are able to simplify the problem by eliminating the constrained variables?

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
Robert Bassett
  • 625
  • 7
  • 12
  • 1
    Cross posted: https://scicomp.stackexchange.com/questions/40878/eliminating-variables-in-semidefinite-programs-using-equality-constraints – Robert Bassett Jan 19 '22 at 03:49

2 Answers2

5

I doubt you can eliminate the fixed variables in general but given some special structure it might be possible.

In my paper I describe how to exploit fixed variables inside a primal-dual interior algorithm for conic quadratic optimization. However, I have not been able to generalize this idea to the semi-definite cone in a useful way.

ErlingMOSEK
  • 3,166
  • 10
  • 21
3

Are you talking about doing it in some particularly clever way? If you simply intend to solve the problem in the original dual space (i.e. seeing $X$ as a matrix parameterized by its elements and optimizing over those variables) it is just a matter of deriving a solution and basis for $Ax=c$ where $x$ are the elements parameterizing $X$, i.e., write $x = x_0 + Hz$ and then replace in $X$. In the modelling toolbox YALMIP, that would correspond to using the option removeequalities (which now more or less is obsolete as it most often would be best to let the solver deal with the equalities)

EDIT: In your case the solution and basis is trivial as all your conditions involve single elements, so I might have misunderstood your question.

Johan Löfberg
  • 1,702
  • 5
  • 9
  • Thanks for your input. I do mean to focus on the situation where individual coordinates are equality constrained. Could you expand what you mean by "the solution and basis is trivial"? – Robert Bassett Jan 19 '22 at 14:27
  • You simply replace element $X_{ij}$ with $c_{ij}$, there is nothing more to do. – Johan Löfberg Jan 19 '22 at 14:30
  • I don't follow. Doesn't fixing the elements complicate operations involving the positive semidefinite cone? – Robert Bassett Jan 19 '22 at 14:39
  • All depends on how you are solving the problem. A classical primal-dual solver for an SDP could work by interpreting the equalities from the primal/kernel side as constraints on the primal cone, or from the dual/image side by equalities on the dual variables or by simply deriving another image representation. This would only be an issue if you are using a very particular solution strategy which has to work with a very particular completely unconstrained representation of a cone. – Johan Löfberg Jan 19 '22 at 14:46
  • Excellent. Could you point out some papers or codebases I could look at to understand this in more detail? I'm not familiar with the various representations of the PSD cone you describe. – Robert Bassett Jan 19 '22 at 14:54
  • 1
    A start perhaps to understand primal vs dual vs image vs kernel https://yalmip.github.io/tutorial/automaticdualization – Johan Löfberg Jan 19 '22 at 18:09