This paper studies online optimization under inventory (budget) constraints.
While online optimization is a well-studied topic, versions with inventory
constraints have proven difficult. We consider a formulation of
inventory-constrained optimization that is a generalization of the classic
one-way trading problem and has a wide range of applications. We present a new
algorithmic framework, \textsf{CR-Pursuit}, and prove that it achieves the
minimal competitive ratio among all deterministic algorithms (up to a
problem-dependent constant factor) for inventory-constrained online
optimization. Our algorithm and its analysis not only simplify and unify the
state-of-the-art results for the standard one-way trading problem, but they
also establish novel bounds for generalizations including concave revenue
functions. For example, for one-way trading with price elasticity, the
\textsf{CR-Pursuit} algorithm achieves a competitive ratio that is within a
small additive constant (i.e., 1/3) to the lower bound of $\ln \theta+1$, where
$\theta$ is the ratio between the maximum and minimum base prices.

该研究提出了一种新的算法框架 CR-Pursuit，用于解决在线优化中的库存约束问题，并证明了在确定性算法中其取得最小的竞争比率。