Search

Stability of the BDF methods of order up to five for parabolic equations can be established by the energy technique via Nevanlinna--Odeh multipliers. The nonexistence of Nevanlinna--Odeh multipliers makes the six-step BDF method special; however, the energy technique was recently extended by the authors in [Akrivis et al., SIAM J. Numer. Anal. \textbf{59} (2021) 2449--2472] and covers all six stable BDF methods. The seven-step BDF method is unstable for parabolic equations, since it is not even zero-stable. In this work, we construct and analyze a stable linear combination of two non zero-stable schemes, the seven-step BDF method and its shifted counterpart, referred to as WSBDF7 method. The stability regions of the WSBDF$q, q\leqslant 7$, with a weight $\vartheta\geqslant1$, increase as $\vartheta$ increases, are larger than the stability regions of the classical BDF$q,$ corresponding to $\vartheta=1$. We determine novel and suitable multipliers for the WSBDF7 method and establish stability for parabolic equations by the energy technique. The proposed approach is applicable for mean curvature flow, gradient flows, fractional equations and nonlinear equations., Comment: 23 pages

Can graded meshes yield more accurate numerical solution than uniform meshes? A time-dependent nonlocal diffusion problem with a weakly singular kernel is considered using collocation method. For its steady-state counterpart, under the sufficiently smooth solution, we first clarify that the standard graded meshes are worse than uniform meshes and may even lead to divergence; instead, an optimal convergence rate arises in so-called anomalous graded meshes. Furthermore, under low regularity solutions, it may suffer from a severe order reduction in (Chen, Qi, Shi and Wu, IMA J. Numer. Anal., 41 (2021) 3145--3174). In this case, conversely, a sharp error estimates appears in standard graded meshes, but offering far less than first-order accuracy. For the time-dependent case, however, second-order convergence can be achieved on graded meshes. The related analysis are easily extended for certain multidimensional problems. Numerical results are provided that confirm the sharpness of the error estimates., Comment: 20pages

The numerical analysis of stochastic time fractional evolution equations presents considerable challenges due to the limited regularity of the model caused by the nonlocal operator and the presence of noise. The existing time-stepping methods exhibit a significantly low order convergence rate. In this work, we introduce a smoothing technique and develop the novel high-order schemes for solving the linear stochastic fractional evolution equations driven by integrated additive noise. Our approach involves regularizing the additive noise through an $m$-fold integral-differential calculus, and discretizing the equation using the $k$-step BDF convolution quadrature. This novel method, which we refer to as the ID$m$-BDF$k$ method, is able to achieve higher-order convergence in solving the stochastic models. Our theoretical analysis reveals that the convergence rate of the ID$2$-BDF2 method is $O(\tau^{\alpha + \gamma -1/2})$ for $1< \alpha + \gamma \leq 5/2$, and $O(\tau^{2})$ for $5/2< \alpha + \gamma <3$, where $\alpha \in (1, 2)$ and $\gamma \in (0, 1)$ denote the time fractional order and the order of the integrated noise, respectively. Furthermore, this convergence rate could be improved to $O(\tau^{\alpha + \gamma -1/2})$ for any $\alpha \in (1, 2)$ and $\gamma \in (0, 1)$, if we employ the ID$3$-BDF3 method. The argument could be easily extended to the subdiffusion model with $\alpha \in (0, 1)$. Numerical examples are provided to support and complement the theoretical findings., Comment: 22pages

Anomalous diffusion in the presence or absence of an external force field is often modelled in terms of the fractional evolution equations, which can involve the hyper-singular source term. For this case, conventional time stepping methods may exhibit a severe order reduction. Although a second-order numerical algorithm is provided for the subdiffusion model with a simple hyper-singular source term $t^{\mu}$, $-2<\mu<-1$ in [arXiv:2207.08447], the convergence analysis remain to be proved. To fill in these gaps, we present a simple and robust smoothing method for the hyper-singular source term, where the Hadamard finite-part integral is introduced. This method is based on the smoothing/ID$m$-BDF$k$ method proposed by the authors [Shi and Chen, SIAM J. Numer. Anal., to appear] for subdiffusion equation with a weakly singular source term. We prove that the $k$th-order convergence rate can be restored for the diffusion-wave case $\gamma \in (1,2)$ and sketch the proof for the subdiffusion case $\gamma \in (0,1)$, even if the source term is hyper-singular and the initial data is not compatible. Numerical experiments are provided to confirm the theoretical results.

