# Storage Optimal Control under Net Metering Policies

Md Umar Hashmi1, Arpan Mukhopadhyay2, Ana Bušić1, and Jocelyne Elias3 1M.U.H.
and A.B are with INRIA, DI ENS, Ecole Normale Supérieure, CNRS, PSL Research
University, Paris, France.2A.M is with Department of Computer Science,
University of Warwick. 3J.E. is with DISI, University of Bologna, Italy,
E-mail<EMAIL_ADDRESS>
###### Abstract

Electricity prices and the end user net load vary with time. Electricity
consumers equipped with energy storage devices can perform energy arbitrage,
i.e., buy when energy is cheap or when there is a deficit of energy, and sell
it when it is expensive or in excess, taking into account future variations in
price and net load. Net metering policies indicate that many of the utilities
apply a customer selling rate lower than or equal to the retail customer
buying rate in order to compensate excess energy generated by end users. In
this paper, we formulate the optimal control problem for an end user energy
storage device in presence of net metering. We propose a computationally
efficient algorithm, with worst case run time complexity of quadratic in terms
of number of samples in lookahead horizon, that computes the optimal energy
ramping rates in a time horizon. The proposed algorithm exploits the problem’s
piecewise linear structure and convexity properties for the discretization of
optimal Lagrange multipliers. The solution has a threshold-based structure in
which optimal control decisions are independent of past or future price as
well as of net load values beyond a certain time horizon, defined as a sub-
horizon. Numerical results show the effectiveness of the proposed model and
algorithm. Furthermore, we investigate the impact of forecasting errors on the
proposed technique. We consider an Auto-Regressive Moving Average (ARMA) based
forecasting of net load together with the Model Predictive Control (MPC). We
numerically show that adaptive forecasting and MPC significantly mitigate the
effects of forecast error on energy arbitrage gains.

##  I Introduction

The share of total energy consumed worldwide by commercial and residential
buildings is around 20% and is projected to grow at an average rate of 1.4%
per year from 2012 to 2040 [1]. The environmental benefit of connecting more
renewable energy sources in meeting the global energy demand is, therefore,
irrefutable. Nowadays, utilities encourage end users to install distributed
generation (DG) sources to satisfy their own energy demands as well as that of
others in the grid [2]. Any excess power generated by such sources is bought
back by the grid and compensated at every billing cycle (monthly or yearly).
This is achieved by Net Metering, which facilitates bi-directional power flow
to and from an end user. Net metering is a policy designed to encourage
private investment in renewable energy [3]. The fruits of this policy are
already visible in California, where more than one million solar projects with
a cumulative capacity exceeding 7 GW [4] are operational.

Future adoption of DG is sensitive to the net-metering policy adopted to
compensate for a surplus generation. A favorable retail rate would accelerate
DG installations [5]. However, incentivizing DG owners pushes utilities to
increase charges per kWh for all the customers, creating a disadvantage for
non-DG compared to DG owners [6]. Therefore, utilities have to find a balance
between promoting DG and penalizing non-DG owners with higher electricity
rates [4]. As a result, net metering policies vary significantly by country
and by state or province. For instance, in the US each state has its own
mechanism for consumer based DGs. Net-Energy Metering or NEM can be
categorized into NEM 1.0 and NEM 2.0, which are the two versions of net-
metering policy in California. NEM 1.0 refers to a policy where buying and
selling prices are equal. When number of users with DG reaches a set cap,
additional users are compensated at a rate lower than retail rate. This
version of net-metering is referred as NEM 2.0 [7, 8]. Similar compensation
mechanisms for surplus consumer generation are also in use in other regions
[3].

Combining energy storage with renewables holds several benefits for storage
owners. For example, the Salt Lake Project in Phoenix Arizona (1995)
demonstrated that the consumption peak and the solar PhotoVoltaic (PV)
generation peak are not aligned. Therefore, energy storage provides
flexibility in using the surplus generation when the demand is high [9].
Storage also adds an economic value to consumers by enabling the use of the
stored energy based on the electricity prices [10] and the user’s own energy
demand. This is achieved through energy arbitrage, i.e., buying energy from
the grid when the buying price is lower and there is not enough stored energy
and selling energy to the grid when the selling price is high and enough
stored energy is available. The design of electricity prices indicates that
energy arbitrage will be more profitable with greater integration of
renewables leading to more volatile electricity prices [11, 12].

In this paper, we formulate the energy arbitrage problem as an optimization
problem under NEM 2.0 net-metering policies (with unequal buying and selling
electricity prices). This formulation also applies to the NEM 1.0 policy as a
special case. Time of operation of the storage is divided into discrete
intervals called instants where the prices remain constant. We show that the
cost function of the arbitrage problem (the sum of the costs of all instants)
is convex and piecewise linear. However, as shown later in the paper, standard
linear programming (LP) based algorithms and convex optimization solvers are
not very efficient for real time operations of storage especially when large
volumes of price data need to be handled. We, therefore, propose an algorithm
based on the Lagrangian dual of the original arbitrage problem. Exploiting the
fact that the objective function is piecewise linear we derive the optimal
action at each instant as a function of the current state of the battery and
the value of an accumulated Lagrange multiplier at that instant which captures
the information about electricity prices at all future instants. We observe
that the mapping between the optimal action and the accumulated Lagrange
multiplier at each instant has a threshold structure. Based on this threshold
structure we propose a fast and efficient way of finding the optimal
accumulated Lagrange multiplier values and corresponding optimal actions at
each instant. Numerical comparisons show that the proposed algorithm is orders
of magnitude faster than standard solvers and is, therefore, suitable for
real-time use with large volumes of price data to process at each instant. The
key contributions of this paper are given below:
$\quad\bullet$ Formulation: We formulate the optimal arbitrage problem under
NEM 2.0 policies as an optimization problem and show that the problem is
convex when expressed in terms of the energy level differences between
consecutive instances.
$\quad\bullet$ Optimal actions: Exploiting the convexity and the piecewise
linear nature of the cost function, we derive a closed form expression of the
optimal action at each instant as a function of an accumulated Lagrange
multiplier that captures the information about future electricity prices,
battery constrains, and charging and discharging efficiencies. This mapping
has a discrete threshold based structure which allows us to devise an
efficient algorithm to find the optimal accumulated Lagrange multiplier values
and the associated optimal actions. The worst case time complexity of the
algorithm is found to be $O(N^{2})$, where $N$ is the number of discrete time
steps. Numerical case-study is presented in Section VIII, where we compare the
run-time of the proposed algorithm over LP- and convex optimization-based
benchmarks.
$\quad\bullet$ Sub-horizon selection: We observe that in order to determine
the optimal action in a certain period within the total time horizon it is
sufficient to consider prices only within a sub-horizon, which is often much
smaller than the entire horizon.
The length of sub-horizon depends on storage constraints and the electricity
price variation. Using this observation we considerably speed up our algorithm
which only needs to look at a small subset of future price data to make
optimal decision.
$\quad\bullet$ Numerical evaluation: We compare our proposed algorithm with
other commercial solvers and observe orders of magnitude improvement in
efficiency. For real-time implementation of the proposed algorithm, we apply
an ARMA-based forecast model with model predictive control (MPC) and
numerically analyze the effect of forecast errors on arbitrage gains using
real data from Pecan Street [13] and ERCOT price data [14].

###  I-A Related work

The problem of optimal energy arbitrage using storage has been the subject of
many recent works e.g., [15, 16, 17, 18]. In [15, 19, 20] a system with
rooftop solar PV and energy storage for a residential setting has been
considered. However, selling of the stored energy to the grid is not allowed
in [15], where an MDP-based approach has been taken to tackle the arbitrage
problem where the future costs are discounted by a constant factor. In [15,
21], [22, 23] it has been shown that the optimal decisions for arbitrage have
a threshold based structure. In this paper, we explore a similar structure for
NEM 2.0 net-metering policies where the buying and selling prices of
electricity can be unequal. Our work is inspired by the prior work of Cruise
et al [24, 25] where a general convex cost function has been considered for
energy arbitrage and the concept of accumulated Lagrange multiplier is
introduced. The concept of decision horizon is also described there and in
prior work [26]. However, due to the generality of the problem, finding the
optimal accumulated Lagrange multiplier was done through an exhaustive search
in a continuous range. In contrast, we deal with a piece-wise linear convex
cost function which enables us to derive a discrete set of threshold values
for the accumulated Lagrange multipliers. These discrete values enable us to
design a significantly more efficient algorithm to search for the optimal
Lagrange multipliers and their corresponding actions. Furthermore, our cost
function is non-differentiable due to which we propose an algorithm going
backward in time to choose the optimal action from an envelope of possible
actions. Finally, unlike [24] our formulation also considers consumer load and
DG.

We observe that under NEM 2.0 compensation, consumer inelastic load and
renewable generation time variation cannot be ignored as the case for NEM 1.0
[27], [28]. Modeling uncertainty in price and net load are essential for real-
time operation of energy storage. Authors in [29] use reinforcement learning
for real-time energy arbitrage. In [17], [30] a receding horizon dynamic
programming method for mitigating uncertainty has been investigated. [31]
proposes a deterministic setting for optimal storage control using spot market
prices of electricity available one day ahead. We use MPC with forecasting for
reducing the effect of uncertainty on arbitrage gains.

Organization: The paper is organized as follows. Section II introduces the
system model. Section III presents a mathematical framework and proposes an
algorithm for solving the arbitrage problem. Section IV presents a real-time
implementation of the proposed optimal arbitrage algorithm. Section V discuss
numerical results and section VI concludes the paper.

##  II System Description

We consider the operation of an electricity user over a fixed period of time.
The user is assumed to be equipped with renewable generation such as a rooftop
solar PV and a battery to store excess generation. It is also connected to the
electricity grid from where it can buy or to which it can sell energy. The
objective is to find an efficient algorithm for a user to make optimal
decisions over a period of varying electricity prices considering variations
in the solar generation and end user load. The total duration, $T$, of
operation is divided into $N$ steps, indexed by $\\{1,...,N\\}$, such that in
each step the buying and selling price of electricity remains constant. The
duration of step $i\in\\{1,...,N\\}$ is denoted as $h_{i}$. Hence,
$T=\sum_{i=1}^{N}h_{i}$. The price of electricity, $p_{\text{elec}}(i)$ is
given as

$p_{\text{elec}}(i)=\begin{cases}p_{b}(i),&\text{if consumption }\geq 0,\\\
p_{s}(i),&\text{otherwise,}\end{cases}\vspace{-7pt}$ (1)

Note $p_{\text{elec}}$ is ex-ante and the consumer is a price taker. The ratio
of selling and buying price is denoted as
$\kappa_{i}=\frac{p_{s}(i)}{p_{b}(i)}$. The end user inelastic consumption is
denoted as $d_{i}$ and renewable generation is given as $r_{i}$. Fig. 1 shows
the block diagram of the system, i.e., an electricity consumer with renewable
generation and battery. Net energy consumption without storage is denoted as
$z_{i}=d_{i}-r_{i}~{}\in\mathbb{R}$.

The efficiency of charging and discharging of the battery are denoted by
$\eta_{\text{ch}},\eta_{\text{dis}}\in(0,1]$, respectively. We denote the
change in the energy level of the battery at $i^{\text{th}}$ instant by
$x_{i}$= $h_{i}\delta_{i}$, where $\delta_{i}$ denotes the ramp rate such that
$\delta_{i}\in[\delta_{\min},\delta_{max}]$ $\forall~{}i$ and
$\delta_{\min}\leq 0,\delta_{\max}\geq 0$ are the minimum and the maximum ramp
rates (kW); $\delta_{i}>0$ implies charging and $\delta_{i}<0$ implies
discharging. Storage energy output is given as

$s_{i}=f(x_{i})=\frac{1}{\eta_{\text{ch}}}[x_{i}]^{+}-\eta_{\text{dis}}[x_{i}]^{-},\vspace{-6pt}$
(2)

where $x_{i}$ must lie in the range from $X_{\min}^{i}=\delta_{\min}h_{i}$ to
$X_{\max}^{i}={\delta_{\max}h_{i}}$. Note $[x_{i}]^{+}=\max(0,x_{i})$ and
$[x_{i}]^{-}=\max(0,-x_{i})$. Alternatively, we can write
$x_{i}=\eta_{\text{ch}}[s_{i}]^{+}-\frac{1}{\eta_{\text{dis}}}[s_{i}]^{-}$.
The limits on $s_{i}$ are given as

$s_{i}\in[S_{\min}^{i},S_{\max}^{i}],\text{where
}S_{\min}^{i}\text{=}\eta_{\text{dis}}X_{\min}^{i},S_{\max}^{i}\text{=}\frac{X_{\max}^{i}}{\eta_{\text{ch}}}.\vspace{-3pt}$
(3)

Let $b_{i}$ denote the energy stored in the battery at the $i^{\textrm{th}}$
step. The battery capacity is defined as

$b_{i}=b_{i-1}+x_{i},\quad b_{i}\in[b_{\min},b_{\max}],\forall i,$ (4)

where $b_{\min},b_{\max}$ are the minimum and the maximum battery capacity
(for avoiding over-charging and over-discharging). The total energy consumed
between time step $i$ and $i+1$ is given as $L_{i}=z_{i}+s_{i}$.

Figure 1: Behind-the-meter electricity consumer with inelastic consumption,
renewable generation and energy storage.

##  III Optimal Arbitrage Problem

The optimal energy arbitrage problem is defined as the minimization of the
cost of consumption subject to the battery constraints. It is given as
follows:

$\displaystyle\text{($P_{\text{NEM}}$)~{}~{}
}\min\sum_{i=1}^{N}C_{nm}^{i}(x_{i}),$ (5) $\displaystyle\text{subject to,
}b_{\min}-b_{0}\leq\sum_{j=1}^{i}x_{j}\leq b_{\max}-b_{0},~{}\forall
i\in\\{1,..,N\\},$
$\displaystyle\vspace{-12pt}x_{i}\in\left[X_{\min}^{i},X_{\max}^{i}\right]~{}\forall
i\in\\{1,..,N\\},$

where $C_{\text{nm}}^{i}(x_{i})$ denotes the energy consumption cost function
at instant $i$ and is given by

$C_{\text{nm}}^{i}(x_{i})=[z_{i}+f(x_{i})]^{+}p_{b}(i)-[z_{i}+f(x_{i})]^{-}p_{s}(i).$
(6)

######  Theorem III.1.

If $p_{b}(i)\geq p_{s}(i)$ for all $i=\\{1,...,N\\}$, then problem
($P_{\text{NEM}}$) is convex in $x$.

From Theorem III.1, which is proved in Appendix A, we note that
$P_{\text{NEM}}$ is convex as long as the buying prices are higher than or
equal to the selling prices. This is generally the case in most practical net
metering policies including NEM 2.0 policies [3], [32].

The convexity of ($P_{\text{NEM}}$) established above helps us exploit the
strong duality property with the dual problem (D). The Lagrangian of
$P_{\text{NEM}}$ is given by
$\mathscr{L}({x,\alpha,\beta})=\sum_{i=1}^{N}(C_{\text{nm}}^{(i)}(x_{i})+\alpha_{i}((b_{\min}-b_{0})-\sum_{j=1}^{i}x_{j})+\beta_{i}(\sum_{j=1}^{i}x_{j}-(b_{\max}-b_{0}))\vphantom{C_{\text{nm}}^{(i)}}).$
The Lagrangian dual of the primal problem is given by

