Simultaneous optimal auctions using augmented lagrangian and surrogate optimization
View Patent ↗A method for determining a market clearing price (“MCP”) in an electricity market, in which an objective function relates the MCP and constraints in terms of a nonlinear programming expression, and the MCP is found by resolving an augmented Lagrangian dual function using a surrogate optimization framework. A system is also provided.
1. A system for determining an electricity market clearing price, subject to a plurality of constraints and an actual purchase cost, comprising:
a data processing system in communication with a mass storage device;
the mass storage device tangibly embodying program instructions that when executed by the data processing system perform the method steps of:
encoding an objective function relating the electricity market clearing price and plurality of constraints in terms of a nonlinear programming expression;
forming a Lagrangian dual function from the objective function;
resolving the Lagrangian dual function using a surrogate optimization framework and the actual purchase cost; and
determining the market price as a function of the resolved Lagrangian dual function where the encoded objective function is:
J
≡
∑
t
=
1
T
∑
i
=
1
I
{
MCP
(
t
)
p
i
(
t
)
+
S
i
(
t
)
}
and MCP(t) is the electricity market clearing price during time t, p i (t) is the amount purchased from a supplier i during a time t, and S i (t) is the capacity related cost of the supplier i during the time t.
2. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for determining an electricity market clearing price, subject to a plurality of constraints and an actual purchase cost, said method steps comprising:
encoding an objective function relating the electricity market clearing price and plurality of constraints in terms of a nonlinear programming expression;
forming a Lagrangian dual function from the objective function;
resolving the Lagrangian dual function using a surrogate optimization framework and the actual purchase cost; and
determining the market price as a function of the resolved Lagrangian dual function where the encoded objective function is:
J
≡
∑
t
=
1
T
∑
i
=
1
I
{
MCP
(
t
)
p
i
(
t
)
+
S
i
(
t
)
}
and MCP(t) is the electricity market clearing price during time t, p i (t) is the amount purchased from a supplier i during a time t, and S i (t) is the capacity related cost of the supplier i during the time t.
3. The article of claim 2 , where the plurality of constraints comprise transmission network constraints.
4. The article of claim 2 , where the forming of a Lagrangian dual function comprises applying Lagrangian relaxation to the nonlinear programming expression; and the surrogate optimization framework comprises repeating, until stopping criteria are satisfied, the steps of:
forming one or more supply sub-problems and a market price sub-problem;
optimizing the market price sub-problem while keeping all other variables at their latest available values;
optimizing at least one of the one or more supply sub-problems; and
updating multipliers used to relax constraints.
5. The article of claim 4 , where the forming of a Lagrangian dual function further comprises augmenting the Lagrangian dual function with one or more penalty terms.
6. The article of claim 5 , where the Lagrangian dual function is:
L
_
c
(
λ
,
η
i
,
p
i
,
MCP
)
≡
∑
t
=
1
T
{
f
(
t
)
+
λ
(
t
)
h
(
t
)
+
0.5
c
h
(
t
)
2
}
+
∑
i
=
1
I
(
η
i
(
t
)
(
g
i
(
t
)
+
z
i
2
(
t
)
)
+
0.5
c
g
i
(
t
)
+
z
i
2
(
t
)
2
)
where L c is the Lagrangian dual function, f(t) is the objective function, h(t) is a demand balance constraint at a time t and λ(t) is an associated Lagrange multiplier, p i is a decision variable of a bid i, MCP is the market clearing price, z i 2 (t) is a non-negative slack variable at time t and η j (t) is an associated Lagrange multiplier, g i (t) is an MOP-bid inequality constraint, and c is a penalty term coefficient.
7. The article of claim 5 , where one or more sub-problems are solved by using backward dynamic programming.
8. The article of claim 5 , where each of the one or more supply sub-problems being associated with a bid i, where the supply sub-problem for bid i is formed as:
min
{
p
i
(
t
)
}
L
i
,
with
L
i
≡
∑
t
=
1
T
{
(
MCP
(
t
)
-
λ
(
t
)
)
p
i
(
t
)
+
S
i
(
t
)
+
0.5
c
(
p
i
(
t
)
2
-
2
p
i
(
t
)
(
P
d
(
t
)
-
∑
j
=
1
,
j
≠
i
I
p
j
(
t
)
)
)
+
[
max
{
0
,
η
i
(
t
)
+
c
(
O
i
r
(
p
i
(
t
)
,
t
)
-
MCP
(
t
)
)
}
]
2
-
η
i
(
t
)
2
2
c
}
where {p i (t)} are the decision variables of bid i during a time t, {p j (t)} j≠i are decision variables of bids other than bid i, λ(t) is a multiplier associated with the system demand constraint during time t; MCP(t) is a market clearing price during time t, O i r (p i (t),t) is a redefined bidprice, η i (t) a multiplier associated with MCP-bid inequality constraint during time t; S i (t) is a capacity related cost of a supplier i during the time t, P d (t) is a system demand during time t, and c is a penalty term coefficient.
9. The article of claim 5 , where the market price sub-problem is associated with a time t, where the market price sub-problem for time t is formed as:
min
MCP
(
t
)
L
MCP
(
t
)
,
with
L
MCP
(
t
)
≡
(
∑
i
=
1
I
p
i
(
t
)
)
MCP
(
t
)
+
∑
i
=
1
I
[
max
{
0
,
η
i
(
t
)
+
c
(
O
i
r
(
p
i
(
t
)
,
t
)
-
MCP
(
t
)
)
}
]
2
2
c
where p i (t) is a decision variable of a bid i during time t, MCP(t) is the market clearing price during time t, O i r (p i (t),t) is a redefined bid price, η i (t) is a multiplier associated with MCP-bid inequality constraint during time t, and c is a penalty term coefficient.
10. The article of claim 5 , where the multipliers are updated based upon either the Surrogate Multiplier Method formulas:
λ k+1 ( t )=λ k ( t )+ c k S λ
and
η i k+1 ( t )=max(0,η 1 k ( t )+ c k S η1 )
or the Surrogate Subgradient Method formulas:
λ k+1 ( t )=λ k ( t )+α k S λ
and
η i k+1 ( t )=max(0,η i k ( t )+α k S ηi ( t ))
where α k an appropriate step size at an iteration k, c k is a penalty term coefficient at iteration k, λ k ( t ) is a multiplier associated with a system demand constraint during a time t at iteration k, η i k ( t ) is a multiplier associated with MCP-bid inequality constraint during time t at iteration k, S λ ( t ) is a component for λ(t) of a surrogate subgradient vector, and S ηi ( t ) is a component for η i ( t ) of the surrogate subgradient vector.
11. The article of claim 2 , where the encoded objective function is:
J
≡
∑
i
=
1
I
(
∑
t
=
1
T
(
MCP
R
(
t
)
P
i
R
(
t
)
+
MCP
E
(
t
)
P
i
E
(
t
)
+
MCP
S
(
t
)
P
i
S
(
t
)
+
MCP
N
(
t
)
P
i
N
(
t
)
)
+
S
i
~
)
and MCP E (t), MCP R (t), MCP S (t), and MCP N (t) are, respectively, market clearing prices for energy, regulation, spinning reserve, and non-spinning reserve markets during time t; P i E (t), P i R (t), P i S (t), and P i N (t) are respectively selected energy, regulation, spinning reserve, and non-spinning reserve prices for a bid i at an hour t, and {tilde over (S)} i is the capacity compensation for the offer i.
12. The article of claim 2 , where the surrogate optimization framework comprises repeating, until stopping criteria are satisfied, the steps of:
forming one or more supply sub-problems, one or more demand sub-problems and a market price sub-problem;
optimizing the market price sub-problem while keeping all other variables at their latest available values;
optimizing at least one of the one or more supply sub-problems;
optimizing at least one of the one or more demand sub-problems; and
updating multipliers used to relax constraints.