-
作者：Chen, Yiwen; Hare, Warren; Jarry-Bolduc, Gabriel
作者单位：University of British Columbia
摘要：Model-based methods are popular in derivative-free optimization (DFO). In most of them, a single model function is built to approximate the objective function. This is generally based on the assumption that the objective function is one black box. However, some real-life and theoretical problems show that the objective function may consist of sev-eral black boxes. In those problems, the information provided by each black box may not be equal. In this situation, one can build multiple submodels...
-
作者：Zhou, Junpeng; Zhang, Na; Li, Qia
作者单位：Sun Yat Sen University; South China Agricultural University; Sun Yat Sen University
摘要：We consider a class of structured fractional programs, where the numerator is the sum of a block-separable (possibly nonsmooth nonconvex) function and a locally Lipschitz differentiable (possibly nonconvex) function, and the denominator is a convex (possibly nonsmooth) function. We first present a novel reformulation for the original problem and show the relationship of their optimal solutions, critical points, and Kurdyka & Lstrok;ojasiewicz (KL) exponents. Inspired by the reformulation, we p...
-
作者：Naegele, Martin; Zenklusen, Rico
作者单位：University of Bonn; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：Short spanning trees subject to additional constraints are important building blocks in various approximation algorithms, and moreover, they capture interesting problem settings on their own. Especially in the context of the traveling salesman problem (TSP), new techniques for finding spanning trees with well-defined properties have been crucial in recent progress. We consider the problem of finding a spanning tree subject to constraints on the edges in a family of cuts forming a laminar famil...
-
作者：Biro, Peter; Klijn, Flip; Klimentova, Xenia; Viana, Ana
作者单位：Corvinus University Budapest; Consejo Superior de Investigaciones Cientificas (CSIC); Barcelona School of Economics; INESC TEC; Instituto Politecnico do Porto
摘要：In a housing market of Shapley and Scarf, each agent is endowed with one indivisible object and has preferences over all objects. An allocation of the objects is in the (strong) core if there exists no (weakly) blocking coalition. We show that, for strict preferences, the unique strong core allocation respects improvement-if an agent's object becomes more desirable for some other agents, then the agent's allotment in the unique strong core allocation weakly improves. We extend this result to w...
-
作者：Baldwin, Elizabeth; Goldberg, Paul W.; Klemperer, Paul; Lock, Edwin
作者单位：University of Oxford; University of Oxford
摘要：This paper develops algorithms to solve strong-substitutes product-mix auctions: it finds competitive equilibrium prices and quantities for agents who use this auction's bidding language to truthfully express their strong-substitutes preferences over an arbitrary number of goods, each of which is available in multiple discrete units. Our use of the bidding language and the information it provides contrasts with existing algorithms that rely on access to a valuation or demand oracle. We compute...
-
作者：Daw, Andrew
作者单位：University of Southern California
摘要：Classic results show that the Hawkes self-exciting point process can be viewed as a collection of temporal clusters, in which exogenously generated initial events give rise to endogenously driven descendant events. This perspective provides the distribution of a cluster's size through a natural connection to branching processes, but this is irrespective of time. Insight into the chronology of a Hawkes process cluster has been much more elusive. Here, we employ this cluster perspective and a no...
-
作者：Attouch, Hedy; Bot, Radu Ioan; Nguyen, Dang-Khoa
作者单位：Universite de Montpellier; Centre National de la Recherche Scientifique (CNRS); University of Vienna; Vietnam National University Ho Chi Minh City (VNUHCM) System
摘要：In a Hilbert setting, we develop a gradient-based dynamic approach for fast solving convex optimization problems. By applying time scaling, averaging, and perturbation techniques to the continuous steepest descent (SD), we obtain high-resolution ordinary differential equations of the Nesterov and Ravine methods. These dynamics involve asymptotically vanishing viscous damping and Hessian-driven damping (either in explicit or implicit form). Mathematical analysis does not require developing a Ly...
-
作者：Milz, Johannes; Surowiec, Thomas M.
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：Optimal values and solutions of empirical approximations of stochastic optimization problems can be viewed as statistical estimators of their true values. From this perspective, it is important to understand the asymptotic behavior of these estimators as the sample size goes to infinity. This area of study has a long tradition in stochastic programming. However, the literature is lacking consistency analysis for problems in which the decision variables are taken from an infinite-dimensional sp...
-
作者：Ezra, Tomer; Feldman, Michal; Gravin, Nikolai; Tang, Zhihao (Gavin)
作者单位：Harvard University; Tel Aviv University; Microsoft; MICROSOFT ISRAEL; Shanghai University of Finance & Economics
摘要：Online algorithms for secretary matching in bipartite weighted graphs have been studied extensively in recent years. We generalize this study to secretary matching in general weighted graphs. In our model, vertices arrive online in a uniformly random order; upon the arrival of a vertex v , the weights of edges from v to all previously arriving vertices are revealed, and the algorithm decides which of these edges, if any, to include in the matching. We provide a tight 5/12-competitive algorithm...
-
作者：Na, Sen; Anitescu, Mihai; Kolar, Mladen
作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley; United States Department of Energy (DOE); Argonne National Laboratory; University of Chicago
摘要：We propose a fast temporal decomposition procedure for solving long -horizon nonlinear dynamic programs. The core of the procedure is sequential quadratic programming (SQP) that utilizes a differentiable exact augmented Lagrangian as the merit function. Within each SQP iteration, we approximately solve the Newton system using an overlapping temporal decomposition strategy. We show that the approximate search direction is still a descent direction of the augmented Lagrangian provided the overla...
