2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ So this definitely works when all eigenvalues are different (because we can construct a basis out of corresponding eigenvectors) but how can we be sure that this will always work even when some eigenvalues are the same? $\endgroup$ – Ranas Apr 23 '13 at 16:36

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.