2018

最新文章

• Approximating graph-constrained max-cut AI翻译
  作者：Shen, Xiangkun; Lee, Jon; Nagarajan, Viswanath
  作者单位：University of Michigan System; University of Michigan
  摘要：An instance of the graph-constrained max-cut ( GCMC) problem consists of ( i) an undirected graphG = ( V, E) and ( ii) edge-weights c : V 2 . R+ on a complete undirected graph. The objective is to find a subset S. V of vertices satisfying some graph-based constraint in G that maximizes the weight u. S, v/. S cuv of edges in the cut ( S, V \ S). The types of graph constraints we can handle include independent set, vertex cover, dominating set and connectivity. Our main results are for the case ...
• On error bound moduli for locally Lipschitz and regular functions AI翻译
  作者：Li, M. H.; Meng, K. W.; Yang, X. Q.
  作者单位：Chongqing University of Arts & Sciences; Hong Kong Polytechnic University
  摘要：In this paper we study local error bound moduli for a locally Lipschitz and regular function via outer limiting subdifferential sets. We show that the distance from 0 to the outer limiting subdifferential of the support function of the subdifferential set, which is essentially the distance from 0 to the end set of the subdifferential set, is an upper estimate of the local error bound modulus. This upper estimate becomes tight for a convex function under some regularity conditions. We show that...
• Max-norm optimization for robust matrix recovery AI翻译
  作者：Fang, Ethan X.; Liu, Han; Toh, Kim-Chuan; Zhou, Wen-Xin
  作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Princeton University; National University of Singapore; University of California System; University of California San Diego
  摘要：This paper studies the matrix completion problem under arbitrary sampling schemes. We propose a new estimator incorporating both max-norm and nuclear-norm regularization, based on which we can conduct efficient low-rank matrix recovery using a random subset of entries observed with additive noise under general non-uniform and unknown sampling distributions. This method significantly relaxes the uniform sampling assumption imposed for the widely used nuclear-norm penalized approach, and makes l...
• Improved approximations for cubic bipartite and cubic TSP AI翻译
  作者：van Zuylen, Anke
  作者单位：William & Mary
  摘要：We show improved approximation guarantees for the traveling salesman problem on cubic bipartite graphs and cubic graphs. For connected cubic bipartite graphs with n nodes, we improve on recent results of Karp and Ravi by giving a local improvement algorithm that finds a tour of length at most 5/ 4n -2. For 2-connected cubic graphs, we show that the techniques of Momke and Svensson can be combined with the techniques of Correa, Larre and Soto, to obtain a tour of length at most ('4/ 3 -1/ 8754...
• Critical solutions of nonlinear equations: stability issues AI翻译
  作者：Izmailov, A. F.; Kurennoy, A. S.; Solodov, M. V.
  作者单位：Lomonosov Moscow State University; Peoples Friendship University of Russia; Derzhavin Tambov State University; Instituto Nacional de Matematica Pura e Aplicada (IMPA)
  摘要：It is known that when the set of Lagrange multipliers associated with a stationary point of a constrained optimization problem is not a singleton, this set may contain so-called critical multipliers. This special subset of Lagrange multipliers defines, to a great extent, stability pattern of the solution in question subject to parametric perturbations. Criticality of a Lagrange multiplier can be equivalently characterized by the absence of the local Lipschitzian error bound in terms of the nat...
• Consistent learning by composite proximal thresholding AI翻译
  作者：Combettes, Patrick L.; Salzo, Saverio; Villa, Silvia
  作者单位：North Carolina State University; Istituto Italiano di Tecnologia - IIT; Polytechnic University of Milan
  摘要：We investigate the modeling and the numerical solution of machine learning problems with prediction functions which are linear combinations of elements of a possibly infinite dictionary of functions. We propose a novel flexible composite regularization model, which makes it possible to incorporate various priors on the coefficients of the prediction function, including sparsity and hard constraints. We show that the estimators obtained by minimizing the regularized empirical risk are consisten...
• Ellipsoidal mixed-integer representability AI翻译
  作者：Del Pia, Alberto; Poskin, Jeffrey
  作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
  摘要：Representability results for mixed-integer linear systems play a fundamental role in optimization since they give geometric characterizations of the feasible sets that can be formulated by mixed-integer linear programming. We consider a natural extension of mixed-integer linear systems obtained by adding just one ellipsoidal inequality. The set of points that can be described, possibly using additional variables, by these systems are called ellipsoidal mixed-integer representable. In this work...
• Approximating min-cost chain-constrained spanning trees: a reduction from weighted to unweighted problems AI翻译
  作者：Linhares, Andre; Swamy, Chaitanya
  作者单位：University of Waterloo
  摘要：We study the min-cost chain-constrained spanning-tree (MCCST) problem: find a min-cost spanning tree in a graph subject to degree constraints on a nested family of node sets. We devise the first polytime algorithm that finds a spanning tree that (i) violates the degree constraints by at most a constant factor and (ii) whose cost is within a constant factor of the optimum. Previously, only an algorithm for unweighted CCST was known (Olver and Zenklusen in Proceedings of the 16th IPCO, pp 324-33...
• A global MINLP approach to symbolic regression AI翻译
  作者：Cozad, Alison; Sahinidis, Nikolaos V.
  作者单位：Carnegie Mellon University; Exxon Mobil Corporation
  摘要：Symbolic regression methods generate expression trees that simultaneously define the functional form of a regression model and the regression parameter values. As a result, the regression problem can search many nonlinear functional forms using only the specification of simple mathematical operators such as addition, subtraction, multiplication, and division, among others. Currently, state-of-the-art symbolic regression methods leverage genetic algorithms and adaptive programming techniques. G...
• Robust multicategory support vector machines using difference convex algorithm AI翻译
  作者：Zhang, Chong; Minh Pham; Fu, Sheng; Liu, Yufeng
  作者单位：University of Waterloo; University of Virginia; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine
  摘要：The support vector machine (SVM) is one of the most popular classification methods in the machine learning literature. Binary SVM methods have been extensively studied, and have achieved many successes in various disciplines. However, generalization to multicategory SVM (MSVM) methods can be very challenging. Many existing methods estimate k functions for k classes with an explicit sum-to-zero constraint. It was shown recently that such a formulation can be suboptimal. Moreover, many existing ...