$\displaystyle\text{(D)}\quad\max\phi({\alpha,\beta}),\quad\text{subject to,
}\alpha_{i},\beta_{i}\geq 0\quad\forall i,$
$\displaystyle\vspace{-5pt}\text{where
}\quad\phi({\alpha,\beta})=\inf_{f(x_{i})\in\left[S_{\min}^{i},S_{\max}^{i}\right]}\mathscr{L}({x,\alpha,\beta})\vspace{-7pt}$

To identify the optimal action at each instant as a function of the Lagrange
multipliers we use the following result from [24]. Note that we have adapted
the theorem to our setting in which we require a separate proof (see Appendix
B) because unlike [24] we do not require the initial and final level of energy
in the storage to be the same.

######  Theorem III.2.

There exists a tuple $(s^{*},x^{*},\mu^{*})$ with $N$-dimensional vectors such
that:

  1. 1.

$s_{i}^{*}=f(x_{i}^{*})\quad\forall i$.

  2. 2.

${x^{*}}=(x_{1}^{*},...,x_{N}^{*})$ is a feasible solution of the optimal
arbitrage problem ($P_{\text{NEM}}$).

  3. 3.

For each $i$, $x_{i}^{*}$ minimizes $C_{\text{nm}}^{(i)}(x)-\mu_{i}^{*}x$.
Here, $\mu_{i}^{*}$ is the optimal accumulated Lagrange multiplier for time
step $i$ and is related to the dual optimal solution $(\alpha^{*},\beta^{*})$
as follows $\mu_{i}^{*}=\sum_{j=i}^{N}(\alpha_{j}^{*}-\beta_{j}^{*})$.

  4. 4.

The optimal accumulated Lagrange multiplier, $\mu_{i}^{*}$, at any time step
$i$ satisfies the following recursive conditions:

     * •

$\mu_{i+1}^{*}=\mu_{i}^{*},\text{ if }b_{\min}<b_{i}^{*}<b_{\max}$,

     * •

$\mu_{i+1}^{*}\leq\mu_{i}^{*},\text{ if }b_{i}^{*}=b_{\min}$,

     * •

$\mu_{i+1}^{*}\geq\mu_{i}^{*},\text{ if }b_{i}^{*}=b_{\max}$.

  5. 5.

Additionally $\mu_{N}^{*}$ at the last instant $N$ satisfies

     * •

$\mu_{N}^{*}=0,\text{ if }b_{\min}<b_{N}^{*}<b_{\max}$,

     * •

$\mu_{N}^{*}\geq 0,\text{ if }b_{N}^{*}=b_{\min}$.

For any tuple $(s^{*},x^{*},\mu^{*})$ satisfying the above conditions,
${s^{*}}$ solves the optimal arbitrage problem ($P_{\text{NEM}}$).

The proof of Theorem III.2 is provided in Appendix B.

######  Remark 1.

From the above theorem we note that the optimal accumulated Lagrange
multiplier $\mu_{i}^{*}$ at the $i$th instant is defined as
$\mu_{i}=\sum_{j=i}^{N}(\alpha_{j}^{*}-\beta_{j}^{*})$. Since $\alpha_{j}^{*}$
and $\beta_{j}^{*}$ depend on the capacity constraints at the $j$th instant,
it is clear that $\mu_{i}^{*}$ depends on the decisions made in the future
instants $i$ through $N$. In other words, $\mu_{i}^{*}$ is the reduction in
the cost due to satisfying the constraints in all future instants. Thus, given
the value of $\mu_{i}^{*}$, in order to find the optimal action at instant $i$
it is sufficient to look for the minimizer of the cost function
$C_{nm}^{(i)}(x)-\mu_{i}^{*}x$ in the range $x\in[X_{\min}^{i},X_{\max}^{i}]$
ignoring the battery capacity constraints for all future instants.

We note that the optimality conditions stated in Theorem III.2 do not depend
on the particular structure of the cost function in $P_{\text{NEM}}$ and are
valid as long as it is a convex function of $x$. In the next subsection we
exploit the specific cost function in our setting to further characterize the
relationship between the optimal actions and the optimal accumulated Lagrange
multipliers. In particular we identify that for the specific cost function in
$P_{\text{NEM}}$ there exists a threshold structure in the optimal solution.

###  III-A Threshold Based Structure of the Optimal Solution

Statement (3) of Theorem III.2 shows that the optimal control decision
$x_{i}^{*}$ in the $i$th instant is the minimizer of
$C_{\text{nm}}^{(i)}(x)-\mu_{i}^{*}x$ for
$f(x_{i})\in\left[S_{\min}^{i},S_{\max}^{i}\right]$. This implies $x_{i}^{*}$
or equivalently $s_{i}^{*}$ is a function of the accumulated Lagrange
multiplier $\mu_{i}$ for time instant $i$. In the theorem below, we show that
the relationship between $s_{i}^{*}$ and $\mu$ is based on different threshold
values of $\mu$.

######  Theorem III.3.

Let $x_{i}^{*}(\mu)$ be the minimizer of the function
$C_{\text{nm}}^{(i)}(x)-\mu^{*}x$ in
$f(x_{i})\in\left[S_{\min}^{i},S_{\max}^{i}\right]$. Furthermore, let
$s_{i}^{*}(\mu)=f(x_{i}^{*}(\mu))$. Then $s_{i}^{*}(\mu)$ is a set valued map
and is given by

$\displaystyle
s_{i}^{*}(\mu)=\begin{cases}~{}\\{S_{\min}^{i}\\},\quad\quad\text{if
}\mu<\mu_{1}^{i},\text{\small\bf(Region 1)}\\\
\left[S_{\min}^{i},0\wedge(-z_{i}\vee S_{\min}^{i})\right],\text{if
}\mu=\mu_{1}^{i},\text{\small\bf(Region 2)}\\\ \\{0\wedge(-z_{i}\vee
S_{\min}^{i})\\},\text{if
}\mu\in(\mu_{1}^{i},\mu_{2}^{i}\wedge\mu_{3}^{i}),\\\ \hskip
85.35826pt\text{\small\bf(Region 3)}\\\ [0\wedge(-z_{i}\vee
S_{\min}^{i}),\mathbb{I}_{(\zeta_{i}<1)}\big{(}0\wedge(-z_{i}\vee
S_{\min}^{i})+\\\ 0\vee(-z_{i}\wedge S_{\max}^{i})\big{)}],\text{if
}\mu=(\mu_{2}^{i}\wedge\mu_{3}^{i}),\text{\small\bf(Region 4)}\\\
\\{\mathbb{I}_{(\zeta_{i}<1)}\big{(}0\wedge(-z_{i}\vee
S_{\min}^{i})+0\vee(-z_{i}\wedge S_{\max}^{i})\big{)}\\},\\\ \text{if
}\mu\in(\mu_{2}^{i}\wedge\mu_{3}^{i},\mu_{2}^{i}\vee\mu_{3}^{i}),\text{\small\bf(Region
5)}\vspace{4pt}\\\ [\mathbb{I}_{(\zeta_{i}<1)}\big{(}0\wedge(-z_{i}\vee
S_{\min}^{i})+0\vee(-z_{i}\wedge S_{\max}^{i})\big{)},\\\ 0\vee(-z_{i}\wedge
S_{\max}^{i})],\text{if
}\mu=(\mu_{2}^{i}\vee\mu_{3}^{i}),\text{\small\bf(Region 6)}\vspace{4pt}\\\
\\{0\vee(-z_{i}\wedge S_{\max}^{i})\\},\text{if
}\mu\in((\mu_{2}^{i}\vee\mu_{3}^{i}),\mu_{4}^{i}),\\\ \hskip
56.9055pt\text{\small\bf(Region 7)}\\\ \left[0\vee(-z_{i}\wedge
S_{\max}^{i}),~{}S_{\max}^{i}\right],\text{if
}\mu=\mu_{4}^{i},\text{\small\bf(Region 8)}\vspace{1pt}\\\
~{}\\{S_{\max}^{i}\\},\quad\quad\text{if
}\mu>\mu_{4}^{i},\text{\small\bf(Region 9)}\\\ \end{cases}\vspace{-10pt}$ (7)

where the four threshold points (based on which nine regions are defined, see
Fig. 2 and Fig. 21 in Appendix C-B) are given as (1)
$\mu_{1}^{i}=\eta_{\text{dis}}p_{s}(i)$, (2)
$\mu_{2}^{i}=\frac{p_{s}(i)}{\eta_{\text{ch}}}$, (3)
$\mu_{3}^{i}=\eta_{\text{dis}}p_{b}(i)$, (4)
$\mu_{4}^{i}=\frac{p_{b}(i)}{\eta_{\text{ch}}}$, and
$\zeta_{i}=\frac{\kappa_{i}}{\eta_{\text{ch}}\eta_{\text{dis}}}$. Here $(a\vee
b)$, $(a\wedge b)$ denote $\max(a,b)$ and $\min(a,b)$, respectively.

The proof of Theorem III.3 is provided in Appendix C. Based on the value of
$\zeta_{i}$ the thresholds are identified.

######  Remark 2.

Note that $s_{i}^{*}(\mu)$ is a set-valued function in $\mu$. Depending on the
value of $\mu$ the set $s_{i}^{*}(\mu)$ can take nine different values in
regions shown as Region 1 through Region 9 in Fig. 2 and Fig. 21 in Appendix
C-B which correspond to the cases $\zeta_{i}<1$ and $\zeta_{i}\geq 1$,
respectively. For each $i$ there are four threshold values
$\mu_{1}^{i},\mu_{2}^{i},\mu_{3}^{i},\mu_{4}^{i}$ at which $s_{i}^{*}(\mu)$
changes. From their expressions given above, it is clear that
$\mu_{1}^{i},\mu_{2}^{i},\mu_{3}^{i},$ and $\mu_{4}^{i}$ correspond to (1) the
effective discharging cost under selling price, (2) the effective charging
cost under selling price, (3) the effective discharging cost under buying
price, and (4) effective charging cost under buying price, respectively.

Figure 2: Regions based on levels of $\mu$ for $\zeta_{i}<1$

######  Remark 3.

We note that $s_{i}^{*}(\mu)$ is monotone non-decreasing map in $\mu$ in the
sense that for $\mu_{1}\leq\mu_{2}$ we have $s_{i}^{*}(\mu_{1})\preceq
s_{i}^{*}(\mu_{2})$, where for two sets $A$ and $B$ we say $A\preceq B$ (resp,
$A\prec B$) if $a\leq b$ (resp $a<b$) for all $a\in A$ and for all $b\in B$.
As a result, the sets $b_{i}^{*}(\mu)$, defined recursively as
$b_{i}^{*}(\mu)=b_{i-1}^{*}(\mu)+x_{i}^{*}(\mu)$ for $i\geq 1$ and
$b_{0}^{*}(\mu)=b_{0}$ are also monotonically non-decreasing in $\mu$. Here,
the addition of two intervals $[a,b]$ and $[c,d]$ denotes the interval
$[a+c,b+d]$.

For NEM 1.0, $p_{b}(i)=p_{s}(i)~{}\forall i$, therefore, the thresholds points
reduces to $\mu_{1}^{i}$ and $\mu_{4}^{i}$. Remark 4 illustrates the threshold
based structure for NEM 1.0.

######  Remark 4.

Note that $\kappa_{i}=1$ implies buying and selling price for time instant $i$
are the same, which corresponds to the NEM 1.0 policy. In case of NEM 1.0, the
optimal actions as derived in our earlier work [28] and can be recovered from
(7) by putting $\kappa_{i}=1$ and merging the regions together. The final
expression is given as follows:

$s_{i}^{*}(\mu)=\begin{cases}\\{S_{\min}^{i}\\},&\text{if
}\mu<\mu_{1}^{i}=p_{s}(i)\eta_{\text{dis}},\\\
\left[S_{\min}^{i},0\right],&\text{if }\mu=\mu_{1}^{i},\\\ \\{0\\},&\text{if
}\mu_{1}^{i}<\mu<p_{b}(i)/\mu_{4}^{i},\\\
\left[0,S_{\max}^{i}\right],&\text{if }\mu=\mu_{4}^{i},\\\
\\{S_{\max}^{i}\\},&\text{if
}\mu>\mu_{4}^{i}=p_{b}(i)/\eta_{\text{ch}},\vspace{-5pt}\end{cases}\vspace{-1pt}$
(8)

Clearly, when $\mu$ lies between $\mu_{1}^{i}$ and $\mu_{4}^{i}$, the optimal
action for the battery is to do nothing, and in this case the cycles of
operation that a battery performs can be controlled by introducing a friction
coefficient facilitating the elimination of low returning transactions [33,
34].

###  III-B Proposed Algorithm

In this section, we describe the algorithm we propose to solve the optimal
energy arbitrage problem formulated previously. The objective of the algorithm
is to find a tuple $(s^{*},x^{*},\mu^{*})$ that satisfies conditions (1)-(5)
of Theorem III.2, and therefore solves ($P_{\text{NEM}}$). The presented
algorithm can be operated for a variable value of $\kappa_{i}$, such that
$\kappa_{i}\in[0,1]~{}\forall~{}i$, covering all net-metering compensation
scheme. The threshold-based structure of the optimal solution (versus
$\kappa_{i}$) is selected using Theorem III.3 and Remark 4. In order to
identify storage actions, we propose a combination of a forward algorithm
(Algorithm 1) which identifies the sub-horizon and envelope of storage actions
and a backward algorithm (Algorithm 2) which runs one time in the identified
sub-horizon to decide the storage control trajectory. Algorithm 1 and
Algorithm 2 together perform optimal arbitrage.

####  III-B1 Description of Algorithm 1

According to the value of $\kappa_{i}$, the lower and upper bound of the
envelope are selected, lines 4–5 of the pseudo code of Algorithm 1. From
condition (4) of Theorem III.2, we can see that $\mu_{i+1}^{*}$ may differ
from the optimal accumulated Lagrange multiplier, $\mu_{i}^{*}$, only when
$b_{i}^{*}=b_{\max}$ or $b_{i}^{*}=b_{\min}$. Thus the value of $\mu$ remains
constant until the battery charge level at a time lies strictly within the
battery capacity limits. Following this key idea, we define the sub-horizon in
Remark 5.

######  Remark 5.

The whole duration $T$ is divided into $M$ periods, indexed as
$\left\\{1,2,\ldots,M\right\\}$. Each period contains a number of consecutive
time instants, such that for all instants $i$ belonging to the same period
$K\in\left\\{1,2,\ldots,M\right\\}$ the value of the accumulated Lagrange
multiplier $\mu_{i}^{*}$ remains the same, denoted as $\mu_{K}$. Each such
period is called sub-horizon.

It follows that at the end instant of each sub-horizon, the battery energy
level touches either $b_{\max}$ or $b_{\min}$. Note that the number of sub-
horizons ($M$), the start and end instants of each sub-horizon $K$, the
$\mu_{K}$ value, and the optimal actions in sub-horizon $K$ depend on the
problem instance and are determined recursively, as described below.

