Convex Optimization · Problem 6.14

Statistical estimation — Boyd & Vandenberghe

Mathematics — Optimization · interpolation-with-positive-real-functions

Problem

[Nes00] Interpolation with positive-real functions. Suppose z1,…,zn∈Cz_1, \ldots, z_n \in \mathbf{C} are nn distinct points with ∣zi∣>1|z_i| > 1. We define KnpK_{\mathrm{np}} as the set of vectors y∈Cny \in \mathbf{C}^n for which there exists a function f:C→Cf : \mathbf{C} \to \mathbf{C} that satisfies the following conditions. • ff is positive-real, which means it is analytic outside the unit circle (i.e., for ∣z∣>1|z| > 1), and its real part is nonnegative outside the unit circle (ℜf(z)≥0\Re f(z) \geq 0 for ∣z∣>1|z| > 1). • ff satisfies the interpolation conditions f(z1)=y1,f(z2)=y2,…,f(zn)=yn.f(z_1) = y_1, \quad f(z_2) = y_2, \quad \ldots, \quad f(z_n) = y_n. If we denote the set of positive-real functions as F\mathcal{F}, then we can express KnpK_{\mathrm{np}} as Knp={y∈Cn∣∃f∈F,  yk=f(zk),  k=1,…,n}.K_{\mathrm{np}} = \{y \in \mathbf{C}^n \mid \exists f \in \mathcal{F},\; y_k = f(z_k),\; k = 1, \ldots, n\}. (a) It can be shown that ff is positive-real if and only if there exists a nondecreasing function ρ\rho such that for all zz with ∣z∣>1|z| > 1, f(z)=iℑf(∞)+∫02πeiθ+z−1eiθ−z−1dρ(θ),f(z) = i\Im f(\infty) + \int_0^{2\pi} \frac{e^{i\theta} + z^{-1}}{e^{i\theta} - z^{-1}} d\rho(\theta), where i=−1i = \sqrt{-1} (see [KN77, page 389]). Use this representation to show that KnpK_{\mathrm{np}} is a closed convex cone. (b) We will use the inner product ℜ(xHy)\Re(x^H y) between vectors x,y∈Cnx, y \in \mathbf{C}^n, where xHx^H denotes the complex conjugate transpose of xx. Show that the dual cone of KnpK_{\mathrm{np}} is given by Knp∗={x∈Cn   ∣   ℑ(1Tx)=0,  ℜ(∑l=1nxle−iθ+zˉl−1e−iθ−zˉl−1)≥0  ∀θ∈[0,2π]}.K^*_{\mathrm{np}} = \left\{ x \in \mathbf{C}^n \;\ \Big| \;\ \Im(\mathbf{1}^T x) = 0,\; \Re\left(\sum_{l=1}^n x_l \frac{e^{-i\theta} + \bar{z}_l^{-1}}{e^{-i\theta} - \bar{z}_l^{-1}}\right) \geq 0 \;\forall \theta \in [0, 2\pi] \right\}. (c) Show that Knp∗={x∈Cn   ∣   ∃Q∈H+n,  xl=∑k=1nQkl1−zk−1zˉl−1,  l=1,…,n}K^*_{\mathrm{np}} = \left\{ x \in \mathbf{C}^n \;\ \Big| \;\ \exists Q \in \mathbf{H}^n_+,\; x_l = \sum_{k=1}^n \frac{Q_{kl}}{1 - z_k^{-1}\bar{z}_l^{-1}},\; l = 1, \ldots, n \right\} where H+n\mathbf{H}^n_+ denotes the set of positive semidefinite Hermitian matrices of size n×nn \times n. Use the following result (known as Riesz-Fej\'er theorem; see [KN77, page 60]). A function of the form ∑k=0n(yke−ikθ+yˉkeikθ)\sum_{k=0}^n (y_k e^{-ik\theta} + \bar{y}_k e^{ik\theta}) is nonnegative for all θ\theta if and only if there exist a0,…,an∈Ca_0, \ldots, a_n \in \mathbf{C} such that ∑k=0n(yke−ikθ+yˉkeikθ)=∣∑k=0nakeikθ∣2.\sum_{k=0}^n (y_k e^{-ik\theta} + \bar{y}_k e^{ik\theta}) = \left| \sum_{k=0}^n a_k e^{ik\theta} \right|^2. (d) Show that Knp={y∈Cn∣P(y)⪰0}K_{\mathrm{np}} = \{y \in \mathbf{C}^n \mid P(y) \succeq 0\} where P(y)∈HnP(y) \in \mathbf{H}^n is defined as P(y)kl=yk+yl‾1−zk−1zˉl−1,l,k=1,…,n.P(y)_{kl} = \frac{y_k + \overline{y_l}}{1 - z_k^{-1}\bar{z}_l^{-1}}, \quad l, k = 1, \ldots, n. The matrix P(y)P(y) is called the Nevanlinna-Pick matrix associated with the points zkz_k, yky_k. Hint. As we noted in part (a), KnpK_{\mathrm{np}} is a closed convex cone, so Knp=Knp∗∗K_{\mathrm{np}} = K^{**}_{\mathrm{np}}. (e) As an application, pose the following problem as a convex optimization problem: minimize∑k=1n∣f(zk)−wk∣2subject tof∈F.\begin{aligned} &\text{minimize} \quad \sum_{k=1}^n |f(z_k) - w_k|^2 \\ &\text{subject to} \quad f \in \mathcal{F}. \end{aligned} The problem data are nn points zkz_k with ∣zk∣>1|z_k| > 1 and nn complex numbers w1,…,wnw_1, \ldots, w_n. We optimize over all positive-real functions ff.

Related theory

Browse the problem library