We investigate the approximability of the following optimization problem. The input is an n× n matrix A=(Aij) with real entries and an originsymmetric convex body K⊂ ℝn that is given by a membership oracle. The task is to compute (or approximate) the maximum of the quadratic form ∑i=1n∑j=1n Aij xixj=⟨ x,Ax⟩ as x ranges over K. This is a rich and expressive family of optimization problems; for different choices of matrices A and convex bodies K it includes a diverse range of optimization problems like maxcut, Grothendieck/noncommutative Grothendieck inequalities, small set expansion and more. While the literature studied these specialmore »
Robust Quadratic Programming with MixedInteger Uncertainty
We study robust convex quadratic programs where the uncertain problem parameters can contain both continuous and integer components. Under the natural boundedness assumption on the uncertainty set, we show that the generic problems are amenable to exact copositive programming reformulations of polynomial size. These convex optimization problems are NPhard but admit a conservative semidefinite programming (SDP) approximation that can be solved efficiently. We prove that the popular approximate Slemma method—which is valid only in the case of continuous uncertainty—is weaker than our approximation. We also show that all results can be extended to the twostage robust quadratic optimization setting if the problem has complete recourse. We assess the effectiveness of our proposed SDP reformulations and demonstrate their superiority over the stateoftheart solution schemes on instances of least squares, project management, and multiitem newsvendor problems.
 Award ID(s):
 1752125
 Publication Date:
 NSFPAR ID:
 10129315
 Journal Name:
 INFORMS Journal on Computing
 ISSN:
 10919856
 Sponsoring Org:
 National Science Foundation
More Like this


Motion planning for high degreeoffreedom (DOF) robots is challenging, especially when acting in complex environments under sensing uncertainty. While there is significant work on how to plan under state uncertainty for lowDOF robots, existing methods cannot be easily translated into the highDOF case, due to the complex geometry of the robot’s body and its environment. In this paper, we present a method that enhances optimizationbased motion planners to produce robust trajectories for highDOF robots for convex obstacles. Our approach introduces robustness into planners that are based on sequential convex programming: We reformulate each convex subproblem as a robust optimization problemmore »

In a chance constrained program (CCP), decision makers seek the best decision whose probability of violating the uncertainty constraints is within the prespecified risk level. As a CCP is often nonconvex and is difficult to solve to optimality, much effort has been devoted to developing convex inner approximations for a CCP, among which the conditional valueatrisk (CVaR) has been known to be the best for more than a decade. This paper studies and generalizes the ALSOX, originally proposed by Ahmed, Luedtke, SOng, and Xie in 2017 , for solving a CCP. We first show that the ALSOX resembles a bilevelmore »

The traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization. Several semidefinite programming relaxations have been proposed recently that exploit a variety of mathematical structures including, for example, algebraic connectivity, permutation matrices, and association schemes. The main results of this paper are twofold. First, de Klerk and Sotirov [de Klerk E, Sotirov R (2012) Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry. Math. Programming 133(1):75–91.] present a semidefinite program (SDP) based on permutation matrices and symmetry reduction; they show that it is incomparable to the subtour elimination linear program but generally dominates it on smallmore »

We describe strong convex valid inequalities for conic quadratic mixed 0–1 optimization. These inequalities can be utilized for solving numerous practical nonlinear discrete optimization problems from valueatrisk minimization to queueing system design, from robust interdiction to assortment optimization through appropriate conic quadratic mixed 0–1 relaxations. The inequalities exploit the submodularity of the binary restrictions and are based on the polymatroid inequalities over binaries for the diagonal case. We prove that the convex inequalities completely describe the convex hull of a single conic quadratic constraint as well as the rotated cone constraint over binary variables and unbounded continuous variables. We thenmore »