Carbon footprint optimization (CFO) is important for sustainable heavy-duty e-truck transportation. We consider the CFO problem for timely transportation of e-trucks, where the truck travels from an origin to a destination across a national highway network subject to a deadline. The goal is to minimize the carbon footprint by orchestrating path planning, speed planning, and intermediary charging planning. We first show that it is NP-hard even just to find a feasible CFO solution. We then develop a $(1+\epsilon_F, 1+\epsilon_\beta)$ bi-criteria approximation algorithm that achieves a carbon footprint within a ratio of $(1+\epsilon_F)$ to the minimum with no deadline violation and at most a ratio of $(1+\epsilon_\beta)$ battery capacity violation (for any positive $\epsilon_F$ and $\epsilon_\beta$). Its time complexity is polynomial in the size of the highway network, $1/\epsilon_F$, and $1/\epsilon_\beta$. Such algorithmic results are among the best possible unless P=NP. Simulation results based on real-world traces show that our scheme reduces up to 11\% carbon footprint as compared to baseline alternatives considering only energy consumption but not carbon footprint.

We study the carbon footprint optimization (CFO) of a heavy-duty e-truck traveling from an origin to a destination across a national highway network subject to a hard deadline, by optimizing path planning, speed planning, and intermediary charging planning. Such a CFO problem is essential for carbon-friendly e-truck operations. However, it is notoriously challenging to solve due to (i) the hard deadline constraint, (ii) positive battery state-of-charge constraints, (iii) non-convex carbon footprint objective, and (iv) enormous geographical and temporal charging options with diverse carbon intensity. Indeed, we show that the CFO problem is NP-hard. As a key contribution, we show that under practical settings it is equivalent to finding a generalized restricted shortest path on a stage-expanded graph, which extends the original transportation graph to model charging options. Compared to alternative approaches, our formulation incurs low model complexity and reveals a problem structure useful for algorithm design. We exploit the insights to develop an efficient dual-subgradient algorithm that always converges. As another major contribution, we prove that (i) each iteration only incurs polynomial-time complexity, albeit it requires solving an integer charging planning problem optimally, and (ii) the algorithm generates optimal results if a condition is met and solutions with bounded optimality loss otherwise. Extensive simulations based on real-world traces show that our scheme reduces up to 28% carbon footprint compared to baseline alternatives. The results also demonstrate that e-truck reduces 56% carbon footprint than internal combustion engine trucks.

Anomalous diffusion is often modelled in terms of the subdiffusion equation, which can involve a weakly singular source term. For this case, many predominant time stepping methods, including the correction of high-order BDF schemes [{\sc Jin, Li, and Zhou}, SIAM J. Sci. Comput., 39 (2017), A3129--A3152], may suffer from a severe order reduction. To fill in this gap, we propose a smoothing method for time stepping schemes, where the singular term is regularized by using a $m$-fold integral-differential calculus and the equation is discretized by the $k$-step BDF convolution quadrature, called ID$m$-BDF$k$ method. We prove that the desired $k$th-order convergence can be recovered even if the source term is a weakly singular and the initial data is not compatible. Numerical experiments illustrate the theoretical results.

We study a transportation problem where two heavy-duty trucks travel across the national highway from separate origins to destinations, subject to individual deadline constraints. Our objective is to minimize their total fuel consumption by jointly optimizing path planning, speed planning, and platooning configuration. Such a two-truck platooning problem is pervasive in practice yet challenging to solve due to hard deadline constraints and enormous platooning configurations to consider. We first leverage a unique problem structure to significantly simplify platooning optimization and present a novel formulation. We prove that the two-truck platooning problem is weakly NP-hard and admits a Fully Polynomial Time Approximation Scheme (FPTAS). The FPTAS can achieve a fuel consumption within a ratio of $(1+\epsilon)$ to the optimal (for any $\epsilon>0$) with a time complexity polynomial in the size of the transportation network and $1/\epsilon$. These results are in sharp contrast to the general multi-truck platooning problem, which is known to be APX-hard and repels any FPTAS. As the FPTAS still incurs excessive running time for large-scale cases, we design an efficient dual-subgradient algorithm for solving large-/national- scale instances. It is an iterative algorithm that always converges. We prove that each iteration only incurs polynomial-time complexity, albeit it requires solving an integer linear programming problem optimally. We characterize a condition under which the algorithm generates an optimal solution and derive a posterior performance bound when the condition is not met. Extensive simulations based on real-world traces show that our joint solution of path planning, speed planning, and platooning saves up to $24\%$ fuel as compared to baseline alternatives.

