Nonlinear Optimization

Monomial-wise Optimal Separable Underestimators for Mixed-Integer Polynomial Optimization

  • Christoph Buchheim
  • Claudia D'Ambrosio
    • Categories (Mixed) Integer Nonlinear Programming, Bound-constrained Optimization, Global Optimization

    In this paper we introduce a new method for solving box-constrained mixed-integer polynomial problems to global optimality. The approach, a specialized branch-and-bound algorithm, is based on the computation of lower bounds provided by the minimization of separable underestimators of the polynomial objective function. The underestimators are the novelty of the approach because the standard approaches … Read more

    A Two-Variable Approach to the Two-Trust-Region Subproblem

  • Samuel Burer
  • Boshi Yang
    • Categories Quadratic Programming, Semi-definite Programming Tags , ,

    The trust-region subproblem minimizes a general quadratic function over an ellipsoid and can be solved in polynomial time using a semidefinite-programming (SDP) relaxation. Intersecting the feasible set with a second ellipsoid results in the two-trust-region subproblem (TTRS). Even though TTRS can also be solved in polynomial-time, existing algorithms do not use SDP. In this paper, … Read more

    Narrowing the difficulty gap for the Celis-Dennis-Tapia problem

  • Immanuel M. Bomze
  • Michael L. Overton
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory, Quadratic Programming Tags , , , ,

    We study the {\em Celis-Dennis-Tapia (CDT) problem}: minimize a non-convex quadratic function over the intersection of two ellipsoids. In contrast to the well-studied trust region problem where the feasible set is just one ellipsoid, the CDT problem is not yet fully understood. Our main objective in this paper is to narrow the difficulty gap that … Read more

    A Derivative-Free Algorithm for Constrained Global Optimization based on Exact Penalty Functions

  • G. Di Pillo
  • Stefano Lucidi
  • Francesco Rinaldi
    • Categories Global Optimization, Nonlinear Optimization

    Constrained global optimization problems can be tackled by using exact penalty approaches. In a preceding paper, we proposed an exact penalty algorithm for constrained problems which combines an unconstrained global minimization technique for minimizing a non-differentiable exact penalty func- tion for given values of the penalty parameter, and an automatic updating of the penalty parameter … Read more

    Derivative-free Robust Optimization for Circuit Design

  • A. Ciccazzo
  • Giampaolo Liuzzi
  • Stefano Lucidi
  • Francesco Rinaldi
  • V. Latorre
    • Categories Nonlinear Optimization, Robust Optimization Tags

    In this paper, we introduce a framework for derivative-free robust optimization based on the use of an efficient derivative-free optimization routine for mixed integer nonlinear problems. The proposed framework is employed to find a robust optimal design of a particular integrated circuit (namely a DC-DC converter commonly used in portable electronic devices). The proposed robust … Read more

    A Parallel Quadratic Programming Method for Dynamic Optimization Problems

  • Moritz Diehl
  • Sebastian Sager
  • Janick V Frasch
    • Categories Control Applications, Quadratic Programming Tags , , ,

    Quadratic programming problems (QPs) that arise from dynamic optimization problems typically exhibit a very particular structure. We address the ubiquitous case where these QPs are strictly convex and propose a dual Newton strategy that exploits the block-bandedness similarly to an interior-point method. Still, the proposed method features warmstarting capabilities of active-set methods. We give details … Read more

    An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex

  • Etienne de Klerk
  • Monique Laurent
  • Zhao Sun
    • Categories Nonlinear Optimization Tags , ,

    The problem of minimizing a polynomial over the standard simplex is one of the basic NP-hard nonlinear optimization problems — it contains the maximum clique problem in graphs as a special case. It is known that the problem allows a polynomial-time approximation scheme (PTAS) for polynomials of fixed degree, which is based on polynomial evaluations … Read more

    Finding Diverse Solutions of High Quality to Binary Integer Programs

  • Renata A. Konrad
  • Andrew C. Trapp
    • Categories 0-1 Programming, Multi-Criteria Optimization, Nonlinear Optimization

    Typical output from an optimization solver is a single optimal solution. At the same time, a set of high-quality and diverse solutions could be beneficial in a variety of contexts, for example problems involving imperfect information, or those for which the structure of high-quality solution vectors can reveal meaningful insights. In view of this, we … Read more

    A Regularized SQP Method with Convergence to Second-Order Optimal Points

  • Philip E. Gill
  • Vyacheslav Kungurtsev
  • Daniel P. Robinson
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , , ,

    Regularized and stabilized sequential quadratic programming methods are two classes of sequential quadratic programming (SQP) methods designed to resolve the numerical and theoretical difficulties associated with ill-posed or degenerate nonlinear optimization problems. Recently, a regularized SQP method has been proposed that provides a strong connection between augmented Lagrangian methods and stabilized SQP methods. The method … Read more

    An efficient gradient method using the Yuan steplength

  • Roberta De Asmundis
  • Daniela di Serafino
  • William W. Hager
  • Gerardo Toraldo
  • Hongchao Zhang
    • Categories Nonlinear Optimization, Quadratic Programming, Unconstrained Optimization Tags , ,

    We propose a new gradient method for quadratic programming, named SDC, which alternates some SD iterates with some gradient iterates that use a constant steplength computed through the Yuan formula. The SDC method exploits the asymptotic spectral behaviour of the Yuan steplength to foster a selective elimination of the components of the gradient along the … Read more