Convex Optimization · Problem 4.38

Duality — Boyd & Vandenberghe

Mathematics — Optimization · lmis-sdps-one-variable-generalized-eigenvalues

Problem

LMIs and SDPs with one variable. The generalized eigenvalues of a matrix pair

(A, B)

, where

A, B \in \mathbf{S}^n

, are defined as the roots of the polynomial

\det(\lambda B - A)

(see \S A.5.3). Suppose

B

is nonsingular, and that

A

and

B

can be simultaneously diagonalized by a congruence, i.e., there exists a nonsingular

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

such that

R^T A R = \mathbf{diag}(a), \qquad R^T B R = \mathbf{diag}(b),

where

a, b \in \mathbf{R}^n

. (A sufficient condition for this to hold is that there exists

t_1, t_2

such that

t_1 A + t_2 B \succ 0

.) (a) Show that the generalized eigenvalues of

(A, B)

are real, and given by

\lambda_i = a_i/b_i

i = 1, \ldots, n

. (b) Express the solution of the SDP

\begin{aligned} \text{minimize} & \quad ct \\ \text{subject to} & \quad tB \preceq A, \end{aligned}

with variable

t \in \mathbf{R}

, in terms of

a

and

b

Intuitive explanation

When two symmetric matrices can be simultaneously diagonalized, the problem decouples into independent scalar comparisons along each diagonal direction. The generalized eigenvalues measure the "ratio" of how $A$ and $B$ scale in their shared eigenbasis—finding where $A$ dominates $B$ by a factor $\lambda$ . For the SDP, you're looking for the smallest scalar $t$ such that $tB - A$ remains negative semidefinite; in the diagonalized form, this becomes a simple constraint on each ratio $a_i/b_i$ , and the answer is determined by the most restrictive one.

Intuitive explanation

Related theory

Linear Equations In One Variable

Browse the problem library