Assume that we have already identified the first $K-1$ ($K\geq 1$) sub-
horizons and determined the values of $s_{i}^{*}$ and $\mu_{i}^{*}$ in all
instants $i$ belonging to these sub-horizons (for $i\in[1,i_{K-1}]$). The
index $i_{K-1}$ denotes the last instant in the $(\\!K-1\\!)$th sub-horizon.
Hence:

  * If $i_{K-1}=N$, then we have already covered the whole period $T$ and the algorithm terminates.

  * If $i_{K-1}<N$, then we proceed to identify the next sub-horizon $K$, i.e., the values of $i_{K}$ (the last instant in sub-horizon $K$), and $\mu_{K}$, and the optimal decisions for the time instants $i\in[i_{K-1}+1,i_{K}]$.

To determine sub-horizon $K$, we start with instant $i_{K-1}+1$ and an initial
value of $\mu_{K}\geq 0$ for that sub-horizon111For the first sub-horizon
$K$=1 (that includes the first time instant) the starting guess value of
$\mu_{1}$ is taken to be $0$ and for every other sub-horizon $K>1$, the
starting guess value of $\mu_{K}$ is taken to be equal to $\mu_{K-1}$. Note
that these choices do not affect the solution given by the algorithm. . We
compute the values of $s_{i}^{*}(\mu_{K})$ and
$b_{i}^{*}(\mu_{K})$222$b_{i}^{*}(\mu_{K})$ is a set containing the values of
lower and upper envelope of optimal battery capacity for the scalar value of
$\mu_{K}$. according to the method described in Remark 4 and Theorem III.3,
for all consecutive time instants $i>i_{K-1}$ until we reach a time instant
$i=i_{\text{break}}$, for which one of the following conditions is satisfied
(we call these as the violation conditions):

  1. C1: $b_{i_{\text{break}}}^{*}(\mu_{K})\prec\left\\{b_{\min}\right\\}$.

  2. C2: $\left\\{b_{\max}\right\\}\prec b_{i_{\text{break}}}^{*}(\mu_{K})$.

  3. C3: $i_{\text{break}}=N,b_{\min}\notin b_{N}^{*}(\mu_{K}),\mu_{K}>0$.

If no $i_{\text{break}}$ is found even after reaching $i=N$, then $K$ is the
last sub-horizon and we set $i_{K}=N$ (and lines 31–36 of the pseudo code are
executed). From condition (5) of Theorem III.2, if $\mu_{K}>0$, then
$b_{N}^{*}=b_{\min}$; else $b_{N}^{*}$ can take any value in the set
$[b_{\min},b_{\max})\cap b_{N}^{*}(\mu_{K})$. The optimal decisions of
$x_{i}^{*}$ and $b_{i}^{*}$, for $i\in[i_{K-1}+1,N]$, are calculated by using
Algorithm 2, discussed in more detail later.

Tuning $\mu$ value: Since the cost function in problem ($P_{\text{NEM}}$) is
piecewise linear, the optimal values of the accumulated Lagrange multipliers
$\mu_{i}^{*}$ are chosen from a discrete set of values corresponding to buying
and selling prices of electricity. This feature transforms ($P_{\text{NEM}}$)
from a continuous optimization problem to a discrete one. Therefore, in the
proposed solution, we specify how to tune the Lagrange multipliers to these
prices to find their optimal values (lines 14, 15 in the pseudo code). The
mechanism to update the value of $\mu_{K}$ is decided by the violation
condition and is detailed in Remark 6.

######  Remark 6.

Now, if condition C1 holds; for the chosen value of $\mu_{K}$, the battery
capacity limit is violated from below at instant $i_{\text{break}}$ since the
set $b_{i_{\text{break}}}(\mu)$ lies strictly below $b_{\min}$. The strategy
here is to increase $\mu_{K}$ value to the

$\mu_{K}=\min\\{p>\mu:p\in\mu_{1}^{i},\mu_{2}^{i},\mu_{3}^{i},\mu_{4}^{i};{i\in(i_{K-1},i_{\text{break}}]}\\}.\vspace{-3pt}$
(9)

Otherwise, if condition C2 or C3 holds, then decrease $\mu_{K}$ to

$\mu_{K}=\max\\{p<\mu:p\in\mu_{1}^{i},\mu_{2}^{i},\mu_{3}^{i},\mu_{4}^{i};{i\in(i_{K-1},i_{\text{break}}]}\\}.\vspace{-3pt}$
(10)

After updating $\mu_{K}$ value, we repeat the same process as before until we
reach a new time instant $i_{\text{break}}$, for which one of the above
conditions is satisfied. Note there is a one-to-one mapping of $s_{i}$ and
$x_{i}$, therefore, $x_{i}^{*}(\mu_{K})$ and consequently $b_{i}^{*}(\mu_{K})$
are monotonically non-decreasing functions in $\mu_{K}$, the potential effect
of the update of $\mu_{K}$ is that $i_{\text{break}}$ is pushed to a later
instant. The update of $\mu_{K}$ is repeated as long as $i_{\text{break}}$
increases (or remains the same), compared to its previous value, stored in
$i_{\text{mem}}$. This part of the proposed algorithm is mirrored in lines
12–16 of the pseudo-code of Algorithm 1. If the value of $i_{\text{break}}$
decreases after updating $\mu_{K}$, then for the previous value
$\mu_{\text{mem}}$ of $\mu_{K}$ there must have been an instant
$i\in[i_{K-1}+1,i_{\text{mem}}]$, where $b_{\max}\in b_{i}^{*}(\mu_{K})$
(violation occurred due to C1) or $b_{\min}\in b_{i}^{*}(\mu_{K})$ (violation
occurred due to C2 or C3). This is due to the fact that both
$\mu_{\text{mem}}$ and $\mu_{K}$ always lie in the range
$\\{\mu_{1}^{i},\mu_{2}^{i},\mu_{3}^{i},\mu_{4}^{i}\\}$, for all $i>i_{K-1}$.
At this point of the algorithm (lines 17–29 of the pseudo-code), $\mu_{K}$ and
$i_{\text{break}}$ are switched back to their previous values, which are
saved, respectively, in $\mu_{\text{mem}}$ and $i_{\text{mem}}$. This value of
$\mu_{K}$ is selected as the final value of the optimal accumulated Lagrange
multiplier corresponding to sub-horizon $K$. The end instant of sub-horizon
$K$, $i_{K}$, is set equal to the latest time instant
$i\in[i_{K-1}+1,i_{\text{break}}]$, for which $b_{\min}\in b_{i}^{*}(\mu_{K})$
or $b_{\max}\in b_{i}^{*}(\mu_{K})$, and $b_{i_{K}}^{*}$ takes the value
$b_{\min}$ in the former case and $b_{\max}$ in the later case.

####  III-B2 Description of Algorithm 2

Using Algorithm 1 we find the optimal battery capacity in a sub-horizon,
$b^{*}(\mu_{K})$. $b^{*}(\mu_{K})\cap[b_{\min},b_{\max}]$ contains information
of the lower and upper feasible envelope of the battery capacity; $\cap$
denotes intersection of regions. We propose a novel method based on backward
step to find the optimal solution among infinite possibilities, described as
BackwardStep, in Algorithm 2. Note that the BackwardStep algorithm is
implemented only one time for a sub-horizon. For each $i$ in the range
$i_{K-1}+1\leq i<i_{K}$, the optimal battery level $b_{i}^{*}$ is found from
$b_{i+1}^{*}$ through the function BackwardStep which uses the backward
recursion $b_{i}^{*}=(b_{i+1}^{*}-x_{i+1}^{*}(\mu_{K}))\cap
b_{i}^{*}(\mu_{K})\cap[b_{\min},b_{\max}]$. If the above backward recursion
returns a set, then any arbitrary value in the set is chosen to be the optimal
battery level. A stylized example demonstrating the operation of the proposed
optimal arbitrage algorithm is presented in Appendix D. Note that the proposed
arbitrage algorithm will return a feasible solution for cases in which at
least one feasible solution exists, and this is ensured by the convexity of
the problem. The optimal solution to $P_{\text{NEM}}$ needs not be unique
since its objective function is not strictly convex. For the case where no
solution exists, the Algorithm 1 due to the while loop will not end (infinite
loop).

###  III-C Properties of the Optimal Arbitrage Solution

We observe that for some values of $\mu$ there is a set of solutions which are
possible. These points are the sub-gradient of the cost function. At these
points, we observe that intermediate ramp rates can be optimal, assuming the
storage ramp rates can only be changed at decision epochs and not in between
the sampling time. We demonstrate this using a numerical case study in Section
VII.

In Theorem III.3 and Remark 4 we provide the conditions for selecting the
thresholds with respect to the accumulated Lagrange multiplier or the shadow
price for the arbitrage problem. In optimization, the shadow price is the
value of the Lagrange multiplier at the optimal solution. From Eq. 7 it is
easy to see that storage thresholds for optimal arbitrage are function of the
following different parameters: (a) price for buying and selling, (b) storage
charging and discharging efficiency, (c) ramping constraint, (d) the
relationship between the ratio of selling and buying price and round-trip
storage efficiency ($\mu_{2}^{i}\leq\mu_{3}^{i}$ or
$\mu_{3}^{i}<\mu_{2}^{i}$), and (e) the consumption level as seen by the
energy meter. The shadow prices are selected from a finite set which is a
function of electricity price and storage efficiencies, see Eq. 9 and Eq. 10.

Inputs: $N$, $T$, $h=(h_{1},\ldots,h_{N})$,
$p_{b}=(p_{b}^{1},\ldots,p_{b}^{N})$, $p_{s}=(p_{s}^{1},\ldots,p_{s}^{N})$,
$b_{0}$, $z=(z_{1},...,z_{N})$,
$b_{\max},b_{\min},\delta_{\max},\delta_{\min},\eta_{\text{ch}},\eta_{\text{dis}}$
Outputs: $s^{*}$=$(s_{1}^{*},s_{2}^{*},..,s_{N}^{*})$,
$b^{*}$=$(b_{1}^{*},b_{2}^{*},..,b_{N}^{*})$,
$\mu^{*}$=$(\mu_{1}^{*},\mu_{2}^{*},..,\mu_{K}^{*})$
Initialize: K=1; $\mu_{K}$=$\mu_{\text{mem}}$=0;
$i_{K-1}$=$i_{K}$=$i_{\text{mem}}$=0; $\mathtt{BreakFlag}$=0

1:while $i_{K}<N$ do

2: for $i=i_{K-1}+1\text{ to }N$ do

3: Compute $\kappa_{i}=p_{s}(i)/p_{b}(i)$

4: if $\kappa_{i}=1$ then Find $s_{i}^{*}(\mu_{K})$ using Remark 4, Eq. 8

5: else Find $s_{i}^{*}(\mu_{K})$ using Theorem III.3, Eq. 7

6: end if

7: $x_{i}^{*}(\mu_{K})$=$f^{-1}(s_{i}^{*}(\mu_{K}))$ and
$b_{i}^{*}(\mu_{K})$=$b_{i-1}^{*}(\mu_{K})+x_{i}^{*}(\mu_{K})$

8: if C1 or C2 or C3 holds then $\mathtt{BreakFlag}\leftarrow 1$;
$i_{\text{break}}\leftarrow i$

9: Break

10: end if

11: end for

12: if $\mathtt{BreakFlag=1}$ and $i_{\text{break}}\geq i_{\text{mem}}$ then

13: $\mathtt{BreakFlag}\leftarrow 0$; $i_{\text{mem}}\leftarrow
i_{\text{break}}$; $\mu_{\text{mem}}\leftarrow\mu_{K}$

14: if $b_{i}^{*}(\mu_{K})\prec\left\\{b_{\min}\right\\}$ then $\mu_{K}$
$\leftarrow$ using Eq. 9,

15: else $\mu_{K}\leftarrow$ using Eq. 10,

16: end if

17: else if $\mathtt{BreakFlag=1}$ and $i_{\text{break}}<i_{\text{mem}}$ then

18: if C1 is True then

19: $i_{K}\leftarrow\max\\{i\in[i_{K-1}+1,i_{\text{mem}}]:b_{\max}\in
b_{i}^{*}(\mu_{\text{mem}})\\}$

20: Assign $b_{i_{K}}^{*}=b_{\max}$

21: else if C2 or C3 is True then

22: $i_{K}\leftarrow\max\\{i\in[i_{K-1}+1,i_{\text{mem}}]:b_{\min}\in
b_{i}^{*}(\mu_{\text{mem}})\\}$

23: Assign $b_{i_{K}}^{*}=b_{\min}$

24: end if

25: $\mu_{K}\leftarrow\mu_{\text{mem}}$; $\mathtt{BreakFlag}\leftarrow 0$;
$i_{\text{break}}\leftarrow i_{\text{mem}}$

26: Update $i_{\text{mem}}\leftarrow i_{K}$

27: BackwardStep($\mu_{K},i_{K-1},i_{K},b^{*},x^{*},\mu^{*}$)

28: $s^{*}=f(x^{*})$ using Eq 2

29: $\mu_{K+1}\leftarrow\mu_{K}$; $K\leftarrow K+1$

30: else

31: $i_{K}\leftarrow N$;

32: if $\mu_{K}>0$ then $b_{N}^{*}\leftarrow b_{\min}$

33: else $b_{N}^{*}\leftarrow[b_{\min},b_{\max})\cap b_{N}^{*}(\mu_{K})$

34: end if

35: BackwardStep($\mu_{K},i_{K-1},i_{K},b^{*},x^{*},\mu^{*}$)

36: $s^{*}=f(x^{*})$ using Eq 2

37: end if

38:end while

Algorithm 1 OptimalArbitrage($p_{b},p_{s},b_{0}$)

###  III-D Complexity Analysis

Using the discrete nature of the optimization problem, we explicitly
characterize the worst case run time of the proposed algorithm. For a sub-
horizon starting from instant $i$, there may be at most $N-i+1$ more time
instants which may be included in the same sub-horizon. Hence, in order to
find the optimal accumulated Lagrange multiplier for the sub-horizon, we may
have to update the value of $\mu_{K}$ in the sub-horizon at most $4(N-i+1)$
times (for NEM 2.0 at each instant $i$ four possible values
$\mu_{1}^{i},\mu_{2}^{i},\mu_{3}^{i},\mu_{4}^{i}$ may be checked). For each
update, a basic set of operations is performed. Furthermore, there may be
separate sub-horizons starting from every time instant $i\in[1,N]$. Hence, a
crude upper bound on the number of times the basic set of operations are
needed to be repeated is $\sum_{i=1}^{N}4(N-i+1)$=$O(N^{2})$. Therefore, the
worst case time complexity of the proposed algorithm is $O(N^{2})$. In most
situations, however, the number of instants included in a sub-horizon does not
grow with $N$ (see Section VI where lookahead horizon is fragmented into sub-
horizons; the length of these sub-horizons is governed by battery parameters,
sampling time and electricity price). Empirically, the run-time complexity of
the proposed algorithm grows approximately linearly with number of samples in
the decision horizon. In Section VIII, we present a numerical case-study
comparing our proposed algorithm with LP- and convex optimization-based
benchmarks and show that our algorithm outperforms these latter.

Inputs: $\mu_{K},i_{K-1},i_{K},b^{*},x^{*},\mu^{*}$
Function: Computes components of the optimal vectors $b^{*},x^{*}$ in the
range $[i_{K-1}+1,i_{K}-1]$. Initialize: $i\leftarrow i_{K}-1$

