Lagrange multiplier no solution or incorrect formulation

  • Thread starter unplebeian
  • Start date
  • #1
154
0
1. The problem statement
I'm stuck with this problem which does not yield a solution. I feel as if I'm not formulating it correctly. Here it is described below. I've also written down the equations as they're easier to be read (attachment)
This is something that I was doing with batteries and thought of using Lagrange multipliers. I have N energy cell or some sort (fuel cell, battery etc.) with different capacities. The basic problem is how to control a multitude of energy sources to meet the power demand. e.g. cell 1, 2, and 3 can each provide 50 Watts each but the cost of each cell is $1/Watt, $3/Watt, and $1.5/Watt and a total power demand of 120 Watts is needs which can fluctuate over time. Assume that I can control the cells using an internal switch of some sort and I use a control variable alpha where 0 <= alpha<= 1 (unitless) which can control the output power of each cell.

At the end I need to find the Total cost and the values of alpha_i

Generalizing:
The i_th energy cell capable of providing a total power of Pi.

Power_demand= alpha1*P1 + alpha2*P2 + ...+ alphaN*PN
where 0 <= alpha_i <= 1.0 (unitless)

The cost needs to be minimized where:
Total_cost= C1*alpha1*P1 + C2*alpha2*P2 + ... + CN*alphaN*PN
where Ci= Dollars/ Watt

Homework Equations



Minimize cost function 'Total_cost' subject to constraint Power_demand

Define Lagrangian as
L= (C1*alpha1*P1 + C2*alpha2*P2 + ... + CN*alphaN*PN) + LAMBDA*(alpha1*P1 + alpha2*P2 + ...+ alphaN*PN )

The Attempt at a Solution



partial_L/partial_alpha_i = Pi+ LAMBDA*Pi
partial_L/partial_LAMBDA = alpha1*P1 + alpha2*P2 + ...+ alphaN*PN - Power_demand
Set first derivatives to zero:
Pi= 0 or LAMBDA= -Ci
and alpha1*P1 + alpha2*P2 + ...+ alphaN*PN - Power_demand

This does not yield any meaningful result as power can't be 0. Can anyone help with this? Am I not formulating the problem correctly?
 

Attachments

Answers and Replies

  • #2
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
1. The problem statement
I'm stuck with this problem which does not yield a solution. I feel as if I'm not formulating it correctly. Here it is described below. I've also written down the equations as they're easier to be read (attachment)
This is something that I was doing with batteries and thought of using Lagrange multipliers. I have N energy cell or some sort (fuel cell, battery etc.) with different capacities. The basic problem is how to control a multitude of energy sources to meet the power demand. e.g. cell 1, 2, and 3 can each provide 50 Watts each but the cost of each cell is $1/Watt, $3/Watt, and $1.5/Watt and a total power demand of 120 Watts is needs which can fluctuate over time. Assume that I can control the cells using an internal switch of some sort and I use a control variable alpha where 0 <= alpha<= 1 (unitless) which can control the output power of each cell.

At the end I need to find the Total cost and the values of alpha_i

Generalizing:
The i_th energy cell capable of providing a total power of Pi.

Power_demand= alpha1*P1 + alpha2*P2 + ...+ alphaN*PN
where 0 <= alpha_i <= 1.0 (unitless)

The cost needs to be minimized where:
Total_cost= C1*alpha1*P1 + C2*alpha2*P2 + ... + CN*alphaN*PN
where Ci= Dollars/ Watt

Homework Equations



Minimize cost function 'Total_cost' subject to constraint Power_demand

Define Lagrangian as
L= (C1*alpha1*P1 + C2*alpha2*P2 + ... + CN*alphaN*PN) + LAMBDA*(alpha1*P1 + alpha2*P2 + ...+ alphaN*PN )

The Attempt at a Solution



partial_L/partial_alpha_i = Pi+ LAMBDA*Pi
partial_L/partial_LAMBDA = alpha1*P1 + alpha2*P2 + ...+ alphaN*PN - Power_demand
Set first derivatives to zero:
Pi= 0 or LAMBDA= -Ci
and alpha1*P1 + alpha2*P2 + ...+ alphaN*PN - Power_demand

This does not yield any meaningful result as power can't be 0. Can anyone help with this? Am I not formulating the problem correctly?
The Lagrange multiplier method fails because you have inequality constraints of the form ## 0 \leq \alpha_i \leq 1 ##. These necessitate the use of the so-called Karush-Kuhn-Tucker (KKT) conditions, rather than simple Lagrange conditions. Google 'Kuhn-Tucker conditions' for more details, or consult a textbook on optimization, or a textbook on Operations Research.

In the meantime, it might be useful for you to know that your problem is a classic and well-studied operations research problem called the continuous knapsack problem (or fractional knapsack problem). It has an operationally simple solution; see, eg.,
http://courses.cs.washington.edu/courses/cse421/04su/slides/fracknap.pdf or
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Greedy/knapscakFrac.htm

