02/22/20

Economic Dispatch

Optimization with inequality

Minimise constraints
f ( x1, x2 ,.. , xn ) Objective function

subject to:
w 1 ( x1 , x2 ,.. , xn ) = 0
 Equality constraints

w m ( x1 , x2 ,.. , xn ) = 0
and:
g1 ( x1 , x2 ,.. , xn ) £ 0
 Inequality constraints

gp ( x1 , x2 ,.. , xn ) £ 0
2

1
 02/22/20

Example: Economic Dispatch

x1 x2
x 1min £ x 1 £ x 1max
L
G1 G2 x 2min £ x 2 £ x 2max

Minimise C = a 1 + b1 x 12 + a 2 + b 2 x 22
Subject to:
Equality constraints
x1 + x 2 = L
x 1 - x 1max £ 0

x 1min - x 1 £ 0
Inequality constraints
x2 - x max
2 £0
x 2min - x 2 £ 0 3

Example: Economic Dispatch

Minimise C = a 1 + b1 x 12 + a 2 + b 2 x 22
Family of ellipses

x2
Ellipse tangent to equality constraint at A
Inequality constraints are satisfied
x1 + x 2 = L

x2max

x2min

x1
x1min x1max
4

2
 02/22/20

Example: Economic Dispatch

What is the solution for a larger load?

x2 Ellipse tangent to equality constraint at B

Inequality constraints are NOT satisfied!

x1 + x 2 = L x 1 + x 2 = L'
x2max

A B
x2min

x1min x1max x1
5

Example: Economic Dispatch

C is the solution because it is the point on
the equality constraint that satisfies the
x2
inequality constraints at minimum cost

x1 + x 2 = L x 1 + x 2 = L'
x2max

A B
x2min

x1min x1max x1
6

3
 02/22/20

Binding Inequality Constraints

• A binding inequality constraint is an inequality
constraint that is satisfied exactly
• Example:
– If we must have x1 ≤ x1max
– And at the solution we have x1 = x1max
– Then the constraint x1 ≤ x1max is said to be binding
• ALL of the inequality constraints must be satisfied
• Only a FEW will be binding (or active) at any given
time
• But we don’t know ahead of time which inequality
constraints will be binding!
• All equality constraints are always binding
7

Solution Using Lagrange Multipliers

Minimise f ( x1 , x2 ,.. , xn )
subject to:
w i ( x1 , x2 ,.. , xn ) = 0 i = 1,...m
g j ( x1 , x2 ,.. , xn ) £ 0 j = 1,...p
Lagrangian function:

( )
 x1 ,.. , xn , l1 ,..., l m , m1 ,..., m p = f ( x1 ,… , xn )
m
+ å liw i ( x1 ,.. , xn )
i=1
p
+ å m j g j ( x1 ,.. , xn )
j=1

4
 02/22/20

Optimality Conditions (Known as the

Karush Kuhn Tucker or KKT conditions)

Optimality Conditions

• partial derivatives of the Lagrange function

that must equal zero at the optimum.
• The complimentary slackness condition,

10

5
 02/22/20

Complementary slackness conditions

Two possibilities for each constraint i:

𝜇 = 0 then the constraint 𝑔 𝑥 is non binding ⟹ 𝑔 𝑥 ≤0

Or

𝑔 𝑥 = 0 then the constraint 𝑔 𝑥 is binding ⟹ 𝜇 ≥ 0

11

11

Solving the problem

• The KKT conditions are not quite enough to
solve the problem
• The complementary slackness conditions:
– Tell us that an inequality constraint is either
binding or non-binding
– DON’T tell us which constraints are binding and
non-binding
• The binding constraints have to be identified
through trial and error

12

12

6
 02/22/20

Example
Minimise
f ( x 1 , x 2 ) = 0.25 x 12 + x 22
Subject to:
w ( x1 ,x 2 ) º 5 - x1 - x 2 = 0
g ( x 1 , x 2 ) º x 1 + 0.2 x 2 - 3 £ 0

13

13

x2
Example
g ( x 1 , x 2 ) º x 1 + 0.2 x 2 - 3 £ 0

f ( x 1 , x 2 ) = 0.25 x 12 + x 22

x1

w ( x 1 , x 2 ) º 5 - x 1 - x 2 =140
14

7
 02/22/20

Example
 ( x 1 , x 2 , l , m ) = f ( x 1 , x 2 ) + lw ( x 1 , x 2 ) + mg ( x 1 , x 2 )
= 0.25 x 12 + x 22 + l ( 5 - x 1 - x 2 ) + m ( x 1 + 0.2 x 2 - 3 )

