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

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

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

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

Robust Principal Component Analysis using Facial Reduction

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

Solving Quadratic Programs to High Precision using Scaled Iterative Refinement

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

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

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

Computational performance of a projection and rescaling algorithm

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

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

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

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

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

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. Citation Submitted for publication Article Download View A Globally Asymptotically Stable Polynomial Vector Field with Rational Coefficients and no Local Polynomial Lyapunov Function

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

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