-
作者：Sun, Jie; Liao, Li-Zhi; Rodrigues, Brian
作者单位：Curtin University; Curtin University; National University of Singapore; Hong Kong Baptist University; Singapore Management University
摘要：A new scheme to cope with two-stage stochastic optimization problems uses a risk measure as the objective function of the recourse action, where the risk measure is defined as the worst-case expected values over a set of constrained distributions. This paper develops an approach to deal with the case where both the first and second stage objective functions are convex linear-quadratic. It is shown that under a standard set of regularity assumptions, this two-stage quadratic stochastic optimiza...
-
作者：Averkov, Gennadiy; Kaibel, Volker; Weltge, Stefan
作者单位：Otto von Guericke University; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：We relate the maximum semidefinite and linear extension complexity of a family of polytopes to the cardinality of this family and the minimum pairwise Hausdorff distance of its members. This result directly implies a known lower bound on the maximum semidefinite extension complexity of 0/1-polytopes. We further show how our result can be used to improve on the corresponding bounds known for polygons with integer vertices. Our geometric proof builds upon nothing else than a simple well-known pr...
-
作者：Cornuejols, Gerard; Lee, Dabeen
作者单位：Carnegie Mellon University
摘要：In this paper, we consider polytopes P that are contained in the unit hypercube. We provide conditions on the set of 0, 1 vectors not contained in P that guarantee that P has a small Chvatal rank. Our conditions are in terms of the subgraph induced by these infeasible 0,1 vertices in the skeleton graph of the unit hypercube. In particular, we show that when this subgraph contains no 4-cycle, the Chvatal rank is at most 3; and when it has tree width 2, the Chvatal rank is at most 4. We also giv...
-
作者：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...
