Month: November 2009

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

    Tightened L0 Relaxation Penalties for Classification

  • Jonathan Eckstein
  • Noam Goldberg
    • Categories (Mixed) Integer Linear Programming, Data-Mining, Statistics Tags , , , , , ,

    In optimization-based classification model selection, for example when using linear programming formulations, a standard approach is to penalize the L1 norm of some linear functional in order to select sparse models. Instead, we propose a novel integer linear program for sparse classifier selection, generalizing the minimum disagreement hyperplane problem whose complexity has been investigated in … Read more

    An Improved Branch-and-Bound Method for Maximum Monomial Agreement

  • Jonathan Eckstein
  • Noam Goldberg
    • Categories 0-1 Programming, Branch and Cut Algorithms, Data-Mining Tags , , , ,

    The NP-hard Maximum Monomial Agreement (MMA) problem consists of finding a single logical conjunction that best fits a weighted dataset of “positive” and “negative” binary vectors. Computing classifiers using boosting methods involves a maximum agreement subproblem at each iteration, although such subproblems are typically solved by heuristic methods. Here, we describe an exact branch and … Read more

    Most tensor problems are NP-hard

  • Christopher Hillar
  • Lek-Heng Lim
    • Categories Applications - Science and Engineering, Global Optimization Theory, Graphs and Matroids Tags , , , , , , , , , ,

    We show that multilinear (tensor) analogues of many efficiently computable problems in numerical linear algebra are NP-hard. Our list here includes: determining the feasibility of a system of bilinear equations, deciding whether a tensor possesses a given eigenvalue, singular value, or spectral norm; approximating an eigenvalue, eigenvector, singular vector, or spectral norm; determining a best … Read more

    A Time Bucket Formulation for the TSP with Time Windows

  • Sanjeeb Dash
  • Oktay Gunluk
  • Andrea Lodi
  • Andrea Tramontani
    • Categories Integer Programming

    The Traveling Salesman Problem with Time Windows (TSPTW) is the problem of finding a minimum-cost path visiting a set of cities exactly once, where each city must be visited within a given time window. We present an extended formulation for the problem based on partitioning the time windows into sub-windows, which we call “buckets”. We … Read more

    A Facial Reduction Algorithm for Finding Sparse SOS Representations

  • Masakazu Muramatsu
  • Hayato Waki
    • Categories Convex Optimization, Global Optimization Theory, Semi-definite Programming Tags , , ,

    Facial reduction algorithm reduces the size of the positive semidefinite cone in SDP. The elimination method for a sparse SOS polynomial ([3]) removes unnecessary monomials for an SOS representation. In this paper, we establish a relationship between a facial reduction algorithm and the elimination method for a sparse SOS polynomial. Citation Technical Report CS-09-02, Department … Read more

    A simple branching scheme for Vertex Coloring Problems

  • Stefano Gualandi
  • Federico Malucelli
    • Categories Graphs and Matroids Tags , ,

    We present a branching scheme for some Vertex Coloring Problems based on a new graph operator called extension. The extension operator is used to generalize the branching scheme proposed by Zykov for the basic problem to a broad class of coloring problems, such as the graph multicoloring, where each vertex requires a multiplicity of colors, … 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

    Multi-Objective Stochastic Linear Programming with General form of Distributions

  • S.I. Ansari
  • Vincent Charles
    • Categories Stochastic Programming

    Probabilistic or Stochastic programming is a framework for modeling optimization problems that involve uncertainty. The basic idea used in solving stochastic optimization problems has so far been to convert a stochastic model into an equivalent deterministic model and is possible when the right hand side resource vector follows some specific distributions such as normal, lognormal … Read more