7
$\begingroup$

Let $\mathbf{A}=\left(a_{ij}\right)$ be a $n\times J$ matrix with $a_{ij}\geq 0$, $n>J$ and such that no row has all its entries equal to zero, and each column has at most one zero. Let also $\mathbf{q}=\left(q_i\right)$ a $n\times 1$ vector of variables. Abusing notation, I'll write $\mathbf{q}^{\beta}=\left(q_i^{\beta}\right)$ for some $\beta>1$. Finally, let $\mathbf{w}=\left(w_j\right)_{1\leq j\leq J}$ with $w_{j}\geq 0$ and $\sum_{j=1}^{J}w_{j}=1$.

Consider the problem

$$\begin{align} \min\limits_{\{q_i\}}& \quad \left(\mathbf{A}\mathbf{w}\right)^{\top}\mathbf{q}^{\beta}\\ \text{s.t.}&\quad \quad \begin{cases} \sum_{i=1}^n q_i=1\\ \mathbf{q}\geq 0. \end{cases} \end{align}$$

and, in particular, the specific problems that result from choosing $\mathbf{w}=\mathbf{e}_k=\left(e_j\right)_{1\leq j\leq J}$ with $e_{k}=1$ and $e_{j}=0\;\forall j\neq k$ for $k=\{1,\dots,J\}$. Observe that the objetive function in the general problem above is a convex combination of the objective in the $J$ specific problems. Let $\mathbf{q}^k$ denote the minimand for each $\mathbf{e}_k$ and call $\mathbf{z}^k=\mathbf{A}^{\top}\left(\mathbf{q}^k\right)^{\beta}$.

If we call $\mathbf{\hat q}$ the solution to the general problem for $\mathbf{w}\neq\mathbf{e}_k\;\forall k$, I believe that there exists $\mathbf{w}^{\prime}$ (with $w_j^\prime\geq 0$ and $\sum w_j^\prime>0$) such that $\mathbf{A}^{\top}\mathbf{\hat q}^{\beta}=\sum_{k=1}^J\mathbf{z}^kw_k^\prime$. In other words, the solution to the general problem is a convex combination of the solutions to the specific problems. Is this correct? If it is, can you provide a reference for the proof?

Edit:

Following @mtanneau's suggestion, I've obtained the closed form solution for the optimal $\mathbf{q}\left(\mathbf{w}\right)=\left(q_i\left(\mathbf{w}\right)\right)$ given $\mathbf{w}$. To simplify notation, write $\mathbf{\bar a}\left(\mathbf{w}\right)=\left(\bar a_i\left(\mathbf{w}\right)\right)=\mathbf{Aw}$, where $\bar a_i\left(\mathbf{w}\right)$ is just the weighted average of the values on row $i$ (with weights given by $\mathbf{w}$). Two cases:

  1. Given $j$, $\exists i^{*}\,|\,a_{i^{*}j}=0$. The assumptions on $\mathbf{A}$ warrant that $i^*$ is unique, and that if $\mathbf{w}$ is such that $\bar a_{i^*}\left(\mathbf{w}\right)=0$, it must be the case that $\bar a_{i}\left(\mathbf{w}\right)>0\;\forall i\neq i^*$. The solution to the specific problem is $q_{i^*}\left(\mathbf{e}_j\right)=1$ and $q_{i}\left(\mathbf{e}_j\right)=0\,\forall i\neq i^*$, and, simmilarly, for those $\mathbf{w}$ such that $\bar a_{i^*}\left(\mathbf{w}\right)=0$, that of the general problem is $q_{i^*}\left(\mathbf{w}\right)=1$ and $q_{i}\left(\mathbf{w}\right)=0\,\forall i\neq i^*$ (if $\bar a_{i}\left(\mathbf{w}\right)>0\,\forall i$, the solution follows the structure in (2) below).

  2. Given $j$, $a_{ij}>0\;\forall i$

$$ q_i\left(\mathbf{w}\right)=\frac{1}{\bar a_i\left(\mathbf{w}\right)^\frac{1}{\beta-1}\sum_{i^{*}=1}^n\left(\frac{1}{\bar a_{i^{*}}\left(\mathbf{w}\right)}\right)^\frac{1}{\beta-1}}$$.

