Minimizing the ratio of two specific non negative quadratic convex functions

Question

$F$ is $m\times m$ diagonal, with real non negative elements

$D$ is $n \times m$ complex

$P$ is $n \times 1$ complex

$A$ is $m \times 1$ complex.

Minimize $\Gamma(A)$, with respect to $A$.

$$\Gamma(A) = \frac{m^2(DA-P)^H (DA-P) + (FA)^H(FA)}{A^HA}$$

It is known that both numerator and denominator of $\Gamma(A)$ are convex and non negative. Also both the terms of the numerator are individually convex and non negative.

Question: An numerical optimization algorithm to find global minimum.

Apart from a reagular solution, I am also interested in a gradient descent based method if possible as the matrices are large. Also $m >> n$.

PS : This question is a specific version of this question.

EDIT : more known information

No constraints on problem but

1. $\sum P = 0$, I mean sum of elements of matrix $P$ is zero.
2. Diagonal elements of $F$ are not all zeros.
3. Also $P^HP \ne 0$.
4. Rows of $D$ are orthogonal to each other. Also they are linearly independent.

Answer 1

If you write $A$ as a vector $x$ (just stack the columns of $A$) both the numerator and the denominator are quadratic in $x$. Let's say the objective is $f(x) / g(x)$ with $g(x)>0$. Dinkelbach noticed that $$\min_x \frac{f(x)}{g(x)} \leq \alpha \Leftrightarrow \min_x \{f(x) - \alpha g(x) \} \leq 0. $$ This allows you to perform bisection search on $\alpha$. The trick is to find the smallest $\alpha$ such that the Hessian of $f(x) - \alpha g(x)$ is still positive semidefinite. After you find that $\alpha$, solve $\min_x \{f(x) - \alpha g(x) \}$ for the corresponding $x$.

Answer 2

Your optimization problem is:

$\text{min}_A \quad \frac{m^2(DA-P)^H (DA-P) + (FA)^H(FA)}{A^HA}$

Rearranging terms, one gets:

$\text{min}_A \quad \frac{A^H (m^2 D^HD + F^H F)A\; -\;2 m^2(P^H D A + P D^H A^H) \;+\; m^2 P^HP}{A^HA}$

While the problem is defined over complex vectors, one can always recast the problem over the reals of dimension 2m, by stacking the real and imaginary parts. The problem over the reals looks like:

$\text{min}_x \quad f(x)\quad \quad \text{where } f(x) = \frac{x^T Q x}{x^T x} - \frac{b^T x}{x^T x} + \frac{c}{x^T x}$

We can see that the first term of $f(x)$ only depends on the direction of $x$, while the last term only depends on its norm. A natural re-parametrization is then $x = \alpha \hat{x}$, where $\alpha >= 0$ and $||\hat{x}||_2 = 1$ and $f(x)$ becomes:

$f(\hat{x},\alpha) = \hat{x}^T Q \hat{x} - \frac{b^T \hat{x}}{\alpha} + \frac{c}{\alpha^2}$

And the optimization problem then becomes:

$\text{min}_{\hat{x} } \quad \text{min}_{\alpha\geq 0} \quad f(\hat{x},\alpha)$

Looking at the inner problem, we get that fixing $\hat{x}$, the problem becomes a minimization of a quadratic polynomial on $\frac{1}{\alpha}$. Taking the gradient w.r.t. $\alpha$ and equating to 0 leads to:

$\frac{b^T \hat{x}}{\alpha^2} - \frac{2c}{\alpha^3} = 0 \quad \to \quad \alpha^* = \frac{2c}{b^T \hat{x}}$ or $\frac{1}{\alpha^*} = \frac{b^T \hat{x}}{2c}$

Plugging that in we get: $f(\hat{x},\alpha^*) = \hat{x}^T Q \hat{x} - \frac{\hat{x} (b b^T) \hat{x}}{2c} + \frac{\hat{x} (b b^T) \hat{x}}{4c} = \hat{x}^T (Q - \frac{b b^T}{4c}) \hat{x}$

The outer problem becomes: $\text{min}_{\hat{x} } \quad \hat{x}^T (Q - \frac{b b^T}{4c}) \hat{x} \quad \text{s.t.} \quad ||\hat{x}||_2 = 1$

which is a simple eigenvalue problem, i.e. $\hat{x}^*$ is the eigenvector corresponding to the lowest eigenvalue of $(Q - \frac{b b^T}{4c})$. Given that $Q$ is built from the matrix D you mention and + rank 1 update, and that D is short and fat with orthogonal columns, you should be able to solve this eigenvalue problem more efficiently than standard methods for dense full-rank dense matrices.

Once you have $\hat{x}^*$, you can find the corresponding $\alpha^*$ using the formula above, and possibly flip the sign of $\alpha \hat{x}$ so that $b^T \hat{x}$ is positive (if you take a look at f(x), you can see that both the first and last terms are invariant to sign flip of $x$, so you can choose the sign that minimizes $-b^Tx$, which is the one for which $b^Tx\geq 0$).