3.11 Maximum entropy
This example, mirroring the SCS entropy example, finds the maximum-entropy distribution on a finite set:
maximize −Σ x_i log x_i
subject to 1ᵀx = 1, x ≥ 0
With only the simplex constraint the maximizer is the uniform distribution x = (⅓, ⅓, ⅓), with entropy log 3. This is the Exponential cone put to work: the epigraph trick turns the nonlinear objective into cone membership.
(require scs)
(provide run-example)
3.11.1 Epigraph form via the exponential cone
Minimizing −Σ x_i log x_i is minimizing Σ t_i subject to t_i ≥ x_i log x_i. That epigraph constraint is exactly exponential-cone membership:
(−t_i, x_i, 1) ∈ K_exp ⟺ x_i·e^(−t_i / x_i) ≤ 1 ⟺ t_i ≥ x_i log x_i
Variables are w = (x₀, x₁, x₂, t₀, t₁, t₂). Row 0 is the simplex equality Σ x = 1 (zero cone); then three exponential-cone triples, each three rows encoding (−t_i, x_i, 1):
(define A (scs:matrix 10 6 1 1 1 0 0 0 ; sum x = 1 (zero cone) 0 0 0 1 0 0 ; s = -t0 -1 0 0 0 0 0 ; s = x0 0 0 0 0 0 0 ; s = 1 0 0 0 0 1 0 ; s = -t1 0 -1 0 0 0 0 ; s = x1 0 0 0 0 0 0 ; s = 1 0 0 0 0 0 1 ; s = -t2 0 0 -1 0 0 0 ; s = x2 0 0 0 0 0 0)) ; s = 1
The 1 rows for the third triple coordinate come from the b vector (the matching A rows are zero). The objective c sums the t_i.
(solve #:A A #:b #(1.0 0.0 0.0 1.0 0.0 0.0 1.0 0.0 0.0 1.0) #:c #(0.0 0.0 0.0 1.0 1.0 1.0) #:cone (make-cone #:zero 1 #:exp-primal 3) #:settings (make-settings #:eps-abs 1e-9 #:eps-rel 1e-9))
Running it.
(scs-result-x (run-example)) ; #(0.333 0.333 0.333 ...) (- (scs-result-pobj (run-example))) ; ~ log 3, the maximum entropy