Note that these papers deal with the problem of maximizing ##V = \sum \alpha_i c_i p_i##, while you want to minimize it. However, you can re-write your problem by setting ##\alpha_i = 1 - \beta_i## for all ##i##. Note that ##0 \leq \beta_i \leq 1## for all i, so the ##\beta_i## form is a standard maximizing knapsack problem.

The papers cited above do not deal very well with actual correctness-proofs. One thing you can do is verify that their so-called "greedy solutions" actually satisfy the KKT conditions. Have fun.
 
Last edited:
  • Like
Likes unplebeian
  • #3
154
0
Thank you! That did solve my problem and the solution I got is now very simple. I can't believe I didn't see that before.

Similar to the greedy problem, I choose the cell with the minimum cost first, try to maximize its contribution and check if the power demand is met. If not, then I select the cell with the lowest cost (out of the remaining cells) and adjust its alpha to see if the power demand is met. And so on...
 
  • #4
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
Thank you! That did solve my problem and the solution I got is now very simple. I can't believe I didn't see that before.

Similar to the greedy problem, I choose the cell with the minimum cost first, try to maximize its contribution and check if the power demand is met. If not, then I select the cell with the lowest cost (out of the remaining cells) and adjust its alpha to see if the power demand is met. And so on...
Right: that works because the "ratio" has the form ##\frac{c p}{p} = c##, so just ordering by cost does the trick.
 
  • #5
154
0
I looked up the KKT conditions and they're a little beyond me at the moment. I was hoping to use LaGrange multipliers to get a nice graphical solution with critical points. Perhaps if the power or cost function had variables, I could partially differentiate the variables (like P= I^2*R) and minimize that current quantity. That would require some modeling of the plant.

Thanks for your help. Ray Vickson! Extremely useful and helpful.
 
  • #6
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
I looked up the KKT conditions and they're a little beyond me at the moment. I was hoping to use LaGrange multipliers to get a nice graphical solution with critical points. Perhaps if the power or cost function had variables, I could partially differentiate the variables (like P= I^2*R) and minimize that current quantity. That would require some modeling of the plant.

Thanks for your help. Ray Vickson! Extremely useful and helpful.
Fortunately, this is a so-called Linear Programming, so can be solved using tools at the high-school level (although this is usually not seen in high school). Here goes.

Write the problem as
[tex] \min Z = \sum_{j=1}^n c_j x_k\\
\text{subject to}\\
\sum_{j=1}^n w_j x_j = W\\
0 \leq x_j \leq 1 \;, j=1, \ldots,n
[/tex]

We can assume all ##w_j > 0##, because: (i) if ##w_s = 0## the variable ##x_s## does not affect the constraint, so may be set to whatever value (0 or 1) makes its contribution to ##Z## the smallest, and (ii) if ##w_s < 0## we can write ##w_s x_s = w_s + w_s (x_s - 1) = w_s + (-w_s)(1-x_s)##. Writing ##w'_s = - w_s > 0## and ##x'_s = 1-x_s \in [0,1]## we would have a term of the form ##w'_s x'_s## in the constraint, with ##w'_s > 0##, and, of course, an "adjusted" value of ##W##.

Use the constraint to solve for one variable in terms of the others; say we solve for ##x_r##. (For now, just go along with it; you will soon see how this gives us what we want. And, for the moment, ##r## is just some number from 1 to n.) So, we have
[tex] x_r = \frac{W}{w_r} - \sum_{j \neq r} \frac{w_j}{w_r} x_j[/tex]
Substitute this into the equation for ##Z##:
[tex] Z = c_r \frac{W}{w_r} + \sum_{j \neq r} \left( c_j - c_r \frac{w_j}{w_r} \right) x_j \equiv (c_r W/w_r) + \sum_{j \neq r} u_j x_j. [/tex]
To minimize ##Z## we would like to set ##x_j = 1## if ##u_j < 0## and ##x_j = 0## if ##u_j > 0##. In other words, we want
[tex] (c_j/w_j) - (c_r/w_r) < 0 \; \longrightarrow x_j = 1\\
(c_j/w_j) - (c_r/w_r) > 0 \; \longrightarrow x_j = 0[/tex]
In other words, if we order the ratios ##c_j/w_j## in ascending order, we want to have ##x_j = 1## for some initial segment ##j = 1,\ldots, r-1## and ##x_j = 0## for ##j = r+1, \ldots n##. So, to find ##r## we just fill in x=1 in ascending order until we go too far; that is, when setting ##x_j = 1## also for ##j=r## gives a sum ##\sum_{j=1}^r w_jx_j > W## (but ##\sum_{j=1}^{r-1} w_j x_j < W##). Then, we just give ##x_r## the necessary fractional value and are done: all ##x_j = 0## for ##j > r##.

This is optimal, because we will have made all ##x_j = 1## when ##u_j < 0## and all ##x_j = 0## when ##u_j > 0##; basically, by re-writing the system properly, we can see the solution "by inspection".
 
Last edited:

Related Threads on Lagrange multiplier no solution or incorrect formulation

  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
1
Views
979
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
13
Views
2K
Top