-
作者：Andreani, Roberto; Haeser, Gabriel; Mito, Leonardo M.; Ramirez, Hector; Silveira, Thiago P.
作者单位：Universidade Estadual de Campinas; Universidade de Sao Paulo; Universidad de Chile; Universidad de Chile
摘要：The well known constant rank constraint qualification [Math. Program. Study 21:110-126, 1984] introduced by Janin for nonlinear programming has been recently extended to a conic context by exploiting the eigenvector structure of the problem. In this paper we propose a more general and geometric approach for defining a new extension of this condition to the conic context. The main advantage of our approach is that we are able to recast the strong second-order properties of the constant rank con...
-
作者：Oliveira, Roberto I.; Thompson, Philip
作者单位：Purdue University System; Purdue University
摘要：Localization has proven to be a valuable tool in the Statistical Learning literature as it allows sharp risk bounds in terms of the problem geometry. Localized bounds seem to be much less exploited in the stochastic optimization literature. In addition, there is an obvious interest in both communities in obtaining risk bounds that require weak moment assumptions or heavier-tails. In this work we use a localization toolbox to derive risk bounds in two specific applications. The first is in port...
-
作者：Malitsky, Yura; Tam, Matthew K. K.
作者单位：Linkoping University; University of Melbourne
摘要：In this work, we study fixed point algorithms for finding a zero in the sum of n >= 2 maximally monotone operators by using their resolvents. More precisely, we consider the class of such algorithms where each resolvent is evaluated only once per iteration. For any algorithm from this class, we show that the underlying fixed point operator is necessarily defined on a d-fold Cartesian product space with d >= n - 1. Further, we show that this bound is unimprovable by providing a family of exampl...
-
作者：Del Pia, Alberto
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
摘要：In this paper, we give an algorithm that finds an e-approximate solution to a mixed integer quadratic programming (MIQP) problem. The algorithm runs in polynomial time if the rank of the quadratic function and the number of integer variables are fixed. The running time of the algorithm is expected unless P=NP. In order to design this algorithm we introduce the novel concepts of spherical form MIQP and of aligned vectors, and we provide a number of results of independent interest. In particular...
-
作者：Baldi, Lorenzo; Mourrain, Bernard
作者单位：Universite Cote d'Azur
摘要：We analyse the representation of positive polynomials in terms of Sums of Squares. We provide a quantitative version of Putinar's Positivstellensatz over a compact basic semialgebraic set S, with a new polynomial bound on the degree of the positivity certificates. This bound involves a Lojasiewicz exponent associated to the description of S. We show that if the gradients of the active constraints are linearly independent on S (Constraint Qualification condition), this Lojasiewicz exponent is e...
-
作者：Dvurechensky, Pavel; Safin, Kamil; Shtern, Shimrit; Staudigl, Mathias
作者单位：Leibniz Association; Weierstrass Institute for Applied Analysis & Stochastics; Moscow Institute of Physics & Technology; Technion Israel Institute of Technology; Maastricht University
摘要：Projection-free optimization via different variants of the Frank-Wolfe method has become one of the cornerstones of large scale optimization for machine learning and computational statistics. Numerous applications within these fields involve the minimization of functions with self-concordance like properties. Such generalized self-concordant functions do not necessarily feature a Lipschitz continuous gradient, nor are they strongly convex, making them a challenging class of functions for first...
-
作者：Bareilles, Gilles; Iutzeler, Franck; Malick, Jerome
作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
摘要：Proximal methods are known to identify the underlying substructure of nonsmooth optimization problems. Even more, in many interesting situations, the output of a proximity operator comes with its structure at no additional cost, and convergence is improved once it matches the structure of a minimizer. However, it is impossible in general to know whether the current structure is final or not; such highly valuable information has to be exploited adaptively. To do so, we place ourselves in the ca...
-
作者：Levin, Eitan; Kileel, Joe; Boumal, Nicolas
作者单位：California Institute of Technology; University of Texas System; University of Texas Austin; University of Texas System; University of Texas Austin; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：We consider the problem of provably finding a stationary point of a smooth function to be minimized on the variety of bounded-rank matrices. This turns out to be unexpectedly delicate. We trace the difficulty back to a geometric obstacle: On a nonsmooth set, there may be sequences of points along which standard measures of stationarity tend to zero, but whose limit points are not stationary. We name such events apocalypses, as they can cause optimization algorithms to converge to non-stationar...
-
作者：Pablo Contreras, Juan; Cominetti, Roberto
作者单位：Universidad Adolfo Ibanez
摘要：This paper investigates optimal error bounds and convergence rates for general Mann iterations for computing fixed-points of non-expansive maps. We look for iterations that achieve the smallest fixed-point residual after n steps, by minimizing a worst-case bound parallel to x(n) - Tx(n)parallel to <= R-n derived from a nested family of optimal transport problems. We prove that this bound is tight so that minimizing R-n yields optimal iterations. Inspired from numerical results we identify iter...
-
作者：Zhao, Renbo; Freund, Robert M.
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：We present and analyze a new generalized Frank-Wolfe method for the composite optimization problem (P) : min(x is an element of)(Rn) f (Ax) + h (x), where f is a theta-logarithmically-homogeneous self-concordant barrier, A is a linear operator and the function h has a bounded domain but is possibly non-smooth. We show that our generalized Frank-Wolfe method requires O((delta(0) + theta + R-h) ln(delta(0)) + (theta + R-h)(2)/epsilon) iterations to produce an epsilon-approximate solution, where ...
