Transformation of Optimization Problem (LP/QP/MIP)?

Question

I have an optimization problem in the form

$\min_{x\geq 0} \sum_{i=1}^N x_i^2$

s.t

(1) $\sum_{i=1}^N a_i/x_i = q$

(2) $\sum_{i \in S_j}^N a_i/x_i \leq r_j$, for all $j = 1,2,\dots, J$

All parameters $(a_1,\dots,a_N,q,r_1,\dots,r_J)$ are positive.

As a small example the problem is:

$\min_{x\geq 0} x_1^2 + x_2^2 + x_3^2 + x_4^2$

s.t

(1) $a_1/x_1 + a_2/x_2 + a_3/x_3 + a_4/x_4 = q$

(2_1) $a_1/x_1 + a_2/x_2 \leq r_1$

(2_2) $a_2/x_2 + a_3/x_3 \leq r_2$

Question: Is it possible to transform this problem into an LP/QP/SOCP/MILP? Preferably something that can be solved using CPLEX or Gurobi?

Answer 1

Make a variable change $y_i = x_i^{-1}$. You now have a model with linear constraints, but with an objective which is a sum of squared inverses $y_i^{-2}$. To handle these, introduce a new variable $z_i$ with $y_i^{-1} \leq z_i$ which you model as SOCPs using the answer in your other post, and your objective will be a function of $z_i^2$. At that point, everything is standard SOCP-representable.

If you want to be lazy, you can use a modelling language such as YALMIP (disclaimer, developed by me). To get an SOCP and connect to Gurobi/cplex/mosek, you use the convexity-aware cpower operator

sdpvar y1 y2
Model = [y1 >= 0, y2 >= 0, y1 + y2 == 1, y1 + 2*y2 <= .5]
objective = cpower(y1,-2) + cpower(y2,-2);
optimize(Model,objective)
value(y1)^-1
value(y2)^-1