Find the Minimum of: $\sum_{i=1}^n a_i^2+\sum_{1\leq i<j\leq n}g_{j-i}a_i a_j+\sum_{i=1}^n q_i a_i$

Question

I'm confused with the following problem when doing my research.

Given $g_i,i=1,2,..,n-1$ and $q_i,i=1,2,..,n$, find the minimum of: $$\sum_{i=1}^n a_i^2+\sum_{1\leq i<j\leq n}g_{j-i}a_i a_j+\sum_{i=1}^n q_i a_i$$

subject to $$\sum_{i=1}^{n} a_i=1,a_i \geq 0$$

If necessary, we can assume the sign of $g_i$ and $q_i$(such as $g_i<0,q_i>0$ for all i) and the value of $|g_i|$ and $|q_i|$ can be sufficiently small for all i. Is there a way to find the closed-form solution of $a_1,a_2,...,a_n$ when the target is minimized? Some approximate methods and some solutions with specific $q_i$ and $g_i$ are also of great help. I would be grateful if there is any hint.

Answer 1

*Please see the discussion under the actual question. There, a closed-form solution for the question without nonnegativity restrictions on the $\{a_i\}$ was asked for, which is given here. *

I would go with a Discrete Fourier Transformation. Let a matrix $U$ with $u_{ j k} =\exp (i (j-1) (k-1) 2 \pi / n)$, then $U^\dagger U = n I$ where $I$ is the identity matrix.

The given problem is to minimize, where $a$ and $q$ are vectors and $G$ is a matrix given by the problem definition $$ a^T G a + a^T q $$

Let vectors $b = U a$ and $r = U q$, and the matrix $H = \frac{1}{n} U G U^\dagger$. $G$ is of Toeplitz structure, so $H$ will not be diagonal (which would be the case for a circulant matrix $G$). Then equivalently minimize

$$ b^T H b + b^T r $$

Now since $b_1 = \sum_i a_i = 1$, this can be written explicitely

$$h_{11} + b_1 r_ 1+ \sum_{j=2}^n (h_{1 j} + h_{j 1} + r_j) b_j + \sum_{j, k=2}^n h_{j k } b_j b_k$$

and the condition $\sum_{i=1}^{n} a_i=1$ is already included. Now minimizing w.r.t. the $b_j$ gives $n-1$ linear equations (where $j = 2 \dots n$)

$$ (h_{1 j} + h_{j 1} + r_j) + \sum_{k=2}^n (h_{k j} + h_{j k}) b_k = 0 $$

Writing this in compact form, with $(n-1)$-dimensional vectors and an $(n-1)\times (n-1)$-dimensional matrix, where the first index is missing, denoted by bars $$ \bar c + \bar F \bar b = \bar 0$$ or

$$a = \frac1n U^\dagger \left(1 \atop \bar b \right) = \frac1n U^\dagger \left(1 \atop - {\bar F}^{-1} \bar c \right) $$

as a closed solution for an extremal point, where it has to be checked whether this is a minimum.

Answer 2

Relaxing the condition $a_i \ge 0$ as suggested in the question discussion, with

$$ M = \left(\matrix{ 1&g_1&g_2&g_3&\cdots&g_n\\ 0&1&g_1&g_2& \cdots&g_{n-1}\\ \vdots&\vdots&\vdots&\vdots&\cdots&\vdots\\ 0&0&0&0&\cdots&g_1\\ 0&0&0&0&\cdots&1 }\right) $$

we have

$$ L(a,\lambda) = a^T\cdot M\cdot a+a^T\cdot q - \lambda (a^T \cdot \hat 1 - 1) $$

with $\hat 1 = (1,\cdots,1)^T$. Also

$$ \nabla L = 2M\cdot a+q-\lambda \hat 1 = 0 $$

then the stationary point is determined as

$$ a^* = \frac 12M^{-1}\cdot(\lambda \hat 1-q) $$

$M^{-1} = \text{adj}(M)$ because $\det (M)=1$ now making

$$ \hat 1^T\cdot a^* = \frac 12 \hat 1^T\cdot\text{adj}(M)\cdot(\lambda \hat 1-q)=1 $$

and then

$$ \lambda = \frac{1+\frac 12 \hat 1^T\cdot\text{adj}(M)\cdot q}{\frac 12 \hat 1^T\cdot\text{adj}(M)\cdot \hat 1} $$

and substituting into $a^*$ we obtain the stationary point.