-
作者：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 ...
-
作者：Dubey, Yatharth; Liu, Siyue
作者单位：Amazon.com; Carnegie Mellon University
摘要：In this note, we study the size of the support of integer solutions to linear equations Ax = b, x is an element of Z(n )where A is an element of Z(mxn), b is an element of Z(n). We give an upper bound on the smallest support size as a function of A, taken as a worst case over all b such that the above system has a solution. This bound is asymptotically tight, and in fact matches the bound given in [1], while the proof presented here is simpler, relying only on linear algebra.
-
作者：Wirth, Elias; Pena, Javier; Pokutta, Sebastian
作者单位：Technical University of Berlin; Carnegie Mellon University
摘要：Recent papers have shown that the Frank-Wolfe algorithm (FW) with open-loop step-sizes exhibits rates of convergence faster than the iconic O(t-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(t<^>{-1})$$\end{document} rate. In particular, when the minimizer of a strongly convex function over a polyto...
-
作者：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...
-
作者：Leconte, Geoffroy; Orban, Dominique
作者单位：Universite de Montreal; Polytechnique Montreal; Universite de Montreal; Polytechnique Montreal
摘要：We develop a worst-case evaluation complexity bound for trust-region methods in the presence of unbounded Hessian approximations. We use the algorithm of Aravkin et al. (SIAM J Optim 32(2):900-929, 2022) as a model, which is designed for nonsmooth regularized problems, but applies to unconstrained smooth problems as a special case. Our analysis assumes that the growth of the Hessian approximation is controlled by the number of successful iterations. We show that the best known complexity bound...
-
作者：Lan, Guanghui; Li, Yan
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：This paper presents a proximal-point-based catalyst scheme for simple first-order methods applied to convex minimization and convex-concave minimax problems. In particular, for smooth and (strongly)-convex minimization problems, the proposed catalyst scheme, instantiated with a simple variant of stochastic gradient method, attains the optimal rate of convergence in terms of both deterministic and stochastic errors. For smooth and strongly-convex-strongly-concave minimax problems, the catalyst ...
-
作者：Gan, Jiarui; Han, Minbiao; Wu, Jibang; Xu, Haifeng
作者单位：University of Oxford; University of Chicago
摘要：This paper provides a systematic study of the robust Stackelberg equilibrium (RSE), which naturally extends the widely adopted solution concept of the strong Stackelberg equilibrium (SSE). The RSE accounts for any possible up-to-delta\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta $$\end{document} suboptimal...
-
作者：Zhang, Penghe; Xiu, Naihua; Qi, Houduo
作者单位：Hong Kong Polytechnic University; Beijing Jiaotong University; Hong Kong Polytechnic University; Hong Kong Polytechnic University
摘要：Indicator functions of taking values of zero or one are essential to numerous applications in machine learning and statistics. The corresponding primal optimization model has been researched in several recent works. However, its dual problem is a more challenging topic that has not been well addressed. One possible reason is that the Fenchel conjugate of any indicator function is finite only at the origin. This work aims to explore the dual optimization for the sum of a strongly convex functio...
-
作者：Kurtz, Jannis
作者单位：University of Amsterdam
摘要：In the realm of robust optimization the k-adaptability approach is one promising method to derive approximate solutions for two-stage robust optimization problems. Instead of allowing all possible second-stage decisions, the k-adaptability approach aims at calculating a limited set of k such decisions already in the first-stage before the uncertainty is revealed. The parameter k can be adjusted to control the quality of the approximation. However, not much is known on how many solutions k are ...
