Mathematics of Operations Research

最新文章

• Robust Faber-Schauder Approximation Based on Discrete Observations of an Antiderivative AI翻译
  作者：Han, Xiyue; Schied, Alexander
  作者单位：University of Waterloo
  摘要：We study the problem of reconstructing the Faber-Schauder coefficients of a continuous functionf from discrete observations of its antiderivative F. For instance, this question arises in financial mathematics when estimating the roughness of volatility from the integrated volatility of an asset price trajectory. Our approach starts with mathematically formulating the reconstruction problem through piecewise quadratic spline interpolation. We then provide a closed-form solution and an in-depth ...
• SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization AI翻译
  作者：Kurpisz, Adam; Potechin, Aaron; Wirth, Elias
  作者单位：ETH Zurich; Swiss Federal Institutes of Technology Domain; ETH Zurich; University of Chicago; Technical University of Berlin
  摘要：We introduce several methods to study the rank of the sum of squares (SoS) hierarchy for problems over the Boolean hypercube. We apply our techniques to improve upon existing results, thus answering several open questions. We answer the question by Laurent regarding the SoS rank of the empty integral hull (EIH) problem. We prove that the SoS rank is between inverted right perpendicularn/2inverted left perpendicular and inverted right perpendicularn/2+ root n log 2ninverted left perpendicular. ...
• Mirror Descent Algorithms for Risk Budgeting Portfolios AI翻译
  作者：Iglesias, Martin Amaiz; Cetingoz, Adil Rengim; Frikha, Noufel
  摘要：This paper introduces and examines numerical approximation schemes for computing risk budgeting portfolios associated to positive homogeneous and subadditive risk measures. We employ mirror descent algorithms to determine the optimal risk budgeting weights in both deterministic and stochastic settings, establishing convergence along with an explicit nonasymptotic quantitative rate for the averaged algorithm. A comprehensive numerical analysis follows, illustrating our theoretical findings acro...
• Theoretical Smoothing Frameworks for Nonsmooth Simple Bilevel Problems AI翻译
  作者：Alcantara, Jan Harold; Takeda, Akiko
  作者单位：RIKEN; University of Tokyo
  摘要：Bilevel programming has recently received a great deal of attention because of its abundant applications in many areas. We study a class of bilevel problems in which the lower-level feasible set is independent of the upper-level variables. The optimal value function approach provides a useful reformulation of the bilevel problem, but its utility is often limited because of the nonsmoothness of the value function even in cases when the associated lower-level function is smooth. In this paper, w...
• Greedy Adversarial Equilibrium: An Efficient Alternative to Nonconvex-Nonconcave Min-Max Optimization AI翻译
  作者：Mangoubi, Oren; Vishnoi, Nisheeth K.
  作者单位：Worcester Polytechnic Institute; Yale University
  摘要：Min-max optimization of a function f from Rd x Rd to R is an important framework for modeling robustness in adversarial settings with applications to optimization, economics, and deep learning. Oftentimes, f is nonconvex-nonconcave, and finding a global min-max point is computationally intractable. There is a long line of work that seeks computationally tractable algorithms for alternatives to the min-max optimization formulation. However, many of these alternative solution concepts guarantee ...
• Newton-CG Methods for Nonconvex Unconstrained Optimization with Holder Continuous Hessian AI翻译
  作者：He, Chuan; Huang, Heng; Lu, Zhaosong
  作者单位：Linkoping University; University System of Maryland; University of Maryland College Park; University of Minnesota System; University of Minnesota Twin Cities
  摘要：In this paper, we consider a nonconvex unconstrained optimization problem minimizing a twice differentiable objective function with Holder continuous Hessian. Specifically, we first propose a Newton-conjugate gradient (Newton-CG) method for finding an approximate firstand second-order stationary point of this problem, assuming the associated Holder parameters are explicitly known. Then, we develop a parameter-free Newton-CG method without requiring any prior knowledge of these parameters. To t...
• Uniform Moment Bounds for Generalized Jackson Networks in Multiscale Heavy Traffic AI翻译
  作者：Guang, Jin; Chen, Xinyun; Dai, J. G.
  作者单位：The Chinese University of Hong Kong, Shenzhen; Cornell University
  摘要：We establish uniform moment bounds for steady-state queue lengths of generalized Jackson networks (GJNs) in multiscale heavy traffic as recently proposed by Dai et al. in 2023. Uniform moment bounds lay the foundation for further analysis of the limit stationary distribution. Our result can be used to verify the crucial moment state space collapse (SSC) assumption in Dai et al. in 2023 to establish a product-form limit of GJN in the multiscale heavy traffic regime. Our proof critically utilize...
• Mode Connectivity in Auction Design AI翻译
  作者：Hertrich, Christoph; Tao, Yixin; Vegh, Laszlo A.
  作者单位：Shanghai University of Finance & Economics; University of Bonn
  摘要：Optimal auction design is a fundamental problem in algorithmic game theory. This problem is notoriously difficult already in very simple settings. Recent work in differentiable economics showed that neural networks can efficiently learn known optimal auction mechanisms and discover interesting new ones. In an attempt to theoretically justify their empirical success, we focus on one of the first such networks, RochetNet, and a generalized version for affine maximizer auctions. We prove that the...
• The IID Prophet Inequality with Limited Flexibility AI翻译
  作者：Perez-Salazar, Sebastian; Singh, Mohit; Toriello, Alejandro
  作者单位：Rice University; University System of Georgia; Georgia Institute of Technology
  摘要：In online sales, sellers usually offer each potential buyer a posted price in a takeit-or-leave fashion. Buyers can sometimes see posted prices faced by other buyers, and changing the price frequently could be considered unfair. The literature on posted-price mechanisms and prophet inequality problems has studied the two extremes of pricing policies, the fixed-price policy and fully dynamic pricing. The former is suboptimal in revenue but is perceived as fairer than the latter. This work exami...
• Relaxations for Binary Polynomial Optimization via Signed Certificates AI翻译
  作者：Xu, Liding; Liberti, Leo
  作者单位：Zuse Institute Berlin; Centre National de la Recherche Scientifique (CNRS); Institut Polytechnique de Paris; Ecole Polytechnique
  摘要：We consider the problem of minimizing a polynomial f over the (binary) hyper-cube. We show that, for a specific set of polynomials, their binary nonnegativity (i.e., on the hypercube) can be checked in polynomial time via minimum cut algorithms, from which we construct a linear programming representation for this set of polynomials. We categorize binary polynomials according to their signed support patterns and develop parameterized linear programming representations for binary nonnegative pol...