Does anyone have the idea to solve the global multivariate minimization problem as below?

$$\text{minimizes}\quad (x_1x_2x_3+x_1x_4x_5+x_1x_6x_7+x_2x_4x_6+x_2x_5x_7+x_3x_4x_7)-(x_1+x_2+x_4+x_7) \\ \text{subject to}\quad 1\leq x_i\leq N, \forall 1\leq i \leq 7, \text{ and }\prod_{i=1}^7 x_i=N$$

where $N>1$ is a constant.

As far as I know that the global minimizer should be $$ (x_1,x_2,x_3,x_4,x_5,x_6,x_7)=(1,1,N^{1/3},1,N^{1/3},N^{1/3},1).$$

However, I don't have any clue to prove this claim, it seems that the function is somehow symmetric, but not totally symmetric for any variables $x_i$.

  • $\begingroup$ Interesting problem. Have you considered to use KKT conditions? $\endgroup$ – Karel Macek Jul 24 '15 at 10:12
  • $\begingroup$ @KarelMacek KKT is possible, but will be very boring solution I suspect. $\endgroup$ – A.Γ. Jul 24 '15 at 10:29
  • $\begingroup$ Yes, KKT might be a way to do it, however, there is no symmetric property included... $\endgroup$ – Iamstuck Jul 24 '15 at 11:39

I don't see how to prove that the global minimum respects the problem's symmetry, but if it does, it can be determined as follows. Write the first term as


to exhibit its symmetry: For each pairing of $x_1$, $x_2$, $x_4$ and $x_7$, the sum of the products of the pairs is multiplied by one of $x_3$, $x_5$ and $x_6$. Thus, the variables within each of these two groups are equivalent and must be equal in a symmetric solution. Denote their common values by $a$ and $b$, respectively; then we want to minimize $6a^2b-4a$ subject to $a^4b^3=N$. Solving the constraint for $b$ and substituting into the objective function yields $6a^2N^{1/3}a^{-4/3}-4a$, or $6a^{2/3}N^{1/3}-4a$. Then setting the derivative with respect to $a$ to zero gives $4a^{-1/3}N^{1/3}-4=0$, with solution $a=N$. Then from the constraint $b=1/N$, which is inadmissible. Thus there is no stationary point in the interior of the admissible region, and the minimum is attained at one of the boundary points. Since the derivative of the objective function is positive for $a\lt N$, the minimum is attained at the lower boundary point, $a=1$. Then $b=N^{1/3}$ follows from the constraint.

  • $\begingroup$ Thanks for your comment, indeed, if we can have a lemma like: If the minimizer (local or global) of this function is always like this form: $x_1=x_2=x_4=x_7$, and $x_3=x_5=x_6$, then we can proceed the argument as you commented, however, I can not find a way to argue this property. $\endgroup$ – Iamstuck Jul 24 '15 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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