# Find $\min \sum_{1\le i\le n} x_i\mathbf{z}^T\mathbf{A}\mathbf{y}_i +\mathbf{b}^T\mathbf{x} +\cdots$

I have been stuck at this problem for a while :(

Given $\mathbf{A}\in\mathbb{R}^{p\times p}, \mathbf{A}\ge 0,\mathbf{A} \text{ symmetric}, \mathbf{b}\in\mathbb{R}^n,\mathbf{c}_i\in\mathbb{R}^p\forall i,\mathbf{d}\in\mathbb{R}^p$.

Consider the function: $$f(\mathbf{x},\mathbf{y},\mathbf{z}) = \sum_{1\le i\le n} x_i\mathbf{z}^T\mathbf{A}\mathbf{y}_i +\mathbf{b}^T\mathbf{x} + \sum_{1\le i\le n}\mathbf{c}_i^T\mathbf{y}_i +\mathbf{d}^T\mathbf{z}$$ where $\mathbf{x}\in \mathbb{R}^n,\mathbf{y}_i\in\mathbb{R}^p \forall i,\mathbf{z}\in \mathbb{R}^p$.

Minimize $f(\mathbf{x},\mathbf{y},\mathbf{z})$ subject to $\mathbf{0}\le\mathbf{x},\mathbf{y}_i,\mathbf{z}\le \mathbf{1}$ and $\mathbf{1}^T\mathbf{x}=\mathbf{1}^T\mathbf{y}_i=\mathbf{1}^T\mathbf{x}=1 \quad \forall i.$

If it can make the problem easier, then remove some (or all) of the three equality constraints:

• $\mathbf{1}^T\mathbf{x}=1$
• $\mathbf{1}^T\mathbf{y}_i=1\quad\forall i,1\le i\le n$
• $\mathbf{1}^T\mathbf{z}=1$

Thank you in advance for any suggestions!

P/s: a related problem: Find $\min x^TAy$ subject to $1^Tx=1^Ty=1,x\ge 0,y\ge 0$.

• For a fixed $x$ vector, minimise $g(Y,z) = f(x_0, Y, z)$ is a bilinear optimisation problem. I don't have experience in bilinear opt, but they are nonconvex... google search might give you some idea. Once you can optimise $g$, you can use any derivative free method for $x$ – jf328 May 20 '15 at 15:56
• @jf328: Thanks. I was about to post a solution with a similar idea (somehow fixing $x$). – Khue May 20 '15 at 20:07

We will solve the problem for the constraints $\mathbf{1}^T\mathbf{x}=\mathbf{1}^T\mathbf{y}_i=\mathbf{1}^T\mathbf{x}=1$ and for a general matrix $\mathbf{A}$ (not necessarily non-negative or symmetric).

First of all, since $f$ is linear with respect to $\mathbf{x}$, an optimal solution is attained at an extreme point, thus we can replace the constraint $\mathbf{x}\in [0,1]^n$ by $\mathbf{x}\in\left\{0,1\right\}^n$. (Of course we have the same statement for $\mathbf{y}$ and $\mathbf{z}$ but we do not need that).

Since $\mathbf{x}\in\left\{0,1\right\}^n$ and $\mathbf{1}^T\mathbf{x}=1$, $\mathbf{x}$ has the form: one component of $\mathbf{x}$ is $1$ and all the others are $0$. Thus, $\mathbf{x}$ can only take $n$ different values. The idea is that we iterate over these $n$ values of $\mathbf{x}$ and minimize the function with respect to $(\mathbf{y},\mathbf{z})$ (which is efficient because we have an analytical solution), then we compare all the $n$ obtained optimal values and pick the best one.

Now, suppose that $\mathbf{x} = \mathbf{x}_0$ where $x_{i_0} = 1$ and $x_i=0$ for any $i\neq i_0$. We have \begin{align*}f(\mathbf{x}_0,\mathbf{y},\mathbf{z}) &=\mathbf{z}^T\mathbf{A}\mathbf{y}_{i_0} + b_{i_0} + \sum_{1\le i\le n}\mathbf{c}_i^T\mathbf{y}_i +\mathbf{d}^T\mathbf{z} \\ &= \left( \mathbf{z}^T\mathbf{A}\mathbf{y}_{i_0} + \mathbf{c}_{i_0}^T\mathbf{y}_{i_0} +\mathbf{d}^T\mathbf{z} \right) + \sum_{1\le i\le n,i\neq i_0}\mathbf{c}_i^T\mathbf{y}_i + b_{i_0}. \end{align*} Denote $\mathbf{y}_i = (y^i_1,y^i_2,\ldots,y^i_p)$. Clearly, the minimum value of $\mathbf{c}_i^T\mathbf{y}_i$ is the smallest component of $\mathbf{c}_i$, and if $j_0(i)$ is the position of this component, then the minimum is attained when $y^i_{j_0(i)} = 1$ and $y^i_j = 0 \forall j\neq j_0(i).$

It remains to minimize $g(\mathbf{y}_{i_0},\mathbf{z}) = \mathbf{z}^T\mathbf{A}\mathbf{y}_{i_0} + \mathbf{c}_{i_0}^T\mathbf{y}_{i_0} +\mathbf{d}^T\mathbf{z}$.

Since $\mathbf{1}^T\mathbf{y}_{i_0} = \mathbf{1}^T\mathbf{z}=1$ we have $$g(\mathbf{y}_{i_0},\mathbf{z}) = \mathbf{z}^T\mathbf{A}\mathbf{y}_{i_0} + \mathbf{z}^T\mathbf{1}\cdot\mathbf{c}_{i_0}^T\mathbf{y}_{i_0} +\mathbf{z}^T\mathbf{d}\cdot \mathbf{1}^T\mathbf{y}_{i_0} = \mathbf{z}^T \left( \mathbf{A} + \mathbf{1}\cdot\mathbf{c}_{i_0}^T + \mathbf{d}\cdot \mathbf{1}^T \right) \mathbf{y}_{i_0}.$$ According to this lemma: Find $\min x^TAy$ subject to $1^Tx=1^Ty=1,x\ge 0,y\ge 0$, the minimum value of $g$ is the smallest component of the matrix $\mathbf{A} + \mathbf{1}\cdot\mathbf{c}_{i_0}^T + \mathbf{d}\cdot \mathbf{1}^T$, and if $(k_0,j_0)$ is the position of this component, then the minimum is attained when $z_{k_0} =1$ and $y^{i_0}_{j_0}=1$.

Finally, we have the following algorithm to solve the problem:

1. Initialize the best-so-far minimum: $f_0=+\infty$.

2. Pre-compute the position $j_0(i)$ of the smallest components of the vectors $\mathbf{c}_i$. Compute the sum of these components: $S_c = \sum_{1\le i\le n}c^i_{j_0(i)}$.

3. For $i=1,2,\ldots,n$:

+) Find the smallest component $m_{k_0,j_0}$ of the matrix $\mathbf{M}=\mathbf{A} + \mathbf{1}\cdot\mathbf{c}_{i}^T + \mathbf{d}\cdot \mathbf{1}^T$.

+) Compute the current minimum $f=m_{k_0,j_0} + (S_c - c^i_{j_0(i)}) + b_{i}$

+) Compare with the best-so-far minimum: if $f \le f_0$ then $f_0 = f$ and set the corresponding optimal solution.

• beautiful (ignore, just to make comment long enough) – jf328 May 21 '15 at 10:38