-
作者：Cifuentes, Diego; Dey, Santanu S.; Xu, Jingye
作者单位：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; El Housni, Omar; Brahim, Marouane Ibn; Lodi, Andrea; Segev, Danny
作者单位：University of California System; University of California Berkeley; Cornell University; Technion Israel Institute of Technology; 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. ...
-
作者：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...
-
作者：Del Pia, Alberto
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
摘要：In this paper we consider the problem of minimizing a general quadratic function over the mixed integer points in an ellipsoid. This problem is strongly NP-hard, NP-hard to approximate within a constant factor, and optimal solutions can be irrational. In our main result we show that an arbitrarily good solution can be found in polynomial time, if we fix the number of integer variables. This algorithm provides a natural extension to the mixed integer setting, of the polynomial solvability of th...
-
作者：Jiang, Nan; Xie, Weijun
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：This paper studies distributionally robust chance constrained programs (DRCCPs), where the uncertain constraints must be satisfied with at least a probability of a prespecified threshold for all probability distributions from the Wasserstein ambiguity set. As DRCCPs are often nonconvex and some DRCCPs may not have mixed-integer reformulations, researchers have been developing various convex inner approximations. Recently, ALSO-X has been proven to outperform the conditional value-at-risk (CVaR...
-
作者：Kobayashi, Yusuke
作者单位：Kyoto University
摘要：In the optimal general factor problem, given a graph G=(V,E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G=(V, E)$$\end{document} and a set B(v)subset of Z\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \...
-
作者：Cartis, Coralia; Zhu, Wenqi
作者单位：University of Oxford
摘要：There has been growing interest in high-order tensor methods for nonconvex optimization, with adaptive regularization, as they possess better/optimal worst-case evaluation complexity globally and faster convergence asymptotically. These algorithms crucially rely on repeatedly minimizing nonconvex multivariate Taylor-based polynomial sub-problems, at least locally. Finding efficient techniques for the solution of these sub-problems, beyond the second-order case, has been an open question. This ...
-
作者：Ghorbal, Khalil; Kozaily, Christelle
作者单位：Inria
摘要：This paper is concerned with a covering problem of Euclidean space by a particular arrangement of cones that are not necessarily full and are allowed to overlap. The problem provides an equivalent geometric reformulation of the solvability of the linear complementarity problem defining the class of Q-matrices. Assuming feasibility, we rely on standard tools from convex geometry to study maximal connected uncovered regions, we term holes. We then use our approach to fully characterize the probl...
-
作者：Grimmer, Benjamin; Li, Danlin
作者单位：Johns Hopkins University
摘要：We consider (stochastic) subgradient methods for strongly convex but potentially nonsmooth non-Lipschitz optimization. We provide new equivalent dual descriptions (in the style of dual averaging) for the classic subgradient method, the proximal subgradient method, and the switching subgradient method. These equivalences enable O(1/T) convergence guarantees in terms of both their classic primal gap and a not previously analyzed dual gap for strongly convex optimization. Consequently, our theory...
