Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$).
share|improve this question
    
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
1  
@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 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.

share|improve this answer
    
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
1  
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

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

share|improve this answer
    
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
1  
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

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)

share|improve this answer
    
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.