New Methods for Parametric Optimization via Differential Equations

arXiv2306.08812MaRDI QIDQ6440352FDOQ6440352

Authors: Heyuan Liu, Paul Grigas 

Publication date: 14 June 2023

Abstract: We develop and analyze several different second-order algorithms for computing a near-optimal solution path of a convex parametric optimization problem with smooth Hessian. Our algorithms are inspired by a differential equation perspective on the parametric solution path and do not rely on the specific structure of the objective function. We present computational guarantees that bound the oracle complexity to achieve a near-optimal solution path under different sets of smoothness assumptions. Under the assumptions, the results are an improvement over the best-known results of the grid search methods. We also develop second-order conjugate gradient variants that avoid exact computations of Hessians and solving of linear equations. We present computational results that demonstrate the effectiveness of our methods over grid search methods on both real and synthetic datasets. On large-scale problems, we demonstrate significant speedups of the second-order conjugate variants as compared to the standard versions of our methods.

This page was built for publication: New Methods for Parametric Optimization via Differential Equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6440352)