-
作者：Bot, Radu I.; Chenchene, Enis; Csetnek, E. Robert; Hulett, David A.
作者单位：University of Vienna
摘要：We analyze fast diagonal methods for simple bilevel programs. Guided by the analysis of the corresponding continuous-time dynamics, under a mild general assumption we provide convergence rates for the inner residual and upper bounds for the outer residual along an ergodic sequence. As the key point of our work, under geometric assumptions for the inner function-namely, a weaker condition attributed to Attouch and Czarnecki and a stronger H & ouml;lderian error bound-we provide a unified conver...
-
作者：Yu, Xian; Basciftci, Beste
作者单位：University System of Ohio; Ohio State University; University of Iowa
摘要：We consider a two-stage distributionally robust optimization (DRO) model with multimodal uncertainty, where both the mode probabilities and uncertainty distributions could be affected by the first-stage decisions. To address this setting, we propose a generic framework by introducing a phi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69...
-
作者：Goodwin, Ariel; Lewis, Adrian S.; Lopez-Acedo, Genaro; Nicolae, Adriana
作者单位：Cornell University; Cornell University; Babes Bolyai University from Cluj
摘要：As a foundation for optimization, convexity is useful beyond the classical settings of Euclidean and Hilbert space. The broader arena of nonpositively curved metric spaces, which includes manifolds like hyperbolic space, as well as metric trees and more general CAT(0) cubical complexes, supports primal tools like proximal operations for geodesically convex functions. However, the lack of linear structure in such spaces complicates dual constructions like subgradients. To address this hurdle, w...
-
作者：Nagy, Marianna E.; Illes, Tibor; Nesterov, Yurii; Rigo, Petra Renata
作者单位：Corvinus University Budapest
摘要：We revisit the main principles for constructing polynomial-time primal-dual interior-point algorithms (IPAs). We investigate the weighted Linear Complementarity Problem (WLCP), by extending the framework of Parabolic Target Space (PTS), proposed by Nesterov (2008) for primal-dual Linear Programming (LP) Problems. This approach has several advantages. The proposed method based on the PTS approach starts from an arbitrary strictly feasible primal-dual pair and follows a single central path towar...
-
作者：Lu, Haihao; Yang, Jinwen
作者单位：Massachusetts Institute of Technology (MIT); University of Chicago
摘要：Convex quadratic programming (QP) is an important class of optimization problem with wide applications in practice. The classic QP solvers are based on either simplex or barrier method, both of which suffer from the scalability issue because their computational bottleneck is solving linear equations. In this paper, we design and analyze a first-order method for QP, called restarted accelerated primal-dual hybrid gradient (rAPDHG), whose computational bottleneck is matrix-vector multiplication....
-
作者：Blauth, Jannis; Klein, Nathan; Nagele, Martin
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Boston University
摘要：Prize-Collecting TSP is a variant of the traveling salesperson problem where one may drop vertices from the tour at the cost of vertex-dependent penalties. The quality of a solution is then measured by adding the length of the tour and the sum of all penalties of vertices that are not visited. We present a polynomial-time approximation algorithm with an approximation guarantee slightly below 1.6, where the guarantee is with respect to the natural linear programming relaxation of the problem. T...
-
作者：Bolte, Jerome; Le, Quoc-Tung; Pauwels, Edouard; Vaiter, Samuel
作者单位：Communaute d'universites et etablissements de Toulouse (Comue); Universite Toulouse 1 Capitole; Toulouse School of Economics; Centre National de la Recherche Scientifique (CNRS); Universite Cote d'Azur; Universite Cote d'Azur
摘要：We first show a simple but striking result in bilevel optimization: unconstrained C infinity\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C<^>\infty $$\end{document} smooth bilevel programming is as hard as general extended-real-valued lower semicontinuous minimization. We then proceed to a worst-case analysis of...
-
作者：Lindner, Niels; Masing, Berenike
作者单位：Free University of Berlin; Zuse Institute Berlin
摘要：The Periodic Event Scheduling Problem (PESP) is the central mathematical tool for periodic timetable optimization in public transport. PESP can be formulated in several ways as a mixed-integer linear program with typically general integer variables. We investigate the split closure of these formulations and show that split inequalities are identical with the recently introduced flip inequalities. While split inequalities are a general mixed-integer programming technique, flip inequalities are ...
-
作者：Dzahini, K. J.; Wild, S. M.
作者单位：United States Department of Energy (DOE); Argonne National Laboratory; United States Department of Energy (DOE); Lawrence Berkeley National Laboratory
摘要：Stochastic directional direct-search (SDDS) algorithms were recently introduced as an extension to stochastically noisy objectives of a broad class of algorithms including the well-known mesh adaptive direct-search (MADS) algorithms developed for the minimization of deterministic functions in a blackbox optimization framework. However, since SDDS methods explore the variable space via directions selected at each iteration from search sets of cardinality depending on the problem dimension, thei...
-
作者：Capelli, Florent; Del Pia, Alberto; Di Gregorio, Silvia
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite d'Artois; CNRS - Institute for Information Sciences & Technologies (INS2I); University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; Universite Paris 13; Centre National de la Recherche Scientifique (CNRS)
摘要：In Binary Polynomial Optimization (BPO), the goal is to find a binary point maximizing a given polynomial function. In this paper, we establish a novel connection between BPO and restricted Boolean circuits from the field of knowledge compilation, enabling us to both unify and significantly extend the state-of-the-art for BPO. Leveraging this connection, we identify a new tractable class of BPO instances: those whose associated hypergraphs have bounded incidence treewidth. This is a significan...
