-
作者：Del Pia, Alberto; Khajavirad, Aida
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; Carnegie Mellon University
摘要：We consider the Multilinear set defined as the set of binary points (x, y) satisfying a collection of multilinear equations of the form , , where denotes a family of subsets of of cardinality at least two. Such sets appear in factorable reformulations of many types of nonconvex optimization problems, including binary polynomial optimization. A great simplification in studying the facial structure of the convex hull of the Multilinear set is possible when is decomposable into simpler Multilinea...
-
作者：Cartis, C.; Scheinberg, K.
作者单位：University of Oxford; Lehigh University
摘要：We present global convergence rates for a line-search method which is based on random first-order models and directions whose quality is ensured only with certain probability. We show that in terms of the order of the accuracy, the evaluation complexity of such a method is the same as its counterparts that use deterministic accurate models; the use of probabilistic models only increases the complexity by a constant, which depends on the probability of the models being good. We particularize an...
-
作者：Ioffe, Alexander D.
作者单位：Technion Israel Institute of Technology
摘要：The results on regularity behavior of solutions to variational inequalities over polyhedral sets proved in a series of papers by Robinson, Ralph and Dontchev-Rockafellar in the 90s has long become classics of variational analysis. But the available proofs are very complicated and practically do not use techniques of variational analysis. The only exception is the proof by Dontchev and Rockafellar of their critical face regularity criterion. In the paper we offer a different approach completely...
-
作者：Kim, Youngdae; Huber, Olivier; Ferris, Michael C.
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
摘要：Affine variational inequalities (AVI) are an important problem class that subsumes systems of linear equations, linear complementarity problems and optimality conditions for quadratic programs. This paper describes PathAVI, a structure-preserving pivotal approach, that can efficiently process (solve or determine infeasible) large-scale sparse instances of the problem with theoretical guarantees and at high accuracy. PathAVI implements a strategy known to process models with good theoretical pr...
-
作者：Esfahani, Peyman Mohajerin; Shafieezadeh-Abadeh, Soroosh; Hanasusanto, Grani A.; Kuhn, Daniel
作者单位：Delft University of Technology; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; University of Texas System; University of Texas Austin
摘要：In data-driven inverse optimization an observer aims to learn the preferences of an agent who solves a parametric optimization problem depending on an exogenous signal. Thus, the observer seeks the agent's objective function that best explains a historical sequence of signals and corresponding optimal actions. We focus here on situations where the observer has imperfect information, that is, where the agent's true objective function is not contained in the search space of candidate objectives,...
-
作者：Fleszar, Krzysztof; Mnich, Matthias; Spoerhase, Joachim
作者单位：Max Planck Society; Maastricht University; University of Bonn; University of Wurzburg
摘要：We study the classical NP-hard problems of finding maximum-size subsets from given sets of k terminal pairs that can be routed via edge-disjoint paths (MaxEDP) or node-disjoint paths (MaxNDP) in a given graph. The approximability of MaxEDP/MaxNDP is currently not well understood; the best known lower bound is 2(Omega(root log n)), assuming NP not subset of DTIME(n(O(log n))). This constitutes a significant gap to the best known approximation upper bound of O(root n) due to Chekuri et al. (Theo...
-
作者：Gottschalk, Corinna; Koster, Arie M. C. A.; Liers, Frauke; Peis, Britta; Schmand, Daniel; Wierz, Andreas
作者单位：RWTH Aachen University; RWTH Aachen University; University of Erlangen Nuremberg
摘要：We study dynamic network flows with uncertain input data under a robust optimization perspective. In the dynamic maximum flow problem, the goal is to maximize the flow reaching the sink within a given time horizon T, while flow requires a certain travel time to traverse an edge. In our setting, we account for uncertain travel times of flow. We investigate maximum flows over time under the assumption that at most travel times may be prolonged simultaneously due to delay. We develop and study a ...
-
作者：Freund, Robert M.; Lu, Haihao
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：Motivated by recent work of Renegar (A framework for applying subgradient methods to conic optimization problems, 2015) we present new computational methods and associated computational guarantees for solving convex optimization problems using first-order methods. Our problem of interest is the general convex optimization problem , where we presume knowledge of a strict lower bound . [Indeed, is naturally known when optimizing many loss functions in statistics and machine learning (least-squar...
-
作者：Dey, Santanu S.; Molinaro, Marco
作者单位：University System of Georgia; Georgia Institute of Technology; Pontificia Universidade Catolica do Rio de Janeiro
摘要：While many classes of cutting-planes are at the disposal of integer programming solvers, our scientific understanding is far from complete with regards to cutting-plane selection, i.e., the task of selecting a portfolio of cutting-planes to be added to the LP relaxation at a given node of the branch-and-bound tree. In this paper we review the different classes of cutting-planes available, known theoretical results about their relative strength, important issues pertaining to cut selection, and...
-
作者：Gribling, Sander; de Laat, David; Laurent, Monique
作者单位：Centrum Wiskunde & Informatica (CWI); Tilburg University
摘要：In this paper we study optimization problems related to bipartite quantum correlations using techniques from tracial noncommutative polynomial optimization. First we consider the problem of finding the minimal entanglement dimension of such correlations. We construct a hierarchy of semidefinite programming lower bounds and show convergence to a new parameter: the minimal average entanglement dimension, which measures the amount of entanglement needed to reproduce a quantum correlation when acc...
