A non-linear semidefinite program

Contents

The main purpose of PUMA is to solve the problem

$\displaystyle\underset{P\in \mathbb{H}^N_R}{\text{min}}\underset{\omega}{\text{max}}\frac{P(\omega)}{R(\omega)}$ for all $\omega$ in the passband

where $P,R$ are positive polynomials of degree at most 2N and $\mathbb{H}^N_R$ (admissible polynomials) is the set of polynomials of degree at most 2N such that the minimum phase function $g_P(\omega)$ is admissible with

$\displaystyle |g_P(\omega)|^2 = \left( 1+ \frac{R(\omega)}{P(\omega)}\right)^{-1}$

Therefore, given a load A with transmission zeros $\alpha_i$ and reflection coefficient $A_{22}$ at the second port, in order to check if a polynomial $P(\omega)$ is admissible, we proceed as follows

Compute the stable function $g_P(\omega)$ as the minimum phase factor of $(1+R/P)^{-1}$
Check for the existence of a schur function $b(\omega)$ such that $b(\alpha_i) = A_{22}(\alpha_i)/g_P(\alpha_i)$ . This is done by testing the positive definiteness of the matrix

$\displaystyle \Delta(P) = \frac{1}{j}\left(\begin{array}{cccc}\frac{1-|\gamma_1|^2}{2j\text{Im}(\alpha_1)} & \frac{1-\gamma_1\overline{\gamma_2}}{\alpha_1 - \overline{\alpha_2}} & \cdots & \frac{1-\gamma_1\overline{\gamma_N}}{\alpha_1 - \overline{\alpha_N}}\\ \frac{1-\gamma_2\overline{\gamma_1}}{\alpha_2 - \overline{\alpha_1}} & \frac{1-|\gamma_2|^2}{2j\text{Im}(\alpha_2)} & \cdots & \frac{1-\gamma_2\overline{\gamma_N}}{\alpha_2 - \overline{\alpha_N}} \\ \vdots & \vdots & \ddots & \vdots\\ \frac{1-\gamma_N \overline{\gamma_1}}{\alpha_N -\overline{\alpha_1}} & \frac{1-\gamma_N\overline{\gamma_2}}{\alpha_N-\overline{\alpha_2}}& \cdots & \frac{1-|\gamma_N|^2}{2j\text{Im}(\alpha_N)}\end{array} \right)$

with $\gamma_i = A_{22}(\alpha_i)/g_P(\alpha_i)$ .

Thus we can write the previous problem as

$\displaystyle\underset{P}{\text{min}}\underset{\omega}{\text{max}}\frac{P(\omega)}{R(\omega)}$ s.t $\Delta(P)\succeq 0$ for all $\omega$ in the passband

This is a min-max problem that minimises the maximum of a linear criterium over the convex cone of positive polynomials P. However the matrix $\Delta(P)$ depends not linearly on P what makes the problem not a standard one.

Solving a min-max problem

In order to deal with the min-max problem we introduce the variable $L=\underset{\omega}{\text{max}}P(\omega)/R(\omega)$ . This allows us to restate the problem as

$\displaystyle \underset{P}{\text{min}} L$

such that:

$\displaystyle P(\omega)\geq 0$ for all $\omega$ real

$\displaystyle \frac{P(\omega)}{R(\omega)}\leq L$ for all $\omega$ in the passband

$\displaystyle \Delta(P)\succeq 0$

Positive polynomials

A polynomial P of degree 2N is non-negative on the real line if and only if there exist a positive semidefinite $(N+1)x(N+1)$ matrix $\Theta_0$ such that

$\displaystyle \psi_N(\omega) \Theta_0 \psi_N^T(\omega) = P(\omega)$

where $\psi_N(\omega)$ is the corresponding basis vector of degree N. For instance, the monomials of degree 0 to N:

$\displaystyle \psi_N = [\omega^N, \omega^{N-1}, \cdots, 0]$

This matrix $\Theta_0$ is called the Gram matrix.

From the Gram matrix $\Theta_0$ it is possible to obtain the coefficients of the corresponding polynomial P with the linear operation

$\displaystyle P = Z\cdot \text{vec}\Theta_0$

where Z is a matrix of size $(2N-1)x(N^2+N)/2$ and $\text{vec}\Theta_0$ is the column vector with the coefficients in the lower triangle of $\Theta_0$ .

Positive polynomials on an interval

The polynomials $Q(\omega)$ of degree 2N that are positive on an interval $[a,b]$ are parametrised as

$\displaystyle Q(\omega) = F(\omega) - (\omega-a)(\omega-b) G(\omega)$

where $F(\omega)$ and $G(\omega)$ are polynomials positive on the real axis of degree 2N and 2N-2 respectively.

Therefore, using the previous theorem, polynomials F,G are positive if and only if there exist positive definite matrices $\Theta_1$ of size $(N+1)x(N+1)$ and $\Theta_2$ of size $NxN$ such that

$\displaystyle \psi_N(\omega) \Theta_1\psi_N^T(\omega) = F(\omega)$

$\displaystyle \psi_{N-1}(\omega) \Theta_2 \psi_{N-1}^T(\omega) = G(\omega)$

As in the previous case, the coefficients of the polynomial Q depend linearly on the matrices $\Theta_1, \Theta_2$

$\displaystyle Q = \Omega \cdot \left[\begin{array}{c} \text{vec}\Theta_1\\\text{vec}\Theta_2\end{array} \right]$

with $\Omega$ a matrix of size $(2N-1)xN^2$

Semi-definite program

Using the previous parametrisation of positive polynomials we can use the positive definite Gram matrices $\Theta_0,\Theta_1, \Theta_2$ to ensure that $P(\omega)$ is a positive polynomial and also that $R(\omega)\cdot L - P(\omega)(\omega)$ is positive in the passband.

Thus we re-parametrice the problem in function of the Gram matrices

$\displaystyle \begin{array}{l} P\rightarrow P(\Theta_0) \\ \Delta(P) \rightarrow \Delta(\Theta_0) \\ Q=RL-P \rightarrow Q(\Theta_1,\Theta_2)\end{array}$

Note that by doing that it is necessary to impose that the matrix $\Theta_0$ and the matrices $\Theta_1,\Theta_2$ represent the same polynomial P. We do that by imposing the linear equalities $Q=R\cdot L - P$ or equivalently $-RL+P+Q = 0$ . Using the above relations we obtain the linear system

$\displaystyle [-R,Z,\Omega] \cdot \left[\begin{array}{c}L\\ \text{vec}\Theta_0 \\ \text{vec}\Theta_1\\\text{vec}\Theta_2\end{array} \right] = 0$

Finally the problem remains

$\displaystyle \underset{\Theta_0,\Theta_1,\Theta_2,L}{min}(L)$ subject to $\Theta_0\succeq 0$ , $\Theta_1\succeq 0$ , $\Theta_2\succeq 0$ , $\Delta(\Theta_0)\succeq 0$ and $\displaystyle [-R,Z,\Omega] \cdot \left[\begin{array}{c}L\\ \text{vec}\Theta_0 \\ \text{vec}\Theta_1\\\text{vec}\Theta_2\end{array} \right] = 0$

This is a standard non linear semi-definite program under linear equality constrains that is solved by means of the matlab toolbox NonSDP.