Minibatch Random Reshuffling for Smooth Convex Optimization: Batch-Size Dependence, Finite-Population Variance, and Quadratic Growth

Random Reshuffling (RR) is the default data-ordering strategy in practice, and it is almost always run with minibatches. The recent theory of Liu shows that single-sample RR dominates SGD in smooth convex optimization for every stepsize below \(2/\hat{L}\), but the role of the batch size has not been worked out. In this note we study … Read more

Frank–Wolfe Theorems for Mixed Integer Quadratic Optimization

The Frank–Wolfe theorem states that a quadratic function bounded from below on a polyhedron attains its infimum. We study when this remains true in the presence of integer variables, for sets defined by quadratic inequalities. Our main result is a complete classification for sets defined by convex quadratic inequalities with rational coefficients and a rational … Read more

A robust BFGS algorithm for unconstrained nonlinear optimization problems

The traditional BFGS algorithm has been proved very efficient. It is convergent for convex non linear optimization problems. However, for non-convex nonlinear optimization problems, it is known that the BFGS algorithm may not be convergent. This paper proposes a robust BFGS algorithm in the sense that the algorithm superlinearly converges to a local minimum under … Read more

A Retrospective-Approximation Interior-Point Method

An algorithm is proposed, analyzed, and tested for solving nonlinearly constrained continuous optimization problem instances wherein the objective function is defined by an expectation over a random variable argument and the constraints include inequalities (and perhaps equalities) involving functions that may be nonconvex. The algorithm combines a retrospective-approximation strategy for handling the objective and an … Read more

Tightening bilinear relaxations using geometric rotation

A classical approach for handling non-convex optimization problems involving bilinear terms is to approximate the bilinear expressions using McCormick relaxations. Such relaxations are central to global optimization methods, with the spatial branch-and-bound (sBB) algorithm being one of the most widely used approaches. In the spatial branching step, the algorithm partitions the feasible region using axis-aligned … Read more

Aries: A Three-Segment Path for Solving Trust-Region Subproblems

Trust-region methods are fundamental to nonlinear optimization, but solving the trust-region subproblem exactly can be computationally expensive.  This paper proposes Aries, a three-segment path  approximation that extends the classical dogleg path while retaining comparable per-iteration work.  We state the assumptions under which the usual trust-region sufficient-decrease argument applies and  describe an adaptive rule for selecting … Read more

Quasinormality in nonlinear second-order cone programming

We introduce quasinormality and pseudonormality for nonlinear second-order cone programming by exploiting the spectral geometry of the Lorentz cone. The proposed quasinormality distinguishes interior and boundary multipliers and, in the latter case, relates constraint violation to the corresponding spectral direction. It recovers classical quasinormality when all cone blocks are one-dimensional and is strictly weaker than … Read more

Normalized-step stochastic SQP methods for nonconvex constrained optimization under heavy-tailed noise

In this paper, we study nonconvex constrained optimization with expectation equality constraints and non-negative bounds under heavy-tailed noise. The objective gradients, constraint values, and constraint Jacobian are accessed through stochastic oracles whose errors have bounded $p$th central moments for some $p\in(1,2)$. These conditions allow infinite-variance errors for the three types of stochastic oracles, rendering traditional … Read more

On the BFGS Method for Unconstrained Optimization

Quasi-Newton methods form the basis of many effective methods for unconstrained and constrained optimization. As the iterations proceed, a quasi-Newton method incorporates new curvature information by performing a low-rank update to a matrix that serves as an approximation to a Hessian matrix of second derivatives. In the years following the publication of the Davidon-Fletcher-Powell (DFP) … Read more

A Stochastic Proximal-Gradient Method for Regularized Generally Constrained Continuous Optimization

A stochastic proximal-gradient method is proposed and analyzed for solving regularized optimization problems subject to nonlinear equality constraints and nonnegativity bounds. The objective function’s values and gradients are available only through inexact stochastic oracles. The method decomposes each trial step into one component that reduces linearized infeasibility and a second component that seeks optimality while … Read more