2
$\begingroup$

Consider the following problem \begin{equation} \begin{aligned} \min_{x,y,z} \quad & \sum_{i=0}^1 \sum_{j=0}^1 \sum_{k=0}^1 a_{ijk} \cdot f_{ijk}(x,y,z), \\ \textrm{s.t.} \quad & 0.1 \leq x \leq 1 \\ \quad & 0.1 \leq y \leq 1 \\ \quad & 0.1 \leq z \leq 1 \\ \end{aligned} \tag{1} \end{equation} where $a_{ijk} \geq 0$ for $(i,j,k) \in \{0,1\}^3$ and $$ f_{ijk}(x,y,z) = \begin{cases} (1-x) \cdot (1-y) \cdot (1-z), &i = 0, j = 0, k = 0 \\ (1-x) \cdot (1-y) \cdot z, &i = 0, j = 0, k = 1 \\ (1-x) \cdot y \cdot (1-z), &i = 0, j = 1, k = 0 \\ (1-x) \cdot y \cdot z, &i = 0, j = 1, k = 1 \\ x \cdot (1-y) \cdot (1-z), &i = 1, j = 0, k = 0 \\ x \cdot (1-y) \cdot z, &i = 1, j = 0, k = 1 \\ x \cdot y \cdot (1-z), &i = 1, j = 1, k = 0 \\ x \cdot y \cdot z, &i = 1, j = 1, k = 1 \end{cases} $$ I initially tried to solve the problem in $(1)$ as a geometric program using a change of variables, but the new feasible set is no longer convex. It is likely that $(1)$ can be solved as a signomial program, but the challenge here is that $(1)$ is in fact a small-scale version of a larger problem.

That is, there are 3 decision variables in $(1)$ and 8 summands. In the more general case, when there are $M$ decision variables, there will be $2^M$ summands. I'm interested in the case when $M > 100$, and so solving the signomial program when the objective function has more than $2^{100}$ terms is likely to be difficult. Therefore, I'm considering the following recursive approach instead, but I'm not sure if it is solvable and would appreciate any feedback.

Using some algebra, we can re-arrange the objective function in $(1)$ so that the problem becomes \begin{equation} \begin{aligned} \min_{x,y,z} \quad & x \cdot g_2(y,z) + y \cdot g_1(z) + z \cdot c, \\ \textrm{s.t.} \quad & 0.1 \leq x \leq 1 \\ \quad & 0.1 \leq y \leq 1 \\ \quad & 0.1 \leq z \leq 1 \\ \end{aligned} \tag{2} \end{equation} where $g_2$ is a quadratic function of $(y,z)$, $g_1$ is a linear function of $z$, and $c \in \mathbb R$. Because $\min_{x,y,z} [\cdot]$ is equivalent to $\min_z [\min_y [\min_x [\cdot]]]$, then the problem in $(2)$ can be re-written as a sequence of 3 sub-problems: \begin{equation} \begin{aligned} \min_{z} \quad & \left\{\begin{aligned}[t] \min_{y} \quad & \left\{\begin{aligned}[t] \min_{x} \quad & x \cdot g_2(y,z), \\ \textrm{s.t.} \quad & 0.1 \leq x \leq 1 \end{aligned}\right\} + y \cdot g_1(z), \\ \textrm{s.t.} \quad & 0.1 \leq y \leq 1 \end{aligned}\right\} + z \cdot c, \\ \textrm{s.t.} \quad & 0.1 \leq z \leq 1 \end{aligned} \tag{3} \end{equation} At this point, I'm not sure how $(3)$ can be solved, since the solution to the inner-most problem \begin{equation} \begin{aligned}[t] \min_{x} \quad & x \cdot g_2(y,z), \\ \textrm{s.t.} \quad & 0.1 \leq x \leq 1 \end{aligned} \end{equation} will either be $x = 0.1$ or $x = 1$ depending on the sign of $g_2(y,z)$. However, the sign of $g_2(y,z)$ can only be determined by choosing $y$ and $z$, but choosing $y$ and $z$ is part of the outer problems. This is similar to a chicken-or-egg problem, and I'm not sure how to proceed.

