 Award ID(s):
 1752125
 NSFPAR ID:
 10129315
 Date Published:
 Journal Name:
 INFORMS Journal on Computing
 ISSN:
 10919856
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

null (Ed.)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 special cases using casespecific reasoning, here we develop a general methodology for treatment of the approximability and inapproximability aspects of these questions. The underlying geometry of K plays a critical role; we show under commonly used complexity assumptions that polytime constantapproximability necessitates that K has type2 constant that grows slowly with n. However, we show that even when the type2 constant is bounded, this problem sometimes exhibits strong hardness of approximation. Thus, even within the realm of type2 bodies, the approximability landscape is nuanced and subtle. However, the link that we establish between optimization and geometry of Banach spaces allows us to devise a generic algorithmic approach to the above problem. We associate to each convex body a new (higher dimensional) auxiliary set that is not convex, but is approximately convex when K has a bounded type2 constant. If our auxiliary set has an approximate separation oracle, then we design an approximation algorithm for the original quadratic optimization problem, using an approximate version of the ellipsoid method. Even though our hardness result implies that such an oracle does not exist in general, this new question can be solved in specific cases of interest by implementing a range of classical tools from functional analysis, most notably the deep factorization theory of linear operators. Beyond encompassing the scenarios in the literature for which constantfactor approximation algorithms were found, our generic framework implies that that for convex sets with bounded type2 constant, constant factor approximability is preserved under the following basic operations: (a) Subspaces, (b) Quotients, (c) Minkowski Sums, (d) Complex Interpolation. This yields a rich family of new examples where constant factor approximations are possible, which were beyond the reach of previous methods. We also show (under commonly used complexity assumptions) that for symmetric norms and unitarily invariant matrix norms the type2 constant nearly characterizes the approximability of quadratic maximization.more » « less

null (Ed.)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 problem that “protects” the solution against deviations due to sensing uncertainty. The parameters of the robust problem are estimated by sampling from the distribution of noisy obstacles, and performing a firstorder approximation of the signed distance function. The original merit function is updated to account for the new costs of the robust formulation at every step. The effectiveness of our approach is demonstrated on two simulated experiments that involve a full body square robot, that moves in randomly generated scenes, and a 7DOF Fetch robot, performing tabletop operations. The results show nearly zero probability of collision for a reasonable range of the noise parameters for Gaussian and Uniform uncertainty.more » « less

null (Ed.)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 small instances. We provide a family of simplicial TSP instances that shows that the integrality gap of this SDP is unbounded. Second, we show that these simplicial TSP instances imply the unbounded integrality gap of every SDP relaxation of the TSP mentioned in the survey on SDP relaxations of the TSP in section 2 of Sotirov [Sotirov R (2012) SDP relaxations for some combinatorial optimization problems. Anjos MF, Lasserre JB, eds., Handbook on Semidefinite, Conic and Polynomial Optimization (Springer, New York), 795–819.]. In contrast, the subtour linear program performs perfectly on simplicial instances. The simplicial instances thus form a natural litmus test for future SDP relaxations of the TSP.more » « less

Identifying causeeffect relations among variables is a key step in the decisionmaking process. Whereas causal inference requires randomized experiments, researchers and policy makers are increasingly using observational studies to test causal hypotheses due to the wide availability of data and the infeasibility of experiments. The matching method is the most used technique to make causal inference from observational data. However, the pair assignment process in onetoone matching creates uncertainty in the inference because of different choices made by the experimenter. Recently, discrete optimization models have been proposed to tackle such uncertainty; however, they produce 01 nonlinear problems and lack scalability. In this work, we investigate this emerging data science problem and develop a unique computational framework to solve the robust causal inference test instances from observational data with continuous outcomes. In the proposed framework, we first reformulate the nonlinear binary optimization problems as feasibility problems. By leveraging the structure of the feasibility formulation, we develop greedy schemes that are efficient in solving robust test problems. In many cases, the proposed algorithms achieve a globally optimal solution. We perform experiments on realworld data sets to demonstrate the effectiveness of the proposed algorithms and compare our results with the stateoftheart solver. Our experiments show that the proposed algorithms significantly outperform the exact method in terms of computation time while achieving the same conclusion for causal tests. Both numerical experiments and complexity analysis demonstrate that the proposed algorithms ensure the scalability required for harnessing the power of big data in the decisionmaking process. Finally, the proposed framework not only facilitates robust decision making through bigdata causal inference, but it can also be utilized in developing efficient algorithms for other nonlinear optimization problems such as quadratic assignment problems. History: Accepted by Ram Ramesh, Area Editor for Data Science and Machine Learning. Funding: This work was supported by the Division of Civil, Mechanical and Manufacturing Innovation of the National Science Foundation [Grant 2047094]. Supplemental Material: The online supplements are available at https://doi.org/10.1287/ijoc.2022.1226 .more » « less

Abstract This paper studies several solution paths of sparse quadratic minimization problems as a function of the weighing parameter of the biobjective of estimation loss versus solution sparsity. Three such paths are considered: the “
path” where the discontinuous$$\ell _0$$ ${\ell}_{0}$ function provides the exact sparsity count; the “$$\ell _0$$ ${\ell}_{0}$ path” where the$$\ell _1$$ ${\ell}_{1}$ function provides a convex surrogate of sparsity count; and the “capped$$\ell _1$$ ${\ell}_{1}$ path” where the nonconvex nondifferentiable capped$$\ell _1$$ ${\ell}_{1}$ function aims to enhance the$$\ell _1$$ ${\ell}_{1}$ approximation. Serving different purposes, each of these three formulations is different from each other, both analytically and computationally. Our results deepen the understanding of (old and new) properties of the associated paths, highlight the pros, cons, and tradeoffs of these sparse optimization models, and provide numerical evidence to support the practical superiority of the capped$$\ell _1$$ ${\ell}_{1}$ path. Our study of the capped$$\ell _1$$ ${\ell}_{1}$ path is interesting in its own right as the path pertains to computable directionally stationary (= strongly locally minimizing in this context, as opposed to globally optimal) solutions of a parametric nonconvex nondifferentiable optimization problem. Motivated by classical parametric quadratic programming theory and reinforced by modern statistical learning studies, both casting an exponential perspective in fully describing such solution paths, we also aim to address the question of whether some of them can be fully traced in strongly polynomial time in the problem dimensions. A major conclusion of this paper is that a path of directional stationary solutions of the capped$$\ell _1$$ ${\ell}_{1}$ regularized problem offers interesting theoretical properties and practical compromise between the$$\ell _1$$ ${\ell}_{1}$ path and the$$\ell _0$$ ${\ell}_{0}$ path. Indeed, while the$$\ell _1$$ ${\ell}_{1}$ path is computationally prohibitive and greatly handicapped by the repeated solution of mixedinteger nonlinear programs, the quality of$$\ell _0$$ ${\ell}_{0}$ path, in terms of the two criteria—loss and sparsity—in the estimation objective, is inferior to the capped$$\ell _1$$ ${\ell}_{1}$ path; the latter can be obtained efficiently by a combination of a parametric pivotinglike scheme supplemented by an algorithm that takes advantage of the Zmatrix structure of the loss function.$$\ell _1$$ ${\ell}_{1}$