-
作者：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.
-
作者：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...
-
作者：Thai Dinh; Fukasawa, Ricardo; Luedtke, James
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; University of Waterloo
摘要：We study the chance-constrained vehicle routing problem (CCVRP), a version of the vehicle routing problem (VRP) with stochastic demands, where a limit is imposed on the probability that each vehicle's capacity is exceeded. A distinguishing feature of our proposed methodologies is that they allow correlation between random demands, whereas nearly all existing exact methods for the VRP with stochastic demands require independent demands. We first study an edge-based formulation for the CCVRP, in...
-
作者：Lan, Guanghui; Zhou, Yi
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：In this paper, we consider a class of finite-sum convex optimization problems whose objective function is given by the average of m (>= 1) smooth components together with some other relatively simple terms. We first introduce a deterministic primal-dual gradient (PDG) method that can achieve the optimal black-box iteration complexity for solving these composite optimization problems using a primal-dual termination criterion. Our major contribution is to develop a randomized primal-dual gradien...
-
作者：Ye, Jane J.; Zhou, Jinchuan
作者单位：University of Victoria; Shandong University of Technology
摘要：The error bound property for a solution set defined by a set-valued mapping refers to an inequality that bounds the distance between vectors closed to a solution of the given set by a residual function. The error bound property is a Lipschitz-like/calmness property of the perturbed solution mapping, or equivalently the metric subregularity of the underlining set-valued mapping. It has been proved to be extremely useful in analyzing the convergence of many algorithms for solving optimization pr...
-
作者：Chateauneuf, Alain; Cornet, Bernard
作者单位：IPAG Business School; heSam Universite; Universite Pantheon-Sorbonne; Paris School of Economics; heSam Universite; Universite Pantheon-Sorbonne; University of Kansas
摘要：Let be an arbitrary set, equipped with an algebra and let be a functional defined on the set of bounded measurable functions . We provide necessary and sufficient conditions for a submodular functional f to be representable as a Choquet integral. From standard properties of the Choquet integral the functional f should be positively homogeneous and constant additive. Our first result shows that these two properties, together with submodularity, characterize a subadditive Choquet integral, when ...
-
作者：Ding, Chao; Sun, Defeng; Sun, Jie; Toh, Kim-Chuan
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; National University of Singapore; National University of Singapore; Curtin University; National University of Singapore
摘要：The class of matrix optimization problems (MOPs) has been recognized in recent years to be a powerful tool to model many important applications involving structured low rank matrices within and beyond the optimization community. This trend can be credited to some extent to the exciting developments in emerging fields such as compressed sensing. The Lowner operator, which generates a matrix valued function via applying a single-variable function to each of the singular values of a matrix, has p...
-
作者：Gottschalk, Corinna; Vygen, Jens
作者单位：RWTH Aachen University; University of Bonn
摘要：We consider the s-t-path TSP: given a finite metric space with two elements s and t, we look for a path from s to t that contains all the elements and has minimum total distance. We improve the approximation ratio for this problem from 1.599 to 1.566. Like previous algorithms, we solve the natural LP relaxation and represent an optimum solution x * as a convex combination of spanning trees. Gao showed that there exists a spanning tree in the support of x * that has only one edge in each narrow...
-
作者：Nesterov, Yu.
摘要：We provide Frank-Wolfe (equivalent to Conditional Gradients) method with a convergence analysis allowing to approach a primal-dual solution of convex optimization problem with composite objective function. Additional properties of complementary part of the objective (strong convexity) significantly accelerate the scheme. We also justify a new variant of this method, which can be seen as a trust-region scheme applying to the linear model of objective function. For this variant, we prove also th...
-
作者：Adamaszek, Anna; Chalermsook, Parinya; Ene, Alina; Wiese, Andreas
作者单位：University of Copenhagen; Aalto University; University of Warwick; Max Planck Society
摘要：We study the Unsplittable Flow problem (UFP) on trees with a submodular objective function. The input to this problem is a tree with edge capacities and a collection of tasks, each characterized by a source node, a sink node, and a demand. A subset of the tasks is feasible if the tasks can simultaneously send their demands from the source to the sink without violating the edge capacities. The goal is to select a feasible subset of the tasks that maximizes a submodular objective function. Our m...
