Convex Optimization · Problem 4.48

Duality — Boyd & Vandenberghe

Mathematics — Optimization · generalized-eigenvalue-minimization

Problem

Generalized eigenvalue minimization. Recall (from example 3.37, or \S A.5.3) that the largest generalized eigenvalue of a pair of matrices

(A, B) \in \mathbf{S}^k \times \mathbf{S}^k_{++}

is given by

\lambda_{\max}(A, B) = \sup_{u \neq 0} \frac{u^T A u}{u^T B u} = \max\{\lambda \mid \det(\lambda B - A) = 0\}.

As we have seen, this function is quasiconvex (if we take

\mathbf{S}^k \times \mathbf{S}^k_{++}

as its domain). We consider the problem

\text{minimize} \quad \lambda_{\max}(A(x), B(x)) \tag{4.73}

where

A, B : \mathbf{R}^n \to \mathbf{S}^k

are affine functions, defined as

A(x) = A_0 + x_1 A_1 + \cdots + x_n A_n, \qquad B(x) = B_0 + x_1 B_1 + \cdots + x_n B_n.

with

A_i, B_i \in \mathbf{S}^k

. (a) Give a family of convex functions

\phi_t : \mathbf{S}^k \times \mathbf{S}^k \to \mathbf{R}

, that satisfy

\lambda_{\max}(A, B) \leq t \iff \phi_t(A, B) \leq 0

for all

(A, B) \in \mathbf{S}^k \times \mathbf{S}^k_{++}

. Show that this allows us to solve (4.73) by solving a sequence of convex feasibility problems. (b) Give a family of matrix-convex functions

\Phi_t : \mathbf{S}^k \times \mathbf{S}^k \to \mathbf{S}^k

that satisfy

\lambda_{\max}(A, B) \leq t \iff \Phi_t(A, B) \preceq 0

for all

(A, B) \in \mathbf{S}^k \times \mathbf{S}^k_{++}

. Show that this allows us to solve (4.73) by solving a sequence of convex feasibility problems with LMI constraints. (c) Suppose

B(x) = (a^T x + b)I

, with

a \neq 0

. Show that (4.73) is equivalent to the convex problem

\begin{array}{ll} \text{minimize} & \lambda_{\max}(s A_0 + y_1 A_1 + \cdots + y_n A_n) \\ \text{subject to} & a^T y + bs = 1 \\ & s \geq 0, \end{array}

with variables

y \in \mathbf{R}^n

s \in \mathbf{R}