-
作者：Homem-de-Mello, Tito; Kopa, Milos; Morton, David P.
作者单位：Universidad Adolfo Ibanez; Charles University Prague; Northwestern University
-
作者：Lozano, Leonardo; Smith, J. Cole
作者单位：Clemson University; Clemson University
摘要：We consider a special class of two-stage stochastic integer programming problems with binary variables appearing in both stages. The class of problems we consider constrains the second-stage variables to belong to the intersection of sets corresponding to first-stage binary variables that equal one. Our approach seeks to uncover strong dual formulations to the second-stage problems by transforming them into dynamic programming (DP) problems parameterized by first-stage variables. We demonstrat...
-
作者：Wang, Alex L.; Kilinc-Karzan, Fatma
作者单位：Carnegie Mellon University
摘要：Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems well-known to be NP-hard in general. In this paper we study conditions under which the standard semidefinite program (SDP) relaxation of a QCQP is tight. We begin by outlining a general framework for proving such sufficient conditions. Then using this framework, we show that the SDP relaxation is tight whenever the quadratic eigenvalue multiplicity, a parameter capturing the amount of symmetry...
-
作者：Kouri, Drew P.; Surowiec, Thomas M.
作者单位：United States Department of Energy (DOE); Sandia National Laboratories; Philipps University Marburg
摘要：In this paper, we develop an algorithm to efficiently solve risk-averse optimization problems posed in reflexive Banach space. Such problems often arise in many practical applications as, e.g., optimization problems constrained by partial differential equations with uncertain inputs. Unfortunately, for many popular risk models including the coherent risk measures, the resulting risk-averse objective function is nonsmooth. This lack of differentiability complicates the numerical approximation o...
-
作者：Cvetkovic, Aleksandar; Protasov, Vladimir Yu
作者单位：Gran Sasso Science Institute (GSSI); Lomonosov Moscow State University
摘要：We address the problems of minimizing and of maximizing the spectral radius over a compact family of non-negative matrices. Those problems being hard in general can be efficiently solved for some special families. We consider the so-called product families, where each matrix is composed of rows chosen independently from given sets. A recently introduced greedy method works very fast. However, it is applicable mostly for strictly positive matrices. For sparse matrices, it often diverges and giv...
-
作者：Kozhasov, Khazhgali; Lasserre, Jean Bernard
作者单位：Braunschweig University of Technology; Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite de Toulouse
摘要：We show that the Euclidean ball has the smallest volume among sublevel sets of nonnegative forms of bounded Bombieri norm as well as among sublevel sets of sum of squares forms whose Gram matrix has bounded Frobenius or nuclear (or, more generally, p-Schatten) norm. These volume-minimizing properties of the Euclidean ball with respect to its representation (as a sublevel set of a form of fixed even degree) complement its numerous intrinsic geometric properties. We also provide a probabilistic ...
-
作者：Fairbrother, Jamie; Turner, Amanda; Wallace, Stein W.
作者单位：Lancaster University; Norwegian School of Economics (NHH)
摘要：Scenario generation is the construction of a discrete random vector to represent parameters of uncertain values in a stochastic program. Most approaches to scenario generation aredistribution-driven, that is, they attempt to construct a random vector which captures well in a probabilistic sense the uncertainty. On the other hand, aproblem-drivenapproach may be able to exploit the structure of a problem to provide a more concise representation of the uncertainty. In this paper we propose an ana...
-
作者：Garatti, S.; Campi, M. C.
作者单位：Polytechnic University of Milan; University of Brescia
摘要：Scenario optimization is a broad methodology to perform optimization based on empirical knowledge. One collects previous cases, called scenarios, for the set-up in which optimization is being performed, and makes a decision that is optimal for the cases that have been collected. For convex optimization, a solid theory has been developed that provides guarantees of performance, and constraint satisfaction, of the scenario solution. In this paper, we open a new direction of investigation: the ri...
-
作者：Latafat, Puya; Themelis, Andreas; Patrinos, Panagiotis
作者单位：KU Leuven; Kyushu University
摘要：This paper analyzes block-coordinate proximal gradient methods for minimizing the sum of a separable smooth function and a (nonseparable) nonsmooth function, both of which are allowed to be nonconvex. The main tool in our analysis is the forward-backward envelope, which serves as a particularly suitable continuous and real-valued Lyapunov function. Global and linear convergence results are established when the cost function satisfies the Kurdyka-Lojasiewicz property without imposing convexity ...
