-
作者：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...
-
作者：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...
-
作者：Eckstein, Jonathan; Yao, Wang
作者单位：Rutgers University System; Rutgers University New Brunswick; Rutgers University System; Rutgers University New Brunswick
摘要：We derive a new approximate version of the alternating direction method of multipliers (ADMM) which uses a relative error criterion. The new version is somewhat restrictive and allows only one of the two subproblems to be minimized approximately, but nevertheless covers commonly encountered special cases. The derivation exploits the long-established relationship between the ADMM and both the proximal point algorithm (PPA) and Douglas-Rachford (DR) splitting for maximal monotone operators, alon...
-
作者：Aragon Artacho, Francisco J.; Fleming, Ronan M. T.; Vuong, Phan T.
作者单位：Universitat d'Alacant; University of Luxembourg
摘要：We introduce two new algorithms to minimise smooth difference of convex (DC) functions that accelerate the convergence of the classical DC algorithm (DCA). We prove that the point computed by DCA can be used to define a descent direction for the objective function evaluated at this point. Our algorithms are based on a combination of DCA together with a line search step that uses this descent direction. Convergence of the algorithms is proved and the rate of convergence is analysed under the Ao...
-
作者：Wu, Chenchen; Wang, Yishui; Lu, Zaixin; Pardalos, Panos M.; Xu, Dachuan; Zhang, Zhao; Du, Ding-Zhu
作者单位：Tianjin University of Technology; Beijing University of Technology; Washington State University; State University System of Florida; University of Florida; Beijing University of Technology; Zhejiang Normal University
摘要：In this paper, we consider the maximum and minimum versions of degree-concentrated fault-tolerant spanning subgraph problem which has many applications in network communications. We prove that both this two problems are NP-hard. For the maximum version, we use DC programming relaxation to propose a heuristic algorithm. Numerical tests indicate that the proposed algorithm is efficient and effective. For the minimum version, we also formulate it as a DC program, and show that the DC algorithm do...
-
作者：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 ...
