2025

最新文章

• McCormick envelopes in mixed-integer PDE-constrained optimization AI翻译
  作者：Leyffer, Sven; Manns, Paul
  作者单位：United States Department of Energy (DOE); Argonne National Laboratory; Dortmund University of Technology
  摘要：McCormick envelopes are a standard tool for deriving convex relaxations of optimization problems that involve polynomial terms. Such McCormick relaxations provide lower bounds, for example, in branch-and-bound procedures for mixed-integer nonlinear programs but have not gained much attention in PDE-constrained optimization so far. This lack of attention may be due to the distributed nature of such problems, which on the one hand leads to infinitely many linear constraints (generally state cons...
• Optimal methods for convex nested stochastic composite optimization AI翻译
  作者：Zhang, Zhe; Lan, Guanghui
  作者单位：University System of Georgia; Georgia Institute of Technology
  摘要：Recently, convex nested stochastic composite optimization (NSCO) has received considerable interest for its applications in reinforcement learning and risk-averse optimization. However, existing NSCO algorithms have worse stochastic oracle complexities, by orders of magnitude, than those for simpler stochastic optimization problems without nested structures. Additionally, these algorithms require all outer-layer functions to be smooth, a condition violated by some important applications. This ...
• Convergence rates for sums-of-squares hierarchies with correlative sparsity AI翻译
  作者：Korda, Milan; Magron, Victor; Rios-Zertuche, Rodolfo
  作者单位：Centre National de la Recherche Scientifique (CNRS); Czech Technical University Prague; UiT The Arctic University of Tromso
  摘要：This work derives upper bounds on the convergence rate of the moment-sum-of-squares hierarchy with correlative sparsity for global minimization of polynomials on compact basic semialgebraic sets. The main conclusion is that both sparse hierarchies based on the Schmudgen and Putinar Positivstellensatze enjoy a polynomial rate of convergence that depends on the size of the largest clique in the sparsity graph but not on the ambient dimension. Interestingly, the sparse bounds outperform the best ...
• Fast Combinatorial Algorithms for Efficient Sortation AI翻译
  作者：Van Dyk, Madison; Klause, Kim; Koenemann, Jochen; Megow, Nicole
  作者单位：University of Bremen; University of Waterloo
  摘要：Modern parcel logistic networks are designed to ship demand between given origin, destination pairs of nodes in an underlying directed network. Efficiency dictates that volume needs to be consolidated at intermediate nodes in typical hub-and-spoke fashion. In practice, such consolidation requires parcel sortation. In this work, we propose a mathematical model for the physical requirements, and limitations of parcel sortation. We then show that it is NP-hard to determine whether a feasible sort...
• Online bipartite matching in the probe-commit model AI翻译
  作者：Borodin, Allan; Macrury, Calum
  作者单位：University of Toronto; Columbia University
  摘要：We consider the classical online bipartite matching problem in the probe-commit model. In this problem, when an online vertex arrives, its edges must be probed to determine if they exist, based on known edge probabilities. A probing algorithm must respect commitment, meaning that if a probed edge exists, it must be used in the matching. Additionally, each online vertex has a patience constraint which limits the number of probes that can be made to its adjacent edges. We introduce a new configu...
• On solving a rank regularized minimization problem via equivalent factorized column-sparse regularized models AI翻译
  作者：Li, Wenjing; Bian, Wei; Toh, Kim-Chuan
  作者单位：Harbin Institute of Technology; National University of Singapore
  摘要：Rank regularized minimization problem is an ideal model for the low-rank matrix completion/recovery problem. The matrix factorization approach can transform the high-dimensional rank regularized problem to a low-dimensional factorized column-sparse regularized problem. The latter can greatly facilitate fast computations in applicable algorithms, but needs to overcome the simultaneous non-convexity of the loss and regularization functions. In this paper, we consider the factorized column-sparse...
• Generalized scaling for the constrained maximum-entropy sampling problem AI翻译
  作者：Chen, Zhongzhu; Fampa, Marcia; Lee, Jon
  作者单位：University of Michigan System; University of Michigan; Universidade Federal do Rio de Janeiro
  摘要：The best practical techniques for exact solution of instances of the constrained maximum-entropy sampling problem, a discrete-optimization problem arising in the design of experiments, are via a branch-and-bound framework, working with a variety of concave continuous relaxations of the objective function. A standard and computationally-important bound-enhancement technique in this context is (ordinary) scaling, via a single positive parameter. Scaling adjusts the shape of continuous relaxation...
• Global optimization for cardinality-constrained minimum sum-of-squares clustering via semidefinite programming AI翻译
  作者：Piccialli, Veronica; Sudoso, Antonio M.
  作者单位：Sapienza University Rome
  摘要：The minimum sum-of-squares clustering (MSSC), or k-means type clustering, has been recently extended to exploit prior knowledge on the cardinality of each cluster. Such knowledge is used to increase performance as well as solution quality. In this paper, we propose a global optimization approach based on the branch-and-cut technique to solve the cardinality-constrained MSSC. For the lower bound routine, we use the semidefinite programming (SDP) relaxation recently proposed by Rujeerapaiboon et...
• Verification of first-order methods for parametric quadratic optimization AI翻译
  作者：Ranjan, Vinit; Stellato, Bartolomeo
  作者单位：Princeton University
  摘要：We introduce a numerical framework to verify the finite step convergence of first-order methods for parametric convex quadratic optimization. We formulate the verification problem as a mathematical optimization problem where we maximize a performance metric (e.g., fixed-point residual at the last iteration) subject to constraints representing proximal algorithm steps (e.g., linear system solutions, projections, or gradient steps). Our framework is highly modular because we encode a wide range ...
• Distributionally Risk-Receptive and Robust Multistage Stochastic Integer Programs and Interdiction Models AI翻译
  作者：Kang, Sumin; Bansal, Manish
  作者单位：Virginia Polytechnic Institute & State University
  摘要：In this paper, we study distributionally risk-receptive and distributionally robust (or risk-averse) multistage stochastic mixed-integer programs (denoted by DRR- and DRO-MSIPs). We present cutting plane-based and reformulation-based approaches for solving DRR- and DRO-MSIPs without and with decision-dependent uncertainty to optimality. We show that these approaches are finitely convergent with probability one. Furthermore, we introduce generalizations of DRR- and DRO-MSIPs by presenting multi...