# Linear approximation of fraction for a maximization problem

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?

• Are the constraints linear? Commented May 6 at 10:42

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.

• let's ignore the fact that I am maximising a quadratic function. I need to ask you what is the best transformation according to you? I think there are different ways to transform this objective. Commented May 17 at 8:40

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.

• can this or.stackexchange.com/questions/8957/… work in my case formulation as a socp ? Commented May 6 at 5:03
• Yes, I have faced this issue, but I am not sure what to do. What if I apply Charnes Copper transformation and then try to maximise it by the introduction of auxiliary variable $max_{x,y,t } \mathbf{t}^2; t = \mathbf{a}\mathbf{y}; \mathbf{y} = 1/\mathbf{b} + \mathbf{x}$ Commented May 6 at 8:19
• The use of the auxiliary variable does not change the fact that you are maximizing a convex quadratic function. I do not see a way to convert this to a SOCP.
– prubin
Commented May 6 at 15:35
• can you show how transformation can done as this is not a standard fraction program. Commented May 7 at 0:21
• My answer applied to the original question (real-valued parameters).
– prubin
Commented May 7 at 3:08