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?

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I think there is a mistake somewhere. The maximum of this function cannot be 2. $\endgroup$
    – Filburt
    Oct 25, 2017 at 19:48
  • $\begingroup$ Maybe. Did you notice the function does not depend on x21 and on y21? $\endgroup$
    – yohbs
    Oct 26, 2017 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, 2017 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, 2017 at 15:33

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.