Convex Optimization · Problem 10.15

Interior-point methods — Boyd & Vandenberghe

Mathematics — Optimization · equality-constrained-entropy-maximization-numerical

Problem

Equality constrained entropy maximization. Consider the equality constrained entropy maximization problem

\begin{array}{ll} \text{minimize} & f(x) = \sum_{i=1}^n x_i \log x_i \\ \text{subject to} & Ax = b, \end{array}

with

\mathbf{dom}\, f = \mathbf{R}^n_{++}

and

A \in \mathbf{R}^{p \times n}

, with

p < n

. (See exercise 10.9 for some relevant analysis.) Generate a problem instance with

n = 100

and

p = 30

by choosing

A

randomly (checking that it has full rank), choosing

\hat{x}

as a random positive vector (e.g., with entries uniformly distributed on

[0,1]

) and then setting

b = A\hat{x}

. (Thus,

\hat{x}

is feasible.) Compute the solution of the problem using the following methods. (a) Standard Newton method. You can use initial point

x^{(0)} = \hat{x}

. (b) Infeasible start Newton method. You can use initial point

x^{(0)} = \hat{x}

(to compare with the standard Newton method), and also the initial point

x^{(0)} = \mathbf{1}

. (c) Dual Newton method, i.e., the standard Newton method applied to the dual problem. Verify that the three methods compute the same optimal point (and Lagrange multiplier). Compare the computational effort per step for the three methods, assuming relevant structure is exploited. (Your implementation, however, does not need to exploit structure to compute the Newton step.)

Related theory

Quantum Entropy And Von Neumann Entropy

Browse the problem library