Unconstrained Optimization

Nonconvex stochastic zeroth-order optimization with decision-dependent distributions: from momentum tracking to coupled sampling

Categories Nonlinear Optimization, Stochastic Programming, Unconstrained Optimization

In this paper, we study nonconvex stochastic optimization with {decision-dependent distributions}, where the decision variable influences the underlying sampling distribution and only stochastic function-value feedback is available. We address two challenges {induced by decision-dependent distributions}: transport error in momentum-based gradient tracking and variance inflation in zeroth-order estimation. We first develop a Polyak-momentum zeroth-order method that … Read more

Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp

Categories Convex Optimization, Unconstrained Optimization

We revisit the Sinkhorn-Knopp (SK) algorithm for the matrix scaling problem. Despite extensive literature on the global convergence of SK and its variants, its local linear convergence behavior remains less understood. We address this gap by providing the first nonasymptotic local analysis of SK that matches the rate obtained from existing asymptotic Jacobian-based arguments. We … Read more

A Minimal-Gradient Subspace Method for Unconstrained Optimization

Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

We propose a minimal-gradient subspace method for unconstrained optimization. For strictly convex quadratics, conjugate gradient can be interpreted as exact minimization over a two-dimensional affine subspace. We use the same reduced subspace in the nonlinear case, but compute a trial step by minimizing a local model of the next gradient norm. For SPD quadratics, every … Read more

A Momentum Trust-Region Algorithm for Unconstrained Optimization

Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

We introduce a Momentum Trust-Region Algorithm for unconstrained optimization that incorporates Nesterov-type acceleration into the classical trust-region framework. The method builds trust-region models around a momentum-shifted point and uses an Armijo-type backtracking procedure to safeguard progress along the resulting displacement. This design preserves the robustness of trust-region methods while exploiting momentum to improve practical efficiency. … Read more

A Quantum Optimization Framework for Data-Assimilation-Augmented Parameter Estimation

Categories Combinatorial Optimization, Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

Parameter estimation is a fundamental challenge in the calibration of ordinary differential equation (ODE) models, where repeated numerical integration can lead to high computational cost. In this work, we investigate whether quantum algorithms can be leveraged to assist parameter estimation in nonlinear dynamical systems. We develop a hybrid classical–quantum framework that reformulates a data-assimilation-augmented parameter … Read more

bAdag: an adaptive block coordinate gradient method for smooth nonconvex functions

Categories Data Science Algorithms, Unconstrained Optimization Tags , , ,

A new Block Coordinate Gradient (BCG) method, dubbed bAdag, for smooth, nonconvex minimization problem is proposed; it falls in the class of Objective Function Free Optimization (OFFO) methods, and it is based on the AdaGrad algorithm. At each iteration, our method computes an adaptive step size based on the cumulative sum of block gradients, instead … Read more

Quadratic Quasi-Newton Optimization – An Interpolated Hybrid Method

Categories Nonlinear Optimization, Unconstrained Optimization Tags ,

We present the Quadratic-Quasi-Newton (QQN) algorithm, a novel optimization method that combines gradient descent and quasi-Newton directions through quadratic interpolation. QQN constructs a parametric path d(t) = t(1 − t)(−∇f) + t 2 d L-BFGS and performs univariate optimization along this path, creating an adaptive interpolation that requires no additional hyperparameters beyond those of its … Read more

Stochastic convergence of parallel asynchronous adaptive first-order methods

Categories Data Science Algorithms, Stochastic Programming, Unconstrained Optimization Tags , , , , ,

A new class of asynchronous adaptive first-order optimization methods is introduced, comprising asynchronous variants of several popular algorithms. Versions of these methods using momentum and/or inexact normalization are also considered. The convergence of methods in the class on non-convex functions is analyzed in a fully stochastic setting, and is shown to be (up to logarithmic … Read more

Stochastic Three Points Method with an Inexact Oracle and Its Application to Steady-State Optimization

Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

We consider unconstrained derivative-free optimization problems in which only inexact function evaluations are available. Specifically, we study the setting where the oracle returns function values with partially controllable inexactness, with the error bounded linearly by a user-specified accuracy parameter, but with an unknown proportionality constant. This framework captures optimization problems arising from approximate simulations or … Read more

A unified framework for inexact adaptive stepsizes in the gradient methods, the conjugate gradient methods and the quasi-Newton methods for strictly convex quadratic optimization

Categories Convex Optimization, Quadratic Programming, Unconstrained Optimization Tags , , , ,

The inexact adaptive stepsizes for the conjugate gradient method and  the quasi-Newton method are very rare. The exact stepsizes in the gradient method, the conjugate gradient method and the  quasi-Newton method for strictly convex quadratic optimization have a unified framework, while the unified framework for inexact adaptive stepsizes  in the gradient method, the conjugate gradient … Read more