Linear approximation of fraction for a maximization problem

Question

I have a problem given as \begin{align*} \underset{\mathbf{x}}{max} & \left|\mathop{\sum_{n=1}^{N}}\left[\frac{\mathbf{a}\left(n\right)}{\mathbf{b}\left(n\right)+\mathbf{x}\left(n\right)}\right]\right|^{2} &\\ \boldsymbol{\mathsf{s.t}\hspace{1em}} & constraint \end{align*}

$\mathbf{x}$ is optimization variable of length $n={1,2,..,N}$, whereas $\mathbf{x}$, $\mathbf{a}$ and $\mathbf{b}$ . I wanted to transform this into a linear form. I am not sure if the Charnes-Cooper transformation can be applied here?

Answer 1

One major issue is that your problem is nonconvex since you are maximizing a function that is not concave, i.e., $\max|z|^2$ or equivalently, $\max|z|$. If $z$ was a real number, you could perhaps pass the hurdle by solving $\max z$ and $\min z$ separately, but this phase/angle-enumeration trick is not possible in general for complex valued $z$. Unless the problem has special structure hidden in constraints or coefficients, this nonconvexity destroys all hope of direct reformulations to a convex optimization standard form, such as LP and SOCP.

A much stronger proof such as NP-hardness would nevertheless be required to rule out indirect reformulations to convex optimization, also known as hidden convexity, which reframe the problem in a vastly different set of variables (e.g., nonlinear substitution). The Charnes-Cooper transformation is an example of this technique, but works on real-valued LP's with a single rational term (linear-over-linear) as the objective function. Your problem is complex-valued and has a sum of rational terms in the objective and so does not apply.

Finally, lets look at the hope for generalizing the Charnes-Cooper transformation. Hence, we would be replacing all variables $x$ by $y/t$ to homogenize the problem (thereby extending the feasible set to a cone), and renormalize from $t=1$ (the original problem) to some other set of normalization constraints with the following properties

1. The new normalization preserves a bijective mapping to the original feasible set so all points can be mapped from $(y,t)$ to $x$, and no solutions of $x$ are missed.

2. The new normalization allows us to simplify the objective function.

I have not been able to find such normalization for your problem, and doubt that any exists. My intuition tells me that this trick would require the problem to be quasi-convex, which it is not in your case, since you are maximizing a function that is not quasi-concave.

Answer 2

You can certainly apply the Charnes-Cooper transformation to each summand, turning your objective function into the square of a linear function of the new variables. The problem then becomes that you are maximizing rather than minimizing a convex quadratic function.