1期

最新文章

• On implicit function theorem for locally Lipschitz equations AI翻译
  作者：Arutyunov, Aram, V; Zhukovskiy, Sergey E.
  作者单位：V.A. Trapeznikov Institute of Control Sciences, Russian Academy of Sciences
  摘要：Equations defined by locally Lipschitz continuous mappings with a parameter are considered. Implicit function theorems for this equation are obtained. The regularity condition is formulated in the terms of the Clarke Jacobian. Implicit functions estimates are derived. It is shown that the considered regularity assumptions are weaker than most of the known ones. The obtained implicit function theorems are applied to derive conditions for upper semicontinuity of the optimal value function for pa...
• A globally convergent proximal Newton-type method in nonsmooth convex optimization AI翻译
  作者：Mordukhovich, Boris S.; Yuan, Xiaoming; Zeng, Shangzhi; Zhang, Jin
  作者单位：Wayne State University; University of Hong Kong; University of Victoria; Southern University of Science & Technology
  摘要：The paper proposes and justifies a new algorithm of the proximal Newton type to solve a broad class of nonsmooth composite convex optimization problems without strong convexity assumptions. Based on advanced notions and techniques of variational analysis, we establish implementable results on the global convergence of the proposed algorithm as well as its local convergence with superlinear and quadratic rates. For certain structured problems, the obtained local convergence conditions do not re...
• A duality based 2-approximation algorithm for maximum agreement forest AI翻译
  作者：Olver, Neil; Schalekamp, Frans; van der Ster, Suzanne; Stougie, Leen; van Zuylen, Anke
  作者单位：University of London; London School Economics & Political Science; Cornell University; Cornell University; Vrije Universiteit Amsterdam
  摘要：We give a 2-approximation algorithm for the Maximum Agreement Forest problem on two rooted binary trees. This NP-hard problem has been studied extensively in the past two decades, since it can be used to compute the rooted Subtree Prune-and-Regraft (rSPR) distance between two phylogenetic trees. Our algorithm is combinatorial and its running time is quadratic in the input size. To prove the approximation guarantee, we construct a feasible dual solution for a novel exponential-size linear progr...
• Perturbed Fenchel duality and first-order methods AI翻译
  作者：Gutman, David H.; Pena, Javier F.
  作者单位：Texas Tech University System; Texas Tech University; Carnegie Mellon University
  摘要：We show that the iterates generated by a generic first-order meta-algorithm satisfy a canonical perturbed Fenchel duality inequality. The latter in turn readily yields a unified derivation of the best known convergence rates for various popular first-order algorithms including the conditional gradient method as well as the main kinds of Bregman proximal methods: subgradient, gradient, fast gradient, and universal gradient methods.
• Sparse PCA on fixed-rank matrices AI翻译
  作者：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 ...
• On the optimality of pseudo-polynomial algorithms for integer programming AI翻译
  作者：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]...
• Affine-invariant contracting-point methods for Convex Optimization AI翻译
  作者：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...
• Multicriteria cuts and size-constrained k-cuts in hypergraphs AI翻译
  作者：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)...
• Inexact accelerated high-order proximal-point methods AI翻译
  作者：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...
• Homogenization for polynomial optimization with unbounded sets AI翻译
  作者：Huang, Lei; Nie, Jiawang; Yuan, Ya-Xiang
  作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; University of California System; University of California San Diego
  摘要：This paper considers polynomial optimization with unbounded sets. We give a homogenization formulation and propose a hierarchy of Moment-SOS relaxations to solve it. Under the assumptions that the feasible set is closed at infinity and the ideal of homogenized equality constraining polynomials is real radical, we show that this hierarchy of Moment-SOS relaxations has finite convergence, if some optimality conditions (i.e., the linear independence constraint qualification, strict complementarit...