1-2期

最新文章

• New finite relaxation hierarchies for concavo-convex, disjoint bilinear programs, and facial disjunctions AI翻译
  作者：Tawarmalani, Mohit
  作者单位：Purdue University System; Purdue University
  摘要：This paper introduces novel relaxation hierarchies for concavo-convex programs (CXP), a class of problems that includes disjoint bilinear programming (DBP) and concave minimization (CM) as special cases. At the core of these hierarchies is an algorithm based on double-description (DD) that computes the barycentric coordinates of a polyhedral cone as rational, non-negative functions representing multipliers associated with the cone's rays. These hierarchies combine geometric structure derived f...
• Sensitivity analysis for mixed binary quadratic programming AI翻译
  作者：Cifuentes, Diego; Dey, Santanu S.; Xu, Jingye
  作者单位：Georgia Institute of Technology; University System of Georgia; Georgia Institute of Technology
  摘要：We consider sensitivity analysis for Mixed Binary Quadratic Programs (MBQPs) with respect to changing right-hand-sides (rhs). We show that even if the optimal solution of a given MBQP is known, it is NP-hard to approximate the change in objective function value with respect to changes in rhs. Next, we study algorithmic approaches to obtaining dual bounds for MBQP with changing rhs. We leverage Burer's completely-positive (CPP) reformulation of MBQPs. Its dual is an instance of co-positive prog...
• P-split formulations: a class of intermediate formulations between big-M and convex hull for disjunctive constraints AI翻译
  作者：Kronqvist, Jan; Misener, Ruth; Tsay, Calvin
  作者单位：Royal Institute of Technology; Imperial College London
  摘要：We develop a class of mixed-integer formulations for disjunctive constraints intermediate to the big-M and convex hull formulations in terms of relaxation strength. The main idea is to capture the best of both the big-M and convex hull formulations: a computationally light formulation with a tight relaxation. The P-split formulations are based on a lifted transformation that splits convex additively separable constraints into P partitions and forms the convex hull of the linearized and partiti...
• Assortment optimization with visibility constraints AI翻译
  作者：Barre, Theo; Housni, Omar El; Brahim, Marouane Ibn; Lodi, Andrea; Segev, Danny
  作者单位：University of California Berkeley; University of California System; University of California Berkeley; Cornell University; Tel Aviv University; Tel Aviv University
  摘要：Motivated by applications in e-retail and online advertising, we study the problem of assortment optimization under visibility constraints (APV). Here, we are given a universe of substitutable products and a stream of customers. The objective is to determine the optimal assortment of products to offer to each customer in order to maximize the total expected revenue, subject to exogenously-given visibility constraints, stating that each product should be shown to a minimum number of customers. ...
• Adjustable robust nonlinear network design without controllable elements under load scenario uncertainties AI翻译
  作者：Thuerauf, Johannes; Gruebel, Julia; Schmidt, Martin
  作者单位：Universitat Trier
  摘要：We study network design problems for nonlinear and nonconvex flow models without controllable elements under load scenario uncertainties, i.e., under uncertain injections and withdrawals. To this end, we apply the concept of adjustable robust optimization to compute a network design that admits a feasible transport for all, possibly infinitely many, load scenarios within a given uncertainty set. For solving the corresponding adjustable robust mixed-integer nonlinear optimization problem, we sh...
• Factorized binary polynomial optimization AI翻译
  作者：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...
• A primal-dual extension of the Goemans-Williamson algorithm for the weighted fractional cut-covering problem AI翻译
  作者：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...
• Quantum computing inspired iterative refinement for semidefinite optimization AI翻译
  作者：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...
• Frank-Wolfe meets Shapley-Folkman: a systematic approach for solving nonconvex separable problems with linear constraints AI翻译
  作者：Dubois-Taine, Benjamin; d'Aspremont, Alexandre
  作者单位：Centre National de la Recherche Scientifique (CNRS); Universite PSL; Ecole Normale Superieure (ENS)
  摘要：We consider separable nonconvex optimization problems under affine constraints. For these problems, the Shapley-Folkman theorem provides an upper bound on the duality gap as a function of the nonconvexity of the objective functions, but does not provide a systematic way to construct primal solutions satisfying that bound. In this work, we develop a two-stage approach to do so. The first stage approximates the optimal dual value with a large set of primal feasible solutions. In the second stage...
• Globally convergent derivative-free methods in nonconvex optimization with and without noise AI翻译
  作者：Khanh, Pham Duy; Mordukhovich, Boris S.; Tran, Dat Ba
  作者单位：Wayne State University
  摘要：This paper addresses the study of nonconvex derivative-free optimization problems, where only information of either smooth objective functions or their noisy approximations is available. General derivative-free methods are proposed for minimizing differentiable (not necessarily convex) functions with globally Lipschitz continuous gradients, where the accuracy of approximate gradients is interacting with stepsizes and exact gradient values. Analysis in the noiseless case guarantees convergence ...