4
$\begingroup$

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?

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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"? $\endgroup$
    – Robert Bassett
    Jan 19, 2022 at 14:27
  • $\begingroup$ You simply replace element $X_{ij}$ with $c_{ij}$, there is nothing more to do. $\endgroup$
    – Johan Löfberg
    Jan 19, 2022 at 14:30
  • $\begingroup$ I don't follow. Doesn't fixing the elements complicate operations involving the positive semidefinite cone? $\endgroup$
    – Robert Bassett
    Jan 19, 2022 at 14:39
  • $\begingroup$ 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. $\endgroup$
    – Johan Löfberg
    Jan 19, 2022 at 14:46
  • 1
    $\begingroup$ A start perhaps to understand primal vs dual vs image vs kernel yalmip.github.io/tutorial/automaticdualization $\endgroup$
    – Johan Löfberg
    Jan 19, 2022 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.