Convex Optimization · Problem 10.9

Interior-point methods — Boyd & Vandenberghe

Mathematics — Optimization · equality-constrained-entropy-maximization

Problem

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

\begin{aligned} \text{minimize} & \quad f(x) = \sum_{i=1}^n x_i \log x_i \nonumber \\ \text{subject to} & \quad Ax = b, \tag{10.42} \end{aligned}

with

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

and

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

. We assume the problem is feasible and that

\mathbf{rank}\, A = p < n

. ((a)) Show that the problem has a unique optimal solution

x^\star

. ((b)) Find

A

b

, and feasible

x^{(0)}

for which the sublevel set

\{x \in \mathbf{R}^n_{++} \mid Ax = b,\, f(x) \leq f(x^{(0)})\}

is not closed. Thus, the assumptions listed in \S10.2.4, page 529, are not satisfied for some feasible initial points. ((c)) Show that the problem (10.42) satisfies the assumptions for the infeasible start Newton method listed in \S10.3.3, page 536, for any feasible starting point. ((d)) Derive the Lagrange dual of (10.42), and explain how to find the optimal solution of (10.42) from the optimal solution of the dual problem. Show that the dual problem satisfies the assumptions listed in \S10.2.4, page 529, for any starting point. The results of part (b), (c), and (d) do not mean the standard Newton method will fail, or that the infeasible start Newton method or dual method will work better in practice. It only means our convergence analysis for the standard Newton method does not apply, while our convergence analysis does apply to the infeasible start and dual methods. (See exercise 10.15.)

Related theory

Quantum Entropy And Von Neumann Entropy

Browse the problem library