# Optimization problem with a bilinear constraint

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?

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

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$$).

• 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. Oct 21, 2020 at 0:14
• @f1ow could you elaborate on how you can linearize the problem even if $x_i$ and $y$ are separately involved in linear constraints? Feb 18 at 19:44