The source files for all examples can be found in /examples.
Minimizing the sum of the k-largest λ
We show how to find the sum of absolute value of the k largest eigenvalues of a symmetric matrix $A \in \mathbb{S}^n$. This problem can be solved as a semidefinite program. The primal and dual forms are stated in Alizadeh [1]:
\[\begin{array}{llll} \text{maximize} & \text{Tr}(AY) - \text{Tr}(AW) & \text{minimize} & kz + Tr(U) + Tr(V) \\ \text{subject to} & \text{Tr}(Y + W) = k & \text{subject to} & zI + V - A \succeq 0 \\ & 0 \preceq Y \preceq I & & zI + U + A \succeq 0 \\ & 0 \preceq W \preceq I & & U, V \succeq 0, \end{array}\]
where $Y, W$ are the variables of the primal and $U, V$ are the variables of the dual problem.
using LinearAlgebra, JuMP, COSMO, Random
rng = Random.MersenneTwister(212)
n = 10
A = 5 .* randn(rng, 10, 10)
A = Symmetric(A, :U)10×10 LinearAlgebra.Symmetric{Float64, Matrix{Float64}}:
3.75235 -10.1468 11.8536 … 8.2426 -2.93578 -1.7936
-10.1468 3.47152 -1.2742 -4.50988 -5.62554 4.1421
11.8536 -1.2742 -5.39872 -3.94134 -5.66674 3.24501
5.08674 -2.33596 -0.452489 0.619368 -2.55535 6.84733
8.83628 1.75814 4.58552 -2.76005 -4.13215 3.39184
4.19718 3.64755 8.93206 … -3.95832 0.445552 -5.50658
0.308163 -5.51088 0.424802 -11.2947 -1.35679 5.7731
8.2426 -4.50988 -3.94134 7.45319 5.59746 0.668617
-2.93578 -5.62554 -5.66674 5.59746 -3.41909 4.27924
-1.7936 4.1421 3.24501 0.668617 4.27924 -7.90178We are interested in minimizing the sum of absolute values of the k=3 largest eigenvalues. Let's formulate the problem in JuMP with COSMO as the backend solver:
k = 3
model = JuMP.Model(optimizer_with_attributes(COSMO.Optimizer, "verbose" => true));
@variable(model, Y[1:n, 1:n], PSD);
@variable(model, W[1:n, 1:n], PSD);
@objective(model, Max, tr(A * Y) - tr(A * W));
@constraint(model, tr(Y + W) == k);
@constraint(model, Symmetric(I - Y) in PSDCone());
@constraint(model, Symmetric(I - W) in PSDCone());
status = JuMP.optimize!(model)Maximize ScalarAffineFunction{Float64}:
0.0 + 3.7523508189482557 Y[1,1] - 20.293699832312356 Y[1,2] + 23.707297407397995 Y[1,3] + 10.173483974258662 Y[1,4] + 17.672568380364623 Y[1,5] + 8.394359502531207 Y[1,6] + 0.6163252774542141 Y[1,7] + 16.485204584051086 Y[1,8] - 5.8715699230474545 Y[1,9] - 3.587206789344531 Y[1,10] + 3.471516652129022 Y[2,2] - 2.5483916017947763 Y[2,3] - 4.671914008173175 Y[2,4] + 3.5162789266137553 Y[2,5] + 7.29510882640416 Y[2,6] - 11.021763702535614 Y[2,7] - 9.019763006552148 Y[2,8] - 11.251078680999203 Y[2,9] + 8.28419725758606 Y[2,10] - 5.398720025917527 Y[3,3] - 0.9049782438741334 Y[3,4] + 9.171033181377727 Y[3,5] + 17.86412086198314 Y[3,6] + 0.8496047140586295 Y[3,7] - 7.882679708057147 Y[3,8] - 11.333473076392334 Y[3,9] + 6.490024292799762 Y[3,10] - 1.1302813075986693 Y[4,4] + 4.26992562502979 Y[4,5] + 3.9493021419886847 Y[4,6] + 1.2066515253584789 Y[4,7] + 1.2387354489046913 Y[4,8] - 5.110699339387313 Y[4,9] + 13.69465350134179 Y[4,10] + 5.410774352632194 Y[5,5] + 8.64456104904172 Y[5,6] - 8.885855026781046 Y[5,7] - 5.5200968108421264 Y[5,8] - 8.264306831498919 Y[5,9] + 6.7836765793492315 Y[5,10] - 1.3261173198140872 Y[6,6] - 12.71867327712938 Y[6,7] - 7.916642467535699 Y[6,8] + 0.8911045949618218 Y[6,9] - 11.013164142409675 Y[6,10] + 12.032953436710665 Y[7,7] - 22.58935309587021 Y[7,8] - 2.7135881376226942 Y[7,9] + 11.54620780115417 Y[7,10] + 7.453187644921954 Y[8,8] + 11.194912794975632 Y[8,9] + 1.3372333084728003 Y[8,10] - 3.4190914894630953 Y[9,9] + 8.558485734597419 Y[9,10] - 7.901776278294789 Y[10,10] - 3.7523508189482557 W[1,1] + 20.293699832312356 W[1,2] - 23.707297407397995 W[1,3] - 10.173483974258662 W[1,4] - 17.672568380364623 W[1,5] - 8.394359502531207 W[1,6] - 0.6163252774542141 W[1,7] - 16.485204584051086 W[1,8] + 5.8715699230474545 W[1,9] + 3.587206789344531 W[1,10] - 3.471516652129022 W[2,2] + 2.5483916017947763 W[2,3] + 4.671914008173175 W[2,4] - 3.5162789266137553 W[2,5] - 7.29510882640416 W[2,6] + 11.021763702535614 W[2,7] + 9.019763006552148 W[2,8] + 11.251078680999203 W[2,9] - 8.28419725758606 W[2,10] + 5.398720025917527 W[3,3] + 0.9049782438741334 W[3,4] - 9.171033181377727 W[3,5] - 17.86412086198314 W[3,6] - 0.8496047140586295 W[3,7] + 7.882679708057147 W[3,8] + 11.333473076392334 W[3,9] - 6.490024292799762 W[3,10] + 1.1302813075986693 W[4,4] - 4.26992562502979 W[4,5] - 3.9493021419886847 W[4,6] - 1.2066515253584789 W[4,7] - 1.2387354489046913 W[4,8] + 5.110699339387313 W[4,9] - 13.69465350134179 W[4,10] - 5.410774352632194 W[5,5] - 8.64456104904172 W[5,6] + 8.885855026781046 W[5,7] + 5.5200968108421264 W[5,8] + 8.264306831498919 W[5,9] - 6.7836765793492315 W[5,10] + 1.3261173198140872 W[6,6] + 12.71867327712938 W[6,7] + 7.916642467535699 W[6,8] - 0.8911045949618218 W[6,9] + 11.013164142409675 W[6,10] - 12.032953436710665 W[7,7] + 22.58935309587021 W[7,8] + 2.7135881376226942 W[7,9] - 11.54620780115417 W[7,10] - 7.453187644921954 W[8,8] - 11.194912794975632 W[8,9] - 1.3372333084728003 W[8,10] + 3.4190914894630953 W[9,9] - 8.558485734597419 W[9,10] + 7.901776278294789 W[10,10]
Subject to:
VectorAffineFunction{Float64}-in-Zeros
┌ ┐
│-3.0 + 1.0 Y[1,1] + 1.0 Y[2,2] + 1.0 Y[3,3] + 1.0 Y[4,4] + 1.0 Y[5,5] + 1.0 Y[6,6] + 1.0 Y[7,7] + 1.0 Y[8,8] + 1.0 Y[9,9] + 1.0 Y[10,10] + 1.0 W[1,1] + 1.0 W[2,2] + 1.0 W[3,3] + 1.0 W[4,4] + 1.0 W[5,5] + 1.0 W[6,6] + 1.0 W[7,7] + 1.0 W[8,8] + 1.0 W[9,9] + 1.0 W[10,10]│
└ ┘ ∈ Zeros(1)
VectorAffineFunction{Float64}-in-Scaled{PositiveSemidefiniteConeTriangle}
┌ ┐
│0.0 + 1.0 Y[1,1] │
│0.0 + 1.4142135623730951 Y[1,2] │
│0.0 + 1.0 Y[2,2] │
│0.0 + 1.4142135623730951 Y[1,3] │
│0.0 + 1.4142135623730951 Y[2,3] │
│0.0 + 1.0 Y[3,3] │
│0.0 + 1.4142135623730951 Y[1,4] │
│0.0 + 1.4142135623730951 Y[2,4] │
│0.0 + 1.4142135623730951 Y[3,4] │
│0.0 + 1.0 Y[4,4] │
│0.0 + 1.4142135623730951 Y[1,5] │
│0.0 + 1.4142135623730951 Y[2,5] │
│0.0 + 1.4142135623730951 Y[3,5] │
│0.0 + 1.4142135623730951 Y[4,5] │
│0.0 + 1.0 Y[5,5] │
│0.0 + 1.4142135623730951 Y[1,6] │
│0.0 + 1.4142135623730951 Y[2,6] │
│0.0 + 1.4142135623730951 Y[3,6] │
│0.0 + 1.4142135623730951 Y[4,6] │
│0.0 + 1.4142135623730951 Y[5,6] │
│0.0 + 1.0 Y[6,6] │
│0.0 + 1.4142135623730951 Y[1,7] │
│0.0 + 1.4142135623730951 Y[2,7] │
│0.0 + 1.4142135623730951 Y[3,7] │
│0.0 + 1.4142135623730951 Y[4,7] │
│0.0 + 1.4142135623730951 Y[5,7] │
│0.0 + 1.4142135623730951 Y[6,7] │
│0.0 + 1.0 Y[7,7] │
│0.0 + 1.4142135623730951 Y[1,8] │
│0.0 + 1.4142135623730951 Y[2,8] │
│0.0 + 1.4142135623730951 Y[3,8] │
│0.0 + 1.4142135623730951 Y[4,8] │
│0.0 + 1.4142135623730951 Y[5,8] │
│0.0 + 1.4142135623730951 Y[6,8] │
│0.0 + 1.4142135623730951 Y[7,8] │
│0.0 + 1.0 Y[8,8] │
│0.0 + 1.4142135623730951 Y[1,9] │
│0.0 + 1.4142135623730951 Y[2,9] │
│0.0 + 1.4142135623730951 Y[3,9] │
│0.0 + 1.4142135623730951 Y[4,9] │
│0.0 + 1.4142135623730951 Y[5,9] │
│0.0 + 1.4142135623730951 Y[6,9] │
│0.0 + 1.4142135623730951 Y[7,9] │
│0.0 + 1.4142135623730951 Y[8,9] │
│0.0 + 1.0 Y[9,9] │
│0.0 + 1.4142135623730951 Y[1,10]│
│0.0 + 1.4142135623730951 Y[2,10]│
│0.0 + 1.4142135623730951 Y[3,10]│
│0.0 + 1.4142135623730951 Y[4,10]│
│0.0 + 1.4142135623730951 Y[5,10]│
│0.0 + 1.4142135623730951 Y[6,10]│
│0.0 + 1.4142135623730951 Y[7,10]│
│0.0 + 1.4142135623730951 Y[8,10]│
│0.0 + 1.4142135623730951 Y[9,10]│
│0.0 + 1.0 Y[10,10] │
└ ┘ ∈ Scaled{PositiveSemidefiniteConeTriangle}(PositiveSemidefiniteConeTriangle(10))
┌ ┐
│0.0 + 1.0 W[1,1] │
│0.0 + 1.4142135623730951 W[1,2] │
│0.0 + 1.0 W[2,2] │
│0.0 + 1.4142135623730951 W[1,3] │
│0.0 + 1.4142135623730951 W[2,3] │
│0.0 + 1.0 W[3,3] │
│0.0 + 1.4142135623730951 W[1,4] │
│0.0 + 1.4142135623730951 W[2,4] │
│0.0 + 1.4142135623730951 W[3,4] │
│0.0 + 1.0 W[4,4] │
│0.0 + 1.4142135623730951 W[1,5] │
│0.0 + 1.4142135623730951 W[2,5] │
│0.0 + 1.4142135623730951 W[3,5] │
│0.0 + 1.4142135623730951 W[4,5] │
│0.0 + 1.0 W[5,5] │
│0.0 + 1.4142135623730951 W[1,6] │
│0.0 + 1.4142135623730951 W[2,6] │
│0.0 + 1.4142135623730951 W[3,6] │
│0.0 + 1.4142135623730951 W[4,6] │
│0.0 + 1.4142135623730951 W[5,6] │
│0.0 + 1.0 W[6,6] │
│0.0 + 1.4142135623730951 W[1,7] │
│0.0 + 1.4142135623730951 W[2,7] │
│0.0 + 1.4142135623730951 W[3,7] │
│0.0 + 1.4142135623730951 W[4,7] │
│0.0 + 1.4142135623730951 W[5,7] │
│0.0 + 1.4142135623730951 W[6,7] │
│0.0 + 1.0 W[7,7] │
│0.0 + 1.4142135623730951 W[1,8] │
│0.0 + 1.4142135623730951 W[2,8] │
│0.0 + 1.4142135623730951 W[3,8] │
│0.0 + 1.4142135623730951 W[4,8] │
│0.0 + 1.4142135623730951 W[5,8] │
│0.0 + 1.4142135623730951 W[6,8] │
│0.0 + 1.4142135623730951 W[7,8] │
│0.0 + 1.0 W[8,8] │
│0.0 + 1.4142135623730951 W[1,9] │
│0.0 + 1.4142135623730951 W[2,9] │
│0.0 + 1.4142135623730951 W[3,9] │
│0.0 + 1.4142135623730951 W[4,9] │
│0.0 + 1.4142135623730951 W[5,9] │
│0.0 + 1.4142135623730951 W[6,9] │
│0.0 + 1.4142135623730951 W[7,9] │
│0.0 + 1.4142135623730951 W[8,9] │
│0.0 + 1.0 W[9,9] │
│0.0 + 1.4142135623730951 W[1,10]│
│0.0 + 1.4142135623730951 W[2,10]│
│0.0 + 1.4142135623730951 W[3,10]│
│0.0 + 1.4142135623730951 W[4,10]│
│0.0 + 1.4142135623730951 W[5,10]│
│0.0 + 1.4142135623730951 W[6,10]│
│0.0 + 1.4142135623730951 W[7,10]│
│0.0 + 1.4142135623730951 W[8,10]│
│0.0 + 1.4142135623730951 W[9,10]│
│0.0 + 1.0 W[10,10] │
└ ┘ ∈ Scaled{PositiveSemidefiniteConeTriangle}(PositiveSemidefiniteConeTriangle(10))
┌ ┐
│1.0 - 1.0 Y[1,1] │
│0.0 - 1.4142135623730951 Y[1,2] │
│1.0 - 1.0 Y[2,2] │
│0.0 - 1.4142135623730951 Y[1,3] │
│0.0 - 1.4142135623730951 Y[2,3] │
│1.0 - 1.0 Y[3,3] │
│0.0 - 1.4142135623730951 Y[1,4] │
│0.0 - 1.4142135623730951 Y[2,4] │
│0.0 - 1.4142135623730951 Y[3,4] │
│1.0 - 1.0 Y[4,4] │
│0.0 - 1.4142135623730951 Y[1,5] │
│0.0 - 1.4142135623730951 Y[2,5] │
│0.0 - 1.4142135623730951 Y[3,5] │
│0.0 - 1.4142135623730951 Y[4,5] │
│1.0 - 1.0 Y[5,5] │
│0.0 - 1.4142135623730951 Y[1,6] │
│0.0 - 1.4142135623730951 Y[2,6] │
│0.0 - 1.4142135623730951 Y[3,6] │
│0.0 - 1.4142135623730951 Y[4,6] │
│0.0 - 1.4142135623730951 Y[5,6] │
│1.0 - 1.0 Y[6,6] │
│0.0 - 1.4142135623730951 Y[1,7] │
│0.0 - 1.4142135623730951 Y[2,7] │
│0.0 - 1.4142135623730951 Y[3,7] │
│0.0 - 1.4142135623730951 Y[4,7] │
│0.0 - 1.4142135623730951 Y[5,7] │
│0.0 - 1.4142135623730951 Y[6,7] │
│1.0 - 1.0 Y[7,7] │
│0.0 - 1.4142135623730951 Y[1,8] │
│0.0 - 1.4142135623730951 Y[2,8] │
│0.0 - 1.4142135623730951 Y[3,8] │
│0.0 - 1.4142135623730951 Y[4,8] │
│0.0 - 1.4142135623730951 Y[5,8] │
│0.0 - 1.4142135623730951 Y[6,8] │
│0.0 - 1.4142135623730951 Y[7,8] │
│1.0 - 1.0 Y[8,8] │
│0.0 - 1.4142135623730951 Y[1,9] │
│0.0 - 1.4142135623730951 Y[2,9] │
│0.0 - 1.4142135623730951 Y[3,9] │
│0.0 - 1.4142135623730951 Y[4,9] │
│0.0 - 1.4142135623730951 Y[5,9] │
│0.0 - 1.4142135623730951 Y[6,9] │
│0.0 - 1.4142135623730951 Y[7,9] │
│0.0 - 1.4142135623730951 Y[8,9] │
│1.0 - 1.0 Y[9,9] │
│0.0 - 1.4142135623730951 Y[1,10]│
│0.0 - 1.4142135623730951 Y[2,10]│
│0.0 - 1.4142135623730951 Y[3,10]│
│0.0 - 1.4142135623730951 Y[4,10]│
│0.0 - 1.4142135623730951 Y[5,10]│
│0.0 - 1.4142135623730951 Y[6,10]│
│0.0 - 1.4142135623730951 Y[7,10]│
│0.0 - 1.4142135623730951 Y[8,10]│
│0.0 - 1.4142135623730951 Y[9,10]│
│1.0 - 1.0 Y[10,10] │
└ ┘ ∈ Scaled{PositiveSemidefiniteConeTriangle}(PositiveSemidefiniteConeTriangle(10))
┌ ┐
│1.0 - 1.0 W[1,1] │
│0.0 - 1.4142135623730951 W[1,2] │
│1.0 - 1.0 W[2,2] │
│0.0 - 1.4142135623730951 W[1,3] │
│0.0 - 1.4142135623730951 W[2,3] │
│1.0 - 1.0 W[3,3] │
│0.0 - 1.4142135623730951 W[1,4] │
│0.0 - 1.4142135623730951 W[2,4] │
│0.0 - 1.4142135623730951 W[3,4] │
│1.0 - 1.0 W[4,4] │
│0.0 - 1.4142135623730951 W[1,5] │
│0.0 - 1.4142135623730951 W[2,5] │
│0.0 - 1.4142135623730951 W[3,5] │
│0.0 - 1.4142135623730951 W[4,5] │
│1.0 - 1.0 W[5,5] │
│0.0 - 1.4142135623730951 W[1,6] │
│0.0 - 1.4142135623730951 W[2,6] │
│0.0 - 1.4142135623730951 W[3,6] │
│0.0 - 1.4142135623730951 W[4,6] │
│0.0 - 1.4142135623730951 W[5,6] │
│1.0 - 1.0 W[6,6] │
│0.0 - 1.4142135623730951 W[1,7] │
│0.0 - 1.4142135623730951 W[2,7] │
│0.0 - 1.4142135623730951 W[3,7] │
│0.0 - 1.4142135623730951 W[4,7] │
│0.0 - 1.4142135623730951 W[5,7] │
│0.0 - 1.4142135623730951 W[6,7] │
│1.0 - 1.0 W[7,7] │
│0.0 - 1.4142135623730951 W[1,8] │
│0.0 - 1.4142135623730951 W[2,8] │
│0.0 - 1.4142135623730951 W[3,8] │
│0.0 - 1.4142135623730951 W[4,8] │
│0.0 - 1.4142135623730951 W[5,8] │
│0.0 - 1.4142135623730951 W[6,8] │
│0.0 - 1.4142135623730951 W[7,8] │
│1.0 - 1.0 W[8,8] │
│0.0 - 1.4142135623730951 W[1,9] │
│0.0 - 1.4142135623730951 W[2,9] │
│0.0 - 1.4142135623730951 W[3,9] │
│0.0 - 1.4142135623730951 W[4,9] │
│0.0 - 1.4142135623730951 W[5,9] │
│0.0 - 1.4142135623730951 W[6,9] │
│0.0 - 1.4142135623730951 W[7,9] │
│0.0 - 1.4142135623730951 W[8,9] │
│1.0 - 1.0 W[9,9] │
│0.0 - 1.4142135623730951 W[1,10]│
│0.0 - 1.4142135623730951 W[2,10]│
│0.0 - 1.4142135623730951 W[3,10]│
│0.0 - 1.4142135623730951 W[4,10]│
│0.0 - 1.4142135623730951 W[5,10]│
│0.0 - 1.4142135623730951 W[6,10]│
│0.0 - 1.4142135623730951 W[7,10]│
│0.0 - 1.4142135623730951 W[8,10]│
│0.0 - 1.4142135623730951 W[9,10]│
│1.0 - 1.0 W[10,10] │
└ ┘ ∈ Scaled{PositiveSemidefiniteConeTriangle}(PositiveSemidefiniteConeTriangle(10))
------------------------------------------------------------------
COSMO v0.8.10 - A Quadratic Objective Conic Solver
Michael Garstka
University of Oxford, 2017 - 2022
------------------------------------------------------------------
Problem: x ∈ R^{110},
constraints: A ∈ R^{221x110} (240 nnz),
matrix size to factor: 331x331,
Floating-point precision: Float64
Sets: DensePsdConeTriangle of dim: 55 (10x10)
DensePsdConeTriangle of dim: 55 (10x10)
DensePsdConeTriangle of dim: 55 (10x10)
DensePsdConeTriangle of dim: 55 (10x10)
ZeroSet of dim: 1
... and 0 more
Settings: ϵ_abs = 1.0e-05, ϵ_rel = 1.0e-05,
ϵ_prim_inf = 1.0e-04, ϵ_dual_inf = 1.0e-04,
ρ = 0.1, σ = 1e-06, α = 1.6,
max_iter = 5000,
scaling iter = 10 (on),
check termination every 25 iter,
check infeasibility every 40 iter,
KKT system solver: QDLDL
Acc: Anderson Type2{QRDecomp},
Memory size = 15, RestartedMemory,
Safeguarded: true, tol: 2.0
Setup Time: 0.59ms
Iter: Objective: Primal Res: Dual Res: Rho:
1 -5.6886e+04 1.6340e+02 4.8007e+00 1.0000e-01
25 3.7049e-04 8.4997e-01 1.7500e-08 1.0000e-01
50 -4.7558e+00 1.6838e-05 2.3707e+01 4.9553e+03
75 -3.3266e+01 1.2198e-03 2.2344e+01 4.9553e+03
100 -7.3809e+01 1.2839e-03 1.3274e+00 1.0090e+02
125 -7.4070e+01 9.6939e-05 3.1665e-02 1.0090e+02
150 -7.4069e+01 2.0422e-15 5.6843e-13 1.0090e+02
------------------------------------------------------------------
>>> Results
Status: Solved
Iterations: 160 (incl. 10 safeguarding iter)
Optimal objective: -74.07
Runtime: 0.175s (175.38ms)opt_objective = JuMP.objective_value(model)74.06893065551017Now, we can check the solution by computing the sum of the absolute value of the 3-largest eigenvalues:
k_λ_abs = sum(sort(abs.(eigen(A).values), rev = true)[1:k])74.06893065551021Solve the dual
Alternatively, we can solve the dual problem:
model = JuMP.Model(optimizer_with_attributes(COSMO.Optimizer, "verbose" => true));
@variable(model, V[1:n, 1:n], PSD);
@variable(model, U[1:n, 1:n], PSD);
@variable(model, z);
@objective(model, Min, k * z + tr(V) + tr(U));
@constraint(model, Symmetric(z .* diagm(0 => ones(n)) + V - A) in PSDCone());
@constraint(model, Symmetric(z .* diagm(0 => ones(n)) + U + A) in PSDCone());
status = JuMP.optimize!(model)Minimize ScalarAffineFunction{Float64}:
0.0 + 3.0 z + 1.0 V[1,1] + 1.0 V[2,2] + 1.0 V[3,3] + 1.0 V[4,4] + 1.0 V[5,5] + 1.0 V[6,6] + 1.0 V[7,7] + 1.0 V[8,8] + 1.0 V[9,9] + 1.0 V[10,10] + 1.0 U[1,1] + 1.0 U[2,2] + 1.0 U[3,3] + 1.0 U[4,4] + 1.0 U[5,5] + 1.0 U[6,6] + 1.0 U[7,7] + 1.0 U[8,8] + 1.0 U[9,9] + 1.0 U[10,10]
Subject to:
VectorAffineFunction{Float64}-in-Scaled{PositiveSemidefiniteConeTriangle}
┌ ┐
│0.0 + 1.0 V[1,1] │
│0.0 + 1.4142135623730951 V[1,2] │
│0.0 + 1.0 V[2,2] │
│0.0 + 1.4142135623730951 V[1,3] │
│0.0 + 1.4142135623730951 V[2,3] │
│0.0 + 1.0 V[3,3] │
│0.0 + 1.4142135623730951 V[1,4] │
│0.0 + 1.4142135623730951 V[2,4] │
│0.0 + 1.4142135623730951 V[3,4] │
│0.0 + 1.0 V[4,4] │
│0.0 + 1.4142135623730951 V[1,5] │
│0.0 + 1.4142135623730951 V[2,5] │
│0.0 + 1.4142135623730951 V[3,5] │
│0.0 + 1.4142135623730951 V[4,5] │
│0.0 + 1.0 V[5,5] │
│0.0 + 1.4142135623730951 V[1,6] │
│0.0 + 1.4142135623730951 V[2,6] │
│0.0 + 1.4142135623730951 V[3,6] │
│0.0 + 1.4142135623730951 V[4,6] │
│0.0 + 1.4142135623730951 V[5,6] │
│0.0 + 1.0 V[6,6] │
│0.0 + 1.4142135623730951 V[1,7] │
│0.0 + 1.4142135623730951 V[2,7] │
│0.0 + 1.4142135623730951 V[3,7] │
│0.0 + 1.4142135623730951 V[4,7] │
│0.0 + 1.4142135623730951 V[5,7] │
│0.0 + 1.4142135623730951 V[6,7] │
│0.0 + 1.0 V[7,7] │
│0.0 + 1.4142135623730951 V[1,8] │
│0.0 + 1.4142135623730951 V[2,8] │
│0.0 + 1.4142135623730951 V[3,8] │
│0.0 + 1.4142135623730951 V[4,8] │
│0.0 + 1.4142135623730951 V[5,8] │
│0.0 + 1.4142135623730951 V[6,8] │
│0.0 + 1.4142135623730951 V[7,8] │
│0.0 + 1.0 V[8,8] │
│0.0 + 1.4142135623730951 V[1,9] │
│0.0 + 1.4142135623730951 V[2,9] │
│0.0 + 1.4142135623730951 V[3,9] │
│0.0 + 1.4142135623730951 V[4,9] │
│0.0 + 1.4142135623730951 V[5,9] │
│0.0 + 1.4142135623730951 V[6,9] │
│0.0 + 1.4142135623730951 V[7,9] │
│0.0 + 1.4142135623730951 V[8,9] │
│0.0 + 1.0 V[9,9] │
│0.0 + 1.4142135623730951 V[1,10]│
│0.0 + 1.4142135623730951 V[2,10]│
│0.0 + 1.4142135623730951 V[3,10]│
│0.0 + 1.4142135623730951 V[4,10]│
│0.0 + 1.4142135623730951 V[5,10]│
│0.0 + 1.4142135623730951 V[6,10]│
│0.0 + 1.4142135623730951 V[7,10]│
│0.0 + 1.4142135623730951 V[8,10]│
│0.0 + 1.4142135623730951 V[9,10]│
│0.0 + 1.0 V[10,10] │
└ ┘ ∈ Scaled{PositiveSemidefiniteConeTriangle}(PositiveSemidefiniteConeTriangle(10))
┌ ┐
│0.0 + 1.0 U[1,1] │
│0.0 + 1.4142135623730951 U[1,2] │
│0.0 + 1.0 U[2,2] │
│0.0 + 1.4142135623730951 U[1,3] │
│0.0 + 1.4142135623730951 U[2,3] │
│0.0 + 1.0 U[3,3] │
│0.0 + 1.4142135623730951 U[1,4] │
│0.0 + 1.4142135623730951 U[2,4] │
│0.0 + 1.4142135623730951 U[3,4] │
│0.0 + 1.0 U[4,4] │
│0.0 + 1.4142135623730951 U[1,5] │
│0.0 + 1.4142135623730951 U[2,5] │
│0.0 + 1.4142135623730951 U[3,5] │
│0.0 + 1.4142135623730951 U[4,5] │
│0.0 + 1.0 U[5,5] │
│0.0 + 1.4142135623730951 U[1,6] │
│0.0 + 1.4142135623730951 U[2,6] │
│0.0 + 1.4142135623730951 U[3,6] │
│0.0 + 1.4142135623730951 U[4,6] │
│0.0 + 1.4142135623730951 U[5,6] │
│0.0 + 1.0 U[6,6] │
│0.0 + 1.4142135623730951 U[1,7] │
│0.0 + 1.4142135623730951 U[2,7] │
│0.0 + 1.4142135623730951 U[3,7] │
│0.0 + 1.4142135623730951 U[4,7] │
│0.0 + 1.4142135623730951 U[5,7] │
│0.0 + 1.4142135623730951 U[6,7] │
│0.0 + 1.0 U[7,7] │
│0.0 + 1.4142135623730951 U[1,8] │
│0.0 + 1.4142135623730951 U[2,8] │
│0.0 + 1.4142135623730951 U[3,8] │
│0.0 + 1.4142135623730951 U[4,8] │
│0.0 + 1.4142135623730951 U[5,8] │
│0.0 + 1.4142135623730951 U[6,8] │
│0.0 + 1.4142135623730951 U[7,8] │
│0.0 + 1.0 U[8,8] │
│0.0 + 1.4142135623730951 U[1,9] │
│0.0 + 1.4142135623730951 U[2,9] │
│0.0 + 1.4142135623730951 U[3,9] │
│0.0 + 1.4142135623730951 U[4,9] │
│0.0 + 1.4142135623730951 U[5,9] │
│0.0 + 1.4142135623730951 U[6,9] │
│0.0 + 1.4142135623730951 U[7,9] │
│0.0 + 1.4142135623730951 U[8,9] │
│0.0 + 1.0 U[9,9] │
│0.0 + 1.4142135623730951 U[1,10]│
│0.0 + 1.4142135623730951 U[2,10]│
│0.0 + 1.4142135623730951 U[3,10]│
│0.0 + 1.4142135623730951 U[4,10]│
│0.0 + 1.4142135623730951 U[5,10]│
│0.0 + 1.4142135623730951 U[6,10]│
│0.0 + 1.4142135623730951 U[7,10]│
│0.0 + 1.4142135623730951 U[8,10]│
│0.0 + 1.4142135623730951 U[9,10]│
│0.0 + 1.0 U[10,10] │
└ ┘ ∈ Scaled{PositiveSemidefiniteConeTriangle}(PositiveSemidefiniteConeTriangle(10))
┌ ┐
│-3.7523508189482557 + 1.0 V[1,1] + 1.0 z │
│14.34981276679237 + 1.4142135623730951 V[1,2] │
│-3.471516652129022 + 1.0 V[2,2] + 1.0 z │
│-16.76359076037738 + 1.4142135623730951 V[1,3] │
│1.8019849827479344 + 1.4142135623730951 V[2,3] │
│5.398720025917527 + 1.0 V[3,3] + 1.0 z │
│-7.193739506490968 + 1.4142135623730951 V[1,4] │
│3.3035420762996757 + 1.4142135623730951 V[2,4] │
│0.6399162530696929 + 1.4142135623730951 V[3,4] │
│1.1302813075986693 + 1.0 V[4,4] + 1.0 z │
│-12.496392942738787 + 1.4142135623730951 V[1,5] │
│-2.486384673551941 + 1.4142135623730951 V[2,5] │
│-6.484899753039027 + 1.4142135623730951 V[3,5] │
│-3.0192933646207725 + 1.4142135623730951 V[4,5] │
│-5.410774352632194 + 1.0 V[5,5] + 1.0 z │
│-5.9357085279575506 + 1.4142135623730951 V[1,6] │
│-5.158420920644218 + 1.4142135623730951 V[2,6] │
│-12.631841001444352 + 1.4142135623730951 V[3,6] │
│-2.7925783255547563 + 1.4142135623730951 V[4,6] │
│-6.112627738158495 + 1.4142135623730951 V[5,6] │
│1.3261173198140872 + 1.0 V[6,6] + 1.0 z │
│-0.43580778310455515 + 1.4142135623730951 V[1,7]│
│7.793563854698682 + 1.4142135623730951 V[2,7] │
│-0.6007612546389146 + 1.4142135623730951 V[3,7] │
│-0.8532314761100718 + 1.4142135623730951 V[4,7] │
│6.283248346077449 + 1.4142135623730951 V[5,7] │
│8.993460121954314 + 1.4142135623730951 V[6,7] │
│-12.032953436710665 + 1.0 V[7,7] + 1.0 z │
│-11.656799950630083 + 1.4142135623730951 V[1,8] │
│6.3779355866285865 + 1.4142135623730951 V[2,8] │
│5.573896275488804 + 1.4142135623730951 V[3,8] │
│-0.8759182360166694 + 1.4142135623730951 V[4,8] │
│3.9032978877527027 + 1.4142135623730951 V[5,8] │
│5.597911573023895 + 1.4142135623730951 V[6,8] │
│15.973084756707157 + 1.4142135623730951 V[7,8] │
│-7.453187644921954 + 1.0 V[8,8] + 1.0 z │
│4.151826908797831 + 1.4142135623730951 V[1,9] │
│7.955714030997934 + 1.4142135623730951 V[2,9] │
│8.013975666712183 + 1.4142135623730951 V[3,9] │
│3.6138101594863783 + 1.4142135623730951 V[4,9] │
│5.843747402359196 + 1.4142135623730951 V[5,9] │
│-0.6301061018439961 + 1.4142135623730951 V[6,9] │
│1.9187965734603816 + 1.4142135623730951 V[7,9] │
│-7.915998752119316 + 1.4142135623730951 V[8,9] │
│3.4190914894630953 + 1.0 V[9,9] + 1.0 z │
│2.5365382462639414 + 1.4142135623730951 V[1,10] │
│-5.857812057526104 + 1.4142135623730951 V[2,10] │
│-4.58914018750414 + 1.4142135623730951 V[3,10] │
│-9.683582356798876 + 1.4142135623730951 V[4,10] │
│-4.796783710634204 + 1.4142135623730951 V[5,10] │
│7.78748304741841 + 1.4142135623730951 V[6,10] │
│-8.16440183318513 + 1.4142135623730951 V[7,10] │
│-0.9455667404496395 + 1.4142135623730951 V[8,10]│
│-6.0517632996221655 + 1.4142135623730951 V[9,10]│
│7.901776278294789 + 1.0 V[10,10] + 1.0 z │
└ ┘ ∈ Scaled{PositiveSemidefiniteConeTriangle}(PositiveSemidefiniteConeTriangle(10))
┌ ┐
│3.7523508189482557 + 1.0 U[1,1] + 1.0 z │
│-14.34981276679237 + 1.4142135623730951 U[1,2] │
│3.471516652129022 + 1.0 U[2,2] + 1.0 z │
│16.76359076037738 + 1.4142135623730951 U[1,3] │
│-1.8019849827479344 + 1.4142135623730951 U[2,3] │
│-5.398720025917527 + 1.0 U[3,3] + 1.0 z │
│7.193739506490968 + 1.4142135623730951 U[1,4] │
│-3.3035420762996757 + 1.4142135623730951 U[2,4] │
│-0.6399162530696929 + 1.4142135623730951 U[3,4] │
│-1.1302813075986693 + 1.0 U[4,4] + 1.0 z │
│12.496392942738787 + 1.4142135623730951 U[1,5] │
│2.486384673551941 + 1.4142135623730951 U[2,5] │
│6.484899753039027 + 1.4142135623730951 U[3,5] │
│3.0192933646207725 + 1.4142135623730951 U[4,5] │
│5.410774352632194 + 1.0 U[5,5] + 1.0 z │
│5.9357085279575506 + 1.4142135623730951 U[1,6] │
│5.158420920644218 + 1.4142135623730951 U[2,6] │
│12.631841001444352 + 1.4142135623730951 U[3,6] │
│2.7925783255547563 + 1.4142135623730951 U[4,6] │
│6.112627738158495 + 1.4142135623730951 U[5,6] │
│-1.3261173198140872 + 1.0 U[6,6] + 1.0 z │
│0.43580778310455515 + 1.4142135623730951 U[1,7] │
│-7.793563854698682 + 1.4142135623730951 U[2,7] │
│0.6007612546389146 + 1.4142135623730951 U[3,7] │
│0.8532314761100718 + 1.4142135623730951 U[4,7] │
│-6.283248346077449 + 1.4142135623730951 U[5,7] │
│-8.993460121954314 + 1.4142135623730951 U[6,7] │
│12.032953436710665 + 1.0 U[7,7] + 1.0 z │
│11.656799950630083 + 1.4142135623730951 U[1,8] │
│-6.3779355866285865 + 1.4142135623730951 U[2,8] │
│-5.573896275488804 + 1.4142135623730951 U[3,8] │
│0.8759182360166694 + 1.4142135623730951 U[4,8] │
│-3.9032978877527027 + 1.4142135623730951 U[5,8] │
│-5.597911573023895 + 1.4142135623730951 U[6,8] │
│-15.973084756707157 + 1.4142135623730951 U[7,8] │
│7.453187644921954 + 1.0 U[8,8] + 1.0 z │
│-4.151826908797831 + 1.4142135623730951 U[1,9] │
│-7.955714030997934 + 1.4142135623730951 U[2,9] │
│-8.013975666712183 + 1.4142135623730951 U[3,9] │
│-3.6138101594863783 + 1.4142135623730951 U[4,9] │
│-5.843747402359196 + 1.4142135623730951 U[5,9] │
│0.6301061018439961 + 1.4142135623730951 U[6,9] │
│-1.9187965734603816 + 1.4142135623730951 U[7,9] │
│7.915998752119316 + 1.4142135623730951 U[8,9] │
│-3.4190914894630953 + 1.0 U[9,9] + 1.0 z │
│-2.5365382462639414 + 1.4142135623730951 U[1,10]│
│5.857812057526104 + 1.4142135623730951 U[2,10] │
│4.58914018750414 + 1.4142135623730951 U[3,10] │
│9.683582356798876 + 1.4142135623730951 U[4,10] │
│4.796783710634204 + 1.4142135623730951 U[5,10] │
│-7.78748304741841 + 1.4142135623730951 U[6,10] │
│8.16440183318513 + 1.4142135623730951 U[7,10] │
│0.9455667404496395 + 1.4142135623730951 U[8,10] │
│6.0517632996221655 + 1.4142135623730951 U[9,10] │
│-7.901776278294789 + 1.0 U[10,10] + 1.0 z │
└ ┘ ∈ Scaled{PositiveSemidefiniteConeTriangle}(PositiveSemidefiniteConeTriangle(10))
------------------------------------------------------------------
COSMO v0.8.10 - A Quadratic Objective Conic Solver
Michael Garstka
University of Oxford, 2017 - 2022
------------------------------------------------------------------
Problem: x ∈ R^{111},
constraints: A ∈ R^{220x111} (240 nnz),
matrix size to factor: 331x331,
Floating-point precision: Float64
Sets: DensePsdConeTriangle of dim: 55 (10x10)
DensePsdConeTriangle of dim: 55 (10x10)
DensePsdConeTriangle of dim: 55 (10x10)
DensePsdConeTriangle of dim: 55 (10x10)
Settings: ϵ_abs = 1.0e-05, ϵ_rel = 1.0e-05,
ϵ_prim_inf = 1.0e-04, ϵ_dual_inf = 1.0e-04,
ρ = 0.1, σ = 1e-06, α = 1.6,
max_iter = 5000,
scaling iter = 10 (on),
check termination every 25 iter,
check infeasibility every 40 iter,
KKT system solver: QDLDL
Acc: Anderson Type2{QRDecomp},
Memory size = 15, RestartedMemory,
Safeguarded: true, tol: 2.0
Setup Time: 0.61ms
Iter: Objective: Primal Res: Dual Res: Rho:
1 -3.1509e+02 2.7621e+01 7.8548e+00 1.0000e-01
25 7.4069e+01 1.3454e-07 2.0250e-08 1.0000e-01
------------------------------------------------------------------
>>> Results
Status: Solved
Iterations: 25
Optimal objective: 74.07
Runtime: 0.003s (2.83ms)opt_objective = JuMP.objective_value(model)74.068931629612This gives the same result.
Problem with A as variable
Above problems are mostly helpful for illustrative purpose. It is obviously easier to find the sum of the k-largest eigenvalues by simply computing the eigenvalues of $A$. However, above results become useful if finding $A$ itself is part of the problem. For example, assume we want to find a valid matrix $A$ under the constraints: $C\, \text{vec}(A) = b$ with the minimum sum of absolute values of the k-largest eigenvalues. We can then solve the equivalent problem:
\[\begin{array}{ll} \text{minimize} & kz + Tr(U) + Tr(V) \\ \text{subject to} & C \text{vec}(A) = b \\ & zI + V - A \succeq 0 \\ & zI + U + A \succeq 0 \\ & U, V \succeq 0. \end{array}\]
References
[1] Alizadeh - Interior point methods in semidefinite programming with applications to combinatorial optimization (1995)
This page was generated using Literate.jl.