-
作者：Del Pia, Alberto
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
摘要：Sparse PCA is the optimization problem obtained from PCA by adding a sparsity constraint on the principal components. Sparse PCA is NP-hard and hard to approximate even in the single-component case. In this paper we settle the computational complexity of sparse PCA with respect to the rank of the covariance matrix. We show that, if the rank of the covariance matrix is a fixed value, then there is an algorithm that solves sparse PCA to global optimality, whose running time is polynomial in the ...
-
作者：Jiang, Jie; Chen, Xiaojun
作者单位：Chongqing University; Hong Kong Polytechnic University
摘要：We formulate pure characteristics demand models under uncertainties of probability distributions as distributionally robust mathematical programs with stochastic complementarity constraints (DRMP-SCC). For any fixed first-stage variable and a random realization, the second-stage problem of DRMP-SCC is a monotone linear complementarity problem (LCP). To deal with ambiguity of probability distributions of the involved random variables in the stochastic LCP, we use the distributionally robust app...
-
作者：Fomin, Fedor, V; Panolan, Fahad; Ramanujan, M. S.; Saurabh, Saket
作者单位：University of Bergen; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Hyderabad; University of Warwick; Homi Bhabha National Institute; Institute of Mathematical Sciences (IMSc) India
摘要：In the classic Integer Programming Feasibility (IPF) problem, the objective is to decide whether, for a given m x n matrix A and an m-vector b = (b(1) ..... b(m) ), there is a non-negative integer n-vector x such that Ax = b. Solving (IPF) is an important step in numerous algorithms and it is important to obtain an understanding of the precise complexity of this problem as a function of natural parameters of the input. The classic pseudo-polynomial time algorithm of Papadimitriou [J. ACM 1981]...
-
作者：Doikov, Nikita; Nesterov, Yurii
摘要：In this paper, we develop new affine-invariant algorithms for solving composite convex minimization problems with bounded domain. We present a general framework of Contracting-Point methods, which solve at each iteration an auxiliary subproblem restricting the smooth part of the objective function onto contraction of the initial domain. This framework provides us with a systematic way for developing optimization methods of different order, endowed with the global complexity bounds. We show tha...
-
作者：Rehfeldt, Daniel; Koch, Thorsten
作者单位：Zuse Institute Berlin; Technical University of Berlin
摘要：The Steiner tree problem in graphs (SPG) is one of the most studied problems in combinatorial optimization. In the past 10 years, there have been significant advances concerning approximation and complexity of the SPG. However, the state of the art in (practical) exact solution of the SPG has remained largely unchallenged for almost 20 years. While the DIMACS Challenge 2014 and the PACE Challenge 2018 brought renewed interest into Steiner tree problems, even the best new SPG solvers cannot mat...
-
作者：Beideman, Calvin; Chandrasekaran, Karthekeyan; Xu, Chao
作者单位：University of Illinois System; University of Illinois Urbana-Champaign
摘要：We address counting and optimization variants of multicriteria global min-cut and size-constrained min-k-cut in hypergraphs. 1. For an r-rank n-vertex hypergraph endowed with t hyperedge-cost functions, we show that the number of multiobjective min-cuts is O(r2(tr) n(3t-1)). In particular, this shows that the number of parametric min-cuts in constant rank hypergraphs for a constant number of criteria is strongly polynomial, thus resolving an open question by Aissi et al. (Math Program 154(1-2)...
-
作者：Nesterov, Yurii
摘要：In this paper, we present a new framework of bi-level unconstrained minimization for development of accelerated methods in Convex Programming. These methods use approximations of the high-order proximal points, which are solutions of some auxiliary parametric optimization problems. For computing these points, we can use different methods, and, in particular, the lower-order schemes. This opens a possibility for the latter methods to overpass traditional limits of the Complexity Theory. As an e...
-
作者：Josz, Cedric
作者单位：Columbia University
摘要：We consider the gradient method with variable step size for minimizing functions that are definable in o-minimal structures on the real field and differentiable with locally Lipschitz gradients. We prove that global convergence holds if continuous gradient trajectories are bounded, with the minimum gradient norm vanishing at the rate o(1/k) if the step sizes are greater than a positive constant. If additionally the gradient is continuously differentiable, all saddle points are strict, and the ...
-
作者：De Rosa, Antonio; Khajavirad, Aida
作者单位：University System of Maryland; University of Maryland College Park; Lehigh University
摘要：Joint object matching, also known as multi-image matching, namely, the problem of finding consistent partial maps among all pairs of objects within a collection, is a crucial task in many areas of computer vision. This problem subsumes bipartite graph matching and graph partitioning as special cases and is NP-hard, in general. We develop scalable linear programming (LP) relaxations with theoretical performance guarantees for joint object matching. We start by proposing a new characterization o...
-
作者：Yu, Qimeng; Kucukyavuz, Simge
作者单位：Northwestern University
摘要：We study the polyhedral convex hull structure of a mixed-integer set which arises in a class of cardinality-constrained concave submodular minimization problems. This class of problems has an objective function in the form of f (alpha(T)x), where f is a univariate concave function, a is a non-negative vector, and x is a binary vector of appropriate dimension. Such minimization problems frequently appear in applications that involve risk-aversion or economies of scale. We propose three classes ...
