Convex Optimization · Problem 4.43

Duality — Boyd & Vandenberghe

Mathematics — Optimization · eigenvalue-optimization-sdp

Problem

Eigenvalue optimization via SDP. Suppose

A : \mathbf{R}^n \to \mathbf{S}^m

is affine, i.e.,

A(x) = A_0 + x_1 A_1 + \cdots + x_n A_n

where

A_i \in \mathbf{S}^m

. Let

\lambda_1(x) \geq \lambda_2(x) \geq \cdots \geq \lambda_m(x)

denote the eigenvalues of

A(x)

. Show how to pose the following problems as SDPs. (a) Minimize the maximum eigenvalue

\lambda_1(x)

. (b) Minimize the spread of the eigenvalues,

\lambda_1(x) - \lambda_m(x)

. (c) Minimize the condition number of

A(x)

, subject to

A(x) \succ 0

. The condition number is defined as

\kappa(A(x)) = \lambda_1(x)/\lambda_m(x)

, with domain

\{x \mid A(x) \succ 0\}

. You may assume that

A(x) \succ 0

for at least one

x

. Hint. You need to minimize

\lambda/\gamma

, subject to

0 \prec \gamma I \preceq A(x) \preceq \lambda I.

Change variables to

y = x/\gamma

t = \lambda/\gamma

s = 1/\gamma

. (d) Minimize the sum of the absolute values of the eigenvalues,

|\lambda_1(x)| + \cdots + |\lambda_m(x)|

. Hint. Express

A(x)

A(x) = A_+ - A_-

, where

A_+ \succeq 0

A_- \succeq 0