[FileFormats.CBF] add support for PSDVAR

[rbassett3]

I recently wrote a JuMP model which I exported to CBF and solved using a solver that doesn't have a JuMP interface. I was reviewing the file to make sense of the output and was surprised to note that the MathOptInterface completely ignores one part of the CBF specification by omitting PSDVAR. It's even written into the code but commented out. Is there a reason for this? It seems like it potentially could generate CBF files which are not solved as efficiently as they could be.

Link to the relevant line of the CBF writer

[odow]

Related: #1402

I closed because no one was really asking for it haha.

It's do-able, but a little tricky to get right. Have you verified that it made a difference to the solver? Which solver is it? What conic form does it expect problems in? Ax + b in K or x in K, Ax = b?

[rbassett3]

I am using SCIP-SDP, with SDP subproblems outsourced to Mosek. So it's x in K, Ax = b.

For the problem I'm working on, I've got to do a deep dive into the JuMP CBF interface. If you don't mind, I'd like to keep this issue open for a bit. I'll test to see if constraining a symmetric variable using PSDCON yields any difference in performance compared to using PSDVAR directly.

On one hand, the formulations seem exactly equivalent, and it's hard for me to imagine a solver doing something special because PSDVAR was used instead of PSDCON. But then why does PSDVAR even exist as part of the CBF specification? Just a shorthand for declaring variables subject to a PSD constraint?

Anyways, I'll test and report back.

[odow]

But then why does PSDVAR even exist as part of the CBF specification

Mosek used to (and maybe still does) require that PSD matrices are "special" and declared up front as PSDVAR. If you added Ax + b in PSD, then we'd add a new matrix S in PSD with the linear constraints Ax + b == S.

[odow]

I'm tempted to close this, but @blegat can decide. I think Ax + b in K is a reasonable thing to write. File formats don't have to be the most solver-efficient format.

[blegat]

I think it's important to support. When a PSD variable is declared as constraint and passed to a solver that only supports variable declared as variable, it will create a new PSD variable as slack and then add equality constraints and that's terribly slow. That's the case for solvers that are expecting PSD variable hence also solvers expecting PSD constraints used behind a Dualization.jl layer ;) Mosek is kind of a special case since it's in a transition between PSD variable and PSD constraints so at the moment it supports both but it will only support PSD constraints at some point (so only PSD variables behind Dualization.jl)

[odow]

We're assuming that the solver implements a file reader for CBF and that it doesn't implement any support for this transition? We also don't (other than this SCIP-SDP solver) have anyone actively using the CBF writer... This is another of those, yes, I agree we could implement it, but I don't know if it's important, or worth the added code complexity.

[blegat]

We're assuming that the solver implements a file reader for CBF and that it doesn't implement any support for this transition?

Does the solver need special support for CBF ? Someone can write a CBF file and then read it and copy it to an SCS solver + dualization layer + bridge layer. There, slack variables will be introduced if the PSD variables were converted to affine PSD constraint when writing to CBF.

[odow]

So one sticking point is that when writing CBF files, we don't have a standard form that maps neatly onto CBF. Their PSDVar's can't be used in integrality, and they're kept in matrix form, not scalarized form, so we'd need to parse every affine expression looking for PSD variables and factor out the required F matrices.

One thing we could easily do is, on reading, if the constraint is I * x in K, then we could add as VectorOfVariables instead of VectorAffineFunction? That'd solve your SCS example.

[blegat]

So one sticking point is that when writing CBF files, we don't have a standard form that maps neatly onto CBF. Their PSDVar's can't be used in integrality, and they're kept in matrix form, not scalarized form, so we'd need to parse every affine expression looking for PSD variables and factor out the required F matrices.

