1
$\begingroup$

I have an optimization problem with bilinear terms in the objective function and constraints, formulated as below:

$$ \begin{array}{ll} \underset {\alpha, \beta, x_1, x_2, \dots, x_N, \\y, z_1, z_2, \dots, z_m} {\text{minimize}} & C_1 x_1 y + C_2 x_2 y + C_3 x_3 y \\ \text{subject to} & z_1 + (A-1) x_1 y + A x_2 y + \dots + A x_N y \leq B \\ & z_2 + A x_1 y + (A-1) x_2 y + \dots + A x_N y \leq B \\ & z_m + A x_1 y + A x_2 y + \dots + (A-1) x_N y \leq B \\ & x_2 + \alpha < D \\ & y + \beta < F\end{array} $$

where $A = \frac1N \in (0,1)$. Is there any way to reformulate the above into a semidefinite program (SDP) or other convex problem, or am I restricted to a non-linear optimization in this case?

$\endgroup$
2
  • $\begingroup$ Where is $z$??? $\endgroup$ Mar 5, 2023 at 17:59
  • $\begingroup$ Why are some integers / reals uppercase and others lowercase? $\endgroup$ Mar 5, 2023 at 18:01

1 Answer 1

4
$\begingroup$

It’s just linear with $u_i=x_iy \ \forall i$.

Update: OP updated their question to mention that $x_i$ and $y$ are separately involved in additional linear constraints:

\begin{array}{ll} \underset {\alpha, \beta, x_1, x_2, \dots, x_N, \\y, z_1, z_2, \dots, z_m} {\text{minimize}} & C_1 x_1 y + C_2 x_2 y + C_3 x_3 y \\ \text{subject to} & z_1 + (A-1) x_1 y + A x_2 y + \dots + A x_N y \leq B \\ & z_2 + A x_1 y + (A-1) x_2 y + \dots + A x_N y \leq B \\ & z_m + A x_1 y + A x_2 y + \dots + (A-1) x_N y \leq B \\ & x_2 + \alpha < D \\ & y + \beta < F\end{array}

However, using the same idea, this can still be reformulated as a linear program. Well, actually two linear programs.

Indeed, let $u_i=x_iy \ \forall i$, $\gamma = \alpha y$, then the above problem becomes \begin{array}{ll} \underset {\gamma, \beta, u_1, u_2, \dots, u_N, \\y, z_1, z_2, \dots, z_m} {\text{minimize}} & C_1 u_1 + C_2 u_2 + C_3 u_3 \\ \text{subject to} & z_1 + (A-1) u_1 + A u_2 + \dots + A u_N \leq B \\ & z_2 + A x_1 y + (A-1) u_2 + \dots + A u_N \leq B \\ & z_m + A u_1 + A u_2 + \dots + (A-1) u_N \leq B \\ & u_2 + \gamma < Dy \mbox{ if } y > 0 \mbox{ and } u_2 + \gamma > Dy \mbox{ if } y < 0\\ & y + \beta < F.\end{array}

If suffices to solve the two LPs with the corresponding additional constraint ($y > 0$ or $y < 0$) and compare the results (together with the case $y=0$ for which the objective is $0$).

$\endgroup$
4
  • $\begingroup$ Apologies I should have mentioned that $x_i$ and $y$ are separately involved in other linear constraints in the formulation. I have edited the problem statement above. $\endgroup$ Oct 21, 2020 at 0:14
  • $\begingroup$ @Fenderman2014 Same answer! $\endgroup$
    – f10w
    Oct 21, 2020 at 0:20
  • $\begingroup$ @f1ow could you elaborate on how you can linearize the problem even if $x_i$ and $y$ are separately involved in linear constraints? $\endgroup$
    – saper0
    Feb 18 at 19:44
  • 1
    $\begingroup$ @saper0 Please see the update. $\endgroup$
    – f10w
    Feb 19 at 11:29

You must log in to answer this question.

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