needsPackage("SemidefiniteProgramming") needsPackage( "SumsOfSquares" ); -- An SDP example (MAXCUT on K_3) C = matrix{{0,1/2,1/2},{1/2,0,1/2},{1/2,1/2,0}}; A = (matrix{{1,0,0},{0,0,0},{0,0,0}},matrix{{0,0,0},{0,1,0},{0,0,0}},matrix{{0,0,0},{0,0,0},{0,0,1}}); b = matrix{{1},{1},{1}}; P = sdp(C, A ,b) (X,y,Z,stat) = optimize P; X Z transpose(b)*y trace(C*X) -- the same example but in the dual formulation clearAll R = QQ[a,b,c]; M = matrix{{1,a,b},{a,1,c},{b,c,1}}; f = a+b+c; P = sdp({a,b,c},M, f); (X,y,Z,stat) = optimize P; X Z -- Univariate SOS R = QQ[t] f = 1+t^4 sol = solveSOS (f) g = sosPoly sol (Q,v) = ( sol#GramMatrix, sol#Monomials ) -- The Motzkin polynomial and a multiple of it clearAll R = QQ[x,y,z] h = x^2 + y^2 + z^2 f = library("Motzkin",R) sol = solveSOS (f) sol = solveSOS (f*h) g = sosPoly sol (Q,v) = ( sol#GramMatrix, sol#Monomials ) -- 5 CYCLE STABLE SET EXAMPLE R = QQ[x1,x2,x3,x4,x5]/ideal(x1^2-x1, x2^2-x2,x3^2-x3,x4^2-x4,x5^2-x5, x1*x2,x2*x3,x3*x4,x4*x5,x1*x5) f =-1*(x1+x2+x3+x4+x5) (t, sol) = lowerBound(f,2) numeric(-t) g = sosPoly sol (Q,v) = ( sol#GramMatrix, sol#Monomials ) (t, sol) = lowerBound(f,4) numeric(-t) g = sosPoly sol (Q,v) = ( sol#GramMatrix, sol#Monomials ) -- MAX-CUT of a 5-CYCLE R = QQ[x1,x2,x3,x4,x5]/ideal(x1^2-1, x2^2-1,x3^2-1,x4^2-1,x5^2-1) f = -1*((1-x1*x2)/2+ (1-x2*x3)/2+ (1-x3*x4)/2+ (1-x4*x5)/2+ (1-x1*x5)/2) (t, sol) = lowerBound(f,2) numeric(t) g = sosPoly sol (Q,v) = ( sol#GramMatrix, sol#Monomials ) (t, sol) = lowerBound(f,4) numeric(t) g = sosPoly sol (Q,v) = ( sol#GramMatrix, sol#Monomials )