0
$\begingroup$

I want to maximize the function $f:\Bbb R^{12}\to\Bbb R$ given by $$\begin{align*} &f(x_1^{(1)},x_1^{(2)},x_2^{(1)},x_2^{(2)},x_3^{(1)},x_3^{(2)},y_1^{(1)},x_1^{(2)},y_2^{(1)},y_2^{(2)},y_3^{(1)},y_3^{(2)})=\\&\frac{1}{2}(-x_1^{(1)} y_1^{(1)} - x_1^{(2)} y_1^{(2)}) + \frac{1}{2} (-x_3^{(1)} y_1^{(1)} - x_3^{(2)} y1^{(2)})+ \\&\frac{1}{2} (-x_1^{(1)} y_3^{(1)} - x_1^{(2)} y_3^{(2)}) + \frac{1}{2} (x_3^{(1)} y_3^{(1)} + x_3^{(2)} y_3^{(2)}) \end{align*}$$ with the constraint $$(x_i^{(1)},x_i^{(2)}),(y_i^{(1)},y_i^{(2)})\in\Bbb S^1, i=1,2,3.$$

(notation: $\Bbb S^1=\{(x,y)\in\Bbb R^2; x^2+y^2=1\}$).

What is the best way to do that?

My attempt: I thought Lagrange Multipliers would be the best way to do it, but before the implementation, I tried to Maximize. Don't works for this, the program runs forever. For the Lagrange Multiplies approach, my code was

ClearAll["Global`*"]
f[x11_, x12_, x21_, x22_, x31_, x32_, y11_, y12_, y21_, y22_, y31_, 
  y32_] := 1/2*(-x11 y11 - x12 y12) + 1/2*(-x31 y11 - x32 y12) + 
  1/2*(-x11 y31 - x12 y32) + 1/2*(x31 y31 + x32 y32)
const1 = -1 + x11^2 + x12^2;
const2 = -1 + x21^2 + x22^2;
const3 = -1 + x31^2 + x32^2;
const4 = -1 + y11^2 + y12^2;
const5 = -1 + y21^2 + y22^2;
const6 = -1 + y31^2 + y32^2;
sols = Solve[{const1 == 0, const2 == 0, const3 == 0, const4 == 0, 
    const5 == 0, const6 == 0, 
    Grad[f[x11, x12, x21, x22, x31, x32, y11, y12, y21, y22, y31, 
       y32], {x11, x12, x21, x22, x31, x32, y11, y12, y21, y22, y31, 
       y32}] == 
     lambda1 Grad[
        const1, {x11, x12, x21, x22, x31, x32, y11, y12, y21, y22, 
         y31, y32}] + 
      lambda2 Grad[
        const2, {x11, x12, x21, x22, x31, x32, y11, y12, y21, y22, 
         y31, y32}] + 
      lambda3 Grad[
        const3, {x11, x12, x21, x22, x31, x32, y11, y12, y21, y22, 
         y31, y32}] + 
      lambda4 Grad[
        const4, {x11, x12, x21, x22, x31, x32, y11, y12, y21, y22, 
         y31, y32}] + 
      lambda5 Grad[
        const5, {x11, x12, x21, x22, x31, x32, y11, y12, y21, y22, 
         y31, y32}] + 
      lambda6 Grad[
        const6, {x11, x12, x21, x22, x31, x32, y11, y12, y21, y22, 
         y31, y32}]}];
values = f[x11, x12, x21, x22, x31, x32, y11, y12, y21, y22, y31, y32] /. sols
Max[values]

There is a problem again. It seems that there are a lot of critical points. Max[values] returned some values in function of $y_3^{(1)}$. What can I do now? Maximize each expression in function of $y_3^{(1)}$ again? I only want the maximum value attained by $f$ in $\Bbb S^1\times\cdots\times\Bbb S^1$, don't care about the points where the maximum is attained. I don't know if it is $\sqrt{2}$ or not.

The last thing I tried was NMaximize. It returns almost immediately the value $\sqrt{2}$. Is this maximum global of local? I will work with lots of functions like the one above. Will NMaximize always gives-me global maxima for this kind of functions?

$\endgroup$
  • $\begingroup$ Is there some geometric background for this? $\endgroup$ – Henrik Schumacher Oct 25 '17 at 19:02
  • $\begingroup$ No much. These functions are obtained through the dot product for vectors, like $f=\sum_{i,j}a_{i,j}\langle x_i,y_j \rangle$, with $x_i, y_i\in\Bbb S^1$. $\endgroup$ – Filburt Oct 25 '17 at 19:06
  • $\begingroup$ You can try parametrizing your constraint, i.e. writing $$x_i^{(1)}=\cos(\theta_i),\quad x_i^{(2)}=\sin(\theta_i)$$ this reduces the dimensionality from 12 to 6, which is a lot. You pay by not having a quadratic function to minimize. My intuition is that that either with or without this trick the minimization should be simple since it's a convex function over a compact domain and out-of-the-box methods should do just fine $\endgroup$ – yohbs Oct 25 '17 at 19:34
  • $\begingroup$ @yohbs So will NMaximize always find a global maximum? It would be awesome $\endgroup$ – Filburt Oct 25 '17 at 19:44
  • $\begingroup$ No, that's not guaranteed, so you need to play with the method and method settings. $\endgroup$ – J. M. is in limbo Oct 26 '17 at 12:29
1
$\begingroup$

The function has a 4-dimensional manifold of maximizers. To see this, do the change of variables as I suggested in the comments:

f2 = FullSimplify[1/2*(-x11 y11 - x12 y12) + 1/2*(-x31 y11 - x32 y12) + 
 1/2*(-x11 y31 - x12 y32) + 1/2*(x31 y31 + x32 y32)/. {x11 -> Cos[q1], x12 -> Sin[q1], x21 -> Cos[q2], 
   x22 -> Sin[q2], x31 -> Cos[q3], x32 -> Sin[q3],
   y11 -> Cos[q4], y12 -> Sin[q4], y21 -> Cos[q5], y22 -> Sin[q5], 
   y31 -> Cos[q6], y32 -> Sin[q6]}]

and you'll find the much simpler function:

1/2 (-Cos[q1 - q4] - Cos[q3 - q4] - Cos[q1 - q6] + Cos[q3 - q6])

Since the maximal value of each cosine is clearly 1, the maximal value of the function is 2, and is obtained whenever q1-q4==Pi, q3-q4==Pi and so on.

$\endgroup$
  • $\begingroup$ I think there is a mistake somewhere. The maximum of this function cannot be 2. $\endgroup$ – Filburt Oct 25 '17 at 19:48
  • $\begingroup$ Maybe. Did you notice the function does not depend on x21 and on y21? $\endgroup$ – yohbs Oct 26 '17 at 0:10
  • $\begingroup$ is this a problem? The function of the OP uses only 8 variables from the 12 available. Anyway, the code should handle any other similar function. $\endgroup$ – Filburt Oct 26 '17 at 1:17
  • $\begingroup$ NMaximize[{1/ 2 (-Cos[q1 - q4] - Cos[q3 - q4] - Cos[q1 - q6] + Cos[q3 - q6]), Thread[0 <= {q1, q3, q4, q6} <= 2 Pi]}, {q1, q3, q4, q6}]also gives Sqrt[2]. $\endgroup$ – Akku14 Nov 25 '17 at 15:33

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.