提出一种每步仅需O(n)计算量的时变凸优化算法，显著降低计算开销。
Time-Varying Convex Optimization with $O(n)$ Computational Complexity
- 仅使用一阶导数，避免求海森逆矩阵，大幅降低计算复杂度。
- 相比原有O(n³)算法，新方法实现O(n)每步计算，适用于大规模问题。
- 可推广至非凸场景，适合实时控制等需要快速响应的系统应用。
本文研究无约束时变凸优化问题，即目标函数随时间变化。我们深入分析该问题，指出在每个时间步冻结代价函数并有限步逼近最小值并非最优跟踪策略。为此，我们提出一类新算法，通过考虑代价函数的时间变化特性，旨在减小对时变最小值的跟踪误差。核心贡献在于：所提算法仅需代价函数关于决策变量的一阶导数，相较于现有需计算代价函数海森逆矩阵的方法，将每步计算复杂度从 $O(n^3)$ 降至 $O(n)$，其中 $n$ 为决策变量维度。该设计不仅极大降低了计算成本，还使算法可应用于非凸优化问题。我们称其为 $O(n)$-算法。这些算法针对不同时间信息可用性场景进行设计，并通过多个实例验证，包括将模型预测控制问题建模为具有流式时变代价的凸优化问题求解。
原文摘要 · Abstract (English)
In this article, we consider the problem of unconstrained time-varying convex optimization, where the cost function changes with time. We provide an in-depth technical analysis of the problem and argue why freezing the cost at each time step and taking finite steps toward the minimizer is not the best tracking solution for this problem. We propose a set of algorithms that by taking into account the temporal variation of the cost aim to reduce the tracking error of the time-varying minimizer of the problem. The main contribution of our work is that our proposed algorithms only require the first-order derivatives of the cost function with respect to the decision variable. This approach significantly reduces computational cost compared to the existing algorithms, which use the inverse of the Hessian of the cost. Specifically, the proposed algorithms reduce the computational cost from $O(n^3)$ to $O(n)$ per timestep, where $n$ is the size of the decision variable. Avoiding the inverse of the Hessian also makes our algorithms applicable to non-convex optimization problems. We refer to these algorithms as $O(n)$-algorithms. These $O(n)$-algorithms are designed to solve the problem for different scenarios based on the available temporal information about the cost. We illustrate our results through various examples, including the solution of a model predictive control problem framed as a convex optimization problem with a streaming time-varying cost function.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。