-
作者：Lee, Jae Hyoung; Lee, Gue Myung
作者单位：Pukyong National University
摘要：In this paper, we establish tractable sum of squares characterizations of the containment of a convex set, defined by a SOS-concave matrix inequality, in a non-convex set, defined by difference of a SOS-convex polynomial and a support function, with Slater's condition. Using our set containment characterization, we derive a zero duality gap result for a DC optimization problem with a SOS-convex polynomial and a support function, its sum of squares polynomial relaxation dual problem, the semide...
-
作者：Kruger, A. Y.; Lopez, M. A.; Thera, M. A.
作者单位：Federation University Australia; Universitat d'Alacant; Centre National de la Recherche Scientifique (CNRS); Universite de Limoges
摘要：Our aim in the current article is to extend the developments in Kruger et al. (SIAM J Optim 20(6):3280-3296, 2010. doi:10.1137/100782206) and, more precisely, to characterize, in the Banach space setting, the stability of the local and global error bound property of inequalities determined by lower semicontinuous functions under data perturbations. We propose new concepts of (arbitrary, convex and linear) perturbations of the given function defining the system under consideration, which turn o...
-
作者：Eghbahi, Reza; Saunderson, James; Fazel, Maryam
作者单位：Cisco Systems Inc; Cisco USA; Monash University; University of Washington; University of Washington Seattle
摘要：We consider a new and general online resource allocation problem, where the goal is to maximize a function of a positive semidefinite (PSD) matrix with a scalar budget constraint. The problem data arrives online, and the algorithm needs to make an irrevocable decision at each step. Of particular interest are classic experiment design problems in the online setting, with the algorithm deciding whether to allocate budget to each experiment as new experiments become available sequentially. We ana...
-
作者：Xu, Huifu; Liu, Yongchao; Sun, Hailin
作者单位：University of Southampton; Dalian University of Technology; Nanjing University of Science & Technology
摘要：A key step in solving minimax distributionally robust optimization (DRO) problems is to reformulate the inner maximization w.r.t. probability measure as a semiinfinite programming problem through Lagrange dual. Slater type conditions have been widely used for strong duality (zero dual gap) when the ambiguity set is defined through moments. In this paper, we investigate effective ways for verifying the Slater type conditions and introduce other conditions which are based on lower semicontinuity...
-
作者：Lee, Jon; Skipper, Daphne; Speakman, Emily
作者单位：University of Michigan System; University of Michigan; United States Department of Defense; United States Navy; United States Naval Academy; Otto von Guericke University
摘要：This is mostly a survey on some mathematical results concerning volumes of polytopes of interest in non-convex optimization. Our motivation is in geometrically comparing relaxations in the context of mixed-integer linear and nonlinear optimization, with the goal of gaining algorithmic and modeling insights. We consider relaxations of: fixed-charge formulations, vertex packing polytopes, boolean-quadric polytopes, and relaxations of graphs of monomials on box domains. Besides surveying the area...
-
作者：Hoai An Le Thi; Tao Pham Dinh
作者单位：Universite de Lorraine
-
作者：Adly, Samir; Dontchev, Asen
作者单位：Universite de Limoges; University of Michigan System; University of Michigan
-
作者：Czarnecki, Marc-Olivier; Thibault, Lionel
作者单位：Universite de Montpellier; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universidad de Chile
摘要：Epi-Lipschitz sets in normed spaces are represented as sublevel sets of Lipschitz functions satisfying a so-called qualification condition. Canonical representations through the signed distance functions associated with the sets are also obtained. New optimality conditions are provided, for optimization problems with epi-Lipschitz set constraints, in terms of the signed distance function.
-
作者：Raymond, Annie; Saunderson, James; Singh, Mohit; Thomas, Rekha R.
作者单位：University of Washington; University of Washington Seattle; Monash University; University System of Georgia; Georgia Institute of Technology
摘要：We consider the problem of finding sum of squares (sos) expressions to establish the non-negativity of a symmetric polynomial over a discrete hypercube whose coordinates are indexed by the k-element subsets of [n]. For simplicity, we focus on the case , but our results extend naturally to all values of . We develop a variant of the Gatermann-Parrilo symmetry-reduction method tailored to our setting that allows for several simplifications and a connection to flag algebras. We show that every sy...
-
作者：Basu, Amitabh; Conforti, Michele; Di Summa, Marco; Paat, Joseph
作者单位：Johns Hopkins University; University of Padua; University of Padua; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：For the one dimensional infinite group relaxation, we construct a sequence of extreme valid functions that are piecewise linear and such that for every natural number k >= 2, there is a function in the sequence with k slopes. This settles an open question in this area regarding a universal bound on the number of slopes for extreme functions. The function which is the pointwise limit of this sequence is an extreme valid function that is continuous and has an infinite number of slopes. This prov...
