Month: December 2010

Solving structured nonlinear least-squares and nonlinear feasibility problems with expensive functions

  • Markus Kaiser
  • Philippe L. Toint
  • Kathrin Klamroth
  • Alexander Thekale
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Nonlinear Systems and Least-Squares Tags , , , , , , ,

    We present an algorithm for nonlinear least-squares and nonlinear feasibility problems, i.e. for systems of nonlinear equations and nonlinear inequalities, which depend on the outcome of expensive functions for which derivatives are assumed to be unavailable. Our algorithm combines derivative-free techniques with filter trust-region methods to keep the number of expensive function evaluations low and … Read more

    Integer-empty polytopes in the 0/1-cube with maximal Gomory-Chvátal rank

  • Sebastian Pokutta
  • Andreas S. Schulz
    • Categories 0-1 Programming, Cutting Plane Approaches, Polyhedra

    We provide a complete characterization of all polytopes P ⊆ [0,1]^n with empty integer hull whose Gomory-Chvátal rank is n (and, therefore, maximal). In particular, we show that the first Gomory- Chvátal closure of all these polytopes is identical. Article Download View Integer-empty polytopes in the 0/1-cube with maximal Gomory-Chvátal rank

    An Exact Penalty Global Optimization Approach for Mixed-Integer Programming Problems

  • Stefano Lucidi
  • Francesco Rinaldi
    • Categories (Mixed) Integer Nonlinear Programming Tags , ,

    In this work, we propose a global optimization approach for mixed-integer programming problems. To this aim, we preliminarily de ne an exact penalty algorithm model for globally solving general problems and we show its convergence properties. Then, we describe a particular version of the algorithm that solves mixed integer problems. Citation DIS Technical Report n. 17, … Read more

    The Convex Geometry of Linear Inverse Problems

  • Venkat Chandrasekaran
  • Benjamin Recht
  • Pablo A. Parrilo
  • Alan S. Willsky
    • Categories Applications - Science and Engineering, Convex Optimization, Semi-definite Programming

    In applications throughout science and engineering one is often faced with the challenge of solving an ill-posed inverse problem, where the number of available measurements is smaller than the dimension of the model to be estimated. However in many practical situations of interest, models are constrained structurally so that they only have a few degrees … Read more

    Convex Graph Invariants

  • Venkat Chandrasekaran
  • Pablo A. Parrilo
  • Alan S. Willsky
    • Categories Convex Optimization, Graphs and Matroids, Robust Optimization

    The structural properties of graphs are usually characterized in terms of invariants, which are functions of graphs that do not depend on the labeling of the nodes. In this paper we study convex graph invariants, which are graph invariants that are convex functions of the adjacency matrix of a graph. Some examples include functions of … Read more

    NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems

  • Amir Ali Ahmadi
  • Alex Olshevsky
  • Pablo A. Parrilo
  • John N. Tsitsiklis
    • Categories Convex Optimization, Global Optimization Theory Tags , , ,

    We show that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can decide whether a multivariate polynomial of degree four (or higher even degree) is globally convex. This solves a problem that has been open since 1992 when N. Z. Shor asked for the complexity of deciding convexity for quartic … Read more

    New approximations for the cone of copositive matrices and its dual

  • Jean-Bernard Lasserre
    • Categories Linear, Cone and Semidefinite Programming

    We provide convergent hierarchies for the cone C of copositive matrices and its dual, the cone of completely positive matrices. In both cases the corresponding hierarchy consists of nested spectrahedra and provide outer (resp. inner) approximations for C (resp. for its dual), thus complementing previous inner (resp. outer) approximations for C (for its dual). In … Read more

    Formulations for Dynamic Lot Sizing with Service Levels

  • Dinakar Gade
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Combinatorial Optimization Tags , , , ,

    In this paper, we study deterministic dynamic lot-sizing problems with service level constraints on the total number of periods in which backorders can occur over the finite planning horizon. We give a natural mixed integer programming formulation for the single item problem (LS-SL-I) and study the structure of its solution. We show that an optimal … Read more

    On reformulations of nonconvex quadratic programs over convex cones by set-semidefinite constraints

  • Gabriele Eichfelder
  • Janez Povh
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming

    The well-known result stating that any non-convex quadratic problem over the nonnegative orthant with some additional linear and binary constraints can be rewritten as linear problem over the cone of completely positive matrices (Burer, 2009) is generalized by replacing the nonnegative orthant with an arbitrary closed convex cone. This set-semidefinite representation result implies new semidefinite … Read more

    A Branch-and-Price Approach to the k-Clustering Minimum Biclique Completion Problem

  • Stefano Gualandi
  • Francesco Maffioli
  • Claudio Magni
    • Categories Applications - OR and Management Sciences, Graphs and Matroids, Integer Programming Tags , , ,

    Given a bipartite graph G = (S , T , E ), we consider the problem of finding k bipartite subgraphs, called clusters, such that each vertex i of S appears in exactly one of them, every vertex j of T appears in each cluster in which at least one of its neighbors appears, and … Read more