# Characterizing the solution of a (non) linear maximization program

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

• 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. – Rolf van Lieshout Sep 26 '19 at 16:04
• @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. – Patricio Sep 26 '19 at 20:32