-
作者：Gupta, Akshita; Hunter, Susan R.
作者单位：Purdue University System; Purdue University
摘要：We consider a two-stage stochastic multi-objective linear program (TSSMOLP) that is a natural generalization of the well-studied two-stage stochastic linear program (TSSLP) allowing modelers to specify multiple objectives in each stage. The second-stage recourse decision is governed by an uncertain multi-objective linear program (MOLP) whose solution maps to an uncertain second-stage nondominated set. The TSSMOLP then comprises the objective, which is the Minkowski sum of a linear term plus th...
-
作者：Nutov, Zeev
作者单位：Open University Israel
摘要：A set family F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{F}$$\end{document} is uncrossable if A boolean AND B,A boolean OR B is an element of F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \u...
-
作者：Luo, Fengqiao; Dey, Shibshankar; Mehrotra, Sanjay
作者单位：Northwestern University
摘要：We present a finitely convergent cutting-plane algorithm for solving a general mixed-integer convex program given an oracle for solving a general convex program. This method is extended to solve a family of two-stage mixed-integer convex programs using cutting planes, with applications to solving distributionally-robust two-stage stochastic mixed-integer convex programs. Analysis is also given for the case where convex programming oracle provides an is an element of-optimal solution. We combin...
-
作者：Alacaoglu, Ahmet; Cevher, Volkan; Wright, Stephen J.
作者单位：University of British Columbia; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
摘要：We prove new complexity bounds for the primal-dual algorithm with random extrapolation and coordinate descent (PURE-CD), which has been shown to obtain promising practical performance for solving convex-concave min-max problems with bilinear coupling and dual separability. Such problems arise in many machine learning contexts, including empirical risk minimization, matrix games, and image processing. Our results either match or improve the best-known complexities of first-order algorithms for ...
-
作者：Zhang, Liang; He, Niao; Muehlebach, Michael
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Max Planck Society
摘要：Variational inequality problems are recognized for their broad applications across various fields including machine learning and operations research. First-order methods have emerged as the standard approach for solving these problems due to their simplicity and scalability. However, they typically rely on projection or linear minimization oracles to navigate the feasible set, which becomes computationally expensive in practical scenarios featuring multiple functional constraints. Existing eff...
-
作者：Nuti, Pranav; Vondrak, Jan
作者单位：Stanford University
摘要：In this paper, we study contention resolution schemes for matchings. Given a fractional matching x and a random set R(x) where each edge e appears independently with probability xe\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_e$$\end{document}, we want to select a matching M subset of R(x)\documentclass[12pt]{m...
-
作者：Liang, Jiaming
作者单位：University of Rochester; University of Rochester
摘要：This paper studies the primal-dual convergence and iteration-complexity of proximal bundle methods for solving nonsmooth problems with convex structures. More specifically, we develop a family of primal-dual proximal bundle methods for solving convex nonsmooth composite optimization problems and establish the iteration-complexity in terms of a primal-dual gap. We also propose a class of proximal bundle methods for solving convex-concave nonsmooth composite saddle-point problems and establish t...
-
作者：Jiang, Nan; Xie, Weijun
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：Distributionally Favorable Optimization (DFO) is a framework for decision-making under uncertainty, with applications spanning various fields, including reinforcement learning, online learning, robust statistics, chance-constrained programming, and two-stage stochastic optimization without complete recourse. In contrast to the traditional Distributionally Robust Optimization (DRO) paradigm, DFO presents a unique challenge- the application of the inner infimum operator often fails to retain the...
-
作者：Huang, Lei; Nie, Jiawang
作者单位：University of California System; University of California San Diego
摘要：This paper studies the matrix Moment-SOS hierarchy for solving polynomial matrix optimization. Our first result is to show the finite convergence of this hierarchy, if the nondegeneracy condition, strict complementarity condition and second order sufficient condition hold at every minimizer, under the Archimedean property. A useful criterion for detecting the finite convergence is the flat truncation. Our second result is to show that every minimizer of the moment relaxation must have a flat t...
-
作者：Vasquez, Sebastian; Lozano, Leonardo; Van Hoeve, Willem-Jan
作者单位：Carnegie Mellon University; University System of Ohio; University of Cincinnati
摘要：Binary bilevel programs are notoriously difficult to solve due to the absence of strong and efficiently computable relaxations. In this work, we introduce a novel single-level reformulation of these programs by leveraging a network flow-based representation of the follower's value function, utilizing decision diagrams and linear programming duality. This approach enables the development of scalable relaxations by applying it to a restricted solution set, which in turn provides dual bounds. We ...
