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

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$).
-
In no particular order: take the discrete Fourier transform; read the faq; ask on math.stackexchange.com –  Yoav Kallus Apr 23 '13 at 17:12
The Kuhn-Tucker conditions also include the complementary slackness conditions and the constraints. These are omitted by you. –  Mark Apr 23 '13 at 17:40
@Yoav Kallus: Can you kindly explain your suggestion concerning the discrete Fourier transform? –  Mark Apr 23 '13 at 18:36
@Mark: Your matrix is circulant. The DFT diagonalizes circulant matrices. –  Steve Huntsman Apr 23 '13 at 19:01
@Steve Huntsman: The DFT is applicable only to numerical matrices. The above one is not such matrix. –  Mark Apr 23 '13 at 19:31

## 3 Answers

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)

-
The second largest eigenvector is doubly degenerate, so you actually pick an eigenvector from a 2d space, not "the eigenvector". –  Yoav Kallus Apr 24 '13 at 0:24
yes, i know that it is not "the" :-) --- (the second largest eigenvalue occurs twice) –  Suvrit Apr 24 '13 at 1:05
Is it possible to solve problem 8 from Mathematical Trivium by V. Arnold "What are the numbers of the maximums, minimums, and saddle points of the function $x^4+y^4+z^4+u^4+t^4$ on the surface $\{x+y+z+u+t=0,x^2+y^2+z^2+u^2+t^2=1,x^3+y^3+z^3+u^3+t^3=c\}$, where $c$ is a real parameter?" in this way? –  Mark Apr 24 '13 at 4:09
@Mark: maybe, though here I think first it'll be good to see how these constraints can be combined to yield a simpler problem---the cubic constraint is the troublesome one...) –  Suvrit Apr 24 '13 at 5:24

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

-
The DFT is applicable only to numerical matrices. The above one is not such matrix –  Mark Apr 23 '13 at 19:32
I have no idea what your objection means. –  Yoav Kallus Apr 23 '13 at 20:13
I mean that the value of $\lambda_2$ is not known. We know only $\lambda_1 = 0$. –  Mark Apr 23 '13 at 20:22
Why did you write $\exp(2πiq)$ in your $F$? If q is integer, this equals one –  Mark Apr 23 '13 at 20:35
Yeah, that was a typo. –  Yoav Kallus Apr 23 '13 at 20:52

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.

-
In the case n=4 I obtain $F=0$ for $a_1=- \sqrt{ \frac{1-2a^2}{2} }, a_2=a, a_3=\sqrt{ \frac{1-2a^2}{2} }, a_4=-a$ and $a \in [-\sqrt{2}/2, \sqrt{2}/2]$, applying the PolynomialSystem command of Maple. –  Mark Apr 23 '13 at 18:29
Maple produces $F=0.866026654668001$ for $a_1 = .256581438083553, a_2 = .380978783536669$, $a_3 = .403290730625114, a_4 = .317540738896204, a_5 = .146705131597625$, $a_6 = -0.0634388318348049, a_7 = -.256584963464397$, $a_8 = -.380976908754637, a_9 = -.403290979782187$, $a_{10} = -.317537774924634, a_{11} = -.146705878274621$, $a_{12} = 0.0634385149651301$ in the case n=12. –  Mark Apr 23 '13 at 19:41
That solution is a sine wave. That suggests the general solution is of the form $a_i=sin(2 \pi i / n)$. –  Carl Feynman Apr 23 '13 at 19:56
@Carl Feynman: What are the amplitude and period in your suggestion? What is the optimal value of the objective function? As far as I know it, the problem under consideration is related to one of the problems from Mathematical Trivium by V. Arnold. –  Mark Apr 23 '13 at 20:05
Whoops, I see that my comment above is incorrect; Mr Kallus didn't give the amplitude either. –  Carl Feynman Apr 23 '13 at 20:23