-
作者：Huang, Chien-Chung; Sellier, Francois
作者单位：Universite PSL; Centre National de la Recherche Scientifique (CNRS); Ecole Normale Superieure (ENS); Universite PSL; Ecole Normale Superieure (ENS); Universite PSL; MINES ParisTech
摘要：Matroid intersection is a classical optimization problem where given two matroids over the same ground set, the goal is to find the largest common independent set. In this paper, we show that there exists a certain sparsifer: a subset of elements of size O(|Sopt| 1/E), where Sopt denotes the optimal solution, that is guaranteed to contain a 3/2 + E approximation while guaranteeing certain robustness properties. We call such a small subset a density constrained subset, which is inspired by the ...
-
作者：Okuno, Takayuki
作者单位：Seikei University
摘要：We study properties of the central path underlying a nonlinear semidefinite optimization problem, called an NSDP for short. The latest radical work on this topic was contributed by Yamashita and Yabe [Yamashita H, Yabe H (2012) Local and superlinear convergence of a primal-dual interior point method for nonlinear semidefinite programming. Mathematical Programming 132(1-2):1-30]: they proved that the Jacobian of a certain equation system derived from the Karush-Kuhn-Tucker (KKT) conditions of t...
-
作者：Gaspard, Mallory E.; Vladimirsky, Alexander
作者单位：Cornell University; Cornell University
摘要：When traveling through a graph with an accessible deterministic path to a target, is it ever preferable to resort to stochastic node-to-node transitions instead? And, if so, what are the conditions guaranteeing that such a stochastic optimal routing policy can be computed efficiently? We aim to answer these questions here by defining a class of Opportunistically Stochastic Shortest Path (OSSP) problems and deriving sufficient conditions for applicability of noniterative label-setting methods. ...
-
作者：Jezequel, Remi; Ostrovskii, Dmitrii; Gaillard, Pierre
作者单位：Inria; Universite PSL; Ecole Normale Superieure (ENS); University System of Georgia; Georgia Institute of Technology; Centre National de la Recherche Scientifique (CNRS); Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); Inria; Institut National Polytechnique de Grenoble
摘要：In the problem of online portfolio selection as formulated by Cover [Cover TM (1991) Universal portfolios. Math. Finance 1(1):1-29], the trader repeatedly distributes the trader's capital over d assets in each of T > 1 rounds with the goal of maximizing the total return. Cover proposed an algorithm, termed universal portfolios, that performs nearly as well as the best (in hindsight) static assignment of a portfolio with an O(d log(T)) logarithmic regret. Without imposing any restrictions on th...
-
作者：Zhao, Renbo
作者单位：University of Iowa
摘要：We present and analyze an away-step Frank-Wolfe method for the convex optimization problem minx is an element of Xf(Ax) + < c , x > , where f is a theta-logarithmically homogeneous self-concordant barrier, A is a linear operator that may be noninvertible, < c , > is a linear function, and X is a nonempty polytope. The applications of primary interest include D-optimal design, inference of multivariate Hawkes processes, and total variationregularized Poisson image deblurring. We establish affin...
-
作者：Kim, Kyoung-Kuk; Kim, Taeho; Fu, Michael C.
作者单位：Korea Advanced Institute of Science & Technology (KAIST); Hong Kong University of Science & Technology; University System of Maryland; University of Maryland College Park; University System of Maryland; University of Maryland College Park
摘要：We consider the problem of estimating a multivariate distribution based on multiple data sources, which include both joint and marginal-only data. Specifically, we introduce a nonparametric approach called Ensemble Copula Coupling (ECC), which can be viewed as a data fusion approach that combines joint and marginal information. The particular setting of interest is input modeling for output analysis of simulated stochastic systems. We apply an ECC-based input model to address uncertainty quant...
-
作者：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); Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); Inria; Institut National Polytechnique de Grenoble; Centre National de la Recherche Scientifique (CNRS); Universite Cote d'Azur
摘要：We introduce the Morse parametric qualification condition for bilevel programming. Generic semialgebraic functions are Morse parametric in a piecewise sense. Thus, bilevel programs with a Morse parametric lower level constitute a relevant intermediate class between strongly convex and fully generic lower levels. In this framework, we study bilevel gradient algorithms with two strategies: the single-step multistep strategy, which involves a sequence of steps on the lower-level problems followed...
-
作者：Liang, Jiaxin (alys); Jasin, Stefanus; Uichanco, Joline
作者单位：McGill University; University of Michigan System; University of Michigan; New York University; New York University Tandon School of Engineering
摘要：This paper addresses operational challenges faced by retailers offering free return policies. We consider a general system with lost sales, positive lead time, periodic review, binomial demand, and an arbitrary restriction on price change frequency. We study the joint pricing and inventory decisions in the presence of stochastic returns. Specifically, when an item is purchased, it can be returned at a future random time and may be restocked for resale after passing an inspection. We assume a g...
-
作者：Fikioris, Giannis; Tardos, Eva
作者单位：Cornell University
摘要：Bandits with knapsacks (BwK), the generalization of the multiarmed bandits problem under global budget constraints, has received a lot of attention in recent years. It has numerous applications, including dynamic pricing, repeated auctions, ad allocation, network scheduling, etc. Previous work focuses on one of the two extremes: stochastic BwK in which the rewards and consumptions of the resources of each round are sampled from an independent and identical distribution and adversarial BwK in w...
-
作者：Chen, Tian; Nie, Tianyang; Wu, Zhen
作者单位：Shandong University; Shandong University
摘要：This paper investigates an indefinite linear-quadratic partially observed meanfield game with common noise, incorporating both state-average and control-average effects. In our model, each agent's state is observed through both individual and public observations, which are modeled as general stochastic processes rather than Brownian motions. It is noteworthy that the weighting matrices in the cost functional are allowed to be indefinite. We derive the optimal decentralized strategies using the...
