Nonlinear Optimization

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

  • Frank E. Curtis
  • Michael J. 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

    A sequential adaptive regularisation using cubics algorithm for solving nonlinear equality constrained optimization

  • Yonggang Pei
  • Shaofang Song
  • Zhu Detong
    • Categories Constrained Nonlinear Optimization Tags , , ,

    The adaptive regularisation algorithm using cubics (ARC) is initially proposed for unconstrained optimization. ARC has excellent convergence properties and complexity. In this paper, we extend ARC to solve nonlinear equality constrained optimization and propose a sequential adaptive regularisation using cubics algorithm inspired by sequential quadratic programming (SQP) methods. In each iteration of our method, the … Read more

    A Globally Convergent Distributed Jacobi Scheme for Block-Structured Nonconvex Constrained Optimization Problems

  • Anirudh Subramanyam
  • Youngdae Kim
  • Michel Schanen
  • François Pacaud
  • Mihai Anitescu
    • Categories Constrained Nonlinear Optimization Tags , ,

    Motivated by the increasing availability of high-performance parallel computing, we design a distributed parallel algorithm for linearly-coupled block-structured nonconvex constrained optimization problems. Our algorithm performs Jacobi-type proximal updates of the augmented Lagrangian function, requiring only local solutions of separable block nonlinear programming (NLP) problems. We provide a cheap and explicitly computable Lyapunov function that allows … Read more

    Distributionally risk-receptive and risk-averse network interdiction problems with general ambiguity set

  • Sumin Kang
  • Manish Bansal
    • Categories Nonlinear Optimization, Stochastic Programming Tags , , , ,

    We introduce generalizations of stochastic network interdiction problem with distributional ambiguity. Specifically, we consider a distributionally risk-averse (or robust) network interdiction problem (DRA-NIP) and a distributionally risk-receptive network interdiction problem (DRR-NIP) where a leader maximizes a follower’s minimal expected objective value for either the worst-case or the best-case, respectively, probability distribution belonging to ambiguity set … Read more

    A unified analysis of descent sequences in weakly convex optimization, including convergence rates for bundle methods

  • Felipe Atenas
  • Claudia Sagastizábal
  • Paulo J. S. Silva
  • Mikhail V. Solodov
    • Categories Complementarity and Variational Inequalities, Nonlinear Optimization Tags , , , , , , ,

    We present a framework for analyzing convergence and local rates of convergence of a class of descent algorithms, assuming the objective function is weakly convex. The framework is general, in the sense that it combines the possibility of explicit iterations (based on the gradient or a subgradient at the current iterate), implicit iterations (using a … Read more

    An adaptive regularization algorithm for unconstrained optimization with inexact function and derivatives values

  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , , ,

    An adaptive regularization algorithm for unconstrained nonconvex optimization is proposed that is capable of handling inexact objective-function and derivative values, and also of providing approximate minimizer of arbitrary order. In comparison with a similar algorithm proposed in Cartis, Gould, Toint (2022), its distinguishing feature is that it is based on controlling the relative error between … Read more

    Trust-region algorithms: probabilistic complexity and intrinsic noise with applications to subsampling techniques

  • Stefania Bellavia
  • Gianmarco Gurioli
  • Benedetta Morini
  • Philippe L. Toint
    • Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , , , , ,

    A trust-region algorithm is presented for finding approximate minimizers of smooth unconstrained functions whose values and derivatives are subject to random noise. It is shown that, under suitable probabilistic assumptions, the new method finds (in expectation) an epsilon-approximate minimizer of arbitrary order q > 0 in at most O(epsilon^{-(q+1)}) inexact evaluations of the function and … Read more

    OPM, a collection of Optimization Problems in Matlab

  • Serge Gratton
  • Philippe L. Toint
    • Categories Bound-constrained Optimization, Optimization Software Benchmark, Unconstrained Optimization Tags , , ,

    OPM is a small collection of CUTEst unconstrained and bound-constrained nonlinear optimization problems, which can be used in Matlab for testing optimization algorithms directly (i.e. without installing additional software). ArticleDownload View PDF