Entropy maximization

A derivative work by Judson Wilson, 6/2/2014.
Adapted from the CVX example of the same name, by Joëlle Skaf, 4/24/2008.

Introduction

Consider the linear inequality constrained entropy maximization problem: $$\begin{array}{ll} \mbox{maximize} & -\sum_{i=1}^n x_i \log(x_i) \\ \mbox{subject to} & \sum_{i=1}^n x_i = 1 \\ & Fx \succeq g, \end{array}$$ where the variable is $x \in \mathbf{{\mbox{R}}}^{n}$.

This problem can be formulated in CVXPY using the entr atom.

Generate problem data



In [1]:

    
import cvxpy as cp
import numpy as np

# Make random input repeatable. 
np.random.seed(0) 

# Matrix size parameters.
n = 20
m = 10
p = 5

# Generate random problem data.
tmp = np.random.rand(n)
A = np.random.randn(m, n)
b = A.dot(tmp)
F = np.random.randn(p, n)
g = F.dot(tmp) + np.random.rand(p)

Formulate and solve problem



In [2]:

    
# Entropy maximization.
x = cp.Variable(shape=n)
obj = cp.Maximize(cp.sum(cp.entr(x)))
constraints = [A*x == b,
               F*x <= g ]
prob = cp.Problem(obj, constraints)
prob.solve(solver=cp.ECOS, verbose=True)

# Print result.
print("\nThe optimal value is:", prob.value)
print('\nThe optimal solution is:')
print(x.value)









    



ECOS 2.0.7 - (C) embotech GmbH, Zurich Switzerland, 2012-15. Web: www.embotech.com/ECOS

It     pcost       dcost      gap   pres   dres    k/t    mu     step   sigma     IR    |   BT
 0  +0.000e+00  -1.183e+01  +7e+01  1e+00  4e-01  1e+00  1e+00    ---    ---    0  0  - |  -  - 
 1  -1.045e+01  -1.419e+01  +2e+01  2e-01  1e-01  4e-01  3e-01  0.7833  5e-02   1  1  1 |  2  1
 2  -5.864e+00  -6.905e+00  +4e+00  7e-02  3e-02  1e-01  5e-02  0.7833  5e-02   1  1  1 |  2  1
 3  -5.590e+00  -6.018e+00  +1e+00  3e-02  1e-02  5e-02  2e-02  0.6266  5e-02   1  1  1 |  2  2
 4  -5.525e+00  -5.621e+00  +3e-01  7e-03  3e-03  1e-02  5e-03  0.7818  1e-02   1  1  1 |  1  1
 5  -5.490e+00  -5.530e+00  +1e-01  3e-03  1e-03  5e-03  2e-03  0.6266  5e-02   1  1  1 |  2  2
 6  -5.484e+00  -5.493e+00  +3e-02  7e-04  3e-04  1e-03  4e-04  0.7833  1e-02   1  1  1 |  1  1
 7  -5.482e+00  -5.485e+00  +1e-02  3e-04  1e-04  4e-04  2e-04  0.6266  5e-02   2  1  1 |  2  2
 8  -5.481e+00  -5.482e+00  +2e-03  6e-05  3e-05  1e-04  4e-05  0.7833  1e-02   1  1  1 |  1  1
 9  -5.481e+00  -5.481e+00  +1e-03  3e-05  1e-05  4e-05  2e-05  0.6266  5e-02   1  1  1 |  2  2
10  -5.481e+00  -5.481e+00  +2e-04  6e-06  3e-06  9e-06  3e-06  0.7833  1e-02   2  1  1 |  1  1
11  -5.481e+00  -5.481e+00  +9e-05  2e-06  1e-06  4e-06  1e-06  0.6266  5e-02   1  0  0 |  2  2
12  -5.481e+00  -5.481e+00  +2e-05  5e-07  2e-07  8e-07  3e-07  0.7833  1e-02   1  0  0 |  1  1
13  -5.481e+00  -5.481e+00  +8e-06  2e-07  1e-07  3e-07  1e-07  0.6266  5e-02   2  0  0 |  2  2
14  -5.481e+00  -5.481e+00  +2e-06  5e-08  2e-08  7e-08  3e-08  0.7833  1e-02   1  0  0 |  1  1
15  -5.481e+00  -5.481e+00  +7e-07  2e-08  9e-09  3e-08  1e-08  0.6266  5e-02   0  0  0 |  2  2
16  -5.481e+00  -5.481e+00  +2e-07  4e-09  2e-09  7e-09  3e-09  0.7833  9e-03   0  0  0 |  1  1
17  -5.481e+00  -5.481e+00  +6e-08  2e-09  8e-10  3e-09  1e-09  0.6266  5e-02   1  0  0 |  2  2
18  -5.481e+00  -5.481e+00  +1e-08  4e-10  2e-10  6e-10  2e-10  0.7833  9e-03   1  0  0 |  1  1

OPTIMAL (within feastol=4.0e-10, reltol=2.7e-09, abstol=1.5e-08).
Runtime: 0.003436 seconds.


The optimal value is: 5.480901488005442

The optimal solution is:
[0.43483319 0.66111715 0.49201039 0.3603062  0.3841663  0.30283659
 0.4173023  0.79107794 0.76667303 0.38292364 1.2479328  0.50416987
 0.68053833 0.67163957 0.13877258 0.5248668  0.08418897 0.56927148
 0.50000247 0.78291311]