11
$\begingroup$

I have the following maximization program

\begin{align} \max\limits_{\{q_i\}}&\quad\sum\limits_{i=1}^nq_i \\ \text{s.t.}&\quad\begin{cases} k_j \geq \sum\limits_{i=1}^n q_i^{1 \over \alpha_i}x_{ij} & j=\{1,\dots,J\} \\ q_i \geq 0 & i=\{1,\dots,n\} \\ \end{cases} \end{align}

with $\alpha_i>0$, and $k_j > 0$ for all indices. Also, $x_{ij}\geq 0 \quad \forall i,j$ and, in addition, it must be the case that, if we fix $i^*$, there exists at least one $j$ for which $x_{i^*j}>0$ and similarly, given $j^*$, there exists at least one $i$ for which $x_{ij^*}>0$. Examination of several examples has led me to believe (and I'd like to prove) that solutions (denoted $q_i^*$) to this problem are of the form:

  1. If $\alpha_i<1 \quad \forall i,$ then $q_i^*>0 \quad \forall i$.
  2. If $\alpha_i \geq 1 \quad \forall i,$ the solution needs not be unique and within a given solution $q_i^*$ can be indeed $0$ for some indices. If, for any of the solutions, we denote $I_+$ the set of indices for which $q_i^*>0$, my claim is that the cardinality of $I_+$ is $1 \leq n^*\leq \min [J,n]$.

The first part is easy, as $\alpha_i<1 \quad \forall i,$ leads to a bounded convex feasible set, but I don't know how to approach the second. Any help would be appreciated.

Edit: If $\alpha_i = 1 \quad \forall i,$ the problem is linear and I believe that my claim is true, because (I think that I recall that) the solution needs to be at a corner or a side of the feasible region. Any hint towards the development of this idea will also be of great help.

Edit #2: I could do with a proof for the case $\alpha_i=\alpha \quad \forall i$

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ For the $\alpha_i=1$ case, the problem reduces to a linear program with a bounded feasible region. For such problems, it is well known that there exists an optimal solution that is a vertex (corner) of the feasible region. You can easily convince yourself this is true by drawing a picture. It is possible that there are multiple optimal vertices, in which case also any convex combination between these vertices is optimal. $\endgroup$
    – Rolf van Lieshout
    Commented Sep 26, 2019 at 16:04
  • $\begingroup$ @RolfvanLieshout. Thanks. For the $\alpha_i>1$ drawing a picture also convinces me that the optimal solution needs to be a corner (or multiple corners, but in this case convex combinations are not optimal, because they're not feasible). My problem is how to translate that belief into a proof. $\endgroup$
    – Patricio
    Commented Sep 26, 2019 at 20:32

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.