¶
º 0.5x1 - l + m = 0
¶x1
¶
º 2x2 - l + 0.2 m = 0
¶x2
¶
º 5 - x1 - x2 = 0
¶l
¶
º x1 + 0.2x2 - 3 £ 0
¶m
m g(x) º m ( x1 + 0.2x2 - 3) = 0 and m ³ 0 15

15

Example
KKT conditions do not tell us if inequality constraint is binding
Must use a trial and error approach

Trial 1: Assume inequality constraint is not binding μ = 0

From solution of example without inequality constraint, we

know that the solution is then:

x1 = 4; x2 = 1
Inserting these values in the inequality constraint, we get:

x1 + 0.2x2 - 3 = 1.2 ³ 0
This solution is thus not an acceptable solution
16

16

8
 02/22/20

Example
Trial 2: Assume that the inequality constraint is binding

¶
º 5 - x1 - x 2 = 0 x 1 = 2.5
¶l
¶ x 2 = 2.5
º x 1 + 0.2 x 2 - 3 = 0
¶m
¶
º 0.5 x 1 - l + m = 0 l = 5.9375
¶x 1
¶ m = 4.6875
º 2 x 2 - l + 0.2 m = 0
¶x 2
All KKT conditions are satisfied. This solution is acceptable
17

17

Example:
x graphical solution
2
g ( x 1 , x 2 ) º x 1 + 0.2 x 2 - 3 £ 0

Solution of problem
with inequality constraint

Solution of problem
f ( x 1 , x 2 ) = 0.25 x 12 + x 22 without inequality
constraint

x1
Solution of problem
without constraints

w ( x 1 , x 2 ) º 5 - x 1 - x 2 =180
18

9
 02/22/20

Application to Economic Dispatch

x1 x2
L
G1 G2

minimise f ( x 1 , x 2 ) = C 1 ( x 1 ) + C 2 ( x 2 )
s.t . w ( x 1 , x 2 ) º L - x 1 - x 2 = 0
g1 ( x 1 , x 2 ) º x 1 - x 1max £ 0
x min
£ x1 £ x max

g 2 ( x 1 , x 2 ) º x 1min - x 1 £ 0
1 1

g 3 ( x 1 , x 2 ) º x 2 - x 2max £ 0
x min
£ x2 £ x max

g 4 ( x 1 , x 2 ) º x 2min - x 2 £ 0
2 2

19

19

Application to Economic Dispatch

 ( x 1 , x 2 ,l ,m 1 ,m 2 ,m 3 ,m 4 ) = C1 ( x 1 ) + C 2 ( x 2 ) + l ( L - x 1 - x 2 )
+ m 1 ( x 1 - x 1max ) + m 2 ( x 1min - x 1 )
+ m 3 ( x 2 - x 2max ) + m 4 ( x 2min - x 2 )
KKT Conditions:

¶ dC 1
º - l + m1 - m 2 = 0
¶x 1 dx 1
¶ dC 2
º -l +m3 -m4 = 0
¶x 2 dx 2
¶
º L - x1 - x 2 = 0
¶l
20

20

10
 02/22/20

Application to Economic Dispatch

KKT Conditions (continued):

¶
º x 1 - x 1max £ 0 m 1 ( x 1 - x 1max ) = 0 ; m 1 ³ 0
¶m 1

¶
º x 1min - x 1 £ 0 m 2 ( x 1min - x 1 ) = 0 ; m 2 ³ 0
¶m 2

¶
º x 2 - x 2max £ 0 m 3 ( x 2 - x 2max ) = 0 ; m 3 ³ 0
¶m 3
¶
º x 2min - x 2 £ 0 m 4 ( x 2min - x 2 ) = 0 ; m 4 ³ 0
¶m 4
21

21

“Solving” these equations

Trial #1: No generator is at a limit

No inequality constraint is binding and all μ’s are equal to zero

¶ dC 1
º -l =0
¶x 1 dx 1 dC 1 dC 2
= =l
¶ dC 2 dx 1 dx 2
º -l =0
¶x 2 dx 2
¶
º L - x1 - x 2 = 0
¶l

All generators operate at the same incremental cost

22

22

11
 02/22/20

Solving the KKT Equations

Trial #2: Generator 1 is at its upper limit; Other limits not binding

x1 - x1max = 0 Þ m1 ³ 0; m 2 = m 3 = m 4 = 0
¶ dC 1 dC 1
º - l + m1 = 0 = l - m1 £ l
¶x 1 dx 1 dx 1
¶ dC 2 dC 2
º -l =0 =l
¶x 2 dx 2 dx 2

