-
作者：Gurbuzbalaban, M.; Ozdaglar, A.; Parrilo, P. A.
作者单位：Rutgers University System; Rutgers University New Brunswick; Massachusetts Institute of Technology (MIT)
摘要：We analyze the convergence rate of the random reshuffling (RR) method, which is a randomized first-order incremental algorithm for minimizing a finite sum of convex component functions. RR proceeds in cycles, picking a uniformly random order (permutation) and processing the component functions one at a time according to this order, i.e., at each cycle, each component function is sampled without replacement from the collection. Though RR has been numerically observed to outperform its with-repl...
-
作者：Gratton, S.; Simon, E.; Toint, Ph L.
作者单位：Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute of Physics (INP); Universite Federale Toulouse Midi-Pyrenees (ComUE); Institut National Polytechnique de Toulouse; University of Namur
摘要：An adaptive regularization algorithm using inexact function and derivatives evaluations is proposed for the solution of composite nonsmooth nonconvex optimization. It is shown that this algorithm needs at most O(| log(similar to)| similar to-2) evaluations of the problem's functions and their derivatives for finding an similar to-approximate first-order stationary point. This complexity bound therefore generalizes that provided by Bellavia et al. (Theoretical study of an adaptive cubic regular...
-
作者：Chen, Liang; Li, Xudong; Sun, Defeng; Toh, Kim-Chuan
作者单位：Hunan University; Hong Kong Polytechnic University; Fudan University; Fudan University; National University of Singapore; National University of Singapore
摘要：In this paper, we show that for a class of linearly constrained convex composite optimization problems, an (inexact) symmetric Gauss-Seidel based majorized multi-block proximal alternating direction method of multipliers (ADMM) is equivalent to an inexact proximal augmented Lagrangian method. This equivalence not only provides new perspectives for understanding some ADMM-type algorithms but also supplies meaningful guidelines on implementing them to achieve better computational efficiency. Eve...
-
作者：Lasserre, Jean B.
作者单位：Centre National de la Recherche Scientifique (CNRS)
摘要：We show that the global minimum (resp. maximum) of a continuous function on a compact set can be approximated from above (resp. from below) by computing the smallest (rest. largest) eigenvalue of a hierarchy of (r x r) tri-diagonal matrices of increasing size. Equivalently it reduces to computing the smallest (resp. largest) root of a certain univariate degree-r orthonormal polynomial. This provides a strong connection between the fields of optimization, orthogonal polynomials, numerical analy...
-
作者：Burachik, Regina S.; Kaya, C. Yalcin
作者单位：University of South Australia
摘要：The Steklov function mu(f)(., t) is defined to average a continuous function f at each point of its domain by using a window of size given by t > 0. It has traditionally been used to approximate f smoothly with small values of t. In this paper, we first find a concise and useful expression for mu(f) for the case when f is a multivariate quartic polynomial. Then we show that, for large enough t, mu(f)(., t) is convex; in other words, mu(f)(., t) convexifies f. We provide an easy-to-compute form...
-
作者：He, Taotao; Tawarmalani, Mohit
作者单位：Shanghai Jiao Tong University; Purdue University System; Purdue University
摘要：In this paper, we devise new relaxations for composite functions, which improve the prevalent factorable relaxations, without introducing additional variables, by exploiting the inner-function structure. We outer-approximate inner-functions using arbitrary under- and over-estimators and then convexify the outer-function over a polytopeP, which models the ordering relationships between the inner-functions and their estimators and utilizes bound information on the inner-functions as well as on t...
-
作者：Pu, Shi; Nedic, Angelia
作者单位：The Chinese University of Hong Kong, Shenzhen; Shenzhen Research Institute of Big Data; Arizona State University; Arizona State University-Tempe
摘要：In this paper, we study the problem of distributed multi-agent optimization over a network, where each agent possesses a local cost function that is smooth and strongly convex. The global objective is to find a common solution that minimizes the average of all cost functions. Assuming agents only have access to unbiased estimates of the gradients of their local cost functions, we consider a distributed stochastic gradient tracking method (DSGT) and a gossip-like stochastic gradient tracking me...
-
作者：Lourenco, Bruno F.
作者单位：University of Tokyo
摘要：We provide a framework for obtaining error bounds for linear conic problems without assuming constraint qualifications or regularity conditions. The key aspects of our approach are the notions of amenable cones and facial residual functions. For amenable cones, it is shown that error bounds can be expressed as a composition of facial residual functions. The number of compositions is related to the facial reduction technique and the singularity degree of the problem. In particular, we show that...
-
作者：Burer, Samuel; Ye, Yinyu
作者单位：University of Iowa; Stanford University
-
作者：Lasserre, Jean B.; Weisser, Tillmann
作者单位：Universite de Toulouse; Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; United States Department of Energy (DOE); Los Alamos National Laboratory; United States Department of Energy (DOE); Los Alamos National Laboratory
摘要：Given X. Rn, e. (0, 1), a parametrized family of probability distributions (mu a)a.A on similar to. Rp, we consider the feasible set X* e. X associated with the distributionally robust chance-constraint X* e = {x. X : Prob mu[ f (x,.) > 0] > 1 - e,. mu. Ma}, whereMa is the set of all possibles mixtures of distributions mu a, a. A. For instance and typically, the family Ma is the set of all mixtures of Gaussian distributions on R with mean and standard deviation a = (a, s) in some compact set A...
