-
作者：Huang, Chien-Chung; Kakimura, Naonori; Kamiyama, Naoyuki
作者单位：Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); Keio University; Kyushu University
摘要：In this paper, we propose new exact and approximation algorithms for the weighted matroid intersection problem. Our exact algorithm is faster than previous algorithms when the largest weight is relatively small. Our approximation algorithm delivers a (1-E)-approximate solution with a running time significantly faster than most known exact algorithms. The core of our algorithms is a decomposition technique: we decompose an instance of the weighted matroid intersection problem into a set of inst...
-
作者：Drusvyatskiy, D.; Paquette, C.
作者单位：University of Washington; University of Washington Seattle
摘要：We consider global efficiency of algorithms for minimizing a sum of a convex function and a composition of a Lipschitz convex function with a smooth map. The basic algorithm we rely on is the prox-linear method, which in each iteration solves a regularized subproblem formed by linearizing the smooth map. When the subproblems are solved exactly, the method has efficiency O(epsilon(-2)), akin to gradient descent for smooth minimization. We show that when the subproblems can only be solved by fir...
-
作者：Fujishige, Satoru; Sano, Yoshio; Zhan, Ping
作者单位：Kyoto University; University of Tsukuba
摘要：We present a non-pricing allocation scheme of divisible goods to agents with utility functions and submodular constraints on goods. The main contribution of the present paper is that through our non-pricing allocation scheme we reveal the close relation between (1) the recent results in the allocation schemes of the random assignment problem and its extensions with ordinal or lexicographic preferences on goods and (2) the monotone algorithms of fair (egalitarian) allocations with separable uti...
-
作者：Dong, Hongbo; Ahn, Miju; Pang, Jong-Shi
作者单位：Washington State University; University of Southern California
摘要：We introduce a new constraint system for sparse variable selection in statistical learning. Such a system arises when there are logical conditions on the sparsity of certain unknown model parameters that need to be incorporated into their selection process. Formally, extending a cardinality constraint, an affine sparsity constraint (ASC) is defined by a linear inequality with two sets of variables: one set of continuous variables and the other set represented by their nonzero patterns. This pa...
-
作者：Qian, Chengde; Quoc Tran-Dinh; Fu, Sheng; Zou, Changliang; Liu, Yufeng
作者单位：Nankai University; University of North Carolina; University of North Carolina Chapel Hill; National University of Singapore; University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina; University of North Carolina Chapel Hill
摘要：We consider the classification problem when the input features are represented as matrices rather than vectors. To preserve the intrinsic structures for classification, a successful method is the support matrix machine (SMM) in Luo et al. (in: Proceedings of the 32nd international conference on machine learning, Lille, France, no 1, pp 938-947, 2015), which optimizes an objective function with a hinge loss plus a so-called spectral elastic net penalty. However, the issues of extending SMM to m...
-
作者：Eberhard, A. C.; Luo, Y.; Liu, S.
作者单位：Royal Melbourne Institute of Technology (RMIT)
摘要：Under the assumption of prox-regularity and the presence of a tilt stable local minimum we are able to show that a VU like decomposition gives rise to the existence of a smooth manifold on which the function in question coincides locally with a smooth function.
-
作者：Grechuk, Bogdan; Zabarankin, Michael
作者单位：University of Leicester; Stevens Institute of Technology
摘要：In a regression with independent and identically distributed normal residuals, the log-likelihood function yields an empirical form of the L-2-norm, whereas the normal distribution can be obtained as a solution of differential entropy maximization subject to a constraint on the L-2-norm of a random variable. The L-1-norm and the double exponential (Laplace) distribution are related in a similar way. These are examples of an inter-regenerative relationship. In fact, L-2-norm and L-1-norm are ju...
-
作者：Shapiro, Alexander
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：In this paper we consider covariance structural models with which we associate semidefinite programming problems. We discuss statistical properties of estimates of the respective optimal value and optimal solutions when the 'true' covariance matrix is estimated by its sample counterpart. The analysis is based on perturbation theory of semidefinite programming. As an example we consider asymptotics of the so-called minimum trace factor analysis. We also discuss the minimum rank matrix completio...
-
作者：Range, Troels Martin; Osterdal, Lars Peter
作者单位：University of Southern Denmark; University of Southern Denmark; Norwegian University of Science & Technology (NTNU); Copenhagen Business School
摘要：How to determine whether one distribution first-order dominates another is a fundamental problem that has many applications in economics, finance, probability theory, and statistics. Nevertheless, little is known about how to efficiently check first-order dominance for finite multivariate distributions. Utilizing that this problem can be formulated as a transportation problem with a special structure, we provide a stronger characterization of multivariate first-order dominance and develop a li...
-
作者：Schmidt, Martin; Sirvent, Mathias; Wollner, Winnifried
作者单位：University of Erlangen Nuremberg; University of Erlangen Nuremberg; Technical University of Darmstadt
摘要：Many mixed-integer optimization problems are constrained by nonlinear functions that do not possess desirable analytical properties like convexity or factorability or cannot even be evaluated exactly. This is, e.g., the case for many problems constrained by differential equations or for models that rely on black-box simulation runs. For these problem classes, we present, analyze, and test algorithms that solve mixed-integer problems with Lipschitz continuous nonlinearities. Our theoretical res...
