-
作者：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...
-
作者：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 ...
