Constraint optimization problem for any dimensionality $n>1$.

Question

I am going to post a particular example for the sake of clarity.

One needs to maximize a real function

$F = a_1a_2 + a_2a_3 + \cdots + a_{n - > 1}a_n + a_na_1;$

with active constraints

$h_1 = a_1 + a_2 + \cdots + a_n = 0;$

$h_2 = a_1^2 + a_2^2 + \cdots +a_n^2 = > 1;$

The gradients in question

$\nabla F = (a_2+a_n,a_3+a_1, \ldots , a_{n-2}+a_n,a_{n-1}+a_1);$

$\nabla h_1 = (1, 1, \ldots ,1, 1);$

$\nabla h_2 = (2a_1,2a_2,\ldots , 2a_{n-1}, 2a_n);$

Because of Kuhn–Tucker conditions it is reasonable to write $\nabla F$ in terms of $\nabla h_1$ and $\nabla h_1$

$$\begin{cases} a_2+a_n = \lambda_1 + 2\lambda_2a_1; \\\ a_3+a_1 = \lambda_1 + 2\lambda_2a_2; \\\ a_4+a_2 = \lambda_1 + 2\lambda_2a_3; \\\ \ldots \\\ a_{n-2} + a_n = \lambda_1 + 2\lambda_2 a_{n-1}; \\\ a_{n-1} + a_1 = \lambda_1 + 2\lambda_2 a_n; \end{cases}$$

$$\begin{pmatrix} 2\lambda_2 & -1 & 0 & 0 & \ldots & 0 & -1 \\\ -1 & 2\lambda_2 & -1 & 0 & \ldots & 0 & 0 \\\ 0 & -1 & 2\lambda_2 & -1 & \ldots &0 & 0 \\\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\\ 0 &0 &0 & 0 & \ldots & 2\lambda_2 & -1 \\\ -1 &0 &0 & 0 & \ldots & -1 & 2\lambda_2 \end{pmatrix} \begin{pmatrix} a_1 \\\ a_2 \\\ a_3 \\\ \vdots \\\ a_{n-1} \\\ a_n \end{pmatrix} = - \lambda_1\begin{pmatrix} 1 \\\ 1 \\\ 1 \\\ \vdots \\\ 1 \\\ 1 \end{pmatrix} $$

By adding up all equations it follows that $\lambda_1 = 0$ so it's a matter of nullspaces.

However is this attempt fruitless? I'm getting nowhere, so at this point references to similar problems would also be appreciated.

---

A few remarks:

1. Case $n=2$ is somewhat trivial, for all valid combinations (there are two of them) $F = -1$.
2. Case $n=3$ brings up the same problem since for all valid combinations $F = -1/2$.
3. $F \le 1$ is an exact upper bound (it follows from properties of scalar multiplication and constructing silly yet valid combinations for sufficiently large $n$).

Answer 1

Since you asked so nicely, here we go: Let $a_k = \sum_{q=0}^{n-1}b_q \exp(2\pi i k q/n)$ (where $b_q=b_{n-q}^*$ by realness). Up to normalization factors I have dropped, $F=\sum_{q=0}^{n-1}|b_q|^2\exp(2\pi i q/n)$ and your constraints give $\sum_{q=0}^{n-1} |b_q|^2 = 1$ and $b_0=0$. So it is easy now to see that $F$ is maximum when $b_1=b_{n-1}=\tfrac{1}{\sqrt{2}}$. In real space, $a_k = C \cos(2\pi k/n+\phi)$.

Answer 2

Here's an alternative way of proving (what Yoav already did), but using different notation.

Let us first write the optimization problem in matrix form. First, define \begin{equation*} d = \begin{bmatrix} 0 & 1 & & \cdots &0\\\\ 0 & 0 & 1 & \\\\ \vdots & & \ddots & \\\\ 0 & 0 & \cdots & &1\\\\ 1 & \cdots &&& 0 \end{bmatrix}. \end{equation*}

The optimization problem at hand is \begin{equation*} \max a^Tda\quad \text{s.t.}\ a^T1 = 0, a^Ta=1. \end{equation*} Writing $D=(d+d^T)/2$, we see that $a^Tda = a^TDa$. So we may actually solve the problem \begin{equation*} \max a^TDa\quad \text{s.t.}\ a^T1 = 0, a^Ta=1. \end{equation*} If we pick $a$ to be the eigenvector corresponding to the second largest eigenvalue of $D$, we see that it satisfies $a^T1=0$ and $a^Ta=1$ (the first largest does not sum to zero). (to see the $a^T1=0$ part is where we use the DFT insight used by Yoav)

Answer 3

I tried a mathematical experiment, using the DirectSearch package http://www.maplesoft.com/applications/view.aspx?SID=101333 , and obtained $\max f = 0.809126470893692 $ for $a_1 = .243175515810934, a_2 = .417367431111117, a_3 = .432125841032896,$ $ a_4 = .281815795280440, a_5= 0.239770895080612e-1, a_6 = -.243248539429584,$ $ a_7 = -.417366236874912, a_8 = -.432123102835062, a_9 = -.281798611220396,$ $ a_{10} = -0.0239247832264742$ in the case $n=10$. The optimal solution is not unique.