Snapshot compressive imaging (SCI) encodes high-speed scene video into a snapshot measurement and then computationally makes reconstructions, allowing for efficient high-dimensional data acquisition. Numerous algorithms, ranging from regularization-based optimization and deep learning, are being investigated to improve reconstruction quality, but they are still limited by the ill-posed and information-deficient nature of the standard SCI paradigm. To overcome these drawbacks, we propose a new key frames assisted hybrid encoding paradigm for compressive video sensing, termed KH-CVS, that alternatively captures short-exposure key frames without coding and long-exposure encoded compressive frames to jointly reconstruct photorealistic video. With the use of optical flow and spatial warping, a deep convolutional neural network framework is constructed to integrate the benefits of these two types of frames. Extensive experiments on both simulations and real data from the prototype we developed verify the superiority of the proposed method.

The aim of this paper is to study the time stepping scheme for approximately solving the subdiffusion equation with a weakly singular source term. In this case, many popular time stepping schemes, including the correction of high-order BDF methods, may lose their high-order accuracy. To fill in this gap, in this paper, we develop a novel time stepping scheme, where the source term is regularized by using a $k$-fold integral-derivative and the equation is discretized by using a modified BDF2 convolution quadrature. We prove that the proposed time stepping scheme is second-order, even if the source term is nonsmooth in time and incompatible with the initial data. Numerical results are presented to support the theoretical results., Comment: 25pages

The existence of multiple load-solution mappings of non-convex AC-OPF problems poses a fundamental challenge to deep neural network (DNN) schemes. As the training dataset may contain a mixture of data points corresponding to different load-solution mappings, the DNN can fail to learn a legitimate mapping and generate inferior solutions. We propose DeepOPF-AL as an augmented-learning approach to tackle this issue. The idea is to train a DNN to learn a unique mapping from an augmented input, i.e., (load, initial point), to the solution generated by an iterative OPF solver with the load and initial point as intake. We then apply the learned augmented mapping to solve AC-OPF problems much faster than conventional solvers. Simulation results over IEEE test cases show that DeepOPF-AL achieves noticeably better optimality and similar feasibility and speedup performance, as compared to a recent DNN scheme, with the same DNN size yet elevated training complexity., Comment: 3 pages,2 figures

Online decision-making in the presence of uncertain future information is abundant in many problem domains. In the critical problem of energy generation scheduling for microgrids, one needs to decide when to switch energy supply between a cheaper local generator with startup cost and the costlier on-demand external grid, considering intermittent renewable generation and fluctuating demands. Without knowledge of future input, competitive online algorithms are appealing as they provide optimality guarantees against the optimal offline solution. In practice, however, future input, e.g., wind generation, is often predictable within a limited time window, and can be exploited to further improve the competitiveness of online algorithms. In this paper, we exploit the structure of information in the prediction window to design a novel prediction-aware online algorithm for energy generation scheduling in microgrids. Our algorithm achieves the best competitive ratio to date for this important problem, which is at most $3-2/(1+\mathcal{O}(\frac{1}{w})),$ where $w$ is the prediction window size. We also characterize a non-trivial lower bound of the competitive ratio and show that the competitive ratio of our algorithm is only $9\%$ away from the lower bound, when a few hours of prediction is available. Simulation results based on real-world traces corroborate our theoretical analysis and highlight the advantage of our new prediction-aware design., Comment: This paper has been accepted into ACM e-Energy 2022 and will appear in the conference proceedings