1:while $i\geq i_{K-1}+1$ do

2: $b_{i}^{*}\leftarrow(b_{i+1}^{*}-x_{i+1}^{*}(\mu_{K}))\cap
b_{i}^{*}(\mu_{K})\cap[b_{\min},b_{\max}]$,

3: $x_{i+1}*\leftarrow b_{i+1}^{*}-b_{i}^{*}$,

4: $\mu_{i}^{*}\leftarrow\mu_{K}$,

5: Calculate $i=i-1$,

6:end while

Algorithm 2 BackwardStep($\mu_{K},i_{K-1},i_{K},b^{*},x^{*},\mu^{*}$)

###  III-E General applicability

The proposed algorithm is generally applicable for a system with finite
capacity constraints and ramp rate constraints, and operating under piecewise
linear convex costs. Since buying and selling decisions in a market are taken
in discrete time-intervals with a fixed commodity price in an interval, in
most cases, the cost function is piecewise linear. The convexity of the cost
function needs an appropriate selection of the decision variable. Once the
convexity of the cost function is ensured, the proposed algorithm can be
applied. For example, in a market of commodities, a participant buys a
commodity and stores it in its inventory, to sell it in the future to make a
profit. Performing such a transaction has a coupling in buying and selling
decisions due to the finite size of the inventory, much like storage
performing arbitrage. At any time, due to infrastructure and/or capital
constraint, the market participant can buy or sell no more than a given limit,
much like the ramp rate constraint of a battery. Applications such as
integrating renewables for self-sufficiency as in [35], [36] and controlling
excess generation as in [37, 38] can use the proposed algorithm for
identifying storage control decisions. More general problems, such as the
wheat trading model as presented in [39], can be solved using the proposed
algorithm.

##  IV Real-Time Implementation

The problem of real time energy arbitrage consists of two coupled subproblems:
(i) the optimal energy arbitrage and (ii) the forecasting of future parameters
(i.e., the electricity price, the end user demand and the solar PV
generation), required for performing optimal arbitrage. Due to the mismatch in
forecasted and actual parameter values, the arbitrage gains will likely be
lower than deterministic optimal arbitrage gains. In this section we present
an online algorithm which uses incrementally improving forecasting of
parameters along with Model Predictive Control (MPC) to decide optimal control
actions. MPC is used to optimize the decisions in current time slots, while
taking into account future time slots. In the receding horizon the forecast is
updated and MPC is implemented again, till end time is reached. The definition
of sub-horizon presented earlier suggests that we only need to accurately
forecast for time instants in proximity to the current time instant, as
optimal actions beyond the current sub-horizon are not influenced by
parameters in future sub-horizons. However, quantifying the length of a sub-
horizon is challenging since it is governed by storage parameters and
variation of prices. A sub-horizon denotes the optimal lookahead in future
intervals for selecting the control decisions. In Section VI we present a
heuristic-based analysis to quantify the required lookahead based on storage
type. We observe that the optimal lookahead for performing arbitrage depends
on the ratio of ramp rate over capacity, efficiency and ratio of buying and
selling price.

The deterministic arbitrage gains expressed as
$V_{a}^{*}=\sum_{i=1}^{N}p_{\text{elec}}(i)(z_{i}-L_{i}^{*}(z_{i},p_{\text{elec}}(i)))$,
provide upper limits on arbitrage gains under complete information setting.
Due to forecast errors, the end user’s energy arbitrage gains are affected.
Realistic arbitrage
gain,$V_{r}=\sum_{i=1}^{N}{p}_{\text{elec}}(i)({z}_{i}-\hat{L}_{i}^{*}(\hat{z}_{i},\hat{p}_{\text{elec}}(i)))$.
$\hat{L}_{i}^{*}$ is the optimal end user net consumption for the forecasted
price signal, $\hat{p}_{\text{elec}}(i)$, and forecasted load vector,
$\hat{z}$. It is evident that $V_{a}^{*}\leq V_{r}$.

###  IV-A Forecast Model

We define the mean behavior of past values of net load without storage at time
step $i$ as

${\mkern 1.5mu\overline{\mkern-1.5muz\mkern-1.5mu}\mkern
1.5mu}_{i}=\frac{1}{D}\sum_{p=1}^{D}z_{(i-pN)}\quad\forall
i\in\\{k,...,N\\},k\geq 1,$ (11)

where $N$ is the number of points in a time horizon of 1 day, and $D$ is the
number of days in the past whose values are considered in calculating $\mkern
1.5mu\overline{\mkern-1.5muz\mkern-1.5mu}\mkern 1.5mu$. The actual value of
net load without storage is given as

${z}_{i}=\mkern 1.5mu\overline{\mkern-1.5muz\mkern-1.5mu}\mkern
1.5mu_{i}+{X}_{i}\quad\forall i\in\\{k,...,N\\},k\geq 1,$ (12)

where ${X}_{i}$ represents the actual difference from the mean behavior. The
forecasted net load (without storage) is given as

$\hat{z}_{i}=\mkern 1.5mu\overline{\mkern-1.5muz\mkern-1.5mu}\mkern
1.5mu_{i}+\hat{X}_{i}\quad\forall i\in\\{k,...,N\\},k\geq 1,$ (13)

where $\hat{X}_{i}$ represents the forecasted difference from the mean
behavior. We define $\hat{X}_{i}\quad\forall i\in\\{k,...,N\\}$ as

$\hat{X}_{k}=\alpha_{1}X_{k-1}+\alpha_{2}X_{k-2}+\alpha_{3}X_{k-3}+\beta_{1}\delta_{k}^{1}+\beta_{2}\delta_{k}^{2}+\beta_{3}\delta_{k}^{3},$
(14)

where $\delta_{k}^{m}=(z_{k-mN}-{\mkern
1.5mu\overline{\mkern-1.5muz\mkern-1.5mu}\mkern 1.5mu}_{k-mN})$ and
$\alpha_{i},\beta_{i}\forall i\in\\{1,2,3\\}$ are constant. Our forecast model
uses the errors in net load without storage for the past three time steps and
the error in the same time step for past three days. At time step $i=k-1$ we
calculate $\hat{X}_{k}$ as shown in Eq 14. We calculate $\hat{X}_{k+1}$ till
$\hat{X}_{N}$ in order to update the forecast signal to be fed to MPC.

$\displaystyle\hat{X}_{N}=\alpha_{1}\hat{X}_{N-1}+\alpha_{2}\hat{X}_{N-2}+\alpha_{3}\hat{X}_{N-3}+\sum_{q=1}^{3}\beta_{q}\delta_{N}^{q}.$

We calculate $\hat{z}$ using Eq. 13. The vector $\hat{z}$ is fed to MPC for
calculating optimal energy storage actions for time step $i=k-1$. At the time
step $i=k$, we can calculate $X_{k}={z}_{k}-\mkern
1.5mu\overline{\mkern-1.5muz\mkern-1.5mu}\mkern 1.5mu_{k}$. Similar steps are
done for $i\in\\{k+1,...,N\\}$, till the end of time horizon is reached.

###  IV-B Model Predictive Control

We calculate energy arbitrage gains sequentially with incrementally improving
the forecast model. To this aim, we implement the forecast model using the
AutoRegressive Moving Average (ARMA) model. In this work, we focus on and
develop a forecast model for the net load consumption of the end user without
storage. The details of the forecast model and an online algorithm for real-
time implementation of the proposed arbitrage algorithm are presented in
Section IV-A. The online algorithm for real-time implementation of optimal
arbitrage algorithm is given as ForecastPlusMPC.

Global Inputs:
$\eta_{\text{ch}},\eta_{\text{dis}},\delta_{\max},\delta_{\min},b_{\max},b_{\min}$,
$b_{0}$
Inputs: $h,N,T,i=0$

1:while $i<N$ do

2: $i=i+1$

3: Forecast $\hat{p}_{elec},\hat{z}$ from time step $i$ to $N$

4: $s^{*}=\texttt{Algorithm1}(\hat{p}_{elec},\hat{z},h,N,T)$

5: $b_{i}^{*}=b_{i-1}+x_{i}^{*}$,

6: Update $b_{0}=b_{i}^{*}$.

7:end while

Algorithm 3 ForecastPlusMPC

##  V Numerical Results

For the numerical evaluation, we use a single end user having an inelastic
power and energy demand and a rooftop solar generation. The end user’s
consumption data with solar generation data are downloaded from the Pecan
Street’s online data repository [13]. We use the data corresponding to user id
379 for May 2, 2016. This is one of the days when the solar generation exceeds
the end user’s consumption for some amount of time. The battery parameters are
set as follows: $b_{\max}$= 1 kWh, $b_{\min}$= 0.1 kWh, $\delta_{\max}$= 0.26
kW, $\delta_{\min}$=$-0.52$ kW. Real-time locational marginal pricing data
from NYISO [40] is used to calculate the optimal ramping trajectory. The
sampling time of the price signal is $h$=15 minutes. Simulations are conducted
using a laptop PC with Intel Core i7-6600 CPU, 2.6 GHz processor and 16 GB
RAM. The results obtained by our algorithm for a lossy battery with
$\eta_{\text{ch}}$ = $\eta_{\text{dis}}$ = 0.95 and for the case of zero
selling price are shown in the figures below. Fig. 3 shows the electricity
buying price and the shadow price, i.e. $\mu^{*}$, calculated using the
proposed algorithm for initial battery charge level $b_{0}=0.5$. Since we
assume zero selling price, implying that it is not beneficial for the end user
to supply power back to the grid, we can observe from Fig. 4 that in the
afternoon when the end user generates more than the consumption, it still
supplies power back to the grid, as the user has no flexibility in form of
storage. However, with the inclusion of storage the net-load saturates at zero
level. Table I compares the run-time of the proposed algorithm with Linear
programming [41], CVX [42] , YALMIP and Matlab’s Fmincon optimization tool.

TABLE I: Comparison of runtime Algorithm Type | Run Time (sec)
---|---
Proposed Algo | 0.019
Linear Program [41] | 0.045
CVX [42] | 0.536
YALMIP [43] with Gurobi | 3.700
Matlab’s Fmincon | 5.693
Figure 3: Price Signal and accumulated Lagrange Multiplier Figure 4: Demand without storage and with optimal storage control TABLE II: Mean and Standard Deviation of arbitrage gains Gain Type | Mean ($) | STD
---|---|---
Ideal ($V_{a}^{*}$) | 0.05481 | 0.04673
Actual ($V_{r}$) | 0.04783 | 0.04922

Fig. 5 shows the solar generation, the end user demand and the energy consumed
from the grid.

Figure 5: Pecan Street Data of a home with solar generation

Now, consider a hypothetical scenario, when this end user might have had
energy storage installed. How much gains could an end user make by installing
an energy storage?

Figure 6: Ramp rate for optimal arbitrage

Fig. 6 shows the ramp rate of the battery. It is evident from Fig. 6 that the
ramping constraints for the battery are met and intermediate ramp rates could
also be optimal.

Figure 7: Optimal Energy level

Fig. 7 shows the optimal battery capacity trajectory. Note from Fig. 3 that
the price has two peaks in the whole day, thus the battery does 2 cycles of
charge and discharge, as shown in Fig. 7.

The comparison of the change in valuation of only storage and only solar with
the variation in the ratio of the selling price and buying price from an end
user’s perspective is studied.

Figure 8: Value of Solar and Storage with the ratio of $p_{s}$ and $p_{b}$

Fig. 8 shows the variation of value of only storage and only renewable with
the change in the selling price of electricity. We define the value of solar
as the difference between cost of consumption with only load and cost of
consumption with load and solar. Similarly, the value of storage is defined as
the difference between the cost of consumption with load and solar and the
cost of consumption with load, solar and battery. The value of storage is
defined as
$\sum_{i=1}^{N}\\{p_{b}[z_{i}]^{+}-p_{s}[z_{i}]^{-}\\}-\sum_{i=1}^{N}\\{p_{b}[z_{i}+s_{i}]^{+}-p_{s}[z_{i}+s_{i}]^{-}\\}$.
We would like to highlight that when selling price is low there is an increase
in the storage value which comes at the cost of decrease in the value of
renewables connected. For zero selling price the value of energy storage for
the numerical evaluation is $ 0.1237.

As the share of renewables connected to power network increases the volatility
in electricity prices will increase in order to incentivize users to differ
their consumption.

Figure 9: Increase in arbitrage gains with volatility in price

Fig. 9 shows that as the variance in electricity price increases, i.e. price
volatility increases, the amount of arbitrage gains for consumers, with full
information about price variation, will increase. The increase in arbitrage
gains with respect to variance can be approximated using a quadratic fit.
Installing energy storage would provide more financial returns under increased
volatility.

Forecast Error and Loss of Opportunity: It is expected that mismatch between
forecast and actual values will possibly generate for the user a loss of
opportunity. This latter is defined as the per unit variation of ideal versus
actual arbitrage gain with respect to ideal arbitrage gains: $\text{Loss of
Opportunity}=\frac{V_{a}^{*}-V_{r}}{V_{a}^{*}}.$ In order to understand the
effect of forecast error in electricity price on the arbitrage gains we
conduct a performance evaluation based on 10,000 simulations for equal buying
and selling prices with battery having $95\%$ charging and discharging
efficiency for different variance of forecast error (= actual price -
forecasted price). Fig. 10 shows that with increasing variance of forecast
error the loss of opportunity for the user will increase. Black dots in Fig.
10 represent the mean value of loss of opportunity corresponding to the
variance in forecast error, which could be fitted with a linear function.

Figure 10: Relationship of Loss of Opportunity and Forecast Error

###  V-A MPC with incrementally improving forecast

We use the Pecan Street data [13] for hourly consumption for house id 379 for
the month of June and July 2016. The day ahead electricity prices in the ERCOT
data are used for the same period [14]. It is assumed that the selling price
is half that of the buying price. The factors in Eq. 14 are
$\alpha_{1}=\beta_{1}=0.27185$, $\alpha_{2}=\beta_{2}=0.14780$ and
$\alpha_{3}=\beta_{3}=0.08036$. Parameters $D=3$ days and $N=24$ hours
(rolling horizon). We use the same parameters of the battery as described in
the previous numerical results. It can be observed that actual and ideal
arbitrage gains are in sync with each other, and that as expected $V_{r}\leq
V_{a}^{*}$. Furthermore, Table II reports the mean and standard deviation of
arbitrage gains ($V_{a}^{*}$ and $V_{r}$) over a period of 2 months. Due to
inaccuracies in forecasting, end user incurs $\approx 12.7\%$ of loss in
possible opportunity during the period of 2 months. The simulation results for
ARMA-based forecasting with MPC are shown in Fig. 11.

Figure 11: Comparison of arbitrage gains for ideal and actual case

##  VI Case Study I: Quantifying the length of a sub-horizon

Identifying optimal lookahead horizon for performing arbitrage would be
essential for maximizing the end user gains. Prior works [16] indicate
selecting a time horizon of 1 day is sensible since the electricity pattern
repeats with a period of one day approximately, being high during peak
consumption hours during the day and low during the night [31].

In this work we claim that the optimal control actions for energy storage
device depends on electricity price and load variations in a smaller part of a
larger time horizon and independent of all points in past or beyond the sub-
horizon. However, identifying this optimal look-ahead period is challenging as
it is governed by variations of electricity price, load and battery
parameters. Next we present a case study for understanding the influence of
battery parameters on the length of a sub-horizon.

