Month: March 2018

Discretization-based algorithms for generalized semi-infinite and bilevel programs with coupling equality constraints

  • Hatim Djelassi
  • Alexander Mitsos
  • Moll Glass
    • Categories Global Optimization Applications, Global Optimization Theory, Semi-infinite Programming

    Discretization-based algorithms are proposed for the global solution of mixed-integer nonlinear generalized semi-infinite (GSIP) and bilevel (BLP) programs with lower-level equality constraints coupling the lower and upper level. The algorithms are extensions, respectively, of the algorithm proposed by Mitsos and Tsoukalas (J Glob Optim 61(1):1–17, 2015. https://doi.org/10.1007/s10898-014-0146-6) and by Mitsos (J Glob Optim 47(4):557–582, 2010. … Read more

    Robust Principal Component Analysis using Facial Reduction

  • Shiqian Ma
  • Linchuan Wei
  • Henry Wolkowicz
  • Fei Wang
    • Categories Data-Mining, Linear, Cone and Semidefinite Programming, Robust Optimization Tags , , ,

    We study algorithms for robust principal component analysis (RPCA) for a partially observed data matrix. The aim is to recover the data matrix as a sum of a low-rank matrix and a sparse matrix so as to eliminate erratic noise (outliers). This problem is known to be NP-hard in general. A classical way to solve … Read more

    On the Complexity of Testing Attainment of the Optimal Value in Nonlinear Optimization

  • Amir Ali Ahmadi
  • Jeffrey Zhang
    • Categories Global Optimization Theory, Nonlinear Optimization, Semi-definite Programming Tags , , , , ,

    We prove that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can test whether the optimal value of a nonlinear optimization problem where the objective and constraints are given by low-degree polynomials is attained. If the degrees of these polynomials are fixed, our results along with previously-known “Frank-Wolfe type” theorems … Read more

    Solving Quadratic Programs to High Precision using Scaled Iterative Refinement

  • Ambros Gleixner
  • Sebastian Sager
  • Tobias Weber
    • Categories Quadratic Programming Tags , , ,

    Quadratic optimization problems (QPs) are ubiquitous, and solution algorithms have matured to a reliable technology. However, the precision of solutions is usually limited due to the underlying floating-point operations. This may cause inconveniences when solutions are used for rigorous reasoning. We contribute on three levels to overcome this issue. First, we present a novel refinement … Read more

    Computational performance of a projection and rescaling algorithm

  • Javier F. Peña
  • Negar Soheili
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , ,

    This paper documents a computational implementation of a {\em projection and rescaling algorithm} for finding most interior solutions to the pair of feasibility problems find $x\in L\cap\mathbb{R}^n_{+} $ and find $x\in L^\perp\cap\mathbb{R}^n_{+},$ where $L$ denotes a linear subspace in $\mathbb{R}^n$ and $L^\perp$ denotes its orthogonal complement. The projection and rescaling algorithm is a recently developed … Read more

    Projective Splitting with Forward Steps: Asynchronous and Block-Iterative Operator Splitting

  • Jonathan Eckstein
  • Patrick R. Johnstone
    • Categories Convex and Nonsmooth Optimization Tags ,

    This work is concerned with the classical problem of finding a zero of a sum of maximal monotone operators. For the projective splitting framework recently proposed by Combettes and Eckstein, we show how to replace the fundamental subproblem calculation using a backward step with one based on two forward steps. The resulting algorithms have the … Read more

    Two-stage Linear Decision Rules for Multi-stage Stochastic Programming

  • Merve Bodur
  • James R. Luedtke
    • Categories Stochastic Programming Tags , ,

    Multi-stage stochastic linear programs (MSLPs) are notoriously hard to solve in general. Linear decision rules (LDRs) yield an approximation of an MSLP by restricting the decisions at each stage to be an affine function of the observed uncertain parameters. Finding an optimal LDR is a static optimization problem that provides an upper bound on the … Read more

    An Integrated Car-and-ride Sharing System for Mobilizing Heterogeneous Travelers with Application in Underserved Communities

  • Siqian Shen
  • Miao Yu
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming, Transportation Tags , , , ,

    The fast-growing carsharing and ride-hailing businesses are generating economic benefits and societal impacts in the modern society. However, both have limitation to cover demand from diverse populations, e.g., travelers in low-income, underserved communities. In this paper, we consider two types of travelers: Type~1 who rent shared cars and Type~2 who need shared rides. We propose … Read more

    Data-DrivenWater Allocation under Climate Uncertainty: A Distributionally Robust Approach

  • Güzin Bayraksan
  • David Love
  • Jangho Park
    • Categories Civil and Environmental Engineering, Robust Optimization, Stochastic Programming Tags , , , ,

    This paper investigates the application of techniques from distributionally robust optimization (DRO) to water allocation under future uncertainty. Specifically, we look at a rapidly-developing area of Tucson, Arizona. Tucson, like many arid and semi-arid regions around the world, faces considerable uncertainty in its ability to provide water for its citizens in the future. The main … Read more

    A Globally Asymptotically Stable Polynomial Vector Field with Rational Coefficients and no Local Polynomial Lyapunov Function

  • Amir Ali Ahmadi
  • Bachir El Khadir
    • Categories Control Applications, Semi-definite Programming, Systems governed by Differential Equations Optimization Tags , , , ,

    We give an explicit example of a two-dimensional polynomial vector field of degree seven that has rational coefficients, is globally asymptotically stable, but does not admit an analytic Lyapunov function even locally. CitationSubmitted for publicationArticleDownload View PDF