Deep learning approaches for the Alternating Current-Optimal Power Flow (AC-OPF) problem are under active research in recent years. A common shortcoming in this area of research is the lack of a dataset that includes both a realistic power network topology and the corresponding realistic loads. To address this issue, we construct an AC-OPF formulation-ready dataset called TAS-97 that contains realistic network information and realistic bus loads from Tasmania's electricity network. We found that the realistic loads in Tasmania are correlated between buses and they show signs of an underlying multivariate normal distribution. Feasibility-optimized end-to-end deep neural network models are trained and tested on the constructed dataset. Trained on samples with bus loads generated from a fitted multivariate normal distribution, our learning-based AC-OPF solver achieves 0.13% cost optimality gap, 99.73% feasibility rate, and 38.62 times of speedup on realistic testing samples when compared to PYPOWER., Comment: 8 pages, 6 figures

Algebraic multigrid (AMG) is one of the most efficient iterative methods for solving large sparse system of equations. However, how to build/check restriction and prolongation operators in practical of AMG methods for nonsymmetric {\em sparse} systems is still an interesting open question [Brezina, Manteuffel, McCormick, Runge, and Sanders, SIAM J. Sci. Comput. (2010); Manteuffel and Southworth, SIAM J. Sci. Comput. (2019)]. This paper deals with the block-structured dense and Toeplitz-like-plus-Cross systems, including {\em nonsymmetric} indefinite, symmetric positive definite (SPD), arising from nonlocal diffusion problem and peridynamic problem. The simple (traditional) restriction operator and prolongation operator are employed in order to handle such block-structured dense and Toeplitz-like-plus-Cross systems, which is convenient and efficient when employing a fast AMG. We focus our efforts on providing the detailed proof of the convergence of the two-grid method for such SPD situations. The numerical experiments are performed in order to verify the convergence with a computational cost of only $\mathcal{O}(N \mbox{log} N)$ arithmetic operations, by using few fast Fourier transforms, where $N$ is the number of the grid points. To the best of our knowledge, this is the first contribution regarding Toeplitz-like-plus-Cross linear systems solved by means of a fast AMG., Comment: 22pages

We study a competitive online optimization problem with multiple inventories. In the problem, an online decision maker seeks to optimize the allocation of multiple capacity-limited inventories over a slotted horizon, while the allocation constraints and revenue function come online at each slot. The problem is challenging as we need to allocate limited inventories under adversarial revenue functions and allocation constraints, while our decisions are coupled among multiple inventories and different slots. We propose a divide-and-conquer approach that allows us to decompose the problem into several single inventory problems and solve it in a two-step manner with almost no optimality loss in terms of competitive ratio (CR). Our approach provides new angles, insights and results to the problem, which differs from the widely-adopted primal-and-dual framework. Specifically, when the gradients of the revenue functions are bounded in a positive range, we show that our approach can achieve a tight CR that is optimal when the number of inventories is small, which is better than all existing ones. For an arbitrary number of inventories, the CR we achieve is within an additive constant of one to a lower bound of the best possible CR among all online algorithms for the problem. We further characterize a general condition for generalizing our approach to different applications. For example, for a generalized one-way trading problem with price elasticity, where no previous results are available, our approach obtains an online algorithm that achieves the optimal CR up to a constant factor.

Data-driven discovery of partial differential equations (PDEs) from observed data in machine learning has been developed by embedding the discovery problem. Recently, the discovery of traditional ODEs dynamics using linear multistep methods in deep learning have been discussed in [Racheal and Du, SIAM J. Numer. Anal. 59 (2021) 429-455; Du et al. arXiv:2103.11488]. We extend this framework to the data-driven discovery of the time-fractional PDEs, which can effectively characterize the ubiquitous power-law phenomena. In this paper, identifying source function of subdiffusion with noisy data using L1 approximation in deep neural network is presented. In particular, two types of networks for improving the generalization of the subdiffusion problem are designed with noisy data. The numerical experiments are given to illustrate the availability using deep learning. To the best of our knowledge, this is the first topic on the discovery of subdiffusion in deep learning with noisy data., Comment: 22 pages, 26 figures