Yes, this is what MosekTools is doing. If a clean way to do this is done in CBF, we could use the utilities to refactor and simplify MosekTools (but that's optional).

[odow]

this is what MosekTools is doing

Oh 😢 now I don't want to look

[blegat]

This is part of the reason MosekTools is not using MatrixOfConstraints

[odow]

I guess at minimum, we could write variable cones of things other than PSDVAR as a preliminary improvement.

[odow]

#2478 added support for some x in K constraints.

I still need to look at EXP and EXP* cones, and PSDVAR block.

[odow]

The EXP cone stuff is #2482

So now all we're missing is PSDVAR.

[odow]

@blegat: am I right in reading that a PSDVAR cannot itself appear in an affine PSD constraint?

Getting this right seems pretty nasty.

[blegat]

I think it can with Mosek, that's what the bar{F}_{ij} matrices are for in https://docs.mosek.com/latest/capi/tutorial-sdo-shared.html}}

[odow]

It can with Mosek, but not with CBF: https://docs.mosek.com/latest/capi/cbf-format.html

$G_i$ does not include $X_j$ variables, and HCOORD explicitly mentions only scalar variables:

[blegat]

This seems possible indeed. That's a limitation of CBF then, I don't think we should do anything special to work around it. If the CBF writer sees PSD variables in a VAF-in-PSD constraint, it should error then.

[odow]

If the CBF writer sees PSD variables in a VAF-in-PSD constraint, it should error then.

Currently we don't write any PSDVAR, so this isn't a problem.

We can add VectorOfVariables-in-PositiveSemidefiniteConeTriangle as PSDVAR if:

• the variables don't appear in another PositiveSemidefiniteConeTriangle constraint
• the variables are not integer

But that seems a bit complicated to implement, and we likely can't share much of the code with MosekTools because they're slightly different.

[rbassett3]

I have been lurking but don't have the Julia or MathOptInterface expertise to be very useful in this discussion.

I just want to say that, given @odow's observation that variables declared PSD can't be used in affine constraints in the CBF format, I think it makes more sense to avoid declaring PSD variables as such in the first place (despite the fact that this is initially what I requested). As an end user, I'd rather err on the side of versatility for a CBF writer, as opposed to @blegat's suggestion of erroring out when psd variables are detected in an affine constraint.

By the way, I asked the Mosek CEO about this design decision on OR Stack Exchange. Here's a link to the question. He acknowledged that explicitly declaring PSD variables can improve solver performance but also noted that there's a lot of redundancy in CBF. Parsing that redundancy is the core issue here, and my feeling is that these redundancy-parsing design decisions should enable more problems to be exported to CBF as opposed to less.

Just my two cents.

[odow]

that variables declared PSD can't be used in affine constraints

There's a subtle correction needed: they can be used in affine-in-cone constraints, but NOT affine-in-PSD constraints.

[joaquimg]

NOT affine-in-PSD constraints.

This fact is not at all clear in the OR Stack Exchange thread, nor in the docs.

Forgive my ignorance, but can't one refer to "inner" variables of a PSDVAR by their scalar indices?

[odow]

Forgive my ignorance, but can't one refer to "inner" variables of a PSDVAR by their scalar indices?

No, because PSDVAR are special "matrix" variables. They are not like x in ExponentialCone.

IMO, MOI has a better design where PositiveSemidefiniteConeTriangle is just a regular cone with vectorized input, instead of pretending that the input is a symmetric matrix. It's not obvious, for example, how you would extend CBF to the logdet or rootdet cones.

[odow]

A new version of CBF could introduce the vectorized PSD cone and deprecate PSDVAR and PSDCON. There's no need for special handling, and I'm reticent to spend too much time mucking around in the writer for what is a niche request. We can read CBF files, which is arguably more important.

[joaquimg]

Does it make sense to have 2 cbf writers?
one that only supports PSDVAR and one that only supports PSDCON?

[odow]

Currently we have one that supports only PSDCON. I think it's fair to leave it at that. It's still a valid file and model. The solver reader could be clever and figure out if it's reading a I * X in PSDCone constraint and add that as a variable instead.

[blegat]

If the CBF writer decides not to support PSD variables then supports_add_constrained_variables should return false and the transformation should be done by a functionize bridge so that it's explicit and not hidden in some hardcoding transformation. So someone usign the CBF writer without bridges will get unsupported errors (which is good) and someone using bridges will have it silently transformed but they can can see it in the bridge graph, which is also good.

[odow]

We're not going to start throwing an error because that would be breaking.

This is also not a real-world issue. No one, apart from @rbassett3 has ever asked about it, and even then, it was why PSDVAR isn't used, not why are VectorOfVariables-in-PSDCone written as PSDCON.

We also automatically promote VectorOfVariables-in-ExponentialCone etc to VectorAffineFunction-in-ExponentialCone if we can't write then as a single x in K VAR.

[blegat]

Isn't the first comment of this issue saying that PSD variables are currently ignored ? This means that any code writing a model with PSD variables is currently incorrect so throwing an error in case there is no bridge layer is a bug-fix, not a breaking change.

[odow]

Isn't the first comment of this issue saying that PSD variables are currently ignored ?

No.

• Currently, all VectorOfVariables-in-PositiveSemidefiniteConeTriangle and VectorAffineFunction-in-PositiveSemidefiniteConeTriangle constraints get written in the PSDCON section.
• VectorOfVariables-in-PositiveSemidefiniteConeTriangle constraints $x \in K$ get written as $I * x + 0 \in K$.
• add_constrained_variables(::Model, :: PositiveSemidefiniteConeTriangle) in fact adds variables in ::Reals and a VectorOfVariables-in-PositiveSemidefiniteConeTriangle constraint.
• All CBF files written by MOI are legal and equivalent to the MOI problem.

To clarify what this issue is about:

• This issue is asking for VectorOfVariables-in-PositiveSemidefiniteConeTriangle variables to be written in the PSDVAR section, where possible.
• Variables that appear in PSDVAR have restrictions:
  • They cannot be integer
  • They cannot appear in other -in-PositiveSemidefiniteConeTriangle connstraints
• [FileFormats.CBF] write VectorOfVariables constraints in VAR block #2478 and [FileFormats.CBF] write out EXP and EXP* as variable cones #2482 added support for writing VectorOfVariables-in-S constraints to the VAR section, where possible. The restrictions are:
  • They cannot appear in other VectorOfVariables-in-S constraints
  • [FileFormats.CBF] write VectorOfVariables constraints in VAR block #2478 and [FileFormats.CBF] write out EXP and EXP* as variable cones #2482 use a heuristic, where they look for contiguously numbered variables in the VectorOfVariables function, where we assume this means they were added together, instead of picking random scalar variables to be part of a set.
• We could do something similar, except it will complicate the wrapper, because we have to parse all -in-PositiveSemidefiniteConeTriangle and VariableIndex-in-Integer constraints before we can decide to add a PSDVAR, and when we do, we then need to create separate F matrices for the objective and affine conic constraints.

Because the current models written by MOI.FileFormats.CBF are valid and equivalent to the original problem (they just don't use PSDVAR), I don't know if complicating the writer to support PSDVAR is worth it. Hence my desire to close this issue.

[blegat]

I see. Then I think we should indeed recover VectorOfVariables constraints in the reader by recognizing the special structure