When $\mathbf{w}=\mathbf{e}_k$, this simplifies to

$$ q_i\left(\mathbf{e}_k\right)=\frac{1}{a_{ik}^\frac{1}{\beta-1}\sum_{i^{*}=1}^n\left(\frac{1}{a_{i^{*}k}}\right)^\frac{1}{\beta-1}}$$.

I don't see how to proceed from here.

$\endgroup$
3
  • $\begingroup$ Each of these problems can be solved in closed form. From there it is not hard to show whether the statement holds or not. $\endgroup$ – mtanneau Nov 23 '20 at 13:41
  • $\begingroup$ Sorry, I realize I had read it wrong... I thought A had at most one non-zero per column :/ The next step is not as straightforward as I thought $\endgroup$ – mtanneau Nov 24 '20 at 13:29
  • $\begingroup$ $\mathbf{A}^{\top}\mathbf{\hat q}^{\beta}=\sum_{k=1}^J\mathbf{z}^kw_k^\prime$ is to be interpreted as "value of the general problem is the convex combination of the values of the specific problems". Could you please be more specific about what your claim concerns, optimization program values or solutions? $\endgroup$ – Konstantin Dec 11 '20 at 21:49
4
$\begingroup$

It is not. Not with the same weights.

Regarding general positive coefficients (not necessarily weights) this is a question of existence of a positive solution to the system $Q_{n\times J} w' = q^w_{n\times 1}$, where $Q = [q^1 ... q^J]$ collects the horizontally stacked column solution vectors to pure objectives, and $q^w$ is the column solution vector of the averaged objective. A natural first step towards resolving this problem is Farkas' lemma.

Proof by counterexample:

Just to have the peace of mind, we shall use the minimal example: $n=J=2$, $\beta = 2$ and $w=(\frac{1}{2},\frac{1}{2})$.

Let $A = \begin{bmatrix} a_1 & b_1 \\ a_2 & b_2\end{bmatrix}$ be the matrix with positive entries.

So we have 3 maximization programs with solutions :

\begin{align} x_1 & = \arg \min_{x\in[0,1]} a_1 x^2 + b_1(1-x)^2 = \frac{b_1}{a_1+b_1}\\ x_2 & = \arg \min_{x\in[0,1]} a_2 x^2 + b_2(1-x)^2 = \frac{b_2}{a_2+b_2}\\ x_w & = \arg \min_{x\in[0,1]} \bar a x^2 + \bar b (1-x)^2 = \frac{\bar b}{\bar a+\bar b}, \end{align}

where $\bar a = \frac{a_1+a_2}{2}$ and $\bar b = \frac{b_1+b_2}{2}$.

It is immediate to see that the minimum of the averaged objective is not the average of the minima of the pure objectives:

$$\frac{x_1+x_2}{2} = \frac{1}{2}\left(\frac{b_1}{a_1+b_1}+ \frac{b_2}{a_2+b_2}\right) \neq \frac{1}{2} \frac{b_1 + b_2}{\bar a + \bar b} = x_w$$.

$\endgroup$
4
  • $\begingroup$ But my claim was that there exists $\mathbf{w}^\prime$, not that it was equal to $\mathbf{w}$. In your example $\mathbf{w}^\prime=\left(\frac{a_1+b_1}{2(\bar{a}+ \bar{b})},\frac{a_2+b_2}{2(\bar{a}+ \bar{b})}\right)$ would satisfy my requirements. $\endgroup$ – Patricio Dec 11 '20 at 20:56
  • $\begingroup$ Yeah, I got that after I wrote up the post. What about the Farkas' lemma, have you tried this avenue before? $\endgroup$ – Konstantin Dec 11 '20 at 21:03
  • $\begingroup$ @Patricio And by the way, do you require $\sum_j w'_j = 1$ or not? "convex combination" suggests that, but there is no mention of this condition in the text. $\endgroup$ – Konstantin Dec 11 '20 at 21:15
  • $\begingroup$ I don't need $\sum w^{\prime}_i=1$, you're right that "convex" is a bit misleading. I'm not familiar with Farkas' Lemma, I'll look into it. $\endgroup$ – Patricio Dec 12 '20 at 5: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.