-
作者：Chmiela, Antonia; Munoz, Gonzalo; Serrano, Felipe
作者单位：Zuse Institute Berlin; Universidad de Chile
摘要：Using the recently proposed maximal quadratic-free sets and the well-known monoidal strengthening procedure, we show how to improve intersection cuts for quadratically-constrained optimization problems by exploiting integrality requirements. We provide an explicit construction that allows an efficient implementation of the strengthened cuts along with computational results showing their improvements over the standard intersection cuts. We also show that, in our setting, there is unique lifting...
-
作者：Lin, Tianyi; Jordan, Michael I.
作者单位：Massachusetts Institute of Technology (MIT); University of California System; University of California Berkeley
摘要：This paper settles an open and challenging question pertaining to the design of simple and optimal high-order methods for solving smooth and monotone variational inequalities (VIs). A VI involves finding x ⋆is an element of X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x<^>\star \in {\mathcal {X}}$$\end{documen...
-
作者：Del Pia, Alberto
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
摘要：In binary polynomial optimization, the goal is to find a binary point maximizing a given polynomial function. In this paper, we propose a novel way of formulating this general optimization problem, which we call factorized binary polynomial optimization. In this formulation, we assume that the variables are partitioned into a fixed number of sets, and that the objective function is written as a sum of r products of linear functions, each one involving only variables in one set of the partition...
-
作者：Proenca, Nathan Benedetto; Silva, Marcel K. de Carli; Sato, Cristiane M.; Tuncel, Levent
作者单位：University of Waterloo; Universidade de Sao Paulo; Universidade Federal do ABC (UFABC)
摘要：We study a weighted generalization of the fractional cut-covering problem, which we relate to the maximum cut problem via antiblocker and gauge duality. This relationship allows us to introduce a semidefinite programming (SDP) relaxation whose solutions may be rounded into fractional cut covers by sampling via the random hyperplane technique. We then provide a 1/alpha GW\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackag...
-
作者：Hanguir, Oussama; Ma, Will; Han, Jiangze; Ryan, Christopher Thomas
作者单位：Columbia University; Columbia University; University of British Columbia
摘要：We consider the problem of designing a linear program that has diverse solutions as the right-hand side varies. This problem arises in video game settings where designers aim to have players use different weapons or tactics as they progress. We model this design question as a choice over the constraint matrix A and cost vector c to maximize the number of possible supports of unique optimal solutions (what we call loadouts) of Linear Programs max{c(inverted perpendicular)x|Ax <= b,x >= 0} with ...
-
作者：Matuschke, Jannik
作者单位：KU Leuven
摘要：Given a set system (E,P) with rho is an element of[0,1](E) and pi is an element of[0,1](P), our goal is to find a probability distribution for a random set S subset of E such that Pr[e is an element of S ]= rho e for all e is an element of E and Pr [P boolean AND S not equal empty set] >= pi P for all P is an element of P. We extend the results of Dahan, Amin, and Jaillet [6] who studied this problem motivated by a security game in a directed acyclic graph (DAG). We focus on the setting where ...
-
作者：Mohammadisiahroudi, Mohammadhossein; Augustino, Brandon; Sampourmahani, Pouya; Terlaky, Tamas
作者单位：Lehigh University
摘要：Iterative Refinement (IR) is a classical computing technique for obtaining highly precise solutions to linear systems of equations, as well as linear optimization problems. In this paper, motivated by the limited precision of quantum solvers, we develop the first IR scheme for solving semidefinite optimization (SDO) problems and explore two major impacts of the proposed IR scheme. First, we prove that the proposed IR scheme exhibits quadratic convergence of the optimality gap without any assum...
-
作者：Garatti, Simone; Campi, Marco C.
作者单位：Polytechnic University of Milan; University of Brescia
摘要：Scenario optimization is an approach to data-driven decision-making that has been introduced some fifteen years ago and has ever since then grown fast. Its most remarkable feature is that it blends the heuristic nature of data-driven methods with a rigorous theory that allows one to gain factual, reliable, insight in the solution. The usability of the scenario theory, however, has been restrained thus far by the obstacle that most results are standing on the assumption of convexity. With this ...
-
作者：Rudi, Alessandro; Marteau-Ferey, Ulysse; Bach, Francis
作者单位：Universite PSL; Ecole Normale Superieure (ENS); Inria
摘要：We consider the global minimization of smooth functions based solely on function evaluations. Algorithms that achieve the optimal number of function evaluations for a given precision level typically rely on explicitly constructing an approximation of the function which is then minimized with algorithms that have exponential running-time complexity. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum. This is done by using infinite s...
-
作者：Dvurechensky, Pavel; Staudigl, Mathias
作者单位：Leibniz Association; Weierstrass Institute for Applied Analysis & Stochastics; University of Mannheim
摘要：A key problem in mathematical imaging, signal processing and computational statistics is the minimization of non-convex objective functions that may be non-differentiable at the relative boundary of the feasible set. This paper proposes a new family of first- and second-order interior-point methods for non-convex optimization problems with linear and conic constraints, combining logarithmically homogeneous barriers with quadratic and cubic regularization respectively. Our approach is based on ...
