-
作者：Ghorbal, Khalil; Kozaily, Christelle
作者单位：Universite de Rennes; Inria
摘要：This paper is concerned with a covering problem of Euclidean space by a particular arrangement of cones that are not necessarily full and are allowed to overlap. The problem provides an equivalent geometric reformulation of the solvability of the linear complementarity problem defining the class of Q-matrices. Assuming feasibility, we rely on standard tools from convex geometry to study maximal connected uncovered regions, we term holes. We then use our approach to fully characterize the probl...
-
作者：Grimmer, Benjamin; Li, Danlin
作者单位：Johns Hopkins University
摘要：We consider (stochastic) subgradient methods for strongly convex but potentially nonsmooth non-Lipschitz optimization. We provide new equivalent dual descriptions (in the style of dual averaging) for the classic subgradient method, the proximal subgradient method, and the switching subgradient method. These equivalences enable O(1/T) convergence guarantees in terms of both their classic primal gap and a not previously analyzed dual gap for strongly convex optimization. Consequently, our theory...
-
作者：Benedek, Marton; Biro, Peter; Kern, Walter; Palvolgyi, Domotor; Paulusma, Daniel
作者单位：Corvinus University Budapest; University of Twente; Eotvos Lorand University; Durham University
摘要：We introduce partitioned matching games as a suitable model for international kidney exchange programmes, where in each round the total number of available kidney transplants needs to be distributed amongst the participating countries in a fair way. A partitioned matching game (N, v) is defined on a graph G = (V, E) with an edge weighting w and a partition V = V-1 boolean OR center dot center dot center dot boolean OR V-n. The player set is N = {1,..., n}, and player p is an element of N owns ...
-
作者：Santiago, Richard; Sergeev, Ivan; Zenklusen, Rico
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：The Matroid Secretary Conjecture is a notorious open problem in online optimization. It claims the existence of an O(1)-competitive algorithm for the Matroid Secretary Problem (MSP). Here, the elements of a weighted matroid appear one-by-one, revealing their weight at appearance, and the task is to select elements online with the goal to get an independent set of largest possible weight. O(1)-competitive MSP algorithms have so far only been obtained for restricted matroid classes and for MSP v...
-
作者：Kim, Do Sang; Nguyen, Minh Tung; Pham, Tien-Son
作者单位：Pukyong National University; Ho Chi Minh University of Banking (HUB); Dalat University
摘要：In this work, the notions of normal cones at infinity to unbounded sets and limiting and singular subdifferentials at infinity for extended real value functions are introduced. Various calculus rules for these notions are established. A complete characterization of the Lipschitz continuity at infinity for lower semicontinuous functions is given. The obtained results are aimed ultimately at applications to diverse problems of optimization, such as optimality conditions, coercive properties, wea...
-
作者：Toint, Philippe L.
作者单位：University of Namur
摘要：The adaptive regularization algorithm for unconstrained nonconvex optimization was shown in [7, 20] to require, under standard assumptions, at most O(& varepsilon;(3/(3-q))) evaluations of the objective function and its derivatives of degrees one and two to produce an & varepsilon;-approximate critical point of order q is an element of{1,2}. This bound was shown to be sharp in [5, 6] for q=1 and in [11] for arbitrary q is an element of{1,2}. This note revisits these results and shows that the ...
-
作者：Kazachkov, Aleksandr M.; Balas, Egon
作者单位：State University System of Florida; University of Florida; Carnegie Mellon University
摘要：Disjunctive cutting planes can tighten a relaxation of a mixed-integer linear program. Traditionally, such cuts are obtained by solving a higher-dimensional linear program, whose additional variables cause the procedure to be computationally prohibitive. Adopting a nu-polyhedral perspective is a practical alternative that enables the separation of disjunctive cuts via a linear program with only as many variables as the original problem. The drawback is that the classical approach of monoidal s...
-
作者：Li, Yan; Shapiro, Alexander
作者单位：Texas A&M University System; Texas A&M University College Station; University System of Georgia; Georgia Institute of Technology
摘要：The main goal of this paper is to discuss several approaches to the formulation of distributionally robust counterparts of Markov Decision Processes, where the transition kernels are not specified exactly but rather are assumed to be elements of the corresponding ambiguity sets. The intent is to clarify some connections between the game and static formulations of distributionally robust MDPs, and delineate the role of rectangularity associated with ambiguity sets in determining these connectio...
-
作者：Wang, Ruodu; Zhang, Zhenyuan
作者单位：University of Waterloo; Stanford University
摘要：We introduce the framework of quadratic-form optimal transport (QOT), whose transport cost has the form integral integral cd pi circle times d pi for some coupling pi between two marginals. Interesting examples of quadratic-form transport cost and their optimization include inequality measurement, the variance of a bivariate function, covariance, Kendall's tau, the Gromov-Wasserstein distance, quadratic assignment problems, and quadratic regularization of classic optimal transport. QOT leads t...
-
作者：Lozano, Leonardo; Borrero, Juan S.
作者单位：University System of Ohio; University of Cincinnati; State University System of Florida; University of South Florida
摘要：We study a class of decision-making problems under uncertainty, where the planner hedges against the worst-case realization in an integer uncertainty set that has a functional dependence on the decisions of the planner. We propose three methods to reformulate and solve these problems: the first is based on a single-level 'semi-infinite' reformulation, where the dependence of the uncertainty on the decisions is modeled with auxiliary binary variables; the second is based on a single-follower bi...
