Nonlinear Optimization

On the complexity of finding first-order critical points in constrained nonlinear optimization

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , ,

    The complexity of finding epsilon-approximate first-order critical points for the general smooth constrained optimization problem is shown to be no worse that O(epsilon^{-2}) in terms of function and constraints evaluations. This result is obtained by analyzing the worst-case behaviour of a first-order shorts-step homotopy algorithm consisting of a feasibility phase followed by an optimization phase, … Read more

    On the impact of symmetry-breaking constraints on spatial Branch-and-Bound for circle packing in a square

  • Alberto Costa
  • Pierre Hansen
  • Leo Liberti
    • Categories Combinatorial Optimization, Global Optimization, Nonlinear Optimization Tags , , , ,

    We study the problem of packing equal circles in a square from the mathematical programming point of view. We discuss different formulations, we analyse formulation symmetries, we propose some symmetry breaking constraints and show that not only do they tighten the convex relaxation bound, but they also ease the task of local NLP solution algorithms … Read more

    On the Moreau-Yosida regularization of the vector k-norm related functions

  • Chao Ding
  • Defeng Sun
  • Kim-Chuan Toh
  • Bin Wu
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , ,

    In this paper, we conduct a thorough study on the first and second order properties of the Moreau-Yosida regularization of the vector $k$-norm function, the indicator function of its epigraph, and the indicator function of the vector $k$-norm ball. We start with settling the vector $k$-norm case via applying the existing breakpoint searching algorithms to … Read more

    Finding largest small polygons with GloptiPoly

  • Didier Henrion
  • Frédéric Messine
    • Categories Global Optimization, Quadratic Programming, Semi-definite Programming Tags , , ,

    A small polygon is a convex polygon of unit diameter. We are interested in small polygons which have the largest area for a given number of vertices $n$. Many instances are already solved in the literature, namely for all odd $n$, and for $n=4, 6$ and $8$. Thus, for even $n\geq 10$, instances of this … Read more

    A Dwindling Filter Line Search Method for Unconstrained Optimization

  • Yannan Chen
  • Wenyu Sun
    • Categories Unconstrained Optimization Tags , , , ,

    In this paper, we propose a new dwindling multidimensional filter second-order line search method for solving large-scale unconstrained optimization problems. Usually, the multidimensional filter is constructed with a fixed envelope, which is a strict condition for the gradient vectors. A dwindling multidimensional filter technique, which is a modification and improvement of the original multidimensional filter, … Read more

    Snow water equivalent estimation using blackbox optimization

  • Stéphane Alarie
  • Charles Audet
  • Vincent Garnier
  • Sébastien Le Digabel
  • Louis-Alexandre Leclaire
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    Accurate measurements of snow water equivalent (SWE) is an important factor in managing water resources for hydroelectric power generation. SWE over a catchment area may be estimated via kriging on measures obtained by snow monitoring devices positioned at strategic locations. The question studied in this paper is to find the device locations that minimize the … Read more

    Second-Order-Cone Constraints for Extended Trust-Region Subproblems

  • Kurt M. Anstreicher
  • Samuel Burer
    • Categories Constrained Nonlinear Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    The classical trust-region subproblem (TRS) minimizes a nonconvex quadratic objective over the unit ball. In this paper, we consider extensions of TRS having extra constraints. When two parallel cuts are added to TRS, we show that the resulting nonconvex problem has an exact representation as a semidefinite program with additional linear and second-order-cone constraints. For … Read more

    A Perry Descent Conjugate Gradient Method with Restricted Spectrum

  • Dongyi Liu
  • Genqi Xu
    • Categories Unconstrained Optimization Tags , , , ,

    A new nonlinear conjugate gradient method, based on Perry’s idea, is presented. And it is shown that its sufficient descent property is independent of any line search and the eigenvalues of $P_{k+1}^{\T}P_{k+1}$ are bounded above, where $P_{k+1}$ is the iteration matrix of the new method. Thus, the global convergence is proven by the spectral analysis … Read more

    Use of quadratic models with mesh adaptive direct search for constrained black box optimization

  • Andrew R. Conn
  • Sébastien Le Digabel
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    We consider a derivative-free optimization, and in particular black box optimization, where the functions to be minimized and the functions representing the constraints are given by black boxes without derivatives. Two fundamental families of methods are available: model-based methods and directional direct search algorithms. This work exploits the flexibility of the second type of methods … Read more

    Convergence analysis of a proximal Gauss-Newton method

  • Saverio Salzo
  • Silvia Villa
    • Categories Nonlinear Systems and Least-Squares, Nonsmooth Optimization

    An extension of the Gauss-Newton algorithm is proposed to find local minimizers of penalized nonlinear least squares problems, under generalized Lipschitz assumptions. Convergence results of local type are obtained, as well as an estimate of the radius of the convergence ball. Some applications for solving constrained nonlinear equations are discussed and the numerical performance of … Read more