Mathematical Programming

最新文章

• Evaluating policies in risk-averse multi-stage stochastic programming AI翻译
  作者：Kozmik, Vaclav; Morton, David P.
  作者单位：Charles University Prague; University of Texas System; University of Texas Austin
  摘要：We consider a risk-averse multi-stage stochastic program using conditional value at risk as the risk measure. The underlying random process is assumed to be stage-wise independent, and a stochastic dual dynamic programming (SDDP) algorithm is applied. We discuss the poor performance of the standard upper bound estimator in the risk-averse setting and propose a new approach based on importance sampling, which yields improved upper bound estimators. Modest additional computational effort is requ...
• A framework of discrete DC programming by discrete convex analysis AI翻译
  作者：Maehara, Takanori; Murota, Kazuo
  作者单位：Japan Science & Technology Agency (JST); Research Organization of Information & Systems (ROIS); National Institute of Informatics (NII) - Japan; University of Tokyo
  摘要：A theoretical framework of difference of discrete convex functions (discrete DC functions) and optimization problems for discrete DC functions is established. Standard results in continuous DC theory are exported to the discrete DC theory with the use of discrete convex analysis. A discrete DC algorithm, which is a discrete analogue of the continuous DC algorithm (Concave-Convex procedure in machine learning) is proposed. The algorithm contains the submodular-supermodular procedure as a specia...
• Cut generation through binarization AI翻译
  作者：Bonami, Pierre; Margot, Francois
  作者单位：Aix-Marseille Universite; Carnegie Mellon University
  摘要：For a mixed integer linear program where all integer variables are bounded, we study a reformulation introduced by Roy that maps general integer variables to a collection of binary variables. We study theoretical properties and empirical strength of rank-2 simple split cuts of the reformulation. We show that for a pure integer problem with two integer variables, these cuts are sufficient to obtain the integer hull of the problem, but that this does not generalize to problems in higher dimensio...
• The all-or-nothing flow problem in directed graphs with symmetric demand pairs AI翻译
  作者：Chekuri, Chandra; Ene, Alina
  作者单位：University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital; Princeton University; University of Warwick; University of Warwick
  摘要：We study the approximability of the All-or-Nothing multicommodity flow problem in directed graphs with symmetric demand pairs (SymANF). The input consists of a directed graph and a collection of (unordered) pairs of nodes . A subset of the pairs is routable if there is a feasible multicommodity flow in such that, for each pair , the amount of flow from to is at least one and the amount of flow from to is at least one. The goal is to find a maximum cardinality subset of the given pairs that can...
• Zero-convex functions, perturbation resilience, and subgradient projections for feasibility-seeking methods AI翻译
  作者：Censor, Yair; Reem, Daniel
  作者单位：University of Haifa
  摘要：The convex feasibility problem (CFP) is at the core of the modeling of many problems in various areas of science. Subgradient projection methods are important tools for solving the CFP because they enable the use of subgradient calculations instead of orthogonal projections onto the individual sets of the problem. Working in a real Hilbert space, we show that the sequential subgradient projection method is perturbation resilient. By this we mean that under appropriate conditions the sequence g...
• A generalization of Lowner-John's ellipsoid theorem AI翻译
  作者：Lasserre, Jean B.
  作者单位：Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite de Toulouse
  摘要：We address the following generalization of the Lowner-John ellipsoid problem. Given a (non necessarily convex) compact set and an even integer , find an homogeneous polynomial of degree such that and has minimum volume among all such sets. We show that is a convex optimization problem even if neither nor are convex! We next show that has a unique optimal solution and a characterization with at most contacts points in is also provided. This is the analogue for of Lowner-John's theorem in the qu...
• Certification of real inequalities: templates and sums of squares AI翻译
  作者：Magron, Victor; Allamigeon, Xavier; Gaubert, Stephane; Werner, Benjamin
  作者单位：Imperial College London; Inria; Institut Polytechnique de Paris; Ecole Polytechnique; Institut Polytechnique de Paris; Ecole Polytechnique; Institut Polytechnique de Paris; Ecole Polytechnique
  摘要：We consider the problem of certifying lower bounds for real-valued multivariate transcendental functions. The functions we are dealing with are nonlinear and involve semialgebraic operations as well as some transcendental functions like , etc. Our general framework is to use different approximation methods to relax the original problem into polynomial optimization problems, which we solve by sparse sums of squares relaxations. In particular, we combine the ideas of the maxplus approximations (...
• A gentle, geometric introduction to copositive optimization AI翻译
  作者：Burer, Samuel
  作者单位：University of Iowa
  摘要：This paper illustrates the fundamental connection between nonconvex quadratic optimization and copositive optimization-a connection that allows the reformulation of nonconvex quadratic problems as convex ones in a unified way. We focus on examples having just a few variables or a few constraints for which the quadratic problem can be formulated as a copositive-style problem, which itself can be recast in terms of linear, second-order-cone, and semidefinite optimization. A particular highlight ...
• Second-order characterizations of tilt stability with applications to nonlinear programming AI翻译
  作者：Mordukhovich, B. S.; Nghia, T. T. A.
  作者单位：Wayne State University
  摘要：The paper is devoted to the study of tilt-stable local minimizers of general optimization problems in finite-dimensional spaces and its applications to classical nonlinear programs with twice continuously differentiable data. The importance of tilt stability has been well recognized from both theoretical and numerical aspects of optimization, and this notion has been extensively studied in the literature. Based on advanced tools of second-order variational analysis and generalized differentiat...
• A condition number theorem in convex programming AI翻译
  作者：Zolezzi, Tullio
  作者单位：University of Genoa
  摘要：A finite-dimensional mathematical programming problem with convex data and inequality constraints is considered. A suitable definition of condition number is obtained via canonical perturbations of the given problem, assuming uniqueness of the optimal solutions. The distance among mathematical programming problems is defined as the Lipschitz constant of the difference of the corresponding Kojima functions. It is shown that the distance to ill-conditioning is bounded above and below by suitable...