-
作者：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 ...
-
作者：Liu, Minghui; Pataki, Gabor
作者单位：SAS Institute Inc; University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine
摘要：In conic linear programming-in contrast to linear programming-the Lagrange dual is not an exact dual: it may not attain its optimal value, or there may be a positive duality gap. The corresponding Farkas' lemma is also not exact (it does not always prove infeasibility). We describe exact duals, and certificates of infeasibility and weak infeasibility for conic LPs which are nearly as simple as the Lagrange dual, but do not rely on any constraint qualification. Some of our exact duals generaliz...
-
作者：Soledad Aronna, M.; Bonnans, J. Frederic; Kroner, Axel
作者单位：Getulio Vargas Foundation; Institut Polytechnique de Paris; Ecole Polytechnique; ENSTA Paris; Universite Paris Saclay
-
作者：Combettes, Patrick L.
作者单位：North Carolina State University
摘要：Several aspects of the interplay between monotone operator theory and convex optimization are presented. The crucial role played by monotone operators in the analysis and the numerical solution of convex minimization problems is emphasized. We review the properties of subdifferentials as maximally monotone operators and, in tandem, investigate those of proximity operators as resolvents. In particular, we study new transformations which map proximity operators to proximity operators, and establ...