Figure 12: Histogram of sub-horizon spread for 0.5C-0.5C battery for CAISO in
2017

###  VI-A Case Study: CAISO 2017 for NEM 1.0

We consider the electricity price for CAISO of 2017 and identify the
variations of the sub-horizon over a year with different energy storage
parameters. The parameters setting in this case study is as follows:

  * •

Electricity price for CAISO in 2017,

  * •

Ramp rate of the battery: we consider 1 kWh capacity battery with 3 different
ramp rates. xC-yC represents that battery takes 1/x hours to completely charge
and 1/y hours to completely discharge.

  * •

Efficiency of the battery: we consider 5 levels of efficiency ($\eta$): 0.99,
0.95, 0.9, 0.8 and 0.7. Here $\eta=\eta_{ch}=\eta_{dis}$.

The performance indices used in this case study are:

  * •

$T_{mean}$: denotes the mean length of a sub-horizon over the whole year,

  * •

$T_{99\%}$: denotes the 99% quantile,

  * •

$T_{worst}$: denotes the worst case length of a sub-horizon,

  * •

$/cycle: denotes dollars per cycle gain and

  * •

Gain: is the total arbitrage gain.

TABLE III: Quantifying the length of sub-horizon Efficiency | $T_{mean}$ | $T_{99\%}$ | $T_{worst}$ | $/cyc | Gains
---|---|---|---|---|---
$\eta$ | hours | hours | hours |  | $
0.5 C - 0.5C Battery
0.99 | 2.45 | 15.33 | 25.75 | 0.037 | 32.80
0.95 | 3.20 | 17.50 | 26.75 | 0.046 | 30.21
0.9 | 4.11 | 20.50 | 26.92 | 0.055 | 27.54
0.8 | 6.68 | 26.70 | 42.42 | 0.068 | 23.21
0.7 | 9.73 | 69.83 | 90.58 | 0.075 | 19.62
1 C - 1 C Battery
0.99 | 1.76 | 11.83 | 18.75 | 0.036 | 59.52
0.95 | 2.14 | 13.00 | 18.75 | 0.047 | 54.84
0.9 | 2.79 | 14.83 | 23.08 | 0.059 | 50.04
0.8 | 4.52 | 18.67 | 33.58 | 0.077 | 42.29
0.7 | 6.37 | 30.67 | 63.50 | 0.085 | 35.86
2 C - 2 C Battery
0.99 | 1.21 | 6.92 | 12.75 | 0.034 | 103.60
0.95 | 1.61 | 9.17 | 14.17 | 0.048 | 95.28
0.9 | 2.10 | 11.00 | 16.33 | 0.062 | 87.02
0.8 | 3.32 | 16.83 | 26.42 | 0.085 | 73.76
0.7 | 4.60 | 23.00 | 58.50 | 0.093 | 62.65

It is evident from Fig. 12 and Table III that the length of look ahead
required for optimal energy storage arbitrage gains reduces as the ramping
rate increases and as the energy storage battery becomes more efficient. As
pointed in [33] that the efficiency creates a dead band in threshold based
structure and increase in efficiency implies battery should not operate during
low returning transactions as it would not be profitable. Dollars per cycle
calculated using prior work [34] shows increase as the efficiency decreases.
For more details refer to [33] and [34]. As the ramping of battery increases
and battery becomes more efficient the optimal look-ahead period decreases
making it more prone to inaccuracies in forecast information. This observation
is in sync with [44].

Table III compares the look-ahead window required in hours for three
batteries. xC-yC battery implies battery takes 1/x hours to charge and 1/y
hours to discharge completely. All the three batteries have the same capacity
but different ramping rates. The arbitrage gains increases as the battery
becomes more efficient and as the ramping rate increases. The $/cycle
calculated here takes into account battery degradation due to operational
cycles. Note the look-ahead window for 0.5C-0.C battery with 95% efficiency
(i.e. $\eta_{ch}=\eta_{dis}=0.95$) is 15.5 hours or below for 99% of sub-
horizons over the whole year (CAISO, 2017), this decrease to 13 hours for
1C-1C battery and further reduces to just 9.17 hours for 2C-2C battery. This
case study indicates that the optimal look-ahead window for performing
arbitrage is not only governed by price variation but also battery ramping
rate and round trip efficiency. Fig. 12 shows the spread of sub-horizons for
0.5C-0.5 battery with varying efficiency. For a highly efficient battery the
spread is much more compact compared to less efficient one.

For instance, faster ramping batteries with same energy capacity require
smaller lookahead horizon compared to slower ramping batteries. [24] performs
numerical studies for a hydro-storage facility in the UK and identifies that
the forecast horizon varies between 1 to 15 days. The horizon is so long due
to a slow ramping capability of hydro-storage. We observe a similar trend
where forecast horizons vary between a few hours to several days for batteries
with varying ramping rates, thus making it essential to model price impacts.
For strictly convex cost function, our proposed algorithm simplifies to the
one proposed in [24].

##  VII Case Study II: Intermediate ramp rate optimality

Several works on energy storage arbitrage use set thresholds according to
which storage operation could be selected from 3 cases, i.e. charge at maximum
rate, discharge at minimum rate or stay idle. We believe energy storage
performing arbitrage could also have intermediate ramping rates which are
neither minimum or maximum nor zero, making the optimal storage ramping
selection a continuous set from minimum discharging rate to maximum charging
rate.

We demonstrate this claim with a stylized example. In this example we consider
only storage case with equal buying and selling price of electricity, in order
to have analytical tractability. Consider the electricity price signal shown
in the first plot of Fig. 13. The battery parameters are as follows:
$b_{0}=500$Wh, $b_{\max}=3000$Wh, $b_{\max}=100$Wh,
$\eta_{ch}=\eta_{dis}=0.9$, $\delta_{\max}=-\delta_{\min}=1000$W. The
electricity price values for hour 1 to 10 are provided here: [1, 0.9, 1.5,
0.8, 0.6, 5, 4.9, 6, 5, 8]. We intend to provide all details of the results
presented in order to ease the reproducibility of the claims made here.

Figure 13: Toy example to show the intermediate ramp rate of energy storage.
Plot 1 shows the electricity price. Plot 2 shows the optimal storage charge
level. Plot 3 shows the storage ramp rate.

The price signal is carefully designed to have values between 1 to 2 cent/kWh
for hour 1 to 5 and higher levels of electricity price for hour 6 to 10. This
could be analogous to low electricity price during the night and significantly
higher price levels during the evening peak. Note that the electricity price
for 7th and 9th hour are at the same level, i.e. 5 cents/kWh. The second plot
of Fig. 13 shows the optimal storage charge level considering electricity
price variation and storage parameters. The third plot of Fig. 13 shows the
ramp rate in $x$ which affects the change in battery charge level in blue and
$s$, output power of storage in red which considers the charging and
discharging efficiency losses. Points marked P1, P2 and P3 shows ramping of
the battery which are neither at maximum, minimum or zero level of ramp rate.

Clearly, based on the price variation for this example storage needs to be
completely charged at the end of 5th hour. In order to discharge during higher
price levels for interval 6 to 10 hour. The order of price levels in 0 to 5
hour are in this order:
$p_{elec}(5)<p_{elec}(4)<p_{elec}(2)<p_{elec}(1)<p_{elec}(3)$. Starting from
$b_{0}=500$Wh, storage needs 2500 Wh of energy to be fully charged at the end
of 5th hour. The battery charges at a ramp rate of 500 W in hour 1. This level
is lower than the max level of ramp rate. The battery reaches a charge level
of 1000 Wh. $p_{elec}(2)$ is the third lower price in hour 1 to 5 and the
battery charges at maximum rate in order to discharge during hour 3 to capture
gains as $p_{elec}(3)$ is the local peak. In subsequent 4th and 5th hour the
battery charges at max level to unity state-of-charge at the end of 5th hour.

The order of price levels in 6 to 10 hour are in this order:
$p_{elec}(7)<p_{elec}(6)=p_{elec}(8)<p_{elec}(8)<p_{elec}(10)$. Clearly,
battery should should discharge maximum possible during 10th hour and then 8th
hour. If the battery is still not completely discharged than during 6th and
9th hour. The incentive of discharging during hour 6 and 9 are equal so
multiple solutions could be possible if the battery is not discharging at its
peak rate. This could be seen in Fig. 14 where two distinct solutions are
plotted (with infinite other combinations possible). All such combinations
provide the same level of arbitrage gains which for this example is 14.89
cents. Since hour 7 has the lowest price level in the interval 6 to 10 hour
and the battery could be discharged completely in slightly less than 3 hours.
Thus storage remains idle during 7th hour.

Figure 14: Two distinct optimal ramping solution for performing energy
arbitrage for the electricity price signal shown in Fig. 13. Figure 15: Shadow
price (accumulated Lagrange multiplier) for the electricity price signal shown
in Fig. 13.

Fig. 15 presents the shadow price (accumulated Lagrange multiplier) for the 2
sub-horizons for this example. First sub-horizon has $\mu_{1}=1.111$ is
applicable for hour 1 to 5 and $\mu_{2}=4.5$ is applicable for hour 6 to 10.
Since the intermediate ramp rate is observed at 1st hour with $p_{elec}(1)=1$
cents/kWh and the battery is charging therefore,
$\mu_{1}=p_{elec}(1)/\eta_{ch}=1.111$. Similarly, the intermediate ramp rate
in the second sub-horizon is observed at 6th or 9th (as same price level) hour
with $p_{elec}(6)=p_{elec}(9)=5$ cents/kWh and the battery is discharging
therefore, $\mu_{2}=p_{elec}(6)\eta_{dis}=p_{elec}(9)\eta_{dis}=4.5$.

Figure 16: Lower, upper and optimal charge level for the electricity price
signal shown in Fig. 13.

Fig. 16 shows the upper and lower envelopes of storage charge level along with
the selected optimal storage charge level. The envelope of solutions is due to
the piecewise linear cost structure of the cost function which provides sub-
gradient like solution at point where the cost function changes its slope.

##  VIII Case Study III: Comparing Run-Time of Algorithms

We compare the run-time of three optimal arbitrage algorithms for a given
battery and present the run-times with different number of samples in the time
horizon of optimization. The three algorithms compared here are:
(a) Proposed algorithm in this work which shows the structure of optimal
arbitrage solution based on price and net-load variation.
(b) Linear Programming: We use the LP formulation proposed in [41]. The LP
formulation is possible due to piecewise linear convex cost functions. In this
formulation we consider: (i) net-metering compensation (with selling price at
best equal to buying price) i.e. $\kappa_{i}\in[0,1]$, (ii) inelastic load,
(iii) consumer renewable generation, (iv) storage charging and discharging
losses, (v) storage ramping constraint and (vi) storage capacity constraint.
Using numerical results we perform sensitivity analysis of batteries for
varying ramp rates and varying ratio of selling and buying price of
electricity.
(c) Convex optimization: There could be several different ways of formulating
optimal arbitrage problem using convex optimization toolbox. We propose one of
the many ways of solving optimal arbitrage problem with convex piecewise
linear cost function using CVX. Since in the optimization formulation we do
not have any binary variable, this optimization problem could be solved using
the default solver, SDPT3333https://tinyurl.com/yfqclqz. The decision variable
$x_{i}$ is separated into two variables given as
$x_{i}=x_{i}^{ch}-x_{i}^{ds},$ where $x_{i}^{ch}\in[0,X_{\max}]$ and
$x_{i}^{ds}\in[0,-X_{\min}]$, denote the charging and discharging values,
respectively.

For the numerical evaluation we use a battery with initial charge level,
$b_{0}$=500 Wh, $b_{\max}$=3000 Wh, $b_{\min}$=100 Wh,
$\eta_{ch}$=$\eta_{dis}$=0.9 and sampling time is equal to 1 hour.

Fig. 17 shows the run-time in seconds for the three described approaches for
performing optimal arbitrage decisions. It can be observed that the proposed
algorithm greatly outperforms the other two approaches in terms of computation
time. With a significantly longer time horizon LP might not be tractable. The
CVX based convex optimization problem also becomes intractable for
optimization horizon greater than $10^{4}$ samples.

Fig. 18 shows the run-time in seconds for our optimal arbitrage algorithm to
obtain the optimal solution for the two cases without and with load. As it can
be seen in this figure, the complexity of the proposed algorithm grows
approximately linearly with the number of samples. The quantification of mean
and standard deviation of sub-horizon is shown in Table IV.

TABLE IV: Sub-horizon characteristics in number of samples Samples in | Mean no. of samples | STD of sub-
---|---|---
time horizon | in sub-horizon | horizon length
10 | 5 | 7.07
100 | 10 | 6.29
1000 | 10.99 | 7.19
10000 | 11.09 | 7.27
100000 | 11.11 | 7.28
Figure 17: Comparison of run-time for CVX based optimization, linear
programming and the proposed algorithm with variation of samples in time
horizon of optimization for storage performing arbitrage. The run-time without
load in blue and with load in red is shown.  Figure 18: Proposed algorithm
run-time comparison for with load (in red) and without load (in blue).

##  IX Conclusion

We formulated the optimal energy arbitrage problem for storage operation such
as batteries for an end user with inelastic load and renewable generation in
presence of net-metering policy for compensating excess electricity
generation. We proposed an efficient algorithm to find an optimal solution,
using a method that transforms a continuous, convex optimization problem into
a discrete one by exploiting the piecewise linear structure of the cost
function. We introduced a method for determining the sub-horizons in the whole
duration and showed that optimal storage control decisions do not depend on
price of electricity and load variations beyond a sub-horizon. The proposed
algorithm is compared with linear programming and convex optimization
formulation to demonstrate the computational efficiency. We show that the
worst-case run-time complexity is quadratic in the time horizon. Auto-
regressive forecast models are implemented for rolling or receding horizon
model predictive control to take into account real-world uncertainties in
electricity price, consumer load and renewable generation.

Theoretical and numerical case studies help us identify the governing
parameters of following: (i) Sub-horizon: is governed by (a) electricity
price, (b) charging and discharging efficiency, (c) sampling time, (d) ratio
of ramp rate and the rated storage capacity and (e) initial storage capacity,
(ii) Shadow price: is governed by (a) electricity price and (b) charging and
discharging efficiency, (iii) Thresholds of storage operation: are governed by
(a) consumer inelastic load, (b) renewable generation, (c) electricity price,
(d) storage ramp rate, (e) charging and discharging efficiency and (f) ratio
of ramp rate and the rated capacity, (iv) Effect of uncertainty on arbitrage
gains: governed by (a) relationship between sampling time and the ratio of
ramp rate and the rated storage capacity, (b) charging and discharging
efficiency. The dependencies require further exploration to quantify their
relationship with each other.