In this work, we analyze the three-step backward differentiation formula (BDF3) method for solving the Allen-Cahn equation on variable grids. For BDF2 method, the discrete orthogonal convolution (DOC) kernels are positive, the stability and convergence analysis are well established in [Liao and Zhang, \newblock Math. Comp., \textbf{90} (2021) 1207--1226; Chen, Yu, and Zhang, \newblock SIAM J. Numer. Anal., Major Revised]. However, the numerical analysis for BDF3 method with variable steps seems to be highly nontrivial, since the DOC kernels are not always positive. By developing a novel spectral norm inequality, the unconditional stability and convergence are rigorously proved under the updated step ratio restriction $r_k:=\tau_k/\tau_{k-1}\leq 1.405$ (compared with $r_k\leq 1.199$ in [Calvo and Grigorieff, \newblock BIT. \textbf{42} (2002) 689--701]) for BDF3 method. Finally, numerical experiments are performed to illustrate the theoretical results. To the best of our knowledge, this is the first theoretical analysis of variable steps BDF3 method for the Allen-Cahn equation.

The subdiffusion equations with a Caputo fractional derivative of order $\alpha \in (0,1)$ arise in a wide variety of practical problems, which is describing the transport processes, in the force-free limit, slower than Brownian diffusion. In this work, we derive the correction schemes of the Lagrange interpolation with degree $k$ ($k\leq 6$) convolution quadrature, called $L_k$ approximation, for the subdiffusion, which are easy to implement on variable grids. The key step of designing correction algorithm is to calculate the explicit form of the coefficients of $L_k$ approximation by the polylogarithm function or Bose-Einstein integral. To construct a $\tau_8$ approximation of Bose-Einstein integral, the desired $(k+1-\alpha)$th-order convergence rate can be proved for the correction $L_k$ scheme with nonsmooth data, which is higher than $k$th-order BDF$k$ method in [Jin, Li, and Zhou, SIAM J. Sci. Comput., 39 (2017), A3129--A3152; Shi and Chen, J. Sci. Comput., (2020) 85:28]. The numerical experiments with spectral method are given to illustrate theoretical results.

Ensuring solution feasibility is a key challenge in developing Deep Neural Network (DNN) schemes for solving constrained optimization problems, due to inherent DNN prediction errors. In this paper, we propose a ``preventive learning'' framework to guarantee DNN solution feasibility for problems with convex constraints and general objective functions without post-processing, upon satisfying a mild condition on constraint calibration. Without loss of generality, we focus on problems with only inequality constraints. We systematically calibrate inequality constraints used in DNN training, thereby anticipating prediction errors and ensuring the resulting solutions remain feasible. We characterize the calibration magnitudes and the DNN size sufficient for ensuring universal feasibility. We propose a new Adversarial-Sample Aware training algorithm to improve DNN's optimality performance without sacrificing feasibility guarantee. Overall, the framework provides two DNNs. The first one from characterizing the sufficient DNN size can guarantee universal feasibility while the other from the proposed training algorithm further improves optimality and maintains DNN's universal feasibility simultaneously. We apply the framework to develop DeepOPF+ for solving essential DC optimal power flow problems in grid operation. Simulation results over IEEE test cases show that it outperforms existing strong DNN baselines in ensuring 100% feasibility and attaining consistent optimality loss ($<$0.19%) and speedup (up to $\times$228) in both light-load and heavy-load regimes, as compared to a state-of-the-art solver. We also apply our framework to a non-convex problem and show its performance advantage over existing schemes., Comment: 62pages, 10 figures. This work is accepted in The Eleventh International Conference on Learning Representations (ICLR2023) as Oral - top 25% accepted

In this paper, a novel principle-driven fiber transmission model based on physical induced neural network (PINN) is proposed. Unlike data-driven models which regard fiber transmission problem as data regression tasks, this model views it as an equation solving problem. Instead of adopting input signals and output signals which are calculated by SSFM algorithm in advance before training, this principle-driven PINN based fiber model adopts frames of time and distance as its inputs and the corresponding real and imaginary parts of NLSE solutions as its outputs. By taking into account of pulses and signals before transmission as initial conditions and fiber physical principles as NLSE in the design of loss functions, this model will progressively learn the transmission rules. Therefore, it can be effectively trained without the data labels, referred as the pre-calculated signals after transmission in data-driven models. Due to this advantage, SSFM algorithm is no longer needed before the training of principle-driven fiber model which can save considerable time consumption. Through numerical demonstration, the results show that this principle-driven PINN based fiber model can handle the prediction tasks of pulse evolution, signal transmission and fiber birefringence for different transmission parameters of fiber telecommunications.

