Constrained Nonlinear Optimization

Lagrangean Decomposition for Mean-Variance Combinatorial Optimization

  • Frank Baumann
  • Christoph Buchheim
  • Anna Ilyina
    • Categories Combinatorial Optimization, Constrained Nonlinear Optimization, Robust Optimization Tags , ,

    We address robust versions of combinatorial optimization problems, focusing on the uncorrelated ellipsoidal uncertainty case, which corresponds to so-called mean-variance optimization. We present a branch and bound-algorithm for such problems that uses lower bounds obtained from Lagrangean decomposition. This approach allows to separate the uncertainty aspect in the objective function from the combinatorial structure of … Read more

    A Primal Heuristic for MINLP based on Dual Information

  • Armin Fügenschuh
  • Jesco Humpola
  • Thomas Lehmann
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, Meta Heuristics

    We present a novel heuristic algorithm to identify feasible solutions of a mixed-integer nonlinear programming problem arising in natural gas transportation: the selection of new pipelines to enhance the network’s capacity to a desired level in a cost-efficient way. We solve this problem in a linear programming based branch-and-cut approach, where we deal with the … 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 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

    Constant rank constraint qualifications: a geometric introduction

  • Roberto Andreani
  • Paulo J. S. Silva
    • Categories Constrained Nonlinear Optimization Tags , ,

    Constraint qualifications (CQ) are assumptions on the algebraic description of the feasible set of an optimization problem that ensure that the KKT conditions hold at any local minimum. In this work we show that constraint qualifications based on the notion of constant rank can be understood as assumptions that ensure that the polar of the … Read more

    Complementarity Formulations of l0-norm Optimization Problems

  • Mingbin Feng
  • John E. Mitchell
  • Jong-Shi Pang
  • Xin Shen
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags , ,

    In a number of application areas, it is desirable to obtain sparse solutions. Minimizing the number of nonzeroes of the solution (its l0-norm) is a difficult nonconvex optimization problem, and is often approximated by the convex problem of minimizing the l1-norm. In contrast, we consider exact formulations as mathematical programs with complementarity constraints and their … Read more

    Rounding on the standard simplex: regular grids for global optimization

  • Immanuel M. Bomze
  • E. Alper Yildirim
  • Stefan Gollowitzer
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory

    Given a point on the standard simplex, we calculate a proximal point on the regular grid which is closest with respect to any norm in a large class, including all $\ell^p$-norms for $p\ge 1$. We show that the minimal $\ell^p$-distance to the regular grid on the standard simplex can exceed one, even for very fine … Read more

    The Euclidean distance degree of an algebraic variety

  • Jan Draisma
  • Emil Horobet
  • Giorgio Ottaviani
  • Bernd Sturmfels
  • Rekha R. Thomas
    • Categories Constrained Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    The nearest point map of a real algebraic variety with respect to Euclidean distance is an algebraic function. For instance, for varieties of low rank matrices, the Eckart-Young Theorem states that this map is given by the singular value decomposition. This article develops a theory of such nearest point maps from the perspective of computational … Read more

    A new formulation of protein evolutionary models that account for structural constraints

  • Andrew J. Bordner
  • Hans D Mittelmann
    • Categories Biomedical Applications, Constrained Nonlinear Optimization Tags , , , ,

    Despite the importance of a thermodynamically stable structure with a conserved fold for protein function, almost all evolutionary models neglect site-site correlations that arise from physical interactions between neighboring amino acid sites. This is mainly due to the difficulty in formulating a computationally tractable model since rate matrices can no longer be used. Here we … Read more

    String-Averaging Projected Subgradient Methods for Constrained Minimization

  • Yair Censor
  • Alexander J. Zaslavski
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , , , , , , , ,

    We consider constrained minimization problems and propose to replace the projection onto the entire feasible region, required in the Projected Subgradient Method (PSM), by projections onto the individual sets whose intersection forms the entire feasible region. Specifically, we propose to perform such projections onto the individual sets in an algorithmic regime of a feasibility-seeking iterative … Read more