## References

  * [1] U. S. D. of Energy, “International energy outlook,” _Energy Information Administration (EIA) USA_ , 2016.
  * [2] Bente Klein, “Renewable energy policy database and support,” Online, https://tinyurl.com/ybtrnohs, 2017.
  * [3] “Net metering, wikipedia,” Online, https://tinyurl.com/ybgzerct, 2017.
  * [4] “California dg stats,” Online, http://tinyurl.com/yymlx3x2, 2019.
  * [5] N. R. Darghouth, R. H. Wiser, G. Barbose, and A. D. Mills, “Net metering and market feedback loops: Exploring the impact of retail rate design on distributed pv deployment,” _Applied Energy_ , vol. 162, pp. 713–722, 2016\.
  * [6] C. Eid, J. R. Guillen, P. F. Marin, and R. Hakvoort, “The economic effect of electricity net-metering with solar pv: Consequences for network cost recovery, cross subsidies and policy objectives,” _Energy Policy_ , vol. 75, pp. 244–254, 2014.
  * [7] “Net energy metering cpuc,” Online, http://tinyurl.com/yyv7r9cq, 2019.
  * [8] A. Gong, C. Brown, and S. Adeyemo, “The financial impact of california’s net energy metering 2.0 policy,” 2017.
  * [9] G. E. Palomino, J. Wiles, J. Stevens, and F. Goodman, “Performance of a grid connected residential photovoltaic system with energy storage,” in _Photovoltaic Specialists Conference, 1997., Conference Record of the Twenty-Sixth IEEE_. IEEE, 1997, pp. 1377–1380.
  * [10] H. Ren, Q. Wu, W. Gao, and W. Zhou, “Optimal operation of a grid-connected hybrid pv/fuel cell/battery energy system for residential applications,” _Energy_ , vol. 113, pp. 702–712, 2016.
  * [11] S. Borenstein, “The long-run efficiency of real-time electricity pricing,” _The Energy Journal_ , vol. 26, no. 3, pp. 93–116, 2005.
  * [12] M. U. Hashmi, D. Muthirayan, and A. Bušić, “Effect of real-time electricity pricing on ancillary service requirements,” in _Ninth eEnergy_. ACM, 2018, pp. 550–555.
  * [13] “Pecan street dataport,” Online, https://dataport.cloud/, 2016.
  * [14] “Energy prices,” Online, http://www.energyonline.com/Data/, 2016.
  * [15] P. M. van de Ven, N. Hegde, L. Massoulié, and T. Salonidis, “Optimal control of end-user energy storage,” _IEEE Transactions on Smart Grid_ , vol. 4, no. 2, pp. 789–797, 2013.
  * [16] P. Mokrian and M. Stephen, “A stochastic programming framework for the valuation of electricity storage,” in _26th USAEE/IAEE North American Conference_. Citeseer, 2006, pp. 24–27.
  * [17] K. Anderson and A. El Gamal, “Co-optimizing the value of storage in energy and regulation service markets,” _Energy Systems_ , pp. 1–19, 2016.
  * [18] J. H. Kim and W. B. Powell, “Optimal energy commitments with storage and intermittent supply,” _Operations research_ , vol. 59, no. 6, pp. 1347–1360, 2011.
  * [19] E. L. Ratnam, S. R. Weller, and C. M. Kellett, “An optimization-based approach for assessing the benefits of residential battery storage in conjunction with solar pv,” in _Bulk Power System Dynamics and Control-IX Optimization, Security and Control of the Emerging Power Grid (IREP), 2013 IREP Symposium_. IEEE, 2013, pp. 1–8.
  * [20] A. Mishra, D. Irwin, P. Shenoy, J. Kurose, and T. Zhu, “Smartcharge: Cutting the electricity bill in smart homes with energy storage,” in _Proceedings of the 3rd Internat. Conference on Future Energy Systems: Where Energy, Computing and Communication Meet_. ACM, 2012.
  * [21] J. Qin, R. Sevlian, D. Varodayan, and R. Rajagopal, “Optimal electric energy storage operation,” in _PES General Meeting_. IEEE, 2012.
  * [22] M. Petrik and X. Wu, “Optimal threshold control for energy arbitrage with degradable battery storage.” in _UAI_ , 2015, pp. 692–701.
  * [23] N. Gast, J.-Y. Le Boudec, A. Proutière, and D.-C. Tomozei, “Impact of storage on the efficiency and prices in real-time electricity markets,” in _Proceedings of the fourth international conference on Future energy systems_. ACM, 2013, pp. 15–26.
  * [24] J. Cruise, L. Flatley, R. Gibbens, and S. Zachary, “Control of energy storage with market impact: Lagrangian approach and horizons,” _Operations Research_ , 2019.
  * [25] ——, “Optimal control of storage incorporating market impact and with energy applications,” _arXiv preprint arXiv:1406.3653_ , 2014.
  * [26] S. Chand, V. N. Hsu, and S. Sethi, “Forecast, solution, and rolling horizons in operations management problems: A classified bibliography,” _Manufacturing & Service Operations Management_, vol. 4, no. 1, pp. 25–43, 2002.
  * [27] Y. Xu and L. Tong, “Optimal operation and economic value of energy storage at consumer locations,” _IEEE Transactions on Automatic Control_ , vol. 62, no. 2, pp. 792–807, 2017.
  * [28] M. U. Hashmi, A. Mukhopadhyay, A. Bušić, and J. Elias, “Optimal control of storage under time varying electricity prices,” _IEEE International Conference on Smart Grid Communications_ , 2017.
  * [29] H. Wang and B. Zhang, “Energy storage arbitrage in real-time markets via reinforcement learning,” in _2018 IEEE Power & Energy Society General Meeting (PESGM)_. IEEE, 2018, pp. 1–5.
  * [30] K. Abdulla, J. De Hoog, V. Muenzel, F. Suits, K. Steer, A. Wirth, and S. Halgamuge, “Optimal operation of energy storage systems considering forecasts and battery degradation,” _IEEE Transactions on Smart Grid_ , vol. 9, no. 3, pp. 2086–2096, 2018.
  * [31] W. Hu, Z. Chen, and B. Bak-Jensen, “Optimal operation strategy of battery energy storage system to real-time electricity price in denmark,” in _Power and Energy Society General Meeting_. IEEE, 2010.
  * [32] “Net metering nrel,” Online, http://tinyurl.com/y27uxjvo, 2017.
  * [33] M. U. Hashmi and A. Busic, “Limiting energy storage cycles of operation,” in _GreenTech, 2018_. IEEE, 2018, pp. 71–74.
  * [34] M. U. Hashmi, W. Labidi, A. Bušic, S.-E. Elayoubi, and T. Chahed, “Long-term revenue estimation for battery performing arbitrage and ancillary services,” in _IEEE SmartGridComm_ , 2018.
  * [35] R. L. Fares and M. E. Webber, “The impacts of storing solar energy in the home to reduce reliance on the utility,” _Nature Energy_ , vol. 2, no. 2, p. 17001, 2017.
  * [36] M. U. Hashmi, L. Pereira, and A. Bušić, “Energy storage in madeira, portugal: Co-optimizing for arbitrage, self-sufficiency, peak shaving and energy backup,” _arXiv preprint arXiv:1904.00463_ , 2019.
  * [37] J. M. Mueller, “Evaluating storage technologies for wind and solar energy,” Ph.D. dissertation, Massachusetts Institute of Technology, 2018.
  * [38] M. U. Hashmi, “Optimization and control of storage in smart grids,” Ph.D. dissertation, L’École Normale Supérieure, 2019.
  * [39] R. F. Hartl, “A forward algorithm for a generalized wheat trading model,” _Zeitschrift für Operations Research_ , vol. 30, no. 3, pp. A135–144, 1986.
  * [40] “Real time lmp,” Online, https://tinyurl.com/2flowo6, 2016.
  * [41] M. Hashmi, A. Mukhopadhyay, A. Busic, and J. Elias, “Optimal storage arbitrage under net metering policies using linear programming,” _accepted to IEEE SmartGridComm_ , July, 2019.
  * [42] I. CVX Research, “CVX: Matlab software for disciplined convex programming, version 2.0,” http://cvxr.com/cvx, Aug. 2012.
  * [43] J. Löfberg, “Yalmip : A toolbox for modeling and optimization in matlab,” in _In Proceedings of the CACSD Conference_ , Taiwan, 2004.
  * [44] Y. Chen, M. U. Hashmi, D. Deka, and M. Chertkov, “Stochastic battery operations using deep neural networks,” in _IEEE ISGT, NA_ , 2019.

##  Appendix A Structure of cost function

###### Proof.

Let $\psi(t)=a[t]^{+}-b[t]^{-}$ with $a\geq b\geq 0$. Using
$t=[t]^{+}-[t]^{-}$ we have $\psi(t)=(a-b)[t]^{+}+bt$. Since both $[t]^{+}$
and $t$ are convex in $t$ and $a-b,b\geq 0$ we have that $\psi$ is convex
since it is the positive sum of two convex functions.

Now let $f(x)=\frac{1}{\eta_{ch}}[x]^{+}-\eta_{dis}[x]^{-}$ (as defined in
(2)) and $h_{i}(s)=[z_{i}+s]^{+}p_{b}(i)-[z_{i}+s]^{-}p_{s}(i)$. Then by the
above reasoning we have that for $p_{b}(i)\geq p_{s}(i)\geq 0$ and
$\eta_{ch},\eta_{dis}\in(0,1]$, $h_{i}$ is convex in $s$ and $f$ is convex in
$x$. Also, note that $h_{i}$ is non-decreasing in $s$. Hence, for
$\lambda\in[0,1]$ we have

$\displaystyle h_{i}\big{(}f(\lambda x+(1-\lambda)y)\big{)}$
$\displaystyle\leq h_{i}\big{(}\lambda f(x)+(1-\lambda)f(y)\big{)}$ (15)
$\displaystyle\leq\lambda h_{i}(f(x))+(1-\lambda)h_{i}(f(y))$ (16)

In the above, the first inequality follows from the convexity of $f$ and non-
decreasing nature of $h_{i}$ and the second inequality follows from convexity
of $h_{i}$. Therefore, we have that $h_{i}\cdot f=h_{i}(f())$ is a convex
function in $x$. This shows that the objective function of (P) is convex in
$x$ since $C_{nm}^{i}=h_{i}\cdot f$. Finally, since the constraints are linear
in $x$, we have that problem (P) is convex. ∎

The cost function of the optimization problem (P) is plotted for the sake of
visual inspection of its convexity. The cost function is denoted as
$C_{nm}(i)$ which equals
$[z_{i}+s_{i}]^{+}p_{b}^{i}-[z_{i}+s_{i}]^{-}p_{s}^{i}$. Reiterating our
convention: consumed electricity is considered to be positive, thus for
$x_{i}>0$ the battery is consuming or in other words charging. The net load
without storage is positive means that load seen from the grid is charged for
consumption. For plotting the cost function with respect to the optimization
variable $x_{i}$ we consider the following two cases:

###  A-A The net load is positive ($z_{i}>0$)

In this case we have the following cost function versus the storage operation.
It is also shown in Fig. 19.

  1. 1.

For charging $C_{nm}(i)=[z_{i}+x_{i}/\eta_{\text{ch}}]p_{b}^{i}$,

  2. 2.

For discharging:

    1. (a)

If $-z_{i}<x_{i}\eta_{\text{dis}}$ then
$C_{nm}(i)=[z_{i}+x_{i}\eta_{\text{dis}}]p_{b}^{i}$,

    2. (b)

Else $C_{nm}(i)=[z_{i}+x_{i}\eta_{\text{dis}}]p_{s}^{i}$.

Figure 19: Cost function for $z_{i}>0$

###  A-B The net load is negative ($z_{i}<0$)

Here the cost function (versus the storage operation) is expressed as follows.
It is illustrated in Fig. 20.

  1. 1.

For charging we have the following conditions:

    1. (a)

If $|z_{i}|<x_{i}/\eta_{\text{ch}}$ then
$C_{nm}(i)=[z_{i}+x_{i}/\eta_{\text{ch}}]p_{b}^{i}$,

    2. (b)

Else $C_{nm}(i)=[z_{i}+x_{i}/\eta_{\text{ch}}]p_{s}^{i}$.

  2. 2.

For discharging we have $C_{nm}(i)=[z_{i}+x_{i}\eta_{\text{dis}}]p_{s}^{i}$.

Figure 20: Cost function for $z_{i}<0$

It can be observed from Fig. 19 and Fig. 20 that when $\kappa_{i}$ exceeds 1,
the plots will become concave. Therefore, in this work we assume that
$\kappa_{i}\in[0,1]$ and hence this assumption ensures the convexity of the
cost function.

##  Appendix B Proof of Theorem III.2

###### Proof.

The optimization problem is convex with respect to the optimization variable
$x^{*}$, using Theorem III.1. From Eq. 2, it is easy to see that there is a
one-to-one mapping of $s_{i}$ and $x_{i}$. We first prove the existence of
$(s^{*},\alpha^{*},\beta^{*})$ such that:

  1. 1.

$s^{*}$ is the primal optimal solution,

  2. 2.

$(\alpha^{*},\beta^{*})$ is the dual optimal solution, and

  3. 3.

the optimality gap is zero (strong duality).

Since the constraints of the primal problem are all linear, weak Slater’s
constraint qualification conditions (which imply strong duality) follow simply
from the feasibility of the primal problem. Clearly, under the assumptions
$b_{\min}\leq b_{\max},\delta_{\min}\leq\delta_{\max}$,
$b_{0}\in[b_{\min},b_{\max}]$, $0\in[\delta_{\min},\delta_{\max}]$ a feasible
solution exists ($s_{i}=0$ for all $i=1,2,\ldots,N$ is feasible). Furthermore,
since the primal objective function is continuous and the constraints define a
convex compact set, its minimum must be finite and achieved at the some
$s^{*}$ in the feasibility region. According to the strong duality theorem,
the above facts imply that the dual problem must be maximized at some
$(\alpha^{*},\beta^{*})$ and the duality gap must be zero.

From the above reasoning it also follows that $(s^{*},\alpha^{*},\beta^{*})$
must be the saddle point satisfying the KKT conditions. Hence, using RHS
inequality of the Saddle Point conditions,

$\displaystyle\mathscr{L}({x^{*},\alpha^{*},\beta^{*}})\leq\mathscr{L}({x,\alpha^{*},\beta^{*}})$
$\displaystyle\implies\sum_{i=1}^{N}\Big{\\{}C_{\text{nm}}^{(i)}(x_{i}^{*})+\alpha_{i}^{*}(b_{\min}-b_{i}^{*})+\beta_{i}^{*}(b_{i}^{*}-b_{max})\Big{\\}}$
$\displaystyle\leq\sum_{i=1}^{N}\Big{\\{}C_{\text{nm}}^{(i)}(x_{i})+\alpha_{i}^{*}(b_{min}-b_{i})+\beta_{i}^{*}(b_{i}-b_{max})\Big{\\}}$

Substituting $b_{i}=b_{0}+\sum_{j=1}^{i}x_{j}$ we get,

$\sum_{i=1}^{N}\Big{\\{}C_{\text{nm}}^{(i)}(x_{i}^{*})-\mu_{i}^{*}x_{i}^{*}\Big{\\}}\leq\sum_{i=1}^{N}\Big{\\{}C_{\text{nm}}(x_{i})-\mu_{i}^{*}x_{i}\Big{\\}}$
(17)

where $\mu_{i}^{*}=\sum_{j=i}^{N}(\alpha_{j}^{*}-\beta_{j}^{*})$.
$\mu_{i}^{*}$ is the accumulated Lagrange multiplier for time instant $i$ to
$N$. Hence,

$\mu_{k}^{*}-\mu_{k+1}^{*}=(\alpha_{k}^{*}-\beta_{k}^{*})$ (18)

