I am interested in this non-convex mixed-integer program:
\begin{array}{cl}
\displaystyle\min\_{(x\_{i},y\_{i})\in\mathbb{Z}^{+}\times\mathbb{Z}^{+}}&\displaystyle\sum\_{i=1}^{K}y\_{i}\left(\displaystyle\frac{x\_{i}}{y\_{i}}-\frac{X}{Y}\right)^{2} \\[0.2cm]
\mathrm{s.t.}&\sum\_{i}x\_{i}=X\;(\mathrm{fixed}) \\
&\sum\_{i}y\_{i}=Y\;(\mathrm{fixed}) \\
&x\_{i}\leqslant y\_{i},\quad i=1,2,\ldots,K
\end{array}
subject to the linear constraints shown above. Attempting to simulate this using optimization softwares like $\textsf{cvxpy}$ becomes unfeasible and incompatible, due to the ratio of quadratic over linear term, i.e. $\frac{x\_{i}^{2}}{y\_{i}}$. Most softwares have no platform for such terms, and if they do it becomes unfeasible for large terms $(X,Y)\sim(10^{6},10^{6})$. Thus, my only approach for a proper numerical modeling of this program is to reformulate it either by convexifying the objective function, or by adding envelopes to the objective function so that it becomes easier to model.



> 
> **Question**: How can the objective function be reformulated or convexified for the purpose of better numerical testing?
> 
> 
> 



How to convexify or reformulate this non-convex MIP?
As @ManfredWeis noted, the objective is equivalent to minimizing $\sum\_{i=1}^K \frac{x\_i^2}{y\_i}$. You can reformulate this as a (convex) mixed integer second-order cone programming (MISOCP) problem by introducing a new variable $z\_i$ and minimizing $2\sum\_i z\_i$ subject to
\begin{align}
\sum\_i x\_i &= X \\
\sum\_i y\_i &= Y \\
x\_i &\le y\_i &&\text{for all $i$} \\
2 z\_i y\_i &\ge x\_i^2 &&\text{for all $i$}
\end{align}


The new constraint is a rotated second-order cone.


Note that, even in the original problem, relaxing integrality yields unique optimal solution $(x\_i^\*,y\_i^\*)=(X/K,Y/K)$ for all $i$, with objective value $0$. Because the relaxation is convex, every integer optimal solution satisfies $x\_i \in \{\lfloor x\_i^\* \rfloor, \lceil x\_i^\* \rceil\}$ and $y\_i \in \{\lfloor y\_i^\* \rfloor, \lceil y\_i^\* \rceil\}$ for all $i$.




---


An alternative reformulation introduces binary decision variables $u\_{ij}$ for $i\in\{1,\dots,K\}$ and $j\in \{0,\dots, X\}$ and $v\_{ik}$ for $i\in\{1,\dots,K\}$ and $k\in \{1,\dots, Y\}$. The problem is to minimize the quadratic function
$$\sum\_{i=1}^K \sum\_{j=0}^X \sum\_{k=1}^Y \frac{j^2}{k} u\_{ij} v\_{ik} \tag1\label1$$
subject to linear constraints
\begin{align}
\sum\_i x\_i &= X \\
\sum\_i y\_i &= Y \\
x\_i &\le y\_i &&\text{for all $i$} \\
\sum\_j u\_{ij} &= 1 &&\text{for all $i$} \\
\sum\_j j u\_{ij} &= x\_i &&\text{for all $i$} \\
\sum\_k v\_{ik} &= 1 &&\text{for all $i$} \\
\sum\_k k v\_{ik} &= y\_i &&\text{for all $i$}
\end{align}
You can call an MIQP (or BQP) solver.


Alternatively, you can linearize \eqref{1} by introducing nonnegative variables $w\_{ijk}$ to represent the product $u\_{ij} v\_{ik}$.
You can then minimize $$\sum\_{i=1}^K \sum\_{j=0}^X \sum\_{k=1}^Y \frac{j^2}{k} w\_{ijk} \tag{1p}\label{1'}$$
The usual linearization imposes linear constraints
\begin{align}
w\_{ijk} &\ge u\_{ij} + v\_{ik} - 1 \tag2\label2 \\
w\_{ijk} &\le u\_{ij} \tag3\label3 \\
w\_{ijk} &\le v\_{ik} \tag4\label4
\end{align}
But you can omit \eqref{3} and \eqref{4} because the objective will drive these constraints to be satisfied naturally.


A more compact linearization instead replaces \eqref{2} with
\begin{align}
\sum\_j w\_{ijk} &= v\_{ik} &&\text{for all $i$ and $k$} \\
\sum\_k w\_{ijk} &= u\_{ij} &&\text{for all $i$ and $j$}
\end{align}


It is also worth noting that without the linking constraints $\sum\_i x\_i = X$ and $\sum\_i y\_i = Y$ the problem decomposes into independent problems, one for each $i$. So Dantzig-Wolfe decomposition or Lagrangian relaxation might perform well.