All generators do NOT operate at the same incremental cost!

The incremental cost of unit 1 is lower…. Why?

If that was possible, more power would be produced by unit 1

23

23

Solving the KKT Equations

Trial #3: Generator 1 is at its lower limit; other limits not binding

x1min - x1 = 0 Þ m 2 ³ 0; m1 = m 3 = m 4 = 0
¶ dC 1 dC 1
º -l -m2 = 0 = l + m2 ³ l
¶x 1 dx 1 dx 1
¶ dC 2 dC 2
º -l =0 =l
¶x 2 dx 2 dx 2

Again, all generators do NOT operate at the same incremental cost!

The incremental cost of unit 1 is higher… Why?

If that was possible, less power would be produced by unit 1

24

24

12
 02/22/20

Physical interpretation of the Lagrangian

Minimise f (x) subject to: g ( x ) = K or K - g ( x ) = 0
Where g ( x ) is either an equality constraint or a
binding inequality constraint
Lagrangian:  ( x, l ) = f (x) + l éë K - g ( x ) ùû
The optimum values of the decision variables and the
Lagrange multipliers are given by the optimality conditions:
¶ ¶ f ¶g
º -l =0
¶x ¶x ¶x
¶ x* , l *
º K - g( x) = 0
¶l 25

25

What happens when I move the constraint?

Equality constraint: g(x) = K + DK
Inequality constraint: g(x) ³ K + DK
Keep Δ𝐾 sufficiently small that an optimal solution still exists
and involves the same binding inequality constraints

The optimal value of the decision variables and of the Lagrange

multipliers change as Δ𝐾 changes:

x * = x(K )
l * = l (K )

26

26

13
 02/22/20

What happens when I move the constraint?

Lagrangian:  ( x, l ) = f (x) + l éë K - g ( x ) ùû
d  df dx dg dx d l
=
dK dx dK
+l-l +
dx dK dK
[ K - g(x)]
Re-arranging the terms, we get

d é df dg ù dx d l
= l +ê -l ú + [ K - g(x)]
dK ë dx dx û dK dK
At the optimum: =0 =0

d
= l*
dK opt
27

27

Physical interpretation of the Lagrangian

* *
( *
)
At the optimum:  x , l = f (x ) + l éë K - g x ùû
* *
( )
Complementary slackness 
=0

The value of the Lagrangian function is thus equal to the

value of the cost or objective function at the optimum

The value of the Lagrange multipliers at the

d
=l * optimal solution thus tell us by how much the
the objective changes when the constraints change
dK opt

The Lagrange multipliers are the marginal cost of the constraints

28

28

14
 02/22/20

Physical Interpretation of Lagrange Multipliers

• The Lagrange multipliers are thus often called

shadow costs
• Non-binding inequality constraints have a zero
marginal cost
• Adding binding constraints always increases
the cost of a solution
• Tightening a constraint increases the cost
• Relaxing a constraint decreases the cost
29

29

Physical Interpretation of Lagrange Multipliers

• Note that these observations are valid only for

sufficiently small changes in the constraints
• If the constraints change substantially, the set
of constraints that is binding at the optimum
may change
• The constraints that are no longer binding
would then have a zero marginal cost
• The newly binding constraints would then
have a non-zero marginal cost
30

30

15
 02/22/20

Example: Economic Dispatch

Using Lagrange Multipliers

31

Example: Economic Dispatch

A load L = 800 MW is supplied by three generating units.
The cost characteristics of these generating units are
given by the following expressions:

C1 = 100 + 8 P1 + 0.1 P12 [$/h] 230 ≤ P1 ≤ 400 MW

C2 = 200 + 7 P2 + 0.06 P22 [$/h] 100 ≤ P2 ≤ 500 MW

C3 = 250 + 9 P3 + 0.07 P32 [$/h] 100 ≤ P3 ≤ 260 MW

Calculate the optimal economic dispatch.

32

32

16
 02/22/20

Example: Form the Lagrangian

 = 100 + 8P1 + 0.1P12
+200 + 7P2 + 0.06P22
+250 + 9P3 + 0.07P32
+ l (L - P1 - P2 - P3 )
+ m1 (P1 - 400) + m2 (230 - P1 )
+ m 3 (P2 - 500) + m 4 (100 - P2 )
+ m5 (P3 - 260) + m6 (100 - P3 )
33

33

Example: Optimality Conditions

Set the partial derivatives of the Lagrangian with respect to the
decision variables and λ to zero:

