-
作者：Orlin, James B.; Schulz, Andreas S.; Udwani, Rajan
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We consider a robust formulation, introduced by Krause et al. (J Artif Intell Res 42: 427- 486, 2011), of the classical cardinality constrained monotone submodular function maximization problem, and give the first constant factor approximation results. The robustness considered is w. r. t. adversarial removal of up to t elements from the chosen set. For the fundamental case of t = 1, we give a deterministic (1 - 1/e) - 1/T(m) approximation algorithm, where m is an input parameter and number of...
-
作者：Teboulle, Marc
作者单位：Tel Aviv University
摘要：We discuss the foundational role of the proximal framework in the development and analysis of some iconic first order optimization algorithms, with a focus on non-Euclidean proximal distances of Bregman type, which are central to the analysis of many other fundamental first order minimization relatives. We stress simplification and unification by highlighting self-contained elementary proof-patterns to obtain convergence rate and global convergence both in the convex and the nonconvex settings...
-
作者：Attouch, Hedy; Chbani, Zaki; Peypouquet, Juan; Redont, Patrick
作者单位：Universite de Montpellier; Centre National de la Recherche Scientifique (CNRS); Cadi Ayyad University of Marrakech; Universidad Tecnica Federico Santa Maria
摘要：In a Hilbert space setting H, we study the fast convergence properties as t -> +infinity of the trajectories of the second-order differential equation x(t) + alpha/t(x) over dot(t) + del Phi(x(t)) = g(t), where del Phi is the gradient of a convex continuously differentiable function Phi : H -> R, alpha is a positive parameter, and g : [t(0),+infinity[-> H is a small perturbation term. In this inertial system, the viscous damping coefficient alpha/t vanishes asymptotically, but not too rapidly....
-
作者：Arpon, Sebastian; Homem-de-Mello, Tito; Pagnoncelli, Bernardo
作者单位：Universidad Adolfo Ibanez
摘要：In this paper we discuss scenario reduction methods for risk-averse stochastic optimization problems. Scenario reduction techniques have received some attention in the literature and are used by practitioners, as such methods allow for an approximation of the random variables in the problem with a moderate number of scenarios, which in turn make the optimization problem easier to solve. The majority of works for scenario reduction are designed for classical risk-neutral stochastic optimization...
-
作者：Guo, Lei; Ye, Jane J.
作者单位：Shanghai Jiao Tong University; University of Victoria
摘要：When the objective function is not locally Lipschitz, constraint qualifications are no longer sufficient for Karush-Kuhn-Tucker (KKT) conditions to hold at a local minimizer, let alone ensuring an exact penalization. In this paper, we extend quasi-normality and relaxed constant positive linear dependence condition to allow the non-Lipschitzness of the objective function and show that they are sufficient for KKT conditions to be necessary for optimality. Moreover, we derive exact penalization r...
-
作者：Lourenco, Bruno F.; Fukuda, Ellen H.; Fukushima, Masao
作者单位：Seikei University; Kyoto University
摘要：In this work, we derive second-order optimality conditions for nonlinear semidefinite programming (NSDP) problems, by reformulating it as an ordinary nonlinear programming problem using squared slack variables. We first consider the correspondence between Karush-Kuhn-Tucker points and regularity conditions for the general NSDP and its reformulation via slack variables. Then, we obtain a pair of no-gap second-order optimality conditions that are essentially equivalent to the ones already consid...
-
作者：Pennanen, Teemu; Perkkioe, Ari-Pekka
作者单位：University of London; King's College London; Technical University of Berlin
摘要：The shadow price of information has played a central role in stochastic optimization ever since its introduction by Rockafellar and Wets in the mid-seventies. This article studies the concept in an extended formulation of the problem and gives relaxed sufficient conditions for its existence. We allow for general adapted decision strategies, which enables one to establish the existence of solutions and the absence of a duality gap e.g. in various problems of financial mathematics where the usua...
-
作者：Lin, Gui-Hua; Luo, Mei-Ju; Zhang, Dali; Zhang, Jin
作者单位：Shanghai University; Liaoning University; Shanghai Jiao Tong University; Hong Kong Baptist University
摘要：This paper considers a class of stochastic second-order-cone complementarity problems (SSOCCP), which are generalizations of the noticeable stochastic complementarity problems and can be regarded as the Karush-Kuhn-Tucker conditions of some stochastic second-order-cone programming problems. Due to the existence of random variables, the SSOCCP may not have a common solution for almost every realization . In this paper, motivated by the works on stochastic complementarity problems, we present a ...
-
作者：Labbe, Jean-Philippe; Manneville, Thibault; Santos, Francisco
作者单位：Hebrew University of Jerusalem; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); Institut Polytechnique de Paris; Ecole Polytechnique; Universidad de Cantabria
摘要：In their paper proving the Hirsch bound for flag normal simplicial complexes, Adiprasito and Benedetti (Math Oper Res 39(4):1340-1348, 2014) define the notion of combinatorial segment. The study of the maximal length of these objects provides the upper bound for the diameter of any normal pure simplicial complex of dimension d with n vertices, and the Hirsch bound if the complexes are moreover flag. In the present article, we propose a formulation of combinatorial segments which is equivalent ...
-
作者：Benchetrit, Yohann
作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
摘要：We prove that every h-perfect line graph and every t-perfect claw-free graph G has the integer round-up property for the chromatic number: for every non-negative integral weight function c on the vertices of G, the weighted chromatic number of (G, c) can be obtained by rounding up its fractional relaxation. As a corollary, we obtain that the weighted chromatic number can be computed in polynomial-time for these graphs. Finally, we show a new example of a graph operation which preserves the int...
