What is going on with this constrained optimization?

Question

I'd like to figure out what is going on when trying to maximize a function (below $a_i$ are real numbers)

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

When we have 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;$

---

So my gradients

$\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);$

$\nabla h_2 = (2a_1,2a_2,\ldots , 2a_n);$

Kuhn-Tucker should provide necessary conditions in this case which is I guess pretty much the same as the method of Lagrange multipliers:

$$\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-1} + a_1 = \lambda_1 + 2\lambda_2 a_n; \end{cases}$$

In a matrix form this is $$\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} $$

How should I proceed?

Answer 1

Consider what happens for $n=2$ and $n=3$.

$n=2$: Only two points satisfy the constraints, $(\frac{1}{\sqrt{2}}, -\frac{1}{\sqrt{2}})$ and $(-\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}})$, and $F$ takes the same value on these two points.

$n=3$: The constraints describe a circle of radius 1 contained in the plane perpendicular to the vector $(1,1,1)$. You have

$2F(a_1,a_2,a_3) = (a_1+a_2+a_3)^2-(a_1^2+a_2^2+a_3^2)=-1$,

for $(a_1,a_2,a_3)$ a vector on this circle. The function $F$ is again constant on the set described by the constraints.

EDIT: Ok, the general case. Note that $F$ is a quadratic form,

$F(a_1,\ldots,a_n) = \left\langle\left(\begin{array}{c} a_1 \\ a_2 \\ a_3 \\ \vdots \\ a_n \end{array}\right),\left( \begin{array}{ccccc} 0 & \frac{1}{2} & 0 & \cdots & \frac{1}{2}\\ \frac{1}{2} & 0 & \frac{1}{2} & \cdots & 0 \\ 0 & \frac{1}{2} & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & & \vdots \\ \frac{1}{2} & 0 & 0 & \cdots \end{array}\right) \left(\begin{array}{c} a_1 \\ a_2 \\ a_3 \\ \vdots \\ a_n \end{array}\right)\right\rangle$

For $n\ge 3$, the biggest eigenvalue of the matrix of this quadratic form is $\lambda_1=1$ (it is a stochastic matrix), with eigenvector $v_1=(1,1,\cdots,1)$. Your constraints mean that you want to maximise this quadratic form on the intersection of the unit sphere with the hyperplane perpendicular to $v_1$. I.e., you are looking for its second biggest eigenvalue.

For $n=3$ that is $-\frac{1}{2}$, as we already knew.

For $n=4$, the eigenvalues are $\lambda_1=1$, $\lambda_2=\lambda_3=0$, $\lambda_4=-1$. So the maximum you are looking for is $0$, it is attained on a circle. The minimum is $-1$, it is attained in two antipodal points.

For bigger $n$ you now have to do a little bit more linear algebra. I think the eigenvalues of these matrices must be known.

EDIT: Let $v_2,\ldots,v_n$ be an orthonormal basis of the subspace perpendicular to $v_1=(1,\cdots,1)$ consisting of eigenvectors of the matrix of the quadratic form $F$. Then we have

$F(a_1,\ldots,a_n)=\sum_{i=2}^n \lambda_i x_i^2$,

if $(a_1,\ldots,a_n)=\sum_{i=2}^n x_i v_i\in \{v_1\}^\perp$. If $(a_1,\ldots,a_n)$ is furthermore a unit vector, then we have $\sum_{i=2}^n x_i^2=1$, and $F(a_1,\cdots,a_n)$ is a weighted average of the eigenvalues $\lambda_2,\ldots,\lambda_n$.

Answer 2

Well, on adding up the n equations you have, you get $$2\sum_{i=1}^{n}a_i = n\lambda_1 + 2\lambda_2\sum_{i=1}^{n}a_i$$ which gives, $\lambda_1 = 0$ as $\sum_{i=1}^{n}a_i=0$.

So now you need to find the nullspace of the matrix, which should hopefully be easier?