# Best way to maximize this multivariable function

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}] ==
const1, {x11, x12, x21, x22, x31, x32, y11, y12, y21, y22,
y31, y32}] +
const2, {x11, x12, x21, x22, x31, x32, y11, y12, y21, y22,
y31, y32}] +
const3, {x11, x12, x21, x22, x31, x32, y11, y12, y21, y22,
y31, y32}] +
const4, {x11, x12, x21, x22, x31, x32, y11, y12, y21, y22,
y31, y32}] +
const5, {x11, x12, x21, x22, x31, x32, y11, y12, y21, y22,
y31, y32}] +
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?

• Is there some geometric background for this? – Henrik Schumacher Oct 25 '17 at 19:02
• 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$. – Filburt Oct 25 '17 at 19:06
• 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 – yohbs Oct 25 '17 at 19:34
• @yohbs So will NMaximize always find a global maximum? It would be awesome – Filburt Oct 25 '17 at 19:44
• No, that's not guaranteed, so you need to play with the method and method settings. – J. M.'s ennui Oct 26 '17 at 12:29

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.

• I think there is a mistake somewhere. The maximum of this function cannot be 2. – Filburt Oct 25 '17 at 19:48
• Maybe. Did you notice the function does not depend on x21 and on y21? – yohbs Oct 26 '17 at 0:10
• 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. – Filburt Oct 26 '17 at 1:17
• 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]. – Akku14 Nov 25 '17 at 15:33