¶
º 8 + 0.2P1 - l + m1 - m2 = 0 (1)
¶P1
¶
º 7 + 0.12P2 - l + m 3 - m 4 = 0 (2)
¶P2
¶
º 9 + 0.14P3 - l + m5 - m6 = 0 (3)
¶P3
¶
º L - P1 - P2 - P3 = 0 (4)

¶l 34

34

17
 02/22/20

Example: Optimality Conditions

Set the partial derivatives of the Lagrangian with respect to the
μ’s to zero:

¶
º P1 - 400 £ 0
¶ m1
¶
º 230 - P1 £ 0
¶ m2
¶
º P2 - 500 £ 0
¶ m3

35

35

Example: Optimality Conditions

Set the partial derivatives of the Lagrangian with respect to the
μ’s to zero:

¶
º 100 - P2 £ 0
¶ m4
¶
º P3 - 260 £ 0
¶ m5
¶
º 100 - P3 £ 0
¶ m6
36

36

18
 02/22/20

Example: Complementary slackness

m1 .(P1 - 400) = 0; m1 ³ 0

m2 .(230 - P1 ) = 0; m2 ³ 0

m3 .(P2 - 500) = 0; m 3 ³ 0

m 4 .(100 - P2 ) = 0; m 4 ³ 0

m5 .(P3 - 260) = 0; m5 ³ 0

m6 .(100 - P3 ) = 0; m6 ³ 0 37

37

Example: First Trial (1)

Assume that none of the inequality constraints is binding

This means that all the μ‘s are zero

Set the μ’s equal to zero in the optimality conditions.

Equations (1) to (3) become:

¶ l-8
º 8 + 0.2P1 - l = 0 Þ P1 =
¶P1 0.2
¶
º 7 + 0.12P2 - l = 0 l-7
¶P2 Þ P2 =
0.12
¶
º 9 + 0.14P3 - l = 0 l-9
¶P3 Þ P3 =
0.14 38

38

19
 02/22/20

Example: First Trial (2)

Inserting these expressions in Equation (4), we get:

L - 5(l - 8) - 8.33(l - 7) - 7.14(l - 9) = 0

With L = 800MW, we get: l = 46.96 $/MWh
Replacing λ in the equations on the previous slide, we have:

P1 = 194.8 MW < P1min = 230 MW

Not a valid solution
P2 = 333.0 MW  trial fails

P3 = 271.2 MW > P3max = 260 MW

39

39

Example: Second Trial (1)

We must try another combination of binding constraints.

6 inequality constraints  26 = 64 possible combinations

Realistic system  ridiculously large number of combinations

Must use information from previous trials

Let us try:

P1 = P1min = 230 MW Þ m2 ¹ 0
P3 = P3max = 260 MW Þ m5 ¹ 0
m1 = m3 = m 4 = m6 = 0
40

40

20
 02/22/20

Example: Second Trial (2)

L - P1 - P2 - P3 = 0

P1 = P1min = 230 MW Þ P2 = 310 MW

P3 = P3max = 260 MW

However, we must check that the μ‘s meet the

complementary slackness conditions

41

41

Example: Second Trial (3)

m1 = m3 = m 4 = m6 = 0
¶
º 8 + 0.2P1 - l - m2 = 0 Þ m2 = 9.8 $/MWh
¶P1
¶
º 7 + 0.12P2 - l = 0 Þ l = 44.2 $/MWh
¶P2
¶
º 9 + 0.14P3 - l + m5 = 0 Þ m5 = -1.2 $/MWh
¶P3
£ 0! 42

42

21
 02/22/20

Example: Second Trial (4)

The constraint P3 £ P3max should not be binding!

What is happening?

First trial:

P1
P1
P1min P1max

P2
P2
P2min P2max

P3
P3
P3min P3max 43

43

Example: Second Trial (5)

In the second trial, we “pushed” P1 towards its lower limit and P3
towards its upper limit. However, there was no need to push P3
because increasing P1 would naturally reduce P3 below its limit.

Second trial:
P1

P1
P1
min P1max

P2
P2
P2min P2max
P3
P3
P3min P3max 44

44

22
 02/22/20

Example: Third Trial (1)

P1 = P1min = 230 MW Þ m2 ¹ 0
m1 = m 3 = m 4 = m5 = m6 = 0

¶
º 7 + 0.12P2 - l = 0
¶P2 l = 44.75 $/MWh
¶ P2 = 315 MW
º 9 + 0.14P3 - l = 0
¶P3
P3 = 255 MW
¶
º L - P1 - P2 - P3 = 0
¶l 45

