Unconstrained Optimization

Shape-Changing Trust-Region Methods Using Multipoint Symmetric Secant Matrices

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

    In this work, we consider methods for large-scale and nonconvex unconstrained optimization. We propose a new trust-region method whose subproblem is defined using a so-called “shape-changing” norm together with densely-initialized multipoint symmetric secant (MSS) matrices to approximate the Hessian. Shape-changing norms and dense initializations have been successfully used in the context of traditional quasi Newton … Read more

    Convergence to a second-order critical point of composite nonsmooth problems by a trust region method

  • Hiroshi Yamashita
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags , , , ,

    An algorithm for finding a first-order and second-order critical point of composite nonsmooth problems is proposed in this paper. For smooth problems, algorithms for searching such a point usually utilize the so called negative-curvature directions. In this paper, the method recently proposed for nonlinear semidefinite problems by the current author is extended for solving general … Read more

    Metrizing Fairness

  • Yves Rychener
  • Bahar Tașkesen
  • Daniel Kuhn
    • Categories Statistics, Stochastic Programming, Unconstrained Optimization Tags , , , , ,

    We study supervised learning problems for predicting properties of individuals who belong to one of two demographic groups, and we seek predictors that are fair according to statistical parity. This means that the distributions of the predictions within the two groups should be close with respect to the Kolmogorov distance, and fairness is achieved by … Read more

    A Constraint Dissolving Approach for Nonsmooth Optimization over the Stiefel Manifold

  • Xiaoyin Hu
  • Nachuan Xiao
  • Xin Liu
  • Kim-Chuan Toh
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

    This paper focus on the minimization of a possibly nonsmooth objective function over the Stiefel manifold. The existing approaches either lack efficiency or can only tackle prox-friendly objective functions. We propose a constraint dissolving function named NCDF and show that it has the same first-order stationary points and local minimizers as the original problem in … Read more

    First- and Second-Order High Probability Complexity Bounds for Trust-Region Methods with Noisy Oracles

  • Liyuan Cao
  • Albert S. Berahas
  • Katya Scheinberg
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    In this paper, we present convergence guarantees for a modified trust-region method designed for minimizing objective functions whose value is computed with noise and for which gradient and Hessian estimates are inexact and possibly random. In order to account for the noise, the method utilizes a relaxed step acceptance criterion and a cautious trust-region radius … Read more

    Worst-Case Complexity of TRACE with Inexact Subproblem Solutions for Nonconvex Smooth Optimization

  • Frank E. Curtis
  • Qi Wang
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

    An algorithm for solving nonconvex smooth optimization problems is proposed, analyzed, and tested. The algorithm is an extension of the Trust Region Algorithm with Contractions and Expansions (TRACE) [Math. Prog. 162(1):132, 2017]. In particular, the extension allows the algorithm to use inexact solutions of the arising subproblems, which is an important feature for solving large-scale … Read more

    Direct search based on probabilistic descent in reduced spaces

  • Lindon Roberts
  • Clément W. Royer
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    Derivative-free algorithms seek the minimum value of a given objective function without using any derivative information. The performance of these methods often worsen as the dimension increases, a phenomenon predicted by their worst-case complexity guarantees. Nevertheless, recent algorithmic proposals have shown that incorporating randomization into otherwise deterministic frameworks could alleviate this effect for direct-search methods. … Read more

    Randomized Policy Optimization for Optimal Stopping

  • Xinyi Guan
  • Velibor Mišić
    • Categories Dynamic Programming, Finance and Economics, Unconstrained Optimization Tags , , , ,

    Optimal stopping is the problem of determining when to stop a stochastic system in order to maximize reward, which is of practical importance in domains such as finance, operations management and healthcare. Existing methods for high-dimensional optimal stopping that are popular in practice produce deterministic linear policies — policies that deterministically stop based on the … Read more

    Constraint Dissolving Approaches for Riemannian Optimization

  • Nachuan Xiao
  • Xin Liu
  • Kim-Chuan Toh
    • Categories Constrained Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    In this paper, we propose a class of constraint dissolving approaches for optimization problems over closed Riemannian manifolds. In these proposed approaches, solving a Riemannian optimization problem is transferred into the unconstrained minimization of a constraint dissolving function named CDF. Different from existing exact penalty functions, the exact gradient and Hessian of CDF are easy … Read more

    Convergence properties of an Objective-Function-Free Optimization regularization algorithm, including an $\mathcal{O}(\epsilon^{-3/2})$ complexity bound

  • Serge Gratton
  • Sadok Jerad
  • Philippe L. Toint
    • Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , , ,

    An adaptive regularization algorithm for unconstrained nonconvex optimization is presented in which the objective function is never evaluated, but only derivatives are used. This algorithm belongs to the class of adaptive regularization methods, for which optimal worst-case complexity results are known for the standard framework where the objective function is evaluated. It is shown in … Read more