-
作者：Bach, Francis
作者单位：Inria; Universite PSL; Ecole Normale Superieure (ENS)
摘要：We consider min-max optimization problems for polynomial functions, where a multivariate polynomial is maximized with respect to a subset of variables, and the resulting maximal value is minimized with respect to the remaining variables. When the variables belong to simple sets (e.g., a hypercube, the Euclidean hypersphere, or a ball), we derive a sum-of-squares formulation based on a primal-dual approach. In the simplest setting, we provide a convergence proof when the degree of the relaxatio...
-
作者：Gupta, Akshita; Hunter, Susan R.
作者单位：Purdue University System; Purdue University
摘要：We consider a two-stage stochastic multi-objective linear program (TSSMOLP) that is a natural generalization of the well-studied two-stage stochastic linear program (TSSLP) allowing modelers to specify multiple objectives in each stage. The second-stage recourse decision is governed by an uncertain multi-objective linear program (MOLP) whose solution maps to an uncertain second-stage nondominated set. The TSSMOLP then comprises the objective, which is the Minkowski sum of a linear term plus th...
-
作者：Doikov, Nikita
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：We study the composite convex optimization problems with a quasi-self-concordant smooth component. This problem class naturally interpolates between classic self-concordant functions and functions with Lipschitz continuous Hessian. Previously, the best complexity bounds for this problem class were associated with trust-region schemes and implementations of a ball optimization oracle. In this paper, we show that for minimizing quasi-self-concordant functions we can use instead the basic Newton ...
-
作者：Nutov, Zeev
作者单位：Open University Israel
摘要：A set family F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{F}$$\end{document} is uncrossable if A boolean AND B,A boolean OR B is an element of F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \u...
-
作者：Nie, Jiawang; Qu, Zheng; Tang, Xindong; Zhang, Linghao
作者单位：University of California System; University of California San Diego; Hong Kong Polytechnic University; Hong Kong Baptist University
摘要：This paper studies the sparse Moment-SOS hierarchy of relaxations for solving sparse polynomial optimization problems. We show that this sparse hierarchy is tight if and only if the objective can be written as a sum of sparse nonnegative polynomials, each of which belongs to the sum of the ideal and quadratic module generated by the corresponding sparse constraints. Based on this characterization, we give several sufficient conditions for the sparse Moment-SOS hierarchy to be tight. In particu...
-
作者：Abdi, Ahmad; Lee, Dabeen
作者单位：University of London; London School Economics & Political Science; Korea Advanced Institute of Science & Technology (KAIST)
摘要：Take a prime power q, an integer n >= 2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n\ge 2$$\end{document}, and a coordinate subspace S subset of GF(q)n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \use...
-
作者：Liu, Shutian; Zhu, Quanyan
作者单位：New York University; New York University Tandon School of Engineering
摘要：Risk measures are commonly used to capture the risk preferences of decision-makers (DMs). The decisions of DMs can be nudged or manipulated when their risk preferences are influenced by factors such as the availability of information about the uncertainties. This work proposes a Stackelberg risk preference design (STRIPE) problem to capture a designer's incentive to influence DMs' risk preferences. STRIPE consists of two levels. In the lower level, individual DMs in a population, known as the ...
-
作者：Xu, Liding; Liberti, Leo
作者单位：Centre National de la Recherche Scientifique (CNRS); Institut Polytechnique de Paris; Ecole Polytechnique
摘要：We study a mixed-integer set S:={(x,t)is an element of{0,1}nxR:f(x)>= t}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {S}:=\{(x,t) \in \{0,1\}<^>n \times \mathbb {R}: f(x) \ge t\}$$\end{document} arising in the submodular maximization problem, where f is a submodular function defined over {0,1}n\document...
-
作者：Carmon, Yair; Hinder, Oliver
作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh
摘要：We prove impossibility results for adaptivity in non-smooth stochastic convex optimization. Given a set of problem parameters we wish to adapt to, we define a price of adaptivity (PoA) that, roughly speaking, measures the multiplicative increase in suboptimality due to uncertainty in these parameters. When the initial distance to the optimum is unknown but a gradient norm bound is known, we show that the PoA is at least logarithmic for expected suboptimality, and double-logarithmic for median ...
-
作者：Joswig, Michael; Klimm, Max; Spitz, Sylvain
作者单位：Technical University of Berlin; Max Planck Society; Technical University of Berlin
摘要：The difference set of an outcome in an auction is the set of types that the auction mechanism maps to the outcome. We give a complete characterization of the geometry of the difference sets that can appear for a dominant strategy incentive compatible multi-unit auction showing that they correspond to regular subdivisions of the unit cube. Similarly, we describe the geometry for affine maximizers for n players and m items, showing that they correspond to regular subdivisions of the m-fold produ...
