Nonlinear Optimization

A Self-Correcting Variable-Metric Algorithm Framework for Nonsmooth Optimization

  • Frank E. Curtis
  • Daniel P. Robinson
  • Baoyu Zhou
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    An algorithm framework is proposed for minimizing nonsmooth functions. The framework is variable-metric in that, in each iteration, a step is computed using a symmetric positive definite matrix whose value is updated as in a quasi-Newton scheme. However, unlike previously proposed variable-metric algorithms for minimizing nonsmooth functions, the framework exploits self-correcting properties made possible through … Read more

    Using Neural Networks to Detect Line Outages from PMU Data

  • Stephen Wright
  • Ching-pei Lee
    • Categories Applications - Science and Engineering, Nonlinear Optimization Tags , , ,

    We propose an approach based on neural networks and the AC power flow equations to identify single- and double- line outages in a power grid using the information from phasor measurement unit sensors (PMUs). Rather than inferring the outage from the sensor data by inverting the physical model, our approach uses the AC model to … Read more

    Numerically tractable optimistic bilevel problems

  • Lorenzo Lampariello
  • Simone Sagratella
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Game Theory Tags , ,

    We consider fully convex lower level standard optimistic bilevel problems. We show that this class of mathematical programs is sufficiently broad to encompass significant real-world applications. We establish that the critical points of a relaxation of the original problem correspond to the equilibria of a suitably defined generalized Nash equilibrium problem. The latter game is … Read more

    Derivative-Free Robust Optimization by Outer Approximations

  • Matt Menickelly
  • Stefan M. Wild
    • Categories Nonsmooth Optimization, Robust Optimization, Unconstrained Optimization Tags , , ,

    We develop an algorithm for minimax problems that arise in robust optimization in the absence of objective function derivatives. The algorithm utilizes an extension of methods for inexact outer approximation in sampling a potentially infinite-cardinality uncertainty set. Clarke stationarity of the algorithm output is established alongside desirable features of the model-based trust-region subproblems encountered. We … Read more

    Underestimate Sequences via Quadratic Averaging

  • Naga Venkata Chaitanya Gudapati
  • Rachael Tappenden
  • Majid Jahani
  • Chenxin Ma
  • Martin Takac
    • Categories Nonlinear Optimization, Unconstrained Optimization

    In this work we introduce the concept of an Underestimate Sequence (UES), which is a natural extension of Nesterov’s estimate sequence. Our definition of a UES utilizes three sequences, one of which is a lower bound (or under-estimator) of the objective function. The question of how to construct an appropriate sequence of lower bounds is … Read more

    From Estimation to Optimization via Shrinkage

  • Gérard Cornuéjols
  • Danial Davarnia
    • Categories Quadratic Programming, Statistics, Stochastic Programming Tags , , , ,

    We study a class of quadratic stochastic programs where the distribution of random variables has unknown parameters. A traditional approach is to estimate the parameters using a maximum likelihood estimator (MLE) and to use this as input in the optimization problem. For the unconstrained case, we show that an estimator that “shrinks” the MLE towards … Read more

    A Dense initialization for limited-memory quasi-Newton methods

  • Johannes Brust
  • Oleg Burdakov
  • Jennifer B. Erway
  • Roummel F. Marcia
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

    We consider a family of dense initializations for limited-memory quasi-Newton methods. The proposed initialization exploits an eigendecomposition-based separation of the full space into two complementary subspaces, assigning a different initialization parameter to each subspace. This family of dense initializations is proposed in the context of a limited-memory Broyden- Fletcher-Goldfarb-Shanno (L-BFGS) trust-region method that makes use … Read more

    Primal-Dual Optimization Algorithms over Riemannian Manifolds: an Iteration Complexity Analysis

  • Shiqian Ma
  • Junyu Zhang
  • Shuzhong Zhang
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    In this paper we study nonconvex and nonsmooth multi-block optimization over Riemannian manifolds with coupled linear constraints. Such optimization problems naturally arise from machine learning, statistical learning, compressive sensing, image processing, and tensor PCA, among others. We develop an ADMM-like primal-dual approach based on decoupled solvable subroutines such as linearized proximal mappings. First, we introduce … Read more

    Globally Solving the Trust Region Subproblem Using Simple First-Order Methods

  • Amir Beck
  • Yakov Vaisbourd
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    We consider the trust region subproblem which is given by a minimization of a quadratic, not necessarily convex, function over the Euclidean ball. Based on the well-known second-order necessary and sufficient optimality conditions for this problem, we present two sufficient optimality conditions defined solely in terms of the primal variables. Each of these conditions corresponds … Read more

    Manifold Sampling for Optimization of Nonconvex Functions that are Piecewise Linear Compositions of Smooth Components

  • Kamil Khan
  • Jeffrey Larson
  • Stefan M. Wild
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags , ,

    We develop a manifold sampling algorithm for the minimization of a nonsmooth composite function $f \defined \psi + h \circ F$ when $\psi$ is smooth with known derivatives, $h$ is a known, nonsmooth, piecewise linear function, and $F$ is smooth but expensive to evaluate. The trust-region algorithm classifies points in the domain of $h$ as … Read more