Mathematical Programming

最新文章

• Statistics with set-valued functions: applications to inverse approximate optimization AI翻译
  作者：Aswani, Anil
  作者单位：University of California System; University of California Berkeley
  摘要：Much of statistics relies upon four key elements: a law of large numbers, a calculus to operationalize stochastic convergence, a central limit theorem, and a framework for constructing local approximations. These elements are well-understood for objects in a vector space (e.g., points or functions); however, much statistical theory does not directly translate to sets because they do not form a vector space. Building on probability theory for random sets, this paper uses variational analysis to...
• Special Issue: Variational Analysis in Modern Statistics Preface AI翻译
  作者：Royset, Johannes O.
  作者单位：United States Department of Defense; United States Navy; Naval Postgraduate School
• Special Issue: Nonconvex Optimization for Statistical Learning Preface AI翻译
  作者：Liu, Yufeng; Pang, Jong-Shi; Xin, Jack
  作者单位：University of North Carolina; University of North Carolina Chapel Hill; University of Southern California; University of California System; University of California Irvine
• Maximization of AUC and Buffered AUC in binary classification AI翻译
  作者：Norton, Matthew; Uryasev, Stan
  作者单位：United States Department of Defense; United States Navy; Naval Postgraduate School; State University System of Florida; University of Florida
  摘要：In binary classification, performance metrics that are defined as the probability that some error exceeds a threshold are numerically difficult to optimize directly and also hide potentially important information about the magnitude of errors larger than the threshold. Defining similar metrics, instead, using Buffered Probability of Exceedance (bPOE) generates counterpart metrics that resolve both of these issues. We apply this approach to the case of AUC, the Area Under the ROC curve, and def...
• Linear convergence of the randomized sparse Kaczmarz method AI翻译
  作者：Schoepfer, Frank; Lorenz, Dirk A.
  作者单位：Carl von Ossietzky Universitat Oldenburg; Braunschweig University of Technology
  摘要：The randomized version of the Kaczmarz method for the solution of consistent linear systems is known to converge linearly in expectation. And even in the possibly inconsistent case, when only noisy data is given, the iterates are expected to reach an error threshold in the order of the noise-level with the same rate as in the noiseless case. In this work we show that the same also holds for the iterates of the recently proposed randomized sparse Kaczmarz method for recovery of sparse solutions...
• On cutting planes for cardinality-constrained linear programs AI翻译
  作者：Kim, Jinhak; Tawarmalani, Mohit; Richard, Jean-Philippe P.
  作者单位：University of South Alabama; Purdue University System; Purdue University; State University System of Florida; University of Florida
  摘要：We derive cutting planes for cardinality-constrained linear programs. These inequalities can be used to separate any basic feasible solution of an LP relaxation of the problem, assuming that this solution violates the cardinality requirement. To derive them, we first relax the given simplex tableau into a disjunctive set, expressed in the space of nonbasic variables. We establish that coefficients of valid inequalities for the closed convex hull of this set obey ratios that can be computed dir...
• Tight relaxations for polynomial optimization and Lagrange multiplier expressionsy AI翻译
  作者：Nie, Jiawang
  作者单位：University of California System; University of California San Diego
  摘要：This paper proposes tight semidefinite relaxations for polynomial optimization. The optimality conditions are investigated. We show that generally Lagrange multipliers can be expressed as polynomial functions in decision variables over the set of critical points. The polynomial expressions are determined by linear equations. Based on these expressions, new Lasserre type semidefinite relaxations are constructed for solving the polynomial optimization. We show that the hierarchy of new relaxatio...
• On the adaptivity gap in two-stage robust linear optimization under uncertain packing constraints AI翻译
  作者：Awasthi, Pranjal; Goyal, Vineet; Lu, Brian Y.
  作者单位：Rutgers University System; Rutgers University New Brunswick; Columbia University
  摘要：In this paper, we study the performance of static solutions in two-stage adjustable robust packing linear optimization problem with uncertain constraint coefficients. Such problems arise in many important applications such as revenue management and resource allocation problems where demand requests have uncertain resource requirements. The goal is to find a two-stage solution that maximizes the worst case objective value over all possible realizations of the second-stage constraints from a giv...
• Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary AI翻译
  作者：Haeser, Gabriel; Liu, Hongcheng; Ye, Yinyu
  作者单位：Universidade de Sao Paulo; Stanford University; Stanford University
  摘要：In this paper we consider the minimization of a continuous function that is potentially not differentiable or not twice differentiable on the boundary of the feasible region. By exploiting an interior point technique, we present first- and second-order optimality conditions for this problem that reduces to classical ones when the derivative on the boundary is available. For this type of problems, existing necessary conditions often rely on the notion of subdifferential or become non-trivially ...
• Partitioning a graph into small pieces with applications to path transversal AI翻译
  作者：Lee, Euiwoong
  作者单位：Carnegie Mellon University
  摘要：Given a graph G=(V,E) and an integer k is an element of N, we study k-Vertex Separator (resp. k-Edge Separator), where the goal is to remove the minimum number of vertices (resp. edges) such that each connected component in the resulting graph has less than k vertices. We also study k-Path Transversal, where the goal is to remove the minimum number of vertices such that there is no simple path of length k. Our main results are the following improved approximation algorithms.O(logk)-approximati...