3
$\begingroup$

I want to know the solution (the values that maximizes the objective function) of the following optimization problem. The objective function is as follows $$f(\mathbf{x})=a_1x_1+a_2x_2+a_3x_3+\cdots a_Nx_N$$ and the constraints are $$b_1x_1+b_2x_2+\cdots b_Nx_N \leq G$$

where all $a_1\cdots a_N, b_1\cdots b_N$ are positive values. (Also all $x_i$'s can only take nonnegative values only)

My study:

I have seen this problem in a research paper. In that paper they convert the inequality constraint to equality constraint (I do not know why and whether its legal or not? please explain). Then they say that the objective function is linear combination therefore we should have an answer (i.e. solution) which has only one non zero $x_i$ (e.g. $x_1=\text{some value},x_2=0 \cdots x_N=0$ etc.) I do not know how they found it. It seems to me that this is quite strightforward however I am unable to understand it. I will be very thankful to you for explaining it.

$\endgroup$
4
$\begingroup$

Order your variables by non increasing values of the ratio $\frac{a_i}{b_i}$. So you want to pick in priority variables with highest ratio (the ones that yield the highest increase of $f$ while keeping the constraint to a minimum). Without loss of generality, suppose the order is $(x_1,x_2,...,x_n)$.

The solution $x_1=\frac{G}{b_1}$, $x_2=...=x_n=0$ is feasible and yields $f=\frac{a_1}{b_1} G$ which is optimal.

Note: One way of proving it is optimal is by using the optimality condition from the simplex algorithm. It is not difficult to compute the reduced costs of this solution: \begin{cases} \hat{c}_{x_1}=0\\ \hat{c}_{x_i}=a_i-b_i\frac{a_1}{b_1}\le 0\quad \forall i=2,...,n \end{cases} which proves that the solution is optimal.

$\endgroup$
  • $\begingroup$ you changed the order of the variables so your $x_1$ may be different from my $x_1$. Is it true for the $a_1$ and $b_1$ also? $\endgroup$ – Frank Moses Nov 2 '16 at 14:27
  • 2
    $\begingroup$ @FrankMoses "Without loss of generality" means that he can rename the variables and it still applies to your question. $\endgroup$ – Hugh Nov 2 '16 at 14:30
  • $\begingroup$ and what is the reason for converting inequality constraints to equality constraints? $\endgroup$ – Frank Moses Nov 2 '16 at 14:52
  • $\begingroup$ You don't really have to depending on the approach you are using. In my approach I don't need it, except if you go into the detail of the proof using the reduced costs, technically the constraint should be handled as an equality with a slack variable that has reduced cost $-a_1/b_1$. $\endgroup$ – Kuifje Nov 2 '16 at 14:54
0
$\begingroup$

This is a linear program on a simplex, --more precisely, on a simplex affinely deformed by the diagonal matrix $\text{diag}(b_1,\ldots,b_N)$.

The solution is attained at a kink $j$, (Nash, late 1940's / early 50's) for which the coefficient $a_j$ is maximal. This corresponds to a best response (pure) strategy in the corresponding zero-sum matrix-game.

Fill out the details.

$\endgroup$

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.