Simultaneous optimal auctions using augmented lagrangian and surrogate optimization

• US 20050137959A1
• Filed: 12/23/2003
• Published: 06/23/2005
• Est. Priority Date: 10/24/2003
• Status: Active Grant

• Current Assignee: Southern California Edison Company (Edison International), University of Connecticut (State of Connecticut)
• Original Assignee: Southern California Edison Company (Edison International)
• Inventors: Zhao, Feng, Chen, Ying, Blankson, William E., Luh, Peter B., Stern, Gary A., Ma, Yaming, Yan, Joseph H., Ni, Ernan
• Granted Patent: US 7,599,866 B2
• Time in Patent Office: Days
• US Class Current: 705/37
• CPC Class Codes: G06Q 20/102 Bill distribution or payments
• CPC Class Codes: G06Q 30/08 Auctions
• CPC Class Codes: G06Q 40/00 Finance; Insurance; Tax strategies; Processing of corporate or income taxes
• CPC Class Codes: G06Q 40/04 Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange

Abstract

A method for determining a market clearing price in an electricity market, subject to a plurality of constraints, comprising the steps of defining an objective function relating the MCP and constraints in terms of a nonlinear programming expression, applying Lagrangian relaxation to the nonlinear programming expression to form a Lagrangian dual function; adding penalty terms to the Lagrangian dual function to form an augmented Lagrangian dual function; resolving the augmented Lagrangian dual function using a surrogate optimization framework comprising repeating, until stopping criteria are satisfied, the steps of forming one or more supply sub-problems and an MCP sub-problem; optimizing the MCP sub-problem while keeping all other variables at their latest available values; optimizing at least one of the one or more supply sub-problems while keeping all other variables at their latest available values; updating multipliers used to relax constraints; determining the MCP in accordance with the resolved augmented Lagrangian dual function; and paying for electricity at the MCP. A system is also provided.

Claims

1. A method for determining a market price, subject to a plurality of constraints and an actual purchase cost, comprising the steps of:

defining an objective function relating the market price and constraints in terms of a nonlinear programming expression, and

minimizing the objective function consistent with the actual purchase cost.

2. The method of claim 1, where the objective function comprises a sum over all market suppliers of the market price times the amount purchased plus the supplier'"'"'s capacity related cost.

3. The method of claim 1, where the objective function is:

$J\equiv <br><br>\underset{t=1}{\overset{T}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{i=1}{\overset{I}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left\{\mathrm{MCP}<br><br>\left(t\right)<br><br>p_i<br><br>\left(t\right)+S_i<br><br>\left(t\right)\right\}$

and MCP(t) is the 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.

4. The method of claim 1, where the constraints include transmission network constraints.

5. The method of claim 1, where the market price is a market clearing price.

6. The method of claim 1, where the market price is a locational marginal price.

7. The method of claim 1, where the market price is a treasury bill price.

8. The method of claim 1, where the step of minimizing the objective function comprises the steps of:

applying Lagrangian relaxation to the nonlinear programming expression to form a Lagrangian dual function;

resolving the Lagrangian dual function using a surrogate optimization framework comprising 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 while keeping all other variables at their latest available values; and

updating multipliers used to relax constraints; and

determining the market price in accordance with the resolved Lagrangian dual function.

9. The method of claim 8, further comprising the step of adding penalty terms to the Lagrangian dual function to form an augmented Lagrangian dual function.

10. The method of claim 9, where the augmented Lagrangian relationship is:

${\stackrel{\_}{L}}_c<br><br>\left(\mathrm{\lambda <br><br>},{\mathrm{\eta <br><br>}}_i,p_i,\mathrm{MCP}\right)\equiv <br><br>\underset{t=1}{\overset{T}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left\{f<br><br>\left(t\right)+\mathrm{\lambda <br><br>}<br><br>\left(t\right)<br><br>h<br><br>\left(t\right)+0.5<br><br>c<br><br>{<br><br>h<br><br>\left(t\right)<br><br>}^2\right\}+\underset{i=1}{\overset{I}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left({\mathrm{\eta <br><br>}}_i<br><br>\left(t\right)<br><br>\left(g_i<br><br>\left(t\right)+z_i^2<br><br>\left(t\right)\right)+0.5<br><br>c<br><br>{<br><br>g_i<br><br>\left(t\right)+z_i^2<br><br>\left(t\right)<br><br>}^2\right)$

where z_i²(t) is a non-negative slack variable.

11. The method of claim 9, where one or more sub-problems are solved by using backward dynamic programming.

12. The method of claim 9, each of the one or more supply sub-problems being associated with an offer i, where the supply sub-problem for offer i is formed as:

$\underset{\left\{p_i<br><br>\left(t\right)\right\}}{\min }<br><br>L_i,\mathrm{with}<br><br>\text{\hspace{1em}<br><br>}<br><br>L_i\equiv <br><br>\underset{t=1}{\overset{T}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left\{\left(\mathrm{MCP}<br><br>\left(t\right)-\mathrm{\lambda <br><br>}<br><br>\left(t\right)\right)<br><br>p_i<br><br>\left(t\right)+S_i<br><br>\left(t\right)+0.5<br><br>c\left({p_i<br><br>\left(t\right)}^2-2<br><br>p_i<br><br>\left(t\right)<br><br>\left(P_d<br><br>\left(t\right)-\underset{j=1,j\ne <br><br>i}{\overset{I}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>p_j<br><br>\left(t\right)\right)\right)+\frac{{\left[\max <br><br>\left\{0,{\mathrm{\eta <br><br>}}_i<br><br>\left(t\right)+c<br><br>\left(O_i^r<br><br>\left(p_i<br><br>\left(t\right),t\right)-\mathrm{MCP}<br><br>\left(t\right)\right)\right\}\right]}^2-{{\mathrm{\eta <br><br>}}_i<br><br>\left(t\right)}^2}{2<br><br>c}\right\}$

where {p_i(t)} are the decision variables and all other decision variables are taken at their latest available values.

13. The method of claim 9, the market price sub-problem being associated with a time t, where the market price sub-problem for time t is formed as:

$\underset{\mathrm{MCP}<br><br>\left(t\right)}{\min }<br><br>L_{\mathrm{MCP}<br><br>\left(t\right)},\mathrm{with}<br><br>\text{\hspace{1em}<br><br>}<br><br>L_{\mathrm{MCP}<br><br>\left(t\right)}\equiv <br><br>\left(\underset{i=1}{\overset{I}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>p_i<br><br>\left(t\right)\right)<br><br>\mathrm{MCP}<br><br>\left(t\right)+\frac{\underset{i=1}{\overset{I}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\left[\max <br><br>\left\{0,{\mathrm{\eta <br><br>}}_i<br><br>\left(t\right)+c<br><br>\left(O_i^r<br><br>\left(p_i<br><br>\left(t\right),t\right)-\mathrm{MCP}<br><br>\left(t\right)\right)\right\}\right]}^2}{2<br><br>c}$

and decision variables other than MCP(t) are taken at their latest available values.

14. The method of claim 9, where the Lagrange multipliers are updated based upon either the Surrogate Multiplier Method formulas:

λ

^k+1(t)=λ

^k(t)+c^kS_λ

(t),

and

η

_i^k+1(t)=max(0, η

_i^k(t)+c^kS<sub>η

i</sub>(t));

or the Surrogate Subgradient Method formulas;

λ

^k+1(t)=λ

^k(t)+α

^kS_λ

(t),

and

η

_i^k+1(t)=max(0, η

_i^k(t)+α

^kS<sub>η

i</sub>(t)),

where α

^k is an appropriate step size at an iteration k.

15. The method of claim 1, where the step of minimizing the objective function comprises the steps of:

applying Lagrangian relaxation to the nonlinear programming expression to form a Lagrangian dual function;

resolving the Lagrangian dual function using a surrogate optimization framework comprising repeating, until stopping criteria are satisfied, the steps of;

forming one or more supply sub-problems;

determining a maximum selected supply offer by optimizing at least one of the one or more supply sub-problems while keeping all other variables at their latest available values;

setting the market price equal to the maximum selected supply offer while keeping all other variables at their latest available values;

updating multipliers used to relax constraints; and

determining the market price in accordance with the resolved Lagrangian dual function.

17. The method of claim 1, where the objective function comprises a sum over all market suppliers of the market price for ancillary services times the amount purchased plus a capacity compensation for the supplier'"'"'s capacity related cost.

18. The method of claim 17, where the ancillary services comprise one or more of energy, regulation, spinning reserve, and non-spinning reserve.

19. The method of claim 1, where the objective function is:

$J\equiv <br><br>\underset{i=1}{\overset{I}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(\underset{t=1}{\overset{T}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left({\mathrm{MCP}}^E<br><br>\left(t\right)<br><br>P_i^E<br><br>\left(t\right)+{\mathrm{MCP}}^R<br><br>\left(t\right)<br><br>P_i^R<br><br>\left(t\right)+{\mathrm{MCP}}^S<br><br>\left(t\right)<br><br>P_i^S<br><br>\left(t\right)+{\mathrm{MCP}}^N<br><br>\left(t\right)<br><br>P_i^N<br><br>\left(t\right)\right)+{\tilde{S}}_i\right)$

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 an offer i at an hour t, and {tilde over (S)}_i is the capacity compensation for the offer i.

20. The method of claim 1, where the step of minimizing the objective function comprises the steps of:

applying Lagrangian relaxation to the nonlinear programming expression to form a Lagrangian dual function;

resolving the Lagrangian dual function using a surrogate optimization framework comprising repeating, until stopping criteria are satisfied, the steps of;

forming 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 demand sub-problems while keeping all other variables at their latest available values; and

updating multipliers used to relax constraints; and

determining the market price in accordance with the resolved Lagrangian dual function.

16. A method for determining a market clearing price (MCP) in an electricity market, subject to a plurality of constraints, comprising the steps of:

defining an objective function relating the MCP and constraints in terms of a nonlinear programming expression,

applying Lagrangian relaxation to the nonlinear programming expression to form a

Lagrangian dual function;

adding penalty terms to the Lagrangian dual function to form an augmented Lagrangian dual function;

resolving the augmented Lagrangian dual function using a surrogate optimization framework comprising repeating, until stopping criteria are satisfied, the steps of;

forming one or more supply sub-problems and an MCP sub-problem;

optimizing the MCP sub-problem while keeping all other variables at their latest available values;

optimizing at least one of the one or more supply sub-problems while keeping all other variables at their latest available values; and

updating multipliers used to relax constraints;

determining the MCP in accordance with the resolved augmented Lagrangian dual function; and

paying for electricity at the MCP.

21. A system for determining a market price, subject to a plurality of constraints and an actual purchase cost, comprising:

a data processing system in communication with a mass storage device;

a computer readable mass storage medium useable in the mass storage device, containing program instructions;

encoding an objective function relating the market price and constraints in terms of a nonlinear programming expression, and

sufficient to cause the data processing system to perform the step of minimizing the objective function consistent with the actual purchase cost.

22. The system of claim 21, where the objective function comprises a sum over all market suppliers of the market price times the amount purchased plus the supplier'"'"'s capacity related cost.

23. The system of claim 21, where the objective function is:

$J\equiv <br><br>\underset{t=1}{\overset{T}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{i=1}{\overset{I}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left\{\mathrm{MCP}<br><br>\left(t\right)<br><br>p_i<br><br>\left(t\right)+S_i<br><br>\left(t\right)\right\}$

and MCP(t) is the market clearing price during time t, p_i(t) is the amount purchased from supplier i during time t, and S_i(t) is the capacity related cost of supplier i during time t.

24. The system of claim 21, where the constraints include transmission network constraints.

25. The system of claim 21, where the market price is a market clearing price.

26. The system of claim 21, where the market price is a locational marginal price.

27. The system of claim 21, where the market price is a treasury bill price.

28. A system for determining a market clearing price (MCP) in an electricity market, subject to a plurality of constraints, comprising:

a data processing system in communication with a mass storage device;

a computer readable mass storage medium useable in the mass storage device, containing program instructions;

encoding an objective function relating the MCP and constraints in terms of a nonlinear programming expression, and

sufficient to cause the data processing system to perform the steps of;

resolving the nonlinear programming expression using a surrogate optimization framework; and

determining the MCP in accordance with the resolved nonlinear programming expression.

29. A computer readable mass storage medium useable in a mass storage device to determine a market price, subject to a plurality of constraints and an actual purchase cost, containing program instructions:

encoding an objective function relating the market price and constraints in terms of a nonlinear programming expression, and

sufficient to cause a data processing system to perform the step of minimizing the objective function consistent with the actual purchase cost.