Nonlinear Optimization

A new sequential optimality condition for constrained optimization and algorithmic consequences

  • Roberto Andreani
  • José Mario Martínez
  • Benar Fux Svaiter
    • Categories Nonlinear Optimization Tags , , ,

    Necessary first-order sequential optimality conditions provide adequate theoretical tools to justify stopping criteria for nonlinear programming solvers. These conditions are satisfied by local minimizers of optimization problems independently of the fulfillment of constraint qual- i cations. A new strong sequential optimality condition is introduced in the present paper. A proof that a well established Augmented Lagrangian … Read more

    An L1 Elastic Interior-Point Method for Mathematical Programs with Complementarity Constraints

  • Zoumana Coulibaly
  • Dominique Orban
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags , , , , , , ,

    We propose an interior-point algorithm based on an elastic formulation of the L1-penalty merit function for mathematical programs with complementarity constraints. The method generalizes that of Gould, Orban and Toint (2003) and naturally converges to a strongly stationary point or delivers a certificate of degeneracy without recourse to second-order intermediate solutions. Remarkably, the method allows … Read more

    A Factorization with Update Procedures for a KKT Matrix Arising in Direct Optimal Control

  • Hans Georg Bock
  • Christian Kirches
  • Sebastian Sager
  • Johannes P. Schlöder
    • Categories Quadratic Programming, Systems governed by Differential Equations Optimization Tags , ,

    Quadratic programs obtained for optimal control problems of dynamic or discrete–time processes usually involve highly block structured Hessian and constraints matrices. Efficient numerical methods for the solution of such QPs have to respect and exploit this block structure. In interior point methods, this is elegantly achieved by the widespread availability of advanced sparse symmetric indefinite … Read more

    PARNES: A rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals

  • Ming Gu
  • Lek-Heng Lim
  • Cinna Julie Wu
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Optimization Software Benchmark Tags , , , , , , ,

    In this article we propose an algorithm, NESTA-LASSO, for the LASSO problem (i.e., an underdetermined linear least-squares problem with a one-norm constraint on the solution) that exhibits linear convergence under the restricted isometry property (RIP) and some other reasonable assumptions. Inspired by the state-of-the-art sparse recovery method, NESTA, we rely on an accelerated proximal gradient … Read more

    Second-Order Cone Relaxations for Binary Quadratic Polynomial Programs

  • Miguel F. Anjos
  • Bissan Ghaddar
  • Juan C. Vera
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , ,

    Several types of relaxations for binary quadratic polynomial programs can be obtained using linear, second-order cone, or semidefinite techniques. In this paper, we propose a general framework to construct conic relaxations for binary quadratic polynomial programs based on polynomial programming. Using our framework, we re-derive previous relaxation schemes and provide new ones. In particular, we … Read more

    Exact Penalty Functions for Nonlinear Integer Programming Problems

  • Stefano Lucidi
  • Francesco Rinaldi
    • Categories Integer Programming, Nonlinear Optimization Tags , ,

    In this work, we study exact continuous reformulations of nonlinear integer programming problems. To this aim, we preliminarily state conditions to guarantee the equivalence between pairs of general nonlinear problems. Then, we prove that optimal solutions of a nonlinear integer programming problem can be obtained by using various exact penalty formulations of the original problem … Read more

    Nonmonotone Filter Method for Nonlinear Optimization

  • Shen Chungen
  • Roger Fletcher
  • Sven Leyffer
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , ,

    We propose a new nonmonotone filter method to promote global and fast local convergence for sequential quadratic programming algorithms. Our method uses two filters: a global g-filter for global convergence, and a local nonmonotone l-filter that allows us to establish fast local convergence. We show how to switch between the two filters efficiently, and we … Read more

    Nonconvex Robust Optimization

  • Kwong Meng Teo
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, Robust Optimization Tags , , , , , ,

    We propose a novel robust optimization technique, which is applicable to nonconvex and simulation-based problems. Robust optimization finds decisions with the best worst-case performance under uncertainty. If constraints are present, decisions should also be feasible under perturbations. In the real-world, many problems are nonconvex and involve computer-based simulations. In these applications, the relationship between decision … Read more

    On the complexity of steepest descent, Newton’s and regularized Newton’s methods for nonconvex unconstrained optimization

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

    It is shown that the steepest descent and Newton’s method for unconstrained nonconvex optimization under standard assumptions may be both require a number of iterations and function evaluations arbitrarily close to O(epsilon^{-2}) to drive the norm of the gradient below epsilon. This shows that the upper bound of O(epsilon^{-2}) evaluations known for the steepest descent … Read more

    Stopping rules and backward error analysis for bound-constrained optimization

  • Serge Gratton
  • Philippe L. Toint
  • Mélodie Mouffe
    • Categories Bound-constrained Optimization, Optimization Software Design Principles Tags , , , ,

    Termination criteria for the iterative solution of bound-constrained optimization problems are examined in the light of backward error analysis. It is shown that the problem of determining a suitable perturbation on the problem’s data corresponding to the definition of the backward error is analytically solvable under mild assumptions. Moreover, a link between existing termination criteria … Read more