Variable steps implicit-explicit multistep methods for PDEs have been presented in [17], where the zero-stability is studied for ODEs; however, the stability analysis still remains an open question for PDEs. Based on the idea of linear multistep methods, we present a simple weighted and shifted BDF2 methods with variable steps for the parabolic problems, which serve as a bridge between BDF2 and Crank-Nicolson scheme. The contributions of this paper are as follows: we first prove that the optimal adjacent time-step ratios for the weighted and shifted BDF2, which greatly improve the maximum time-step ratios for BDF2 in [11,15]. Moreover, the unconditional stability and optimal convergence are rigorous proved, which make up for the vacancy of the theory for PDEs in [17]. Finally, numerical experiments are given to illustrate theoretical results., Comment: 19 pages, 6 figures

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., Comment: 12 pages, 6 figures

Recently, the error analysis of BDF$k$ $(1\leqslant k\leqslant5)$ SAV (scalar auxiliary variable) schemes are given in \cite{Huangg:20} for the classical Allen-Cahn equation. However, it remains unavailable for BDF$6$ SAV schemes. In this paper, we construct and analyze BDF$6$ SAV schemes for the time-fractional dissipative systems. We carry out a rigorous error analysis for the time-fractional Allen-Cahn equation, which also fills up a gap for the classical case. Finally, numerical experiment is shown to illustrate the effectiveness of the presented methods. As far as we know, this is the first SAV schemes for the time-fractional dissipative systems., Comment: 17 pages

A low noise linearly frequency modulated continuous wave laser source with a wide frequency bandwidth is demonstrated. By two-dimensional thermal tuning, the laser source shows 42 GHz continuous frequency tuning with 49.86 Hz intrinsic linewidth under static operation. For dynamical FMCW, the laser source has 10.25 GHz frequency bandwidth at 100 Hz chirped frequency and 5.56 GHz at 1 kHz chirped frequency. With pre-distortion linearization, it can distinguish 3 m length difference at 45 km distance in the fibre length measured experiment, which demonstrate a potential for application in ultra-long fibre sensing and FMCW LiDAR.

AC optimal power flow (AC-OPF) problems need to be solved more frequently in the future to maintain stable and economic power system operation. To tackle this challenge, a deep neural network-based voltage-constrained approach (DeepOPF-V) is proposed to solve AC-OPF problems with high computational efficiency. Its unique design predicts voltages of all buses and then uses them to reconstruct the remaining variables without solving non-linear AC power flow equations. A fast post-processing process is developed to enforce the box constraints. The effectiveness of DeepOPF-V is validated by simulations on IEEE 118/300-bus systems and a 2000-bus test system. Compared with existing studies, DeepOPF-V achieves decent computation speedup up to four orders of magnitude and comparable performance in optimality gap and preserving the feasibility of the solution., Comment: 4 pages, 1 figure

The significant presence of demand charges in electric bills motivates large-load customers to utilize energy storage to reduce the peak procurement from the grid. We herein study the problem of energy storage allocation for peak minimization, under the online setting where irrevocable decisions are sequentially made without knowing future demands. The problem is uniquely challenging due to (i) the coupling of online decisions across time imposed by the inventory constraints and (ii) the noncumulative nature of the peak procurement. We apply the CR-Pursuit framework and address the challenges unique to our minimization problem to design an online algorithm achieving the optimal competitive ratio (CR) among all online algorithms. We show that the optimal CR can be computed in polynomial time by solving a linear number of linear-fractional problems. More importantly, we generalize our approach to develop an \emph{anytime-optimal} online algorithm that achieves the best possible CR at any epoch, given the inputs and online decisions so far. The algorithm retains the optimal worst-case performance and attains adaptive average-case performance. Trace-driven simulations show that our algorithm can decrease the peak demand by an extra 19% compared to baseline alternatives under typical settings.