Finding the maximum value of a sum involving several parameters

[moriheru]

Homework Statement

Given that
a₁+a₂+a₃+... +a₇=1 and that all a_j is smaller than 1 and greater than 0 and variable , find the maximum value of

6a₁+5a₂+4a₃+...+ a₆

Homework Equations

no further constraints

The Attempt at a Solution

I have no idea how to solve this problem specifically, but I do recall a technique called lagrange multipliers that may come in handy. If anyone could direct me to a computer program that would do the calculations for me or help me solve this problem non-numerically I would be very grateful. Thank you!

 

[Charles Link]

Please clarify, because I think you had posted a similar problem yesterday. Is it ## 5a_2 ## or ## 5/a_2 ## etc.? Also, I think your sum should be ## a_1 ## to ## a_6 ## is equal to ## 1 ##. ## \\ ## Anyway, Lagrange multipliers should work. With Lagrange multipliers you let ## f(a_1, a_2,...,a_6, \lambda)=6/a_1+5/a_2+...+\lambda (a_1+...+a_6-1) ##. You then take a partial derivative of ## f(a_1,..., a_6,\lambda) ## w.r.t. each variable and set to zero to get you an equation, and you take the partial w.r.t. ## \lambda ## and set to zero, which essentially gives you your constraint equation. The solution is straightforward. 7 equations and 7 unknowns.

 

[moriheru]

Please clarify, because I think you had posted a similar problem yesterday. Is it ## 5a_2 ## or ## 5/a_2 ## etc.? Also, I think your sum should be ## a_1 ## to ## a_6 ## is equal to ## 1 ##. Anyway, Lagrange multipliers should work.

Yes I did post a similar thread yesterday, but it was deleted by the moderators. I mean 5a and not 5/a as I wrote in my previous thread. Sorry, if that caused any confusion. The sum from 1-6 equals one and not 1-7. I understand why you would think so, but I eliminated a₇ in a previous step. Is there anyway I could simply let a computer solve this problem for me, without having to do the calculations myself or coding or downloading a suitable Programm? Thanks for the reply!

 

[Charles Link]

In the form that you have it, clearly ## a_1=0 ## gives a maximum, (## 6/a_1= +\infty ##), so that there is no good numerical solution of any kind.

 

[moriheru]

Sorry my mistake it is 6a₁ and not 6/a₁. I am sorry, this is turning out to be quite a mess...

 

[Charles Link]

That also has a simple answer: ## a_1 =1 ##; ## a_2=a_3=a_4=a_5=a_6=0 ##. The maximum value is ## 6 ##. And Lagrange multiplier method does not get the solution, because in this case the derivatives are not equal to zero. The solution can be seen by inspection.

 

[Ray Vickson]

Homework Statement

Given that
a₁+a₂+a₃+... +a₇=1 and that all a_j is smaller than 1 and greater than 0 and variable , find the maximum value of

6a₁+5a₂+4a₃+...+ a₆

Homework Equations

no further constraints

The Attempt at a Solution

I have no idea how to solve this problem specifically, but I do recall a technique called lagrange multipliers that may come in handy. If anyone could direct me to a computer program that would do the calculations for me or help me solve this problem non-numerically I would be very grateful. Thank you!

As written your problem has NO solution. If you have strict inequalities ##0 < a_i < 1, \: i = 1, \ldots, 7## your constraint set is open and the function ##f(a) = 6 a_1 + 5 a_2 + \cdots + a_6## does not have a maximum on that constraint set. It has a supremum, but not a maximum. A simpler, similar example would be ##\max x## on ##0 < x < 1##, which has no solution.

However, if you make the inequalities non-strict (so ##0 \leq a_i \leq 1, \; i = 1, \ldots, 7##) you get a standard linear programming problem that can be solved quite easily by the bounded-variable simplex method. Alternatively, you can use a Lagrange multiplier method, but you need to use the so-called Karush-Kuhn-Tucker conditions instead of just setting derivatives to zero---it is NOT the standard Lagrange-multiplier method that you are probably thinking of!

You can easily get a numerical solution in EXCEL, using the Solver Tool. Other spreadsheets have similar tools available.There are also numerous free on-line linear programming solvers that can solve small problems like yours.

 

[moriheru]

Thanks! Could you link me to the websites you suggested?If I were interested in the suprememum how would I go about that? The same way?

 

[Ray Vickson]

Thanks! Could you link me to the websites you suggested?If I were interested in the suprememum how would I go about that? The same way?

The supremum (in the open-set version) is just the maximum in the closed-set version.

Google "on-line linear programming solvers" to see what is available. Some of them solvers are not particularly user-friendly, but if you just need to solve one or two problems that is not really a big issue.

 

[moriheru]

The supremum (in the open-set version) is just the maximum in the closed-set version.

Google "on-line linear programming solvers" to see what is available. Some of them solvers are not particularly user-friendly, but if you just need to solve one or two problems that is not really a big issue.

Thank you so much!

 

[Ray Vickson]

Thank you so much!

Just as a matter of interest, the Lagrange multiplier solution is as follows. Let
$$L = \sum_{i=1}^7 (7-i) x_i + \lambda(1-\sum_{i=1}^7 x_i).$$
For the maximization problem with bound constraints ##0 \leq x_i \leq 1## for all ##i##, the (Karush-Kuhn-Tucker) optimality conditions are:
(1) If ##x_i = 0## then ##\partial L / \partial x_i \leq 0##.
(2) If ##x_i = 1## then ##\partial L / \partial x_i \geq 0## .
(3) If ##0 < x_i < 1## then ##\partial L / \partial x_i = 0##.

Let us guess the solution ##x_1 = 1## all other ##x_i = 0##.
$$\begin{array}{l}
\partial L/ \partial x_1 = 6 - \lambda \geq 0\\
\partial L / \partial x_2 = 5 - \lambda \leq 0 \\
\hspace{1cm} \vdots \\
\partial L / \partial x_6 = 1 - \lambda \leq 0 \\
\partial L / \partial x_7 = - \lambda \leq 0
\end{array}
$$
These conditions are satisfied by choosing any ##\lambda## between 5 and 6. Since the problem is a so-called "convex programming problem" the conditions are also sufficient to guarantee a global constrained maximum. In other words, the intuitive solution ##x = (1,0,0,0,0,0,0)## is provably optimal.

Much simpler, however, is to note that the constraints ##x_i \leq 1## are redundant because if ##\sum_i x_i = 1## and each ##x_i \geq 0## then each ##x_i## is automatically ##\leq 1##. Therefore, the original problem is equivalent to
$$\begin{array}{rcl}
\max Z &=& \sum_{i=1}^7 (7-i) x_i \\
\text{s.t.}&& \sum_{i=1}^7 x_i = 1 \\
&&x_i \geq 0, \; i = 1,2, \ldots, 7
\end{array}
$$

That makes the problem almost trivial: the simplex method takes just one step: use the equality constraint to write
$$x_1 = 1 - \sum_{i=2}^7 x_i ,$$
giving
$$Z = 6 - 1x_2 - 2 x_3 - 3 x_4 - 4 x_5 - 5 x_6 - 6 x_7.$$
We obtain ##Z = 6## if we set all ##x_2 = \cdots = x_7## equal to zero, but get ##Z < 6## if any of the variables ##x_2, \cdots, x_7## is ##> 0##. Therefore, the optimal solution is obtained as ##x = (1,0,,0,0,0,0).##