45

Example: Third Trial (2)

¶
º 8 + 0.2P1 - l - m2 = 0 Þ m2 = 9.25 $/MWh
¶P1
Solution that satisfies all the optimality conditions:

P1 = 230 MW
P2 = 315 MW
P3 = 255 MW
l = 44.75 $/MWh  Cost of an extra MW of load
m2 = 9.25 $/MWh  Value of reducing P1min by 1MW
46

46

23
 02/22/20

Example: Optimal Solution

Third trial:
P1

P1
P1min P1max
P2
P2
P2min P2max
P3
P3
P3min P3max 47

47

Practical Economic Dispatch

48

24
 02/22/20

Equal Incremental Cost Dispatch

dC A dC B dC C
dPA dPB dPC

PA PB PC

PA + PB + PC 49

49

Lambda search algorithm

1. Choose a starting value for l

dC A (PA ) dC B (PB ) dCC (PC )

2. Calculate PA ,PB ,PC such that = = =l
dPA dPB dPC

3. If one of these values exceeds its lower or upper limit, fix it at that limit

4. Calculate PTOTAL = PA + PB + PC

5. If PTOTAL < L, then increase l

Else If PTOTAL > L, then decrease l
Else If PTOTAL » L, then exit

6. Go To Step 2 50

50

25
 02/22/20

Linear Cost Curves

CA CB

PA PB

PA MAX PB MAX

dC A dC B
dPA dPB

l
PA PB

PA MAX PB MAX

51

51

Linear Cost Curves

CA CB

PA PB

PA MAX PB MAX

dC A dC B
dPA dPB

l
PA PB

PAMAX PBMAX
52

52

26
 02/22/20

Linear Cost Curves

CA CB

PA PB

PA MAX PB MAX

dC A dC B
dPA dPB

PA PB

PA MAX PB MAX

53

53

Linear Cost Curves

• The output of the unit with the lowest
incremental cost (in this case unit A) is
increased first (it is “loaded” first)
• The output of the other units is not increased
until unit A is loaded up to its maximum
• The output of the unit with second lowest
incremental cost is then increased (i.e. the
“second cheapest” unit)
• And so on until the generation meets the load
54

54

27
 02/22/20

Linear cost curves with minimum generation

CA CB

PA PB

PA MIN PA MAX PB MIN PB MAX

dC A dC B
dPA dPB

PA PB

PA MIN PA MAX PB MIN PB MAX

55

55

Linear cost curves with minimum

generation
• All generating units are first loaded up to their
minimum generation
• The generating units are then loaded in order
of incremental cost

56

56

28
 02/22/20

Piecewise Linear Cost Curves

CA CB

PA PB

dC A dC B
dPA dPB

PA PB

57

57

Economic Dispatch with Piecewise Linear Cost Curves

CA CB

PA PB

dC A dC B
dPA dPB

l
PA PB

58

58

29
 02/22/20

Economic Dispatch with Piecewise Linear Cost Curves

CA CB

PA PB

dC A dC B
dPA dPB

l
PA PB

59

59

Economic Dispatch with Piecewise Linear Cost Curves

CA CB

PA PB

dC A dC B
dPA dPB

PA PB

60

60

30
 02/22/20

Economic Dispatch with Piecewise Linear Cost Curves

CA CB

PA PB

dC A dC B
dPA dPB

PA PB

61

61

Economic Dispatch with Piecewise Linear Cost Curves

CA CB

PA PB

dC A dC B
dPA dPB

PA PB

62

62

31
 02/22/20

Economic Dispatch with Piecewise Linear Cost Curves

• All generators except one are at breakpoints of their cost

curve
• The marginal generator is between breakpoints to balance the
load and generation
• Not well-suited for lambda-search algorithm
• Very fast table lookup algorithm:
– Rank all the segments of the piecewise linear cost
curves in order of incremental cost
– First dispatch all the units at their minimum
generation
– Then go down the table until the generation
matches the load

63

63

Example
dC A
dPA
Unit PSegment Ptotal Lambda
0.7 A&B min 20+30 = 50 50
B 70-20=50 100 0.1
0.5
0.3 A 80-30=50 150 0.3
A 120-80=40 190 0.5
30 80 120 150 PA B 110-70=40 230 0.6
A 150-120=30 260 0.7
B 140-110=30 290 0.8
dC B
dPB

0.8 If Pload = 210MW

0.6 The optimal economic dispatch is:
PA = 120MW
0.1 PB = 90 MW
20 70 110 140
PB λ = 0.6
64

64

32