A Simple yet Highly Accurate Prediction-Correction Algorithm for Time-Varying Optimization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916678794739712 |
|---|---|
| author | Kamijima, Tomoya Marumo, Naoki Takeda, Akiko |
| author_facet | Kamijima, Tomoya Marumo, Naoki Takeda, Akiko |
| contents | This paper proposes a simple yet highly accurate prediction-correction algorithm, SHARP, for unconstrained time-varying optimization problems. Its prediction is based on an extrapolation derived from the Lagrange interpolation of past solutions. Since this extrapolation can be computed without Hessian matrices or even gradients, the computational cost is low. To ensure the stability of the prediction, the algorithm includes an acceptance condition that rejects the prediction when the update is excessively large. The proposed method achieves a tracking error of $O(h^{p})$, where $h$ is the sampling period, assuming that the $p$th derivative of the target trajectory is bounded and the convergence of the correction step is locally linear. We also prove that the method can track a trajectory of stationary points even if the objective function is non-convex. Numerical experiments demonstrate the high accuracy of the proposed algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_05798 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Simple yet Highly Accurate Prediction-Correction Algorithm for Time-Varying Optimization Kamijima, Tomoya Marumo, Naoki Takeda, Akiko Optimization and Control This paper proposes a simple yet highly accurate prediction-correction algorithm, SHARP, for unconstrained time-varying optimization problems. Its prediction is based on an extrapolation derived from the Lagrange interpolation of past solutions. Since this extrapolation can be computed without Hessian matrices or even gradients, the computational cost is low. To ensure the stability of the prediction, the algorithm includes an acceptance condition that rejects the prediction when the update is excessively large. The proposed method achieves a tracking error of $O(h^{p})$, where $h$ is the sampling period, assuming that the $p$th derivative of the target trajectory is bounded and the convergence of the correction step is locally linear. We also prove that the method can track a trajectory of stationary points even if the objective function is non-convex. Numerical experiments demonstrate the high accuracy of the proposed algorithm. |
| title | A Simple yet Highly Accurate Prediction-Correction Algorithm for Time-Varying Optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2504.05798 |