# SemidefiniteOptimization for operator norms: Stuck at the edge of dual feasibility

Can someone give a workaround and/or explanation why Problem 1/Problem 2 fail to solve through SemidefiniteOptimization? Problem 3 works. (I'm using 12.1.0 on Mac). The main difference is that Problem 1+2 use diagonal matrix constraint, whereas Problem 3 matrix constraint has no 0's. I could solve them without calling SemidefiniteOptimization, but prefer to have a single solution to cover a wide range of cases.

### Problem 1

Implementation below below fails with Stuck at the edge of dual feasibility.

Find operator norm of $$f(A)=5A$$ by solving the following problem:

$$\text{min}_{A,x} x$$

Subject to $$I\succ A \succ -I\\ x I \succ -5 A$$

d = 1;
ii = IdentityMatrix[d];
(* Symbolic symmetric d-by-d matrix *)
ClearAll[a];
X = 5*ii;
A = Array[a[Min[#1, #2], Max[#1, #2]] &, {d, d}];
vars = DeleteDuplicates[Flatten[A]];

cons0 = VectorGreaterEqual[{A, -ii}, {"SemidefiniteCone", d}];
cons1 = VectorGreaterEqual[{ii, A}, {"SemidefiniteCone", d}];
cons2 = VectorGreaterEqual[{x ii, -X.A}, {"SemidefiniteCone", d}];
SemidefiniteOptimization[x, cons0 && cons1 && cons2, {x}~Join~vars]


### Problem 2

This example in $$2$$ dimension gives a different error: The matrix {{0.,1.},{2.,0.}} is not Hermitian or real and symmetric. Where did this matrix come from?

Find operator norm of $$f(A)=\left(\begin{matrix}1&0\\0&2\end{matrix}\right) A$$ by solving the following problem:

$$\text{min}_{A,x} x$$ Subject to $$I \succ A \succ -I\\ x I \succ -\left(\begin{matrix}1&0\\0&2\end{matrix}\right) A$$

d = 2;
ii = IdentityMatrix[d];
ClearAll[a];
extractVars[mat_] := DeleteDuplicates@Cases[Flatten@A, _a];
A = Array[a[Min[#1, #2], Max[#1, #2]] &, {d, d}];
vars = extractVars[A];
X = DiagonalMatrix@Range@d;
cons0 = VectorGreaterEqual[{A, -ii}, {"SemidefiniteCone", d}];
cons1 = VectorGreaterEqual[{ii, A}, {"SemidefiniteCone", d}];
cons2 = VectorGreaterEqual[{x ii, -X.A}, {"SemidefiniteCone", d}];
SemidefiniteOptimization[x, cons0 && cons1 && cons2, {x}~Join~vars]
(* Prints SemidefiniteOptimization::herm: The matrix {{0.,1.},{2.,0.}} is not Hermitian or real and symmetric. *)


### Problem 3

For this problem SemidefiniteOptimization works, even though the problem seems harder than the previous two.

Find operator norm of $$f(A)=\sum_i^{d^2} V_i' A V_i$$ by solving the following problem:

$$\text{min}_{A,x} x$$ Subject to $$I \succ A \succ -I\\ x I \succ -\sum_i^{d^2} V_i' A V_i \\$$

d = 4;
SeedRandom[1];
ii = IdentityMatrix[d];
ClearAll[a];
extractVars[mat_] := DeleteDuplicates@Cases[Flatten@A, _a];
A = Array[a[Min[#1, #2], Max[#1, #2]] &, {d, d}];
Vs = Table[RandomReal[{-1, 1}, {d, d}], {d^2}];
B = Total[Transpose[#].A.# & /@ Vs];
vars = extractVars[A];
X = DiagonalMatrix@Range@d;
cons0 = VectorGreaterEqual[{A, -ii}, {"SemidefiniteCone", d}];
cons1 = VectorGreaterEqual[{ii, A}, {"SemidefiniteCone", d}];
cons2 = VectorGreaterEqual[{x ii, -B}, {"SemidefiniteCone", d}];
solution =
A /. SemidefiniteOptimization[x, cons1 && cons2, {x}~Join~vars];
Print["result matches Russo-Dye: ",
Norm[solution - IdentityMatrix[d]] < 10^-7] (* True *)

• I think you want I>=A>=-I. The first constraint looks wrong. I assume you are using the infinity norm for the vector space. If that is also the norm for your operator space then it is the largest row sum of absolute values in A. Sep 9, 2020 at 18:21
• good point about the constraint, but creates same issue for SemidefiniteProgramming. I'm interpreting elements of vector space as matrices and using standard matrix norm rather than infinity norm, as in section 2.5 of Bhatia's cmat.edu.uy/~lessa/tesis/Positive%20Definite%20Matrices.pdf Sep 9, 2020 at 19:43
• Your code from Problem 2 works well for me in 12.0 on Windows 10, outputting {x -> -1., a[1, 1] -> 1., a[1, 2] -> 0., a[2, 2] -> 0.746381}. Sep 11, 2020 at 6:13
• Interesting, I'm running on 12.1, it seems SemidefiniteOptimization was modified in that version Sep 11, 2020 at 13:49

The following is less about the SemidefiniteOptimization function and more about the mathematical problem you are trying to solve --- and if there were no character limit this would be a comment rather than an answer --- but it seems to me that what your code outputs is not the operator norm? I slightly adjusted the code of your "Problem 3" so the new target function is $$f(A)=\begin{pmatrix}1&0\\0&2\end{pmatrix}A\begin{pmatrix}1&0\\0&2\end{pmatrix}\,.$$ This map has operator norm $$4$$, attained on $$e_2e_2^\top$$; yet the following adaptation of your code:

d = 2;
ii = IdentityMatrix[d];
ClearAll[a];
extractVars[mat_] := DeleteDuplicates@Cases[Flatten@A, _a];
A = Array[a[Min[#1, #2], Max[#1, #2]] &, {d, d}];
B = {{1, 0}, {0, 2}} . A . {{1, 0}, {0, 2}};
vars = extractVars[A];
cons0 = VectorGreaterEqual[{A, -ii}, {"SemidefiniteCone", d}];
cons1 = VectorGreaterEqual[{ii, A}, {"SemidefiniteCone", d}];
cons2 = VectorGreaterEqual[{x ii, -B}, {"SemidefiniteCone", d}];
SemidefiniteOptimization[x, cons0 && cons1 && cons2, {x}~Join~vars]


outputs {x -> -1., a[1, 1] -> 1., a[1, 2] -> 0., a[2, 2] -> 0.641407} which, evaluating $$f$$ on the alleged solution $$f\begin{pmatrix}1&0\\0&0.641407\end{pmatrix}=\begin{pmatrix}1&0\\0&2.56563\end{pmatrix}$$ suggests that the code optimized the smallest rather than the largest singular value of $$f(A)$$. If I have misinterpreted your objective or something about your code please let me know!

• you are right, I was playing around with representations from Watrous "Quantum Information", it's Eq. 2.87 for completely positive map $f$, it seems it should be max and not min Apr 7, 2023 at 16:50
• I guess it's called "Operator Sum Representation", so the underlying issue was -- how do you find the norm of operator given its OSR form. Your example gives OSR where the sum is just 1 term, but for general completely positive maps, you can have more than one term in the sum Apr 7, 2023 at 17:45