3
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ Your objective function is already convex. $\endgroup$ Commented Jun 11, 2023 at 18:21

3 Answers 3

2
+100
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

If I read your question right, then the following steps of expanding and simplifying should work:

$\sum_{i=1}^{K}y_{i}\left(\frac{x_{i}}{y_{i}}-\frac{X}{Y}\right)^{2}$

$\sum_{i=1}^{K}y_{i}\left(\frac{x_{i}Y-y_{i}X}{y_iY}\right)^{2}$

$\frac{1}{Y^2}\sum_{i=1}^{K}\frac{\left(x_{i}Y-y_{i}X\right)^{2}}{y_i}$

$\frac{1}{Y^2}\sum_{i=1}^{K}\left(\frac{x_{i}^2Y^2}{y_i}-2\frac{x_iYy_iX}{y_i}+\frac{y_i^2X^2}{y_i}\right)$

$\frac{1}{Y^2}\sum_{i=1}^{K}\frac{x_{i}^2Y^2}{y_i}-2\frac{1}{Y^2}\sum_{i=1}^{K}\frac{x_iYy_iX}{y_i}+\frac{1}{Y^2}\sum_{i=1}^{K}\frac{y_i^2X^2}{y_i}$

$\sum_{i=1}^{K}\frac{x_{i}^2}{y_i}-2\frac{X}{Y}\sum_{i=1}^{K}x_i+\frac{X^2}{Y^2}\sum_{i=1}^{K}y_i$

$\sum_{i=1}^{K}\frac{x_{i}^2}{y_i}-2\frac{X}{Y}X+\frac{X^2}{Y^2}Y$

$\sum_{i=1}^{K}\frac{x_{i}^2}{y_i}-2\frac{X^2}{Y}+\frac{X^2}{Y}$

and finally, because adding constants to the objective doesn't change the solution:

$\sum_{i=1}^{K}\frac{x_{i}^2}{y_i}$

$\endgroup$
1
  • $\begingroup$ Thank you very much for your detailed derivations. My main question is mainly concerned with the last term you obtained: a quadratic term over a linear term. How can we transform this term into something that is convex or linear? This term itself can not be modeled on any numerical software. I am grateful for your answer. $\endgroup$
    – SPARSE
    Commented Jun 11, 2023 at 17:18
0
$\begingroup$

Your objective function is already convex. This follows because the Hessian matrix $$\frac2{y^3}\,\begin{bmatrix} y^2&-xy\\-xy&x^2 \end{bmatrix}$$ of the map $\mathbb R\times(0,\infty)\ni(x,y)\mapsto y\Big(\dfrac xy-r\Big)^2$ is positive semidefinite, for any given real $r$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .