2026

最新文章

• 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...
• Sensor network localization has a benign landscape after low-dimensional relaxation AI翻译
  作者：Criscitiello, Christopher; McRae, Andrew D.; Rebjock, Quentin; Boumal, Nicolas
  作者单位：University of Pennsylvania; Institut Polytechnique de Paris; Centre National de la Recherche Scientifique (CNRS); Ecole Nationale des Ponts et Chaussees; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
  摘要：We consider the sensor network localization problem, which is closely related to multidimensional scaling and Euclidean distance matrix completion. Given a ground truth configuration of n points in R-& ell;, we observe a subset of the pairwise distances and aim to recover the underlying configuration (up to rigid transformations). We show with a simple counterexample that the associated optimization problem is nonconvex and may admit spurious local minimizers, even when all distances are known...
• Exact worst-case convergence rates of gradient descent: a complete analysis for all constant stepsizes over nonconvex and convex functions AI翻译
  作者：Rotaru, Teodor; Glineur, Francois; Patrinos, Panagiotis
  作者单位：KU Leuven; Universite Catholique Louvain
  摘要：We consider gradient descent with constant stepsizes and derive exact worst-case convergence rates on the minimum gradient norm of the iterates. Our analysis covers all possible stepsizes and arbitrary upper/lower bounds on the curvature of the objective function, thus including convex, strongly convex and weakly convex (hypoconvex) objective functions. Among the challenging parts of the analysis, we note the necessity to exploit dependencies between non-consecutive iterates. While this compli...
• An exact penalty approach for equality constrained optimization over a convex set AI翻译
  作者：Xiao, Nachuan; Tang, Tianyun; Wang, Shiwei; Toh, Kim-Chuan
  作者单位：The Chinese University of Hong Kong, Shenzhen; University of Chicago; Chinese Academy of Sciences; National University of Singapore; National University of Singapore
  摘要：In this paper, we consider the nonlinear constrained optimization problem (NCP) with a constraint set 1C := {x is an element of X : c(x) = 0}, where X is a closed convex subset of Rn. We propose an exact penalty approach, named constraint dissolving approach, that transforms (NCP) into its corresponding constraint dissolving problem (CDP). The transformed problem (CDP) admits X as its feasible region with a locally Lipschitz smooth objective function. We prove that (NCP) and (CDP) share the sa...
• A Randomized Linearly Convergent Frank-Wolfe-type Method for Smooth Convex Minimization over the Spectrahedron AI翻译
  作者：Garber, Dan
  作者单位：Technion Israel Institute of Technology
  摘要：We consider the problem of minimizing a smooth and convex function over the n-dimensional spectrahedron - the set of real symmetric n & times;n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n imes n$$\end{document} positive semidefinite matrices with unit trace, which underlies numerous applications in statistics,...
• 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...