Modeling sum of k-smallest eigenvalues of a symmetric matrix in JuMP

Specific Domains Optimization (Mathematical)
2

This is the same as -sum of the k largest eigenvalues of X for which a reformulation is given in p. 147 of “Lectures on modern convex optimization” of Ben-Tal and Nemirovski.
So for the first k eigenvalues of X, you would do

using LinearAlgebra, JuMP
n = LinearAlgebra.checksquare(X) # Same as size(X, 1) but also check that it is square
@variable(model, Z[1:n, 1:n], Symmetric)
@variable(model, s)
@constraint(model, Symmetric(Z - X + s * Matrix(I, n, n)) >= 0)

Then k * s + tr(Z) is constrained to be an upper bound to the sum of the largest k eigenvalues. So if it’s minimized, it will be equal to it.
And if this is minimized or

2 Likes