$\endgroup$
9
  • $\begingroup$ As you actually have lots of multiplication of the variables, using any global solver can lead to the linearization of these terms and finally slow convergence. It also would be worth trying the Lagrangian method. Do you try that? $\endgroup$
    – A.Omidi
    Dec 11, 2023 at 7:39
  • $\begingroup$ @A.Omidi could you elaborate on the "global solver" (including linearization) part and the "Lagrangian method" part in an answer? $\endgroup$
    – mhdadk
    Dec 11, 2023 at 7:43
  • $\begingroup$ Some global solvers can turn out the term like $(x.y.z)$ into two bilinear terms internally. One $(x.w)$, and the second $(w=y.z)$. Then linearizing these bilinear terms by RLT. (E.g, McCormick envelope). Also, for the LR, I do not have more experience with that, specifically, when the problem is of the form NLP/MINLP, but this link might be a good starting point. $\endgroup$
    – A.Omidi
    Dec 11, 2023 at 8:06
  • 1
    $\begingroup$ @A.Omidi thanks for the explanation. What does "RLT" stand for? $\endgroup$
    – mhdadk
    Dec 11, 2023 at 8:08
  • 1
    $\begingroup$ @A.Omidi thanks a lot for your help. If you would like to compile this information into an answer, I would be happy to accept it. $\endgroup$
    – mhdadk
    Dec 11, 2023 at 8:19

2 Answers 2

1
$\begingroup$

As you noticed, the optimal $x$ must be on the bound. By symmetry, $y$ and $z$ must also be on the bound.

We can recursively evaluate the objective of all $2^M$ vertices, and then choose the optimal one.

Let's take $M=3$ as an example. Given $a_{ijk}$, fix $k=0$ and with $a_{ij0}$, we have an $M=2$ subproblem, so we can calculate the objective values on 4 vertices $f^0_{x,y}$. Similarly, we can fix $k=1$ and calculate another 4 values $f^1_{x,y}$. Then we have $$ f_{x,y,z} = f^0_{x,y}(1-z)+f^1_{x,y}z $$ for all vertices $(x,y,z)$.

The time complexity is exponential, but since the data size is exponential, the solution is not bad I think.

$\endgroup$
6
  • $\begingroup$ Very interesting observation. I'm not sure what you mean by "By symmetry, $y$ and $z$ must also be on the bound". What does "symmetry" mean here? $\endgroup$
    – mhdadk
    Dec 12, 2023 at 10:58
  • $\begingroup$ @mhdadk $\min_{x,y,z}[\cdot]$ is equivalent to $\min_z \min_y \min_x$, as well as $\min_x \min_y \min_z$ and $\min_x \min_z \min_y$. $\endgroup$
    – xd y
    Dec 13, 2023 at 1:42
  • $\begingroup$ Thank you! This is a good catch. I guess what you mean then is that we can repeat my factorizations above but have on the inside a linear function of $y$ instead of a linear function of $x$, and then put the $\min_y$ on the inside instead of the $\min_x$. $\endgroup$
    – mhdadk
    Dec 13, 2023 at 2:02
  • $\begingroup$ Just one more question: Is your computation for $M=3$ just the same as evaluating the objective function at all $8$ vertices? If not, how is your approach more efficient? $\endgroup$
    – mhdadk
    Dec 13, 2023 at 2:04
  • 1
    $\begingroup$ It reuses intermediate results when computing different vertices. For example, it doesn't have to calculate $f^0_{1, 1}$ twice when calculating $f_{1,1,1}$ and $f_{1,1,0}$, but if you directly calculate them, $f^0_{1, 1}$ seems to be calculated twice. But I don't know if it is a large advantage for time complexity because both of them are exponential. ($O(2^n)$ and $O(2^{2n})$ maybe?) I have tested that optimal solution is always a vertex, but I didn't compare the two evaluating approaches. $\endgroup$
    – xd y
    Dec 13, 2023 at 2:37
2
$\begingroup$

As you actually have lots of multiplication of the variables, using any global solver can lead to the linearization of these terms and finally slow convergence. As an alternative, it would be worth trying the Lagrangian method. For that, this link might be a good starting point. (Noted that it might lead to a sub-optimal solution).

However, some global solvers can turn out the term like $(x.y.z)$ into two bilinear terms internally. One $(x.w)$, and the second $(w=y.z)$. Then linearizing these bilinear terms by RLT or Reformulation Linearization Technique. (E.g, McCormick envelope).

As far as I know, many of the global NLP/MINLP/QCP/MIQCP solvers, support these kinds of linearization.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.