Mathematical Programming

最新文章

• Regularized nonlinear acceleration AI翻译
  作者：Scieur, Damien; d'Aspremont, Alexandre; Bach, Francis
  作者单位：Inria; Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); Universite PSL; Ecole Normale Superieure (ENS); Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I)
  摘要：We describe a convergence acceleration technique for unconstrained optimization problems. Our scheme computes estimates of the optimum from a nonlinear average of the iterates produced by any optimization method. The weights in this average are computed via a simple linear system, whose solution can be updated online. This acceleration scheme runs in parallel to the base algorithm, providing improved estimates of the solution on the fly, while the original optimization method is running. Numer...
• A tight2-approximation for linear 3-cut AI翻译
  作者：Berczi, Kristof; Chandrasekaran, Karthekeyan; Kiraly, Tamas; Madan, Vivek
  作者单位：Eotvos Lorand University; University of Illinois System; University of Illinois Urbana-Champaign
  摘要：We investigate the approximability of the linear 3-cut problem in directed graphs. The input here is a directed graph D = (V, E) with node weights and three specified terminal nodes s, r, t. V, and the goal is to find a minimum weight subset of nonterminal nodes whose removal ensures that s cannot reach r and t, and r cannot reach t. The precise approximability of linear 3-cut has been wide open until now: the best known lower bound under the unique games conjecture (UGC) was 4/3, while the be...
• Certifiably optimal sparse inverse covariance estimation AI翻译
  作者：Bertsimas, Dimitris; Lamperski, Jourdain; Pauphilet, Jean
  作者单位：Massachusetts Institute of Technology (MIT)
  摘要：We consider the maximum likelihood estimation of sparse inverse covariance matrices. We demonstrate that current heuristic approaches primarily encourage robustness, instead of the desired sparsity. We give a novel approach that solves the cardinality constrained likelihood problem to certifiable optimality. The approach uses techniques from mixed-integer optimization and convex optimization, and provides a high-quality solution with a guarantee on its suboptimality, even if the algorithm is t...
• Balas formulation for the union of polytopes is optimal AI翻译
  作者：Conforti, Michele; Di Summa, Marco; Faenza, Yuri
  作者单位：University of Padua; Columbia University
  摘要：A celebrated theorem of Balas gives a linear mixed-integer formulation for the union of two nonempty polytopes whose relaxation gives the convex hull of this union. The number of inequalities in Balas formulation is linear in the number of inequalities that describe the two polytopes and the number of variables is doubled. In this paper we show that this is best possible: in every dimension there exist two nonempty polytopes such that if a formulation for the convex hull of their union has a n...
• Risk minimization, regret minimization and progressive hedging algorithms AI翻译
  作者：Sun, Jie; Yang, Xinmin; Yao, Qiang; Zhang, Min
  作者单位：Curtin University; National University of Singapore; Chongqing Normal University; East China Normal University; New York University; NYU Shanghai; Chinese Academy of Sciences; Xinjiang Institute of Ecology & Geography, CAS; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS
  摘要：This paper begins with a study on the dual representations of risk and regret measures and their impact on modeling multistage decision making under uncertainty. A relationship between risk envelopes and regret envelopes is established by using the Lagrangian duality theory. Such a relationship opens a door to a decomposition scheme, called progressive hedging, for solving multistage risk minimization and regret minimization problems. In particular, the classical progressive hedging algorithm ...
• The subdifferential of measurable composite max integrands and smoothing approximation AI翻译
  作者：Burke, James V.; Chen, Xiaojun; Sun, Hailin
  作者单位：University of Washington; University of Washington Seattle; Hong Kong Polytechnic University; Nanjing Normal University
  摘要：The subdifferential calculus for the expectation of nonsmooth random integrands involves many fundamental and challenging problems in stochastic optimization. It is known that for Clarke regular integrands, the Clarke subdifferential of the expectation equals the expectation of their Clarke subdifferential. In particular, this holds for convex integrands. However, little is known about the calculation of Clarke subgradients for the expectation of non-regular integrands. The focus of this contr...
• Weakly homogeneous variational inequalities and solvability of nonlinear equations over cones AI翻译
  作者：Gowda, M. Seetharama; Sossa, David
  作者单位：University System of Maryland; University of Maryland Baltimore County; Universidad de O'Higgins
  摘要：Given a closed convex cone C in a finite dimensional real Hilbert space H, a weakly homogeneous map fC -> H is a sum of two continuous maps h and g, where h is positively homogeneous of degree gamma (>= 0) on C and g(x)=o(||x||gamma) as ||x||->infinity in C. Given such a map f, a nonempty closed convex subset K of C, and a q is an element of H, we consider the variational inequality problem, VI(f,K,q), of finding an x is an element of K such that f(x)+q,x-x >= 0 for all x is an element of K. I...
• Lopsided convergence: an extension and its quantification AI翻译
  作者：Royset, Johannes O.; Wets, Roger J-B
  作者单位：United States Department of Defense; United States Navy; Naval Postgraduate School; University of California System; University of California Davis
  摘要：Much of the development of lopsided convergence for bifunctions defined on product spaces was in response to motivating applications. A wider class of applications requires an extension that would allow for arbitrary domains, not only product spaces. This leads to an extension of the definition and its implications that include the convergence of solutions and optimal values of a broad class of minsup problems. In the process we relax the definition of lopsided convergence even for the classic...
• Subdifferential characterization of probability functions under Gaussian distribution AI翻译
  作者：Hantoute, Abderrahim; Henrion, Rene; Perez-Aros, Pedro
  作者单位：Universidad de Chile; Leibniz Association; Weierstrass Institute for Applied Analysis & Stochastics
  摘要：Probability functions figure prominently in optimization problems of engineering. They may be nonsmooth even if all input data are smooth. This fact motivates the consideration of subdifferentials for such typically just continuous functions. The aim of this paper is to provide subdifferential formulae of such functions in the case of Gaussian distributions for possibly infinite-dimensional decision variables and nonsmooth (locally Lipschitzian) input data. These formulae are based on the sphe...
• Beating the 2-approximation factor for global bicut AI翻译
  作者：Berczi, Kristof; Chandrasekaran, Karthekeyan; Kiraly, Tamas; Lee, Euiwoong; Xu, Chao
  作者单位：Eotvos Lorand University; University of Illinois System; University of Illinois Urbana-Champaign; Carnegie Mellon University
  摘要：In the fixed-terminal bicut problem, the input is a directed graph with two specified nodes s and t and the goal is to find a smallest subset of edges whose removal ensures that s cannot reach tandt cannot reach s. In the global bicut problem, the input is a directed graph and the goal is to find a smallest subset of edges whose removal ensures that there exist two nodes s and t such that s cannot reach tandt cannot reach s. Fixed-terminal bicut and global bicut are natural extensions of {s,t}...