Nonlinear Optimization

Two efficient gradient methods with approximately optimal stepsizes based on regularization models for unconstrained optimization

  • Zexian Liu
  • Wangli Chu
  • Hongwei Liu
    • Categories Unconstrained Optimization Tags , , , ,

    It is widely accepted that the stepsize is of great significance to gradient method. Two efficient gradient methods with approximately optimal stepsizes mainly based on regularization models are proposed for unconstrained optimization. More exactly, if the objective function is not close to a quadratic function on the line segment between the current and latest iterates, … Read more

    Stable Recovery of Sparse Signals With Non-convex Weighted $r$-Norm Minus $1$-Norm

  • Jianwen Huang
  • Feng Zhang
  • Xinling Liu
  • Jianjun Wang
    • Categories Constrained Nonlinear Optimization, Data-Mining, Nonsmooth Optimization Tags , , ,

    Given the measurement matrix $A$ and the observation signal $y$, the central purpose of compressed sensing is to find the most sparse solution of the underdetermined linear system $y=Ax+z$, where $x$ is the $s$-sparse signal to be recovered and $z$ is the noise vector. Zhou and Yu \cite{Zhou and Yu 2019} recently proposed a novel … Read more

    A barrier Lagrangian dual method for multi-stage stochastic convex semidefinite optimization

  • Baha Alzalg
  • Asma Gafour
    • Categories Nonlinear Optimization, Semi-definite Programming, Stochastic Programming Tags , , , ,

    In this paper, we present a polynomial-time barrier algorithm for solving multi-stage stochastic convex semidefinite optimization based on the Lagrangian dual method which relaxes the nonanticipativity constraints. We show that the barrier Lagrangian dual functions for our setting form self-concordant families with respect to barrier parameters. We also use the barrier function method to improve … Read more

    A minibatch stochastic Quasi-Newton method adapted for nonconvex deep learning problems

  • Joshua D. Griffin
  • Majid Jahani
  • Martin Takac
  • Seyedalireza Yektamaram
  • Wenwen Zhou
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , ,

    In this study, we develop a limited memory nonconvex Quasi-Newton (QN) method, tailored to deep learning (DL) applications. Since the stochastic nature of (sampled) function information in minibatch processing can affect the performance of QN methods, three strategies are utilized to overcome this issue. These involve a novel progressive trust-region radius update (suitable for stochastic … Read more

    Inexact Restoration for Minimization with Inexact Evaluation both of the Objective Function and the Constraints

  • Luís Felipe Bueno
  • F. Larreal
  • José Mario Martínez
    • Categories Constrained Nonlinear Optimization Tags , ,

    In a recent paper an Inexact Restoration method for solving continuous constrained optimization problems was analyzed from the point of view of worst-case functional complexity and convergence. On the other hand, the Inexact Restoration methodology was employed, in a different research, to handle minimization problems with inexact evaluation and simple constraints. These two methodologies are … Read more

    A Trust Region Method for the Optimization of Noisy Functions

  • Shigeng Sun
  • Jorge Nocedal
    • Categories Nonlinear Optimization Tags , ,

    Classical trust region methods were designed to solve problems in which function and gradient information are exact. This paper considers the case when there are bounded errors (or noise) in the above computations and proposes a simple modification of the trust region method to cope with these errors. The new algorithm only requires information about … Read more

    Graph topology invariant gradient and sampling complexity for decentralized and stochastic optimization

  • Guanghui Lan
  • Yuyuan Ouyang
  • Yi Zhou
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Stochastic Programming Tags , , ,

    One fundamental problem in decentralized multi-agent optimization is the trade-off between gradient/sampling complexity and communication complexity. We propose new algorithms whose gradient and sampling complexities are graph topology invariant, while their communication complexities remain optimal. For convex smooth deterministic problems, we propose a primal dual sliding (PDS) algorithm that computes an $\epsilon$-solution with $O((\tilde{L}/\epsilon)^{1/2})$ gradient … Read more

    Worst-Case Complexity of an SQP Method for Nonlinear Equality Constrained Stochastic Optimization

  • Frank E. Curtis
  • Michael O'Neill
  • Daniel P. Robinson
    • Categories Constrained Nonlinear Optimization, Stochastic Programming Tags , , ,

    A worst-case complexity bound is proved for a sequential quadratic optimization (commonly known as SQP) algorithm that has been designed for solving optimization problems involving a stochastic objective function and deterministic nonlinear equality constraints. Barring additional terms that arise due to the adaptivity of the monotonically nonincreasing merit parameter sequence, the proved complexity bound is … Read more

    Using an Analytical Computational-Geometry Library to Model Nonoverlap and Boundary-Distance Constraints and their Application to Packing Poly-Bézier Shapes

  • Paul Morton
    • Categories Applications - Science and Engineering, Bound-constrained Optimization, Optimization Software and Modeling Systems Tags , , , , , , , , , , ,

    In this paper we will show how to model nonoverlap as well as uniform and nonuniform boundary-distance constraints between poly-Bézier shapes using an analytical computational-geometry library. We then use this capability to develop, implement and analyze analytical-optimization solutions to minimum-area rectangular-boundary packing-problems as well as minimum-area one- and two-dimensional puzzle-piece packing-problems. In the process, we … Read more

    Orbital $\varphi$-regularity in coincidence and fixed point problems in metric spaces

  • Nguyen Huu Tron
    • Categories Nonlinear Optimization Tags , , , ,

    The purpose of the present paper is to establish some (approximate) fixed point or coincidence theorems for set-valued mappings defined on metric spaces under the so-called orbital \varphi-regularity of the considered mappings. This is a type of (\varphi,\gamma)-regularity of set-valued mappings which is weaker than orbital regularity. In turn, it is used in the previous … Read more