  The high proportions of demand charges in electric bills motivate large-power
customers to leverage energy storage for reducing the peak procurement from the
outer grid. Given limited energy storage, we expect to maximize the peak-demand
reduction in an online fashion, challenged by the highly uncertain demands and
renewable injections, the non-cumulative nature of peak consumption, and the
coupling of online decisions. In this paper, we propose an optimal online
algorithm that achieves the best competitive ratio, following the idea of
maintaining a constant ratio between the online and the optimal offline
peak-reduction performance. We further show that the optimal competitive ratio
can be computed by solving a linear number of linear-fractional programs.
Moreover, we extend the algorithm to adaptively maintain the best competitive
ratio given the revealed inputs and actions at each decision-making round. The
adaptive algorithm retains the optimal worst-case guarantee and attains
improved average-case performance. We evaluate our proposed algorithms using
real-world traces and show that they obtain up to 81% peak reduction of the
optimal offline benchmark. Additionally, the adaptive algorithm achieves at
least 20% more peak reduction against baseline alternatives.
