Rank1 PSD constraint dual variables

Specific Domains Optimization (Mathematical)
,
1

Hi,
I ran the following code in JuMP,

@variable(m, x[1:n]>=0)
@variable(m, X[1:n,1:n],  Symmetric)
@constraint(m, X_xx_cons, [1 x'; x X] in PSDCone() )
@objective(m, Min, tr(Q'*X)+dot(b,x))
optimize!(m)
A = dual(X_xx_cons)

and after solving it, the dual variable A is an upper triangular matrix. How can I recover the dual variable of constraint X_xx_cons that is a positive semidefinite matrix ? ( Is it because of symmetry, the off diagonal of A is two times what it supposed to be?) Thank you.

1 Like
2

Hi there,

What is n, Q, and b?

the dual variable A is an upper triangular matrix

Hmm. That seems like a bug. Try explicitly wrapping the [1 x'; x X] in `Symmetric:

using JuMP, SCS, LinearAlgebra
n = 3
b = rand(n)
Q = [1 0.5 0; 0.5 1 0.5; 0 0.5 1]
model = Model(SCS.Optimizer)
@variable(model, x[1:n] >= 0)
@variable(model, X[1:n, 1:n], Symmetric)
c = @constraint(model, Symmetric([1 x'; x X]) in PSDCone())
@objective(model, Min, LinearAlgebra.tr(Q * X) + b' * x)
optimize!(model)
julia> A = dual(c)
4×4 Symmetric{Float64, Matrix{Float64}}:
 2.06697e-12   9.3909e-7   1.32841e-6   9.38912e-7
 9.3909e-7     1.0         0.5         -8.0519e-14
 1.32841e-6    0.5         1.0          0.5
 9.38912e-7   -8.0519e-14  0.5          1.0
3

I’ve opened an issue: Bug in dual of PositiveSemidefiniteConeSquare · Issue #1830 · jump-dev/MathOptInterface.jl · GitHub

4

Hi,

Thank you for the reply. I think in my code, I did not have Symmetric() in the constraint.

5

In fact, if I delete Symmetric(), I got this

n = 3
b = rand(n)
Q = [1 0.5 0; 0.5 1 0.5; 0 0.5 1]
model = Model(Mosek.Optimizer)
@variable(model, x[1:n] >= 0)
@variable(model, X[1:n, 1:n], Symmetric)
c = @constraint(model, [1 x'; x X] in PSDCone())
@objective(model, Min, LinearAlgebra.tr(Q * X) + b' * x)
optimize!(model)
julia> A = dual(c)
4×4 Matrix{Float64}:
 4.79303e-9  2.15225e-5  5.44024e-5  5.29432e-5
 0.0         1.0         1.0         3.88365e-10
 0.0         0.0         1.0         1.0
 0.0         0.0         0.0         1.0
6

Yes, I think this is a bug. You can work-around it by using Symmetric.

7

Hi Oscar,

One follow up question, in JuMP, are there alternative ways to express constraint X-x*x^top \succeq 0? I have tried the following but it does not work, is it because JuMP only allows affine expression in PSDCone()?

n = 3
b = rand(n)
Q = [1 0.5 0; 0.5 1 0.5; 0 0.5 1]
model = Model(Mosek.Optimizer)
@variable(model, x[1:n] >= 0)
@variable(model, X[1:n, 1:n], Symmetric)
c = @constraint(model,  X-x*x' in PSDCone() )
@objective(model, Min, LinearAlgebra.tr(Q * X) + b' * x)
optimize!(model)

ERROR: MathOptInterface.UnsupportedConstraint{MathOptInterface.ScalarQuadraticFunction{Float64}, MathOptInterface.LessThan{Float64}}: `MathOptInterface.ScalarQuadraticFunction{Float64}`-in-`MathOptInterface.LessThan{Float64}` constraint is not supported by the model: Unable to transform a quadratic constraint into a second-order cone constraint because the quadratic constraint is not strongly convex.

Convex constraints that are not strongly convex (i.e., the matrix is positive semidefinite but not positive definite) are not supported yet.

Note that a quadratic equality constraint is non-convex.

Thanks!

1 Like
8

It’s actually the solver that doesn’t support this, and JuMP can’t reformulate the problem into something that the solver supports because X - x * x' is non convex.

9

Thank you.

1 Like