3.5 Semidefinite program
A semidefinite program optimizes over positive semidefinite (PSD) matrices. (This requires the LAPACK-enabled SCS build, which this package ships.) Over symmetric 2×2 matrices X = [[a b] [b c]] we solve
minimize trace(X) = a + c
subject to X ⪰ 0, b = 1
X ⪰ 0 with b = 1 forces ac ≥ 1, so a + c ≥ 2 with equality at a = c = 1. The optimum is (a, b, c) = (1, 1, 1).
(require scs)
(provide run-example)
3.5.1 The svec scaling
SCS represents a k×k symmetric matrix by the lower triangle stacked column-wise, with the off-diagonal entries scaled by √2 (so that the standard inner product is preserved). For our 2×2 matrix that vector is svec(X) = (a, √2·b, c). To make the cone slack equal svec(X) we put −diag(1, √2, 1) on the PSD block:
(define root2 (sqrt 2.0)) (define A (scs:matrix 4 3 0 1 0 ; b = 1 (zero cone) -1 0 0 ; svec = (a, root2 b, c) 0 (- root2) 0 0 0 -1))
#:psd takes the list of matrix dimensions k (here ’(2)); the block length is k(k+1)/2.
(solve #:A A #:b #(1.0 0.0 0.0 0.0) #:c #(1.0 0.0 1.0) #:cone (make-cone #:zero 1 #:psd '(2)) #:settings (make-settings #:eps-abs 1e-9 #:eps-rel 1e-9))
Running it.
(scs-result-x (run-example)) ; #(1.0 1.0 1.0) = (a, b, c)