-
作者：Tran, Hoang Anh; Toh, Kim-Chuan
作者单位：National University of Singapore; National University of Singapore
摘要：The moment-SOS hierarchy, which is based on Putinar-type (quadratic module) and Schm & uuml;dgen-type (preordering) sum-of-squares positivity certificates, is a widely applicable framework to address polynomial optimization problems over basic semi-algebraic sets. Recent works show that the convergence rate of this hierarchy over certain simple sets, namely, the unit ball, hypercube, and standard simplex, is of the order O(1/r2) , where r denotes the level of the moment-SOS hierarchy. This pap...
-
作者：Monteiro, Renato D. C.; Sujanani, Arnesh; Cifuentes, Diego
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：This paper introduces HALLaR, a new first-order method for solving large-scale semidefinite programs (SDPs) with bounded domain. HALLaR is an inexact augmented Lagrangian (AL) method where the AL subproblems are solved by a hybrid low-rank (HLR) method. The recipe behind HLR is based on two key ingredients: 1) an adaptive inexact proximal point method with inner acceleration; 2) Frank-Wolfe steps to escape from spurious local stationary points. In contrast to the low-rank method of Burer and M...
-
作者：Borst, Sander; Kashaev, Danish; Koh, Zhuan Khye
作者单位：Max Planck Society; Boston University
摘要：The online matching problem was introduced by Karp, Vazirani and Vazirani (STOC 1990) on bipartite graphs with vertex arrivals. It is well-known that the optimal competitive ratio is 1-1/e\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1-1/e$$\end{document} for both integral and fractional versions of the problem. ...
-
作者：Liu, Hongcheng; Tong, Jindong
作者单位：State University System of Florida; University of Florida
摘要：This paper studies sample average approximation (SAA) in solving convex or strongly convex stochastic programming (SP) problems. In estimating SAA's sample efficiency, the state-of-the-art sample complexity bounds entail metric entropy terms (such as the logarithm of the feasible region's covering number), which often grow polynomially with problem dimensionality. While it has been shown that metric entropy-free complexity rates are attainable under a uniform Lipschitz condition, such an assum...
-
作者：Warme, David M.
摘要：We study the notion of strength of inequalities used in integer and mixed-integer programming, and the branch-and-cut algorithms used to solve such problems. Strength is an ethereal property lacking any good formal definition, but crucially affects speed of computations. We review several quantitative indicators proposed in the literature that we claim provide a measure of the relative strength of inequalities with respect to a given polyhedron. We evaluate two of these indicators (extreme poi...
-
作者：Lasserre, Jean B.
作者单位：Centre National de la Recherche Scientifique (CNRS); Communaute d'universites et etablissements de Toulouse (Comue); Universite Toulouse 1 Capitole; Toulouse School of Economics
摘要：Given two measures mu,nu\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mu ,\nu $$\end{document} on Rd\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \...
-
作者：Kilinc-Karzan, Fatma; Sun, Shengding
作者单位：Carnegie Mellon University; University of Cambridge
摘要：We study quadratic programs with m ball constraints, and the strength of a lifted convex relaxation for it recently proposed by Burer (2024). Burer shows this relaxation is exact when m=2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m=2$$\end{document}. For general m, Burer (2024) provides numerical evidence that...
-
作者：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...
-
作者：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...
-
作者：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. ...
