Month: July 2014

Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone

  • Monique Laurent
  • Teresa Piovesan
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , ,

    We investigate the completely positive semidefinite cone $\mathcal{CS}_+^n$, a new matrix cone consisting of all $n\times n$ matrices that admit a Gram representation by positive semidefinite matrices (of any size). In particular we study relationships between this cone and the completely positive and doubly nonnegative cones, and between its dual cone and trace positive non-commutative … Read more

    Analyzing Node-Weighted Oblivious Matching Problem via Continuous LP with Jump Discontinuity

  • T-H. Hubert Chan
  • Fei Chen
  • Xiaowei Wu
    • Categories Graphs and Matroids Tags , ,

    We prove the first non-trivial performance ratio strictly above 0.5 for the weighted Ranking algorithm on the oblivious matching problem where nodes in a general graph can have arbitrary weights. We have discovered a new structural property of the ranking algorithm: if a node has two unmatched neighbors, then it will still be matched even … Read more

    Power-Capacity and Ramp-Capability Reserves for Wind Integration in Power-Based UC

  • Ross Baldick
  • Germán Morales-España
  • Javier García-González
  • Andres Ramos
    • Categories Applications - OR and Management Sciences, Robust Optimization, Stochastic Programming Tags , , , ,

    This paper proposes a power-based network-constrained unit commitment (UC) model as an alternative to the traditional deterministic UCs to deal with wind generation uncertainty. The formulation draws a clear distinction between power-capacity and ramp-capability reserves to deal with wind production uncertainty. These power and ramp requirements can be obtained from wind forecast information. The model … Read more

    An elementary proof of linear programming optimality conditions without using Farkas’ lemma

  • Anders Forsgren
  • Margaret H. Wright
    • Categories Linear Programming Tags , ,

    Although it is easy to prove the sufficient conditions for optimality of a linear program, the necessary conditions pose a pedagogical challenge. A widespread practice in deriving the necessary conditions is to invoke Farkas’ lemma, but proofs of Farkas’ lemma typically involve “nonlinear” topics such as separating hyperplanes between disjoint convex sets, or else more … Read more

    An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric distribution

  • Etienne de Klerk
  • Monique Laurent
  • Zhao Sun
    • Categories Global Optimization, Nonlinear Optimization Tags , ,

    We study the minimization of fixed-degree polynomials over the simplex. This problem is well-known to be NP-hard, as it contains the maximum stable set problem in graph theory as a special case. In this paper, we consider a rational approximation by taking the minimum over the regular grid, which consists of rational points with denominator … Read more

    Stochastic Topology Design Optimization for Continuous Elastic Materials

  • Miguel Carrasco
  • Benjamin Ivorra
  • Ángel M. Ramos
    • Categories Mechanical Engineering, Multidisciplinary Design Optimization, Stochastic Programming

    In this paper, we develop a stochastic model for topology optimization. We find robust structures that minimize the compliance for a given main load having a stochastic behavior. We propose a model that takes into account the expected value of the compliance and its variance. We show that, similarly to the case of truss structures, … Read more

    Tight MIP Formulations of the Power-Based Unit Commitment Problem

  • Claudio Gentile
  • Germán Morales-España
  • Andres Ramos
    • Categories (Mixed) Integer Linear Programming, Scheduling Tags , , , , ,

    This paper provides the convex hull description for the basic operation of slow- and quick-start units in power-based unit commitment (UC) problems. The basic operating constraints that are modeled for both types of units are: 1) generation limits and 2) minimum up and down times. Apart from this, the startup and shutdown processes are also … Read more

    A Tight MIP Formulation of the Unit Commitment Problem with Start-up and Shut-down Constraints

  • Claudio Gentile
  • Germán Morales-España
  • Andres Ramos
    • Categories (Mixed) Integer Linear Programming, Scheduling Tags , ,

    This paper provides the convex hull description for the following basic operating constraints of a single power generation unit in Unit Commitment (UC) problems: 1) generation limits, 2) startup and shutdown capabilities, and 3) minimum up and down times. Although the model does not consider some crucial constraints, such as ramping, the proposed constraints can … Read more

    An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization

  • Qihang Lin
  • Zhaosong Lu
  • Lin Xiao
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization, Stochastic Programming Tags , ,

    We consider the problem of minimizing the sum of two convex functions: one is smooth and given by a gradient oracle, and the other is separable over blocks of coordinates and has a simple known structure over each block. We develop an accelerated randomized proximal coordinate gradient (APCG) method for minimizing such convex composite functions. … Read more

    Linear conic optimization for nonlinear optimal control

  • Didier Henrion
  • Edouard Pauwels
    • Categories Control Applications, Infinite Dimensional Optimization, Semi-definite Programming

    Infinite-dimensional linear conic formulations are described for nonlinear optimal control problems. The primal linear problem consists of finding occupation measures supported on optimal relaxed controlled trajectories, whereas the dual linear problem consists of finding the largest lower bound on the value function of the optimal control problem. Various approximation results relating the original optimal control … Read more