Daniel P. Robinson – Page 3 – Optimization Online

An Inexact Regularized Newton Framework with a Worst-Case Iteration Complexity of $\mathcal{O}(\epsilon^{-3/2})$ for Nonconvex Optimization

Published: 2017/09/27, Updated: 2018/03/14

An algorithm for solving smooth nonconvex optimization problems is proposed that, in the worst-case, takes $\mathcal{O}(\epsilon^{-3/2})$ iterations to drive the norm of the gradient of the objective function below a prescribed positive real number $\epsilon$ and can take $\mathcal{O}(\epsilon^{-3})$ iterations to drive the leftmost eigenvalue of the Hessian of the objective above $-\epsilon$. The proposed … Read more

Exploiting Negative Curvature in Deterministic and Stochastic Optimization

Published: 2017/02/28, Updated: 2019/08/26

Stochastic Programming, Unconstrained Optimization deep neural networks, negative curvature, stochastic optimization, unconstrained optimization

This paper addresses the question of whether it can be beneficial for an optimization algorithm to follow directions of negative curvature. Although some prior work has established convergence results for algorithms that integrate both descent and negative curvature directions, there has not yet been numerical evidence showing that such methods offer significant performance improvements. In … Read more

Complexity Analysis of a Trust Funnel Algorithm for Equality Constrained Optimization

Published: 2017/01/02, Updated: 2019/08/26

Constrained Nonlinear Optimization, Nonlinear Optimization equality constrained optimization, nonconvex optimization, nonlinear optimization, trust funnel methods, worst-case iteration-complexity

A method is proposed for solving equality constrained nonlinear optimization problems involving twice continuously differentiable functions. The method employs a trust funnel approach consisting of two phases: a first phase to locate an $\epsilon$-feasible point and a second phase to seek optimality while maintaining at least $\epsilon$-feasibility. A two-phase approach of this kind based on … Read more

A Reduced-Space Algorithm for Minimizing $\ell_1hBcRegularized Convex Functions

Published: 2016/02/19, Updated: 2019/08/26

Convex Optimization active-set methods, convex optimization, model prediction, nonlinear optimization, reduced-space methods, sparse optimization, subspace minimization

We present a new method for minimizing the sum of a differentiable convex function and an $\ell_1$-norm regularizer. The main features of the new method include: $(i)$ an evolving set of indices corresponding to variables that are predicted to be nonzero at a solution (i.e., the support); $(ii)$ a reduced-space subproblem defined in terms of … Read more

A Dual Gradient-Projection Method for Large-Scale Strictly Convex Quadratic Problems

Published: 2016/02/19

Quadratic Programming convex quadratic minimization, gradient projection, sparse computation

The details of a solver for minimizing a strictly convex quadratic objective function subject to general linear constraints is presented. The method uses a gradient projection algorithm enhanced with subspace acceleration to solve the bound-constrained dual optimization problem. Such gradient projection methods are well-known, but are typically employed to solve the primal problem when only … Read more

A Flexible ADMM Algorithm for Big Data Applications

Published: 2015/03/23

Convex Optimization

We present a flexible Alternating Direction Method of Multipliers (F-ADMM) algorithm for solving optimization problems involving a strongly convex objective function that is separable into $n \geq 2$ blocks, subject to (non-separable) linear equality constraints. The F-ADMM algorithm uses a \emph{Gauss-Seidel} scheme to update blocks of variables, and a regularization term is added to each … Read more

A Filter SQP Method: Local Convergence and Numerical Results

Published: 2014/12/19

Constrained Nonlinear Optimization filter, large-scale optimization, nonlinear programming, restoration phase, sequential quadratic programming

The work by Gould, Loh, and Robinson [“A filter method with unified step computation for nonlinear optimization”, SIAM J. Optim., 24 (2014), pp. 175–209] established global convergence of a new filter line search method for finding local first-order solutions to nonlinear and nonconvex constrained optimization problems. A key contribution of that work was that the … Read more

A Trust Region Algorithm with a Worst-Case Iteration Complexity of ${\cal O}(\epsilon^{-3/2})$ for Nonconvex Optimization

Published: 2014/10/21, Updated: 2019/08/26

Nonlinear Optimization, Unconstrained Optimization global convergence, local convergence, nonconvex optimization, nonlinear optimization, trust-region methods, unconstrained optimization, worst-case evaluation complexity, worst-case iteration-complexity

We propose a trust region algorithm for solving nonconvex smooth optimization problems. For any $\bar\epsilon \in (0,\infty)$, the algorithm requires at most $\mathcal{O}(\epsilon^{-3/2})$ iterations, function evaluations, and derivative evaluations to drive the norm of the gradient of the objective function below any $\epsilon \in (0,\bar\epsilon]$. This improves upon the $\mathcal{O}(\epsilon^{-2})$ bound known to hold for … Read more

Adaptive Augmented Lagrangian Methods: Algorithms and Practical Numerical Experience

Published: 2014/08/19, Updated: 2017/01/02

Constrained Nonlinear Optimization, Nonlinear Optimization augmented lagrangian method, large-scale optimization, matrix-free methods, nonconvex optimization, nonlinear optimization, steering methods

In this paper, we consider augmented Lagrangian (AL) algorithms for solving large-scale nonlinear optimization problems that execute adaptive strategies for updating the penalty parameter. Our work is motivated by the recently proposed adaptive AL trust region method by Curtis et al. [An adaptive augmented Lagrangian method for large-scale constrained optimization, Math. Program. 152 (2015), pp.201–245.]. … Read more

A Globally Convergent Stabilized SQP Method: Superlinear Convergence

Published: 2014/07/01, Updated: 2014/07/08

Constrained Nonlinear Optimization augmented lagrangian method, nonlinear constraints, nonlinear programming, primal-dual algorithms, regularized methods, sequential quadratic programming, stabilized sqp

Regularized and stabilized sequential quadratic programming (SQP) methods are two classes of methods designed to resolve the numerical and theoretical difficulties associated with ill-posed or degenerate nonlinear optimization problems. Recently, a regularized SQP method has been proposed that allows convergence to points satisfying certain second-order KKT conditions (SIAM J. Optim., 23(4):1983–2010, 2013). The method is … Read more