The complementary slackness conditions for the Lagrangian are defined as

$\displaystyle\alpha_{i}(b_{\min}-b_{i})=0,\quad\beta_{i}(b_{i}-b_{\max})=0,\forall
i\text{ s.t. }\alpha_{i},\beta_{i}\geq 0$

Equation (8) derived above and complementary slackness conditions imply the
following relation between $\mu_{k}^{*}$ and $\mu_{k+1}^{*}$,

$\displaystyle\mu_{k+1}^{*}\begin{cases}=\mu_{k}^{*},&\text{if
}b_{min}<b_{k}^{*}<b_{max}\quad\text{ as
}\quad\alpha_{k}^{*}=\beta_{k}^{*}=0\\\ \leq\mu_{k}^{*},&\text{if
}b_{k}^{*}=b_{min}\quad\text{ as }\quad\alpha_{k}^{*}\geq 0\text{ and
}\beta_{k}^{*}=0\\\ \geq\mu_{k}^{*},&\text{if }b_{k}^{*}=b_{max}\quad\text{ as
}\quad\alpha_{k}^{*}=0\text{ and }\beta_{k}^{*}\geq 0\end{cases}$

The accumulated Lagrangian i.e. $\mu$ for the $N^{th}$ (last) instant is
$\mu_{N}^{*}=\alpha_{N}^{*}-\beta_{N}^{*}$, therefore

$\displaystyle\mu_{N}^{*}=\begin{cases}=0^{*},&\text{if
}b_{min}<b_{N}^{*}<b_{max}\\\ \geq 0,&\text{if }b_{N}^{*}=b_{min}\\\ \leq
0,&\text{if }b_{N}^{*}=b_{max}\end{cases}$

Such a ${x^{*}}$ solves the optimal arbitrage problem (P) and
${\alpha^{*},\beta^{*}}$ solves the dual problem. ∎

##  Appendix C Proof of Theorem III.3

For a given $\mu_{i}^{*}=\mu$ the optimal decision $s_{i}^{*}(\mu)$ is given
by minimizing Eq. 19.

$[z_{i}+s_{i}]^{+}p_{b}(i)-[z_{i}+s_{i}]^{-}p_{s}(i)-\mu\Big{(}\eta_{\text{ch}}[s_{i}]^{+}-\frac{1}{\eta_{\text{dis}}}[s_{i}]^{-}\Big{)}$
(19)

Hence, in order to minimize Eq. 19 we consider the sign of $(z_{i}+s_{i})$ and
$s_{i}$. This will provide the following cases

  * J1: $s_{i}(p_{b}(i)-\mu\eta_{\text{ch}})$ s.t. $z_{i}+s_{i}\geq 0$ and $s_{i}\in[0,S_{\max}]$,

  * J2: $s_{i}(p_{s}(i)-\mu\eta_{\text{ch}})$ s.t. $z_{i}+s_{i}\leq 0$ and $s_{i}\in[0,S_{\max}]$,

  * J3: $s_{i}\Big{(}p_{b}(i)-\frac{\mu}{\eta_{\text{dis}}}\Big{)}$ s.t. $z_{i}+s_{i}\geq 0$ and $s_{i}\in[S_{\min},0]$,

  * J4: $s_{i}\Big{(}p_{s}(i)-\frac{\mu}{\eta_{\text{dis}}}\Big{)}$ s.t. $z_{i}+s_{i}\leq 0$ and $s_{i}\in[S_{\min},0]$.

The accumulated Lagrange multiplier, $\mu$, can be viewed as the shadow price
of decision making. Based on conditions J1 to J4, the value of $\mu$ will
divide the price levels into nine cases. Table V lists the constraints and
minimizing conditions, we will use this table to find optimal value of
$s_{i}^{*}$.

