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}x_{ij} & j=\{1,\dots,J\} \\ q_i \geq 0 & i=\{1,\dots,n\} \\ \end{cases} \end{align}

with $\alpha>0$, $x_{ij}\geq 0$ and $k_j \geq 0$ for all indices. I'd like to prove that if $\mathbf q^*=(q_1^*,\dots,q_n^*)$ is a solution to this problem for $\mathbf k^*=(k_1^*,\dots,k_J^*),$ then $\delta^{\alpha}\mathbf q^*$ is a solution for $\delta \mathbf k^*.$

I proceed by contradiction:

Assume that the solution for $\delta \mathbf k^*$ was $\mathbf {\hat q}$ and such that $\sum\limits_{i=1}^n \hat q_i>\delta^{\alpha}\sum\limits_{i=1}^n q_i^*$. Consider $\mathbf {\bar q}=\dfrac1{\delta^{\alpha}}\mathbf {\hat q}.$ It is easily seen that $\mathbf {\bar q}$ is feasible for $\mathbf k^*$. But we have that

$$\sum_{i=1}^n \bar q_i>\sum_{i=1}^n q_i^*,$$

so $\mathbf q^*$ cannot be a solution for $\mathbf k^*$.

Is this correct? I worry that if the program has multiple solutions (and this can be the case when $\alpha>1$) my proof is not general enough or even wrong altogether.

Edit: Perhaps it would be more accurate to say that, letting $\mathbf S(\mathbf k) $ denote the set of solutions to the maximization program for a given $\mathbf k$, $$\mathbf q^*\in \mathbf S(\mathbf k^*) \iff \delta^{\alpha}\mathbf q^*\in \mathbf S(\delta\mathbf k^*)$$


1 Answer 1


Your logic seems fine to me. There's no issue with multiple solutions: just make $\hat{\bf{q}}$ any optimal solution to the modified problem.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.