Linear, Cone and Semidefinite Programming

Large-Scale Parallel Multibody Dynamics with Frictional Contact on the Graphical Processing Unit

  • Mihai Anitescu
  • Dan Negrut
  • Alessandro Tasora
    • Categories Complementarity and Variational Inequalities, Mechanical Engineering, Second-Order Cone Programming Tags , ,

    In the context of simulating the frictional contact dynamics of large systems of rigid bodies, this paper reviews a novel method for solving large cone complementarity problems by means of a fixed-point iteration algorithm. The method is an extension of the Gauss-Seidel and Gauss-Jacobimethods with overrelaxation for symmetric convex linear complementarity problems. Convergent under fairly … Read more

    Estimating Bounds for Quadratic Assignment Problems Associated with Hamming and Manhattan Distance Matrices based on Semidefinite Programming

  • Hans D Mittelmann
  • Jiming Peng
    • Categories Applications - OR and Management Sciences, Semi-definite Programming Tags , , ,

    Quadratic assignment problems (QAPs) with a Hamming distance matrix of a hypercube or a Manhattan distance matrix of rectangular grids arise frequently from communications and facility locations and are known to be among the hardest discrete optimization problems. In this paper we consider the issue of how to obtain lower bounds for those two classes … Read more

    Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion

  • Dimitris Bertsimas
  • Xuan Vinh Doan
  • Karthik Natarajan
  • Chung-Piaw Teo
    • Categories Semi-definite Programming, Stochastic Programming

    In this paper, we propose a semidefinite optimization (SDP) based model for the class of minimax two-stage stochastic linear optimization problems with risk aversion. The distribution of the second-stage random variables is assumed to be chosen from a set of multivariate distributions with known mean and second moment matrix. For the minimax stochastic problem with … Read more

    On the computation of $C^*$ certificates

  • Florian Jarre
  • Katrin Schmallowsky
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags

    The cone of completely positive matrices $C^*$ is the convex hull of all symmetric rank-1-matrices $xx^T$ with nonnegative entries. Determining whether a given matrix $B$ is completely positive is an $\cal NP$-complete problem. We examine a simple algorithm which — for a given input $B$ — either determines a certificate proving that $B\in C^*$ or … Read more

    Copositive programming motivated bounds on the stability and the chromatic numbers

  • Igor Dukanovic
  • Franz Rendl
    • Categories Graphs and Matroids, Linear, Cone and Semidefinite Programming Tags , , ,

    The Lovász theta number of a graph G can be viewed as a semidefinite programming relaxation of the stability number of G. It has recently been shown that a copositive strengthening of this semidefinite program in fact equals the stability number of G. We introduce a related strengthening of the Lovász theta number toward the … Read more

    Linear Programming for Mechanism Design: An Application to Bidder Collusion at First-Price Auctions

  • Giuseppe Lopomo
  • Peng Sun
  • Leslie Marx
    • Categories Applications - OR and Management Sciences, Game Theory, Linear Programming Tags , , ,

    We demonstrate the use of linear programming techniques in the analysis of mechanism design problems. We use these techniques to analyze the extent to which a first-price auction is robust to collusion when, contrary to some prior literature on collusion at first-price auctions, the cartel cannot prevent its members from bidding at the auction. In … Read more

    A Newton-CG Augmented Lagrangian Method for Semidefinite Programming

  • Defeng Sun
  • Kim-Chuan Toh
  • Xinyuan Zhao
    • Categories Nonsmooth Optimization, Semi-definite Programming Tags , , ,

    We consider a Newton-CG augmented Lagrangian method for solving semidefinite programming (SDP) problems from the perspective of approximate semismooth Newton methods. In order to analyze the rate of convergence of our proposed method, we characterize the Lipschitz continuity of the corresponding solution mapping at the origin. For the inner problems, we show that the positive … Read more

    Tractable Robust Expected Utility and Risk Models for Portfolio Optimization

  • Karthik Natarajan
  • Melvyn Sim
  • Joline Uichanco
    • Categories Finance and Economics, Robust Optimization, Second-Order Cone Programming

    Expected utility models in portfolio optimization is based on the assumption of complete knowledge of the distribution of random returns. In this paper, we relax this assumption to the knowledge of only the mean, covariance and support information. No additional assumption on the type of distribution such as normality is made. The investor’s utility is … Read more

    Parallel implementation of a semidefinite programming solver based on CSDP on a distributed memory cluster

  • Etienne de Klerk
  • Ivan D. Ivanov
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , ,

    In this paper we present the algorithmic framework and practical aspects of implementing a parallel version of a primal-dual semidefinite programming solver on a distributed memory computer cluster. Our implementation is based on the CSDP solver and uses a message passing interface (MPI), and the ScaLAPACK library. A new feature is implemented to deal with … Read more

    Homogeneous algorithms for monotone complementarity problems over symmetric cones

  • Akiko Yoshise
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    In \cite{aYOSHISE06}, the author proposed a homogeneous model for standard monotone nonlinear complementarity problems over symmetric cones and show that the following properties hold: (a) There is a path that is bounded and has a trivial starting point without any regularity assumption concerning the existence of feasible or strictly feasible solutions. (b) Any accumulation point … Read more