Constrained Nonlinear Optimization

A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis

  • Etienne de Klerk
  • Monique Laurent
    • Categories Constrained Nonlinear Optimization, Global Optimization, Semi-definite Programming

    The generalized problem of moments is a conic linear optimization problem over the convex cone of positive Borel measures with given support. It has a large variety of applications, including global optimization of polynomials and rational functions, options pricing in finance, constructing quadrature schemes for numerical integration, and distributionally robust optimization. A usual solution approach, … Read more

    Adaptive regularization algorithms with inexact evaluations for nonconvex optimization

  • Stefania Bellavia
  • Benedetta Morini
  • Philippe L. Toint
  • Gianmarco Gurioli
    • Categories Constrained Nonlinear Optimization, Data-Mining, Unconstrained Optimization Tags , , , ,

    A regularization algorithm using inexact function values and inexact derivatives is proposed and its evaluation complexity analyzed. This algorithm is applicable to unconstrained problems and to problems with inexpensive constraints (that is constraints whose evaluation and enforcement has negligible cost) under the assumption that the derivative of highest degree is beta-H\”{o}lder continuous. It features a … Read more

    Deterministic upper bounds in global minimization with nonlinear equality constraints

  • Christian Füllner
  • Peter Kirst
  • Oliver Stein
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory

    We address the problem of deterministically determining upper bounds in continuous non-convex global minimization of box-constrained problems with equality constraints. These upper bounds are important for the termination of spatial branch-and-bound algorithms. Our method is based on the theorem of Miranda which helps to ensure the existence of feasible points in certain boxes. Then, the … Read more

    Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Constrained Nonlinear Optimization, Data-Mining, Nonlinear Systems and Least-Squares Tags , , , , ,

    We provide sharp worst-case evaluation complexity bounds for nonconvex minimization problems with general inexpensive constraints, i.e.\ problems where the cost of evaluating/enforcing of the (possibly nonconvex or even disconnected) constraints, if any, is negligible compared to that of evaluating the objective function. These bounds unify, extend or improve all known upper and lower complexity bounds … Read more

    Inexact alternating projections on nonconvex sets

  • Dmitriy Drusvyatskiy
  • Adrian Lewis
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    Given two arbitrary closed sets in Euclidean space, a simple transversality condition guarantees that the method of alternating projections converges locally, at linear rate, to a point in the intersection. Exact projection onto nonconvex sets is typically intractable, but we show that computationally-cheap inexact projections may suffice instead. In particular, if one set is defined … Read more

    Sparse Mean-Reverting Portfolios via Penalized Likelihood Optimization

  • Aleksandr Y. Aravkin
  • Tim Leung
  • Jize Zhang
    • Categories Constrained Nonlinear Optimization, Finance and Economics Tags , ,

    An optimization approach is proposed to construct sparse portfolios with mean-reverting price behaviors. Our objectives are threefold: (i) design a multi-asset long-short portfolio that best fits an Ornstein-Uhlenbeck process in terms of maximum likelihood, (ii) select portfolios with desirable characteristics of high mean reversion and low variance though penalization, and (iii) select a parsimonious portfolio … Read more

    Numerical Solution of Optimal Control Problems with Switches, Switching Costs and Jumps

  • Christian Kirches
  • Ekaterina Kostina
  • Andreas Meyer
  • Matthias Schlöder
    • Categories Constrained Nonlinear Optimization, Systems governed by Differential Equations Optimization

    In this article, we present a framework for the numerical solution of optimal control problems, constrained by ordinary differential equations which can run in (finitely many) different modes, where a change of modes leads to additional switching cost in the cost function, and whenever the system changes its mode, jumps in the differential states are … Read more

    On the Convergence to Stationary Points of Deterministic and Randomized Feasible Descent Directions Methods

  • Amir Beck
  • Nadav Hallak
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , ,

    We study the class of nonsmooth nonconvex problems in which the objective is to minimize the difference between a continuously differentiable function (possibly nonconvex) and a convex (possibly nonsmooth) function over a convex polytope. This general class contains many types of problems, including difference of convex functions (DC) problems, and as such, can be used … Read more

    Non-monotone Inexact Restoration Method for nonlinear programming

  • Fermín S. V. Bazán
  • Juliano B. Francisco
  • Douglas S. Gonçalves
  • Lila L. T. Paredes
    • Categories Constrained Nonlinear Optimization

    This paper deals with a new variant of the Inexact Restoration Method of Fischer and Friedlander (COAP, 46, pp. 333-346, 2010). We propose an algorithm that replaces the monotone line-search performed in the tangent phase (with regard to the penalty function) by a non-monotone one. Con- vergence to feasible points satisfying the approximate gradient projection … Read more

    Decision Diagram Decomposition for Quadratically Constrained Binary Optimization

  • David Bergman
  • Leonardo Lozano
    • Categories Constrained Nonlinear Optimization, Integer Programming, Quadratic Programming

    In recent years the use of decision diagrams within the context of discrete optimization has proliferated. This paper continues this expansion by proposing the use of decision diagrams for modeling and solving binary optimization problems with quadratic constraints. The model proposes the use of multiple decision diagrams to decompose a quadratic matrix so that each … Read more