Month: January 2008

Convex Optimization Methods for Dimension Reduction and Coefficient Estimation in Multivariate Linear Regression

  • Zhaosong Lu
  • Renato D.C. Monteiro
  • Ming Yuan
    • Categories Convex Optimization, Nonsmooth Optimization, Statistics Tags , , , , , ,

    In this paper, we study convex optimization methods for computing the trace norm regularized least squares estimate in multivariate linear regression. The so-called factor estimation and selection (FES) method, recently proposed by Yuan et al. [17], conducts parameter estimation and factor selection simultaneously and have been shown to enjoy nice properties in both large and … Read more

    An Adaptive Linear Approximation Algorithm for Copositive Programs

  • Stefan Bundfuss
  • Mirjam Duer
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    We study linear optimization problems over the cone of copositive matrices. These problems appear in nonconvex quadratic and binary optimization, for instance the maximum clique problem and other combinatorial problems can be reformulated as such a problem. We present new polyhedral inner and outer approximations of the copositive cone which we show to be exact … Read more

    A Class Representative Model for Pure Parsimony Haplotyping

  • Daniele Catanzaro
  • Martine Labbé
  • Alessandra Godi
    • Categories (Mixed) Integer Linear Programming, Basic Sciences Applications Tags , ,

    Parsimonious haplotype estimation from aligned Single Nucleotide Polymorphism (SNP) fragments consists of finding the minimum number of haplotypes necessary to explain a given set of genotypes. This problem is known to be NP-Hard. Here we describe a new integer linear-programming model to tackle this problem based on the concept of class representatives, already used for … Read more

    Test instances for the traffic assignment problem

  • Frédéric Babonneau
  • Jean-Philippe Vial
    • Categories Network Optimization, Transportation Tags , , ,

    This short note on the Traffic Assignment Problem (TAP) provides the relevant information on test problems previously used in the literature to facilitate benchmarking Citation Technical report, Ordecsys, 2008. Article Download View Test instances for the traffic assignment problem

    Size constrained graph partitioning polytope. Part II: Non-trivial facets

  • Martine Labbé
  • F. Aykut Özsoy
    • Categories 0-1 Programming, Polyhedra Tags , , , ,

    We consider the problem of clustering a set of items into subsets whose sizes are bounded from above and below. We formulate the problem as a graph partitioning problem and propose an integer programming model for solving it. This formulation generalizes several well-known graph partitioning problems from the literature like the clique partitioning problem, the … Read more

    Size constrained graph partitioning polytope. Part I: Dimension and trivial facets

  • Martine Labbé
  • F. Aykut Özsoy
    • Categories 0-1 Programming, Polyhedra Tags , , , , ,

    We consider the problem of clustering a set of items into subsets whose sizes are bounded from above and below. We formulate the problem as a graph partitioning problem and propose an integer programming model for solving it. This formulation generalizes several well-known graph partitioning problems from the literature like the clique partitioning problem, the … Read more

    LASSO-Patternsearch Algorithm with Application to Ophthalmology and Genomic Data

  • Barbara Klein
  • Stephen Wright
  • Ronald Klein
  • Kristine Lee
  • Weiliang Shi
  • Grace Wahba
    • Categories Nonsmooth Optimization, Statistics Tags , ,

    The LASSO-Patternsearch algorithm is proposed as a two-step method to identify clusters or patterns of multiple risk factors for outcomes of interest in demographic and genomic studies. The predictor variables are dichotomous or can be coded as dichotomous. Many diseases are suspected of having multiple interacting risk factors acting in concert, and it is of … Read more

    A Redundant Klee-Minty Construction with All the Redundant Constraints Touching the Feasible Region

  • Eissa Nematollahi
  • Tamás Terlaky
    • Categories Linear Programming Tags , , , ,

    By introducing some redundant Klee-Minty constructions, we have previously shown that the central path may visit every vertex of the Klee-Minty cube having $2^n-2$ “sharp” turns in dimension $n$. In all of the previous constructions, the maximum of the distances of the redundant constraints to the corresponding facets is an exponential number of the dimension … Read more

    Formulation and solution strategies for nonparametric nonlinear stochastic programs, with an application in finance

  • Fabian Bastin
  • Philippe L. Toint
  • Cinzia Cirillo
    • Categories Finance and Economics, Nonlinear Optimization, Stochastic Programming Tags , , ,

    We consider a class of stochastic programming models where the uncertainty is classically represented using parametric distributions families. The parameters are then usually estimated together with the optimal value of the problem. However, misspecification of the underlying random variables often leads to irrealistic results when little is known about their true distributions. We propose to … Read more

    A difference of convex formulation of value-at-risk constrained optimization

  • R. Hochreiter
  • Georg Ch. Pflug
  • David Wozabal
    • Categories Finance and Economics, Global Optimization, Stochastic Programming Tags , , ,

    In this article, we present a representation of value-at-risk (VaR) as a difference of convex (D.C.) functions in the case where the distribution of the underlying random variable is discrete and has finitely many atoms. The D.C. representation is used to study a financial risk-return portfolio selection problem with a VaR constraint. A branch-and-bound algorithm … Read more