A bipartite bilinear program (BBP) is a quadratically constrained quadratic optimization problem where the variables can be partitioned into two sets such that fixing the variables in any one of the sets results in a linear program. We propose a new second order cone representable (SOCP) relaxation for BBP, which we show is stronger than … Read more
The application of decision diagrams in combinatorial optimization has proliferated in the last decade. In recent years, authors have begun to investigate how to utilize not one, but a set of diagrams, to model constraints and objective function terms. Optimizing over a collection of decision diagrams, the problem we refer to as the consistent path … Read more
In this paper, we consider perturbation properties of a linear second-order conic optimization problem and its Lagrange dual in which all parameters in the problem are perturbed. We prove the upper semi-continuity of solution mappings for the primal problem and the Lagrange dual problem. We demonstrate that the optimal value function can be expressed as … Read more
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
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
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
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
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
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
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