TABLE V: Conditions to check Tag | $[z_{i}+s_{i}]$ | $[s_{i}]$ |  $\min$ Condition | Desired scenario
---|---|---|---|---
J1 | +ve | +ve | $s_{i}(p_{b}(i)-\mu\eta_{\text{ch}})$ | $(p_{b}(i)-\mu\eta_{\text{ch}})\leq 0$
J2 | -ve | +ve | $s_{i}(p_{s}(i)-\mu\eta_{\text{ch}})$ | $(p_{s}(i)-\mu\eta_{\text{ch}})\leq 0$
J3 | +ve | -ve | $s_{i}(p_{b}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | $(p_{b}(i)-\frac{\mu}{\eta_{\text{dis}}})\geq 0$
J4 | -ve | -ve | $s_{i}(p_{s}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | $(p_{s}(i)-\frac{\mu}{\eta_{\text{dis}}})\geq 0$

From Table V we can see the conditions of desired scenarios. Based on
conditions J1 to J4, we can observe there will be four distinct levels in
price signal which will subsequently divide the real line into nine possible
levels for the accumulated Lagrange multiplier ($\mu$) as shown in Fig 2 and
Fig. 21.

###  C-A For $\kappa_{i}\in[0,\eta_{\text{ch}}\eta_{\text{dis}})$

Region 1: $\mu<\eta_{\text{dis}}p_{s}(i)$: The minimizing conditions will be
achieved by J3 and J4 as shown below:

Tag | $[z_{i}+s_{i}]$ | $[s_{i}]$ |  $\min$ Condition | Sign | Comment
---|---|---|---|---|---
J1 | +ve | +ve | $s_{i}(p_{b}(i)-\mu\eta_{\text{ch}})$ | \+ (+) | Undesired
J2 | -ve | +ve | $s_{i}(p_{s}(i)-\mu\eta_{\text{ch}})$ | \+ (+) | Undesired
J3 | +ve | -ve | $s_{i}(p_{b}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (+) | Desired
J4 | -ve | -ve | $s_{i}(p_{s}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (+) | Desired

From J4 if $(z_{i}+s_{i})<0$ then $s_{i}^{*}=[S_{\min},S_{\min}]$ and from J3
if $(z_{i}+s_{i})\geq 0$ then $s_{i}^{*}=[S_{\min},S_{\min}]$. Therefore,
irrespective the sign of $z_{i}$ the optimal value is $[S_{\min},S_{\min}]$.

Region 2: $\mu=\eta_{\text{dis}}p_{s}(i)$: The minimizing conditions will be
achieved by J3 and J4 is a don’t care condition with only constraint on
$s_{i}$ being negative or zero.

Tag | $[z_{i}+s_{i}]$ | $[s_{i}]$ |  $\min$ Condition | Sign | Comment
---|---|---|---|---|---
J1 | +ve | +ve | $s_{i}(p_{b}(i)-\mu\eta_{\text{ch}})$ | \+ (+) | Undesired
J2 | -ve | +ve | $s_{i}(p_{s}(i)-\mu\eta_{\text{ch}})$ | \+ (+) | Undesired
J3 | +ve | -ve | $s_{i}(p_{b}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (+) | Desired
J4 | -ve | -ve | $s_{i}(p_{s}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (0) | Don’t Care

Sub-Case 1:  from J3 and J4 if $z_{i}\geq 0$ then
$s_{i}^{*}=[S_{\min},\max(-z_{i},S_{\min})]$.

Sub-Case 2:  from J4 if $z_{i}<0$ then $s_{i}^{*}=[S_{\min},0]$.

Region 3:
$\mu\in(\eta_{\text{dis}}p_{s}(i),\frac{p_{s}(i)}{\eta_{\text{ch}}})$: The
minimizing conditions will be achieved by minimizing J3. All other conditions,
i.e., J1, J2 and J4 are undesired.

Tag | $[z_{i}+s_{i}]$ | $[s_{i}]$ |  $\min$ Condition | Sign | Comment
---|---|---|---|---|---
J1 | +ve | +ve | $s_{i}(p_{b}(i)-\mu\eta_{\text{ch}})$ | \+ (+) | Undesired
J2 | -ve | +ve | $s_{i}(p_{s}(i)-\mu\eta_{\text{ch}})$ | \+ (+) | Undesired
J3 | +ve | -ve | $s_{i}(p_{b}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (+) | Desired
J4 | -ve | -ve | $s_{i}(p_{s}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (-) | Undesired

Sub-Case 1:  from J3 if $z_{i}\geq 0$ then
$s_{i}^{*}=[\max\\{-z_{i},S_{\min}\\},\max\\{-z_{i},S_{\min}\\}]$.

Sub-Case 2:  from J2 and J4 $s_{i}^{*}=[0,0]$.

Region 4: $\mu=\frac{p_{s}(i)}{\eta_{\text{ch}}}$: The minimizing conditions
will be achieved by minimizing J3. J2 is a don’t care condition.

Tag | $[z_{i}+s_{i}]$ | $[s_{i}]$ |  $\min$ Condition | Sign | Comment
---|---|---|---|---|---
J1 | +ve | +ve | $s_{i}(p_{b}(i)-\mu\eta_{\text{ch}})$ | \+ (+) | Undesired
J2 | -ve | +ve | $s_{i}(p_{s}(i)-\mu\eta_{\text{ch}})$ | \+ (0) | Don’t Care
J3 | +ve | -ve | $s_{i}(p_{b}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (+) | Desired
J4 | -ve | -ve | $s_{i}(p_{s}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (-) | Undesired

Sub-Case 1:  from J3 if $z_{i}\geq 0$ then
$s_{i}^{*}=[\max\\{-z_{i},S_{\min}\\},\max\\{-z_{i},S_{\min}\\}]$.

Sub-Case 2:  from J2, if $z_{i}<0$ then
$s_{i}^{*}=[0,\min\\{-z_{i},S_{\max}\\}]$.

Region 5:
$\mu\in(\frac{p_{s}(i)}{\eta_{\text{ch}}},\eta_{\text{dis}}p_{b}(i))$: The
minimizing conditions will be achieved by minimizing J2 and J3.

Tag | $[z_{i}+s_{i}]$ | $[s_{i}]$ |  $\min$ Condition | Sign | Comment
---|---|---|---|---|---
J1 | +ve | +ve | $s_{i}(p_{b}(i)-\mu\eta_{\text{ch}})$ | \+ (+) | Undesired
J2 | -ve | +ve | $s_{i}(p_{s}(i)-\mu\eta_{\text{ch}})$ | \+ (-) | Desired
J3 | +ve | -ve | $s_{i}(p_{b}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (+) | Desired
J4 | -ve | -ve | $s_{i}(p_{s}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (-) | Undesired

Sub-Case 1:  from J3 if $z_{i}\geq 0$ then
$s_{i}^{*}=[\max\\{-z_{i},S_{\min}\\},\max\\{-z_{i},S_{\min}\\}]$.

Sub-Case 2:  from J2, if $z_{i}<0$ then
$s_{i}^{*}=[\min\\{-z_{i},S_{\max}\\},\min\\{-z_{i},S_{\max}\\}]$.

Region 6: $\mu=\eta_{\text{dis}}p_{b}(i)$: The minimizing conditions will be
achieved by J2 and J3 is a don’t care condition with only constraint on
$s_{i}$ being negative or zero.

Tag | $[z_{i}+s_{i}]$ | $[s_{i}]$ |  $\min$ Condition | Sign | Comment
---|---|---|---|---|---
J1 | +ve | +ve | $s_{i}(p_{b}(i)-\mu\eta_{\text{ch}})$ | \+ (+) | Undesired
J2 | -ve | +ve | $s_{i}(p_{s}(i)-\mu\eta_{\text{ch}})$ | \+ (-) | Desired
J3 | +ve | -ve | $s_{i}(p_{b}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (0) | Don’t Care
J4 | -ve | -ve | $s_{i}(p_{s}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (-) | Undesired

Sub-Case 1:  from J3 if $z_{i}\geq 0$ then
$s_{i}^{*}=[\max\\{-z_{i},S_{\min}\\},0]$.

Sub-Case 2:  from J2 if $z_{i}<0$ then
$s_{i}^{*}=[\min\\{-z_{i},S_{\max}\\},\min\\{-z_{i},S_{\max}\\}]$.

Region 7:
$\mu\in(\eta_{\text{dis}}p_{b}(i),\frac{p_{b}(i)}{\eta_{\text{ch}}})$: The
minimizing conditions will be achieved by J2. All other cases will be
undesirable.

Tag | $[z_{i}+s_{i}]$ | $[s_{i}]$ |  $\min$ Condition | Sign | Comment
---|---|---|---|---|---
J1 | +ve | +ve | $s_{i}(p_{b}(i)-\mu\eta_{\text{ch}})$ | \+ (+) | Undesired
J2 | -ve | +ve | $s_{i}(p_{s}(i)-\mu\eta_{\text{ch}})$ | \+ (-) | Desired
J3 | +ve | -ve | $s_{i}(p_{b}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (-) | Undesired
J4 | -ve | -ve | $s_{i}(p_{s}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (-) | Undesired

Sub-Case 1:  from J2 if $z_{i}<0$ then
$s_{i}^{*}=[\min\\{-z_{i},S_{\max}\\},\min\\{-z_{i},S_{\max}\\}]$.

Sub-Case 2:  if $z_{i}\geq 0$ then do nothing, $s_{i}^{*}=[0,0]$. This is
because J1 and J3 covers two direction of movement i.e. charging and
discharging, both of which will increase the objective function

Region 8: $\mu=\frac{p_{b}(i)}{\eta_{\text{ch}}}$: The minimizing conditions
will be achieved by J2 and J1 is a don’t care condition.

Tag | $[z_{i}+s_{i}]$ | $[s_{i}]$ |  $\min$ Condition | Sign | Comment
---|---|---|---|---|---
J1 | +ve | +ve | $s_{i}(p_{b}(i)-\mu\eta_{\text{ch}})$ | \+ (0) | Don’t Care
J2 | -ve | +ve | $s_{i}(p_{s}(i)-\mu\eta_{\text{ch}})$ | \+ (-) | Desired
J3 | +ve | -ve | $s_{i}(p_{b}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (-) | Undesired
J4 | -ve | -ve | $s_{i}(p_{s}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (-) | Undesired

Sub-Case 1:  from J2 and J1 if $z_{i}<0$ then
$s_{i}^{*}=[\min\\{-z_{i},S_{\max}\\},S_{\max}]$.

Sub-Case 2:  from J1 is $z_{i}\geq 0$ then $s_{i}^{*}=[0,S_{\max}]$.

Region 9: $\mu>\frac{p_{b}(i)}{\eta_{\text{ch}}}$: The minimizing conditions
will be achieved by J2 and J1.

Tag | $[z_{i}+s_{i}]$ | $[s_{i}]$ |  $\min$ Condition | Sign | Comment
---|---|---|---|---|---
J1 | +ve | +ve | $s_{i}(p_{b}(i)-\mu\eta_{\text{ch}})$ | \+ (-) | Desired
J2 | -ve | +ve | $s_{i}(p_{s}(i)-\mu\eta_{\text{ch}})$ | \+ (-) | Desired
J3 | +ve | -ve | $s_{i}(p_{b}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (-) | Undesired
J4 | -ve | -ve | $s_{i}(p_{s}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (-) | Undesired

Irrespective of sign of $z_{i}$, $s_{i}^{*}=[S_{\max},S_{\max}]$.

###  C-B Proof of Theorem III.3 for
$\kappa_{i}\in[\eta_{\text{ch}}\eta_{\text{dis}},1)$

Figure 21: Regions based on levels of $\mu$ for $\zeta_{i}\geq 1$

Based on four levels of prices shown in Fig 21, the range is divided into into
nine possible bands for the accumulated Lagrange multiplier.

Region 1: $\mu<\eta_{\text{dis}}p_{s}(i)$: The minimizing conditions will be
achieved by J3 and J4 as shown below

Tag | $[z_{i}+s_{i}]$ | $[s_{i}]$ | min Condition | Sign | Comment
---|---|---|---|---|---
J1 | +ve | +ve | $s_{i}(p_{b}(i)-\mu\eta_{\text{ch}})$ | \+ (+) | Undesired
J2 | -ve | +ve | $s_{i}(p_{s}(i)-\mu\eta_{\text{ch}})$ | \+ (+) | Undesired
J3 | +ve | -ve | $s_{i}(p_{b}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (+) | Desired
J4 | -ve | -ve | $s_{i}(p_{s}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (+) | Desired

From J4 if $(z_{i}+s_{i})<0$ then $s_{i}^{*}=[S_{\min},S_{\min}]$ and from J3
if $(z_{i}+s_{i})\geq 0$ then $s_{i}^{*}=[S_{\min},S_{\min}]$. Therefore,
irrespective the sign of $z_{i}$ the optimal value is $[S_{\min},S_{\min}]$.

Region 2: $\mu=\eta_{\text{dis}}p_{s}(i)$: The minimizing conditions will be
achieved by J3 and J4 is a don’t care condition with only constraint on
$s_{i}$ being negative or zero.

Tag | $[z_{i}+s_{i}]$ | $[s_{i}]$ | min Condition | Sign | Comment
---|---|---|---|---|---
J1 | +ve | +ve | $s_{i}(p_{b}(i)-\mu\eta_{\text{ch}})$ | \+ (+) | Undesired
J2 | -ve | +ve | $s_{i}(p_{s}(i)-\mu\eta_{\text{ch}})$ | \+ (+) | Undesired
J3 | +ve | -ve | $s_{i}(p_{b}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (+) | Desired
J4 | -ve | -ve | $s_{i}(p_{s}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (0) | Don’t Care

Sub-Case 1:  from J3 and J4 if $z_{i}\geq 0$ then
$s_{i}^{*}=[S_{\min},\max\\{-z_{i},S_{\min}\\}]$.

Sub-Case 2:  from J4 if $z_{i}<0$ then $s_{i}^{*}=[S_{\min},0]$.

Region 3: $\mu\in(\eta_{\text{dis}}p_{s}(i),\eta_{\text{dis}}p_{b}(i))$: The
minimizing conditions will be achieved by minimizing J3. All other conditions,
i.e., J1, J2 and J4 are undesired.

Tag | $[z_{i}+s_{i}]$ | $[s_{i}]$ | min Condition | Sign | Comment
---|---|---|---|---|---
J1 | +ve | +ve | $s_{i}(p_{b}(i)-\mu\eta_{\text{ch}})$ | \+ (+) | Undesired
J2 | -ve | +ve | $s_{i}(p_{s}(i)-\mu\eta_{\text{ch}})$ | \+ (+) | Undesired
J3 | +ve | -ve | $s_{i}(p_{b}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (+) | Desired
J4 | -ve | -ve | $s_{i}(p_{s}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (-) | Unesired

Sub-Case 1:  from J3 if $z_{i}\geq 0$ then
$s_{i}^{*}=[\max\\{-z_{i},S_{\min}\\},\max\\{-z_{i},S_{\min}\\}]$.

Sub-Case 2:  from J2 and J4 $s_{i}^{*}=[0,0]$.

Region 4: $\mu=\eta_{\text{dis}}p_{b}(i)$:

Tag | $[z_{i}+s_{i}]$ | $[s_{i}]$ | min Condition | Sign | Comment
---|---|---|---|---|---
J1 | +ve | +ve | $s_{i}(p_{b}(i)-\mu\eta_{\text{ch}})$ | \+ (+) | Undesired
J2 | -ve | +ve | $s_{i}(p_{s}(i)-\mu\eta_{\text{ch}})$ | \+ (+) | Undesired
J3 | +ve | -ve | $s_{i}(p_{b}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (0) | Don’t Care
J4 | -ve | -ve | $s_{i}(p_{s}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (-) | Undesired

Sub-Case 1:  from J3 if $z_{i}\geq 0$ then
$s_{i}^{*}=[\max\\{-z_{i},S_{\min}\\},0]$.

Sub-Case 2:  from J2 and J4, if $z_{i}<0$ then $s_{i}^{*}=[0,0]$.

Region 5:
$\mu\in(\eta_{\text{dis}}p_{b}(i),\frac{p_{s}(i)}{\eta_{\text{ch}}})$:

Tag | $[z_{i}+s_{i}]$ | $[s_{i}]$ | min Condition | Sign | Comment
---|---|---|---|---|---
J1 | +ve | +ve | $s_{i}(p_{b}(i)-\mu\eta_{\text{ch}})$ | \+ (+) | Undesired
J2 | -ve | +ve | $s_{i}(p_{s}(i)-\mu\eta_{\text{ch}})$ | \+ (+) | Undesired
J3 | +ve | -ve | $s_{i}(p_{b}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (-) | Undesired
J4 | -ve | -ve | $s_{i}(p_{s}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (-) | Undesired

Sub-Case 1:  from J1 and J3 if $z_{i}\geq 0$ then $s_{i}^{*}=[0,0]$.

Sub-Case 2:  from J2 and J4, if $z_{i}<0$ then $s_{i}^{*}=[0,0]$.

Region 6: $\mu=\frac{p_{s}(i)}{\eta_{\text{ch}}}$:

Tag | $[z_{i}+s_{i}]$ | $[s_{i}]$ | min Condition | Sign | Comment
---|---|---|---|---|---
J1 | +ve | +ve | $s_{i}(p_{b}(i)-\mu\eta_{\text{ch}})$ | \+ (+) | Undesired
J2 | -ve | +ve | $s_{i}(p_{s}(i)-\mu\eta_{\text{ch}})$ | \+ (0) | Don’t Care
J3 | +ve | -ve | $s_{i}(p_{b}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (-) | Undesired
J4 | -ve | -ve | $s_{i}(p_{s}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (-) | Undesired

Sub-Case 1:  from J1 and J3 if $z_{i}\geq 0$ then $s_{i}^{*}=[0,0]$.

Sub-Case 2:  from J2 if $z_{i}<0$ then
$s_{i}^{*}=[0,\min\\{-z_{i},S_{\max}\\}]$.

Region 7:
$\mu\in(\frac{p_{s}(i)}{\eta_{\text{ch}}},\frac{p_{b}(i)}{\eta_{\text{ch}}})$:
The minimizing conditions will be achieved by J2. All other cases will be
undesirable.

Tag | $[z_{i}+s_{i}]$ | $[s_{i}]$ | min Condition | Sign | Comment
---|---|---|---|---|---
J1 | +ve | +ve | $s_{i}(p_{b}(i)-\mu\eta_{\text{ch}})$ | \+ (+) | Undesired
J2 | -ve | +ve | $s_{i}(p_{s}(i)-\mu\eta_{\text{ch}})$ | \+ (-) | Desired
J3 | +ve | -ve | $s_{i}(p_{b}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (-) | Undesired
J4 | -ve | -ve | $s_{i}(p_{s}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (-) | Undesired

Sub-Case 1:  from J2 if $z_{i}<0$ then
$s_{i}^{*}=[\min\\{-z_{i},S_{\max}\\},\min\\{-z_{i},S_{\max}\\}]$.

Sub-Case 2:  if $z_{i}\geq 0$ then do nothing, $s_{i}^{*}=[0,0]$. This is
because J1 and J3 covers two direction of movement i.e. charging and
discharging, both of which will increase the objective function

Region 8: $\mu=\frac{p_{b}(i)}{\eta_{\text{ch}}}$: The minimizing conditions
will be achieved by J2 and J1 is a don’t care condition.

Tag | $[z_{i}+s_{i}]$ | $[s_{i}]$ | min Condition | Sign | Comment
---|---|---|---|---|---
J1 | +ve | +ve | $s_{i}(p_{b}(i)-\mu\eta_{\text{ch}})$ | \+ (0) | Don’t Care
J2 | -ve | +ve | $s_{i}(p_{s}(i)-\mu\eta_{\text{ch}})$ | \+ (-) | Desired
J3 | +ve | -ve | $s_{i}(p_{b}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (-) | Undesired
J4 | -ve | -ve | $s_{i}(p_{s}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (-) | Undesired

Sub-Case 1:  from J2 and J1 if $z_{i}<0$ then
$s_{i}^{*}=[\min\\{-z_{i},S_{\max}\\},S_{\max}]$.

Sub-Case 2:  from J1 is $z_{i}\geq 0$ then $s_{i}^{*}=[0,S_{\max}]$.

Region 9: $\mu>\frac{p_{b}(i)}{\eta_{\text{ch}}}$: The minimizing conditions
will be achieved by J2 and J1.

Tag | $[z_{i}+s_{i}]$ | $[s_{i}]$ | min Condition | Sign | Comment
---|---|---|---|---|---
J1 | +ve | +ve | $s_{i}(p_{b}(i)-\mu\eta_{\text{ch}})$ | \+ (-) | Desired
J2 | -ve | +ve | $s_{i}(p_{s}(i)-\mu\eta_{\text{ch}})$ | \+ (-) | Desired
J3 | +ve | -ve | $s_{i}(p_{b}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (-) | Undesired
J4 | -ve | -ve | $s_{i}(p_{s}(i)-\frac{\mu}{\eta_{\text{dis}}})$ | \- (-) | Undesired

Irrespective of sign of $z_{i}$, $s_{i}^{*}=[S_{\max},S_{\max}]$.

##  Appendix D Stylized Example

In this appendix we present a stylized example to demonstrate the operation of
the proposed optimal arbitrage algorithm which is composed of Alg. 1 and Alg.
2. Alg. 1 is used to identify a sub-horizon and returns the lower and the
upper envelope of battery charge level in the sub-horizon. Alg. 2 is
implemented once for a sub-horizon to identify the optimal battery charge
level.

We consider the case with $\kappa_{i}=1$ implies buying and selling price for
time instant $i$ are the same and charging and discharging efficiency equal to
1. For equal buying and selling price, minimizing the total cost of
consumption, i.e., $\sum(z_{i}+s_{i})p_{\text{elec}}(i)$, is equivalent to
minimizing the cost of operation of storage, $\sum s_{i}p_{\text{elec}}(i)$.
Here the price of electricity,
$p_{\text{elec}}(i)=p_{s}(i)=p_{b}(i)~{}\forall~{}i$ [28].

The optimal control decision $x_{i}^{*}$ in the $i$th instant minimizes the
function $C_{\text{storage}}^{(i)}(x)-\mu_{i}^{*}x$ for
$x\in\left[X_{\min}^{i},X_{\max}^{i}\right]$. $x_{i}^{*}(\mu)$ is given by:

$x_{i}^{*}(\mu)=\begin{cases}[X_{\min}^{i},X_{\min}^{i}],&\text{if
}\mu<p_{\text{elec}}(i),\\\ \left[X_{\min}^{i},X_{\max}^{i}\right],&\text{if
}\mu=p_{\text{elec}}(i),\\\ [X_{\max}^{i},X_{\max}^{i}],&\text{if
}\mu>p_{\text{elec}}(i),\end{cases}$ (20)

where $C_{\text{storage}}^{(i)}(x_{i})=s_{i}p_{\text{elec}}(i)$. For
$\mu=p_{\text{elec}}(i)$, $x_{i}^{*}(\mu)$ takes an envelope of values. This
threshold based structure has a sub-gradient. For any other value of $\mu$ it
is a singleton set.

This example considers a lossless battery under equal buying and selling price
of electricity. For this example the price of electricity is assumed to be in
ascending order (worst case), i.e., $0<p_{1}<p_{2}<p_{3}...$ and so on. The
accumulated Lagrange multiplier ($\mu$) is initiated from zero. Fig. 22 shows
the battery charge level trajectory for $\mu=0$. The battery charge level has
a feasible trajectory till $i=1$. The temporary sub-horizon has sample between
$i=0$ and $i=1$. Since $p_{1}>\mu$ therefore, battery should discharge at
maximum rate, based on the threshold based structure.

Figure 22: Battery charge level trajectory for $\mu=0$

In the next iteration of the algorithm the accumulated Lagrange multiplier
should be increased to the price level in the identified sub-horizon, i.e.
$p_{1}$. The value of $\mu$ is increased because of the lower capacity
violation in Fig. 22, see Condition (4) of Theorem III.2. With this alteration
of $\mu$, the temporary sub-horizon has increased from $i=0$ to $i=2$, as no
feasible charge level exists at $i=3$.

Figure 23: Battery charge level trajectory for $\mu=p_{1}$

In the next iteration the value of $\mu$ is increased to $p_{2}$. For the
first time instant the battery should charge as $\mu>p_{1}$. For the second
time instant the battery charge level has an envelope based structure between
$i=1$ to $i=2$. For the third time $\mu<p_{3}$ therefore, the battery should
discharge. The new temporary sub-horizon has increased from $i=0$ to $i=4$, as
shown in Fig. 24.

Figure 24: Battery charge level trajectory for $\mu=p_{2}$ Figure 25: Battery
charge level trajectory for $\mu=p_{3}$ Figure 26: Battery charge level
trajectory for $\mu=p_{4}$

Similar adjustment of $\mu$ is performed till the sub-horizon keeps
increasing, see Fig. 22 to 26. Any further increase in $\mu$ from the case
denoted in Fig. 26 decreases the length of the sub-horizon, shown in Fig. 27.

Figure 27: Battery charge level trajectory for $\mu=p_{5}$

The value of $\mu$ associated with case shown in Fig. 26 is called the optimal
accumulated Lagrange multiplier denoted as $\mu^{*}$ for the sub-horizon. For
this example $\mu^{*}=p_{4}$. The value of battery charge level trajectory
associated with $\mu^{*}$ is the input to Alg.2. Note the value of $\mu^{*}$
acts as the shadow price and remains constant for a sub-horizon. The value of
$\mu^{*}$ is selected from finite number of discrete levels of electricity
price in the sub-horizon. This makes the proposed algorithm computationally
very efficient due to this discretization of a continuous optimization
problem.

Alg. 2 takes as input the envelope of battery charge level and identifies the
optimal solution. BackwardStep algorithm fix the last time instant in the sub-
horizon at $b_{\min}$ and back-calculates the optimal battery charge level.
For time instant where $\mu^{*}$ is equal to the price level, anything from
$X_{\min}$ to $X_{max}$ is possible. Note neither charging or discharging is
profitable or loss here, however, the battery could charge some more if there
are possible discharging opportunities in adjacent time periods in the sub-
horizon. Similarly, the battery could discharge here if there are lower
discharging opportunities in adjacent time periods in the sub-horizon. This
period provides a slack in adjusting battery charge level. It is essential to
note that in this period intermediate ramp rate could be possible, contrary to
all prior works on threshold based optimal decision making. The optimal
battery capacity is shown in Fig. 28.

Figure 28: Optimal Battery charge level

The next sub-horizon begins at $i=7$ as the optimal actions have been
identified from $i=0$ to $i=6$.