-
作者：Chen, Yin; Dang, Chuangyin
作者单位：City University of Hong Kong
摘要：The notion of perfect equilibrium was formulated by Selten (Int J Game Theory 4(1):25-55, 1975) as a strict refinement of Nash equilibrium. For an extensive-form game with perfect recall, every perfect equilibrium of its agent normal-form game yields a perfect equilibrium of the extensive-form game. This paper aims to develop a differentiable homotopy method for computing perfect equilibria of normal-form games. To accomplish this objective, we constitute an artificial game by introducing a co...
-
作者：Huerga, L.; Jimenez, B.; Luc, D. T.; Novo, V.
作者单位：Universidad Nacional de Educacion a Distancia (UNED); Ton Duc Thang University; Ton Duc Thang University
摘要：In this paper, we introduce some new notions of quasi efficiency and quasi proper efficiency for multiobjective optimization problems that reduce to the most important concepts of approximate and quasi efficient solutions given up to now. We establish main properties and provide characterizations for these solutions by linear and nonlinear scalarizations. With the help of quasi efficient solutions, a generalized subdifferential of a vector mapping is introduced, which generates a number of app...
-
作者：Gutman, David H.; Pena, Javier F.
作者单位：Texas Tech University System; Texas Tech University; Carnegie Mellon University
摘要：The condition number of a differentiable convex function, namely the ratio of its smoothness to strong convexity constants, is closely tied to fundamental properties of the function. In particular, the condition number of a quadratic convex function is the square of the aspect ratio of a canonical ellipsoid associated to the function. Furthermore, the condition number of a function bounds the linear rate of convergence of the gradient descent algorithm for unconstrained convex minimization. We...
-
作者：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...
