-
作者：Wirth, Elias; Pena, Javier; Pokutta, Sebastian
作者单位：Technical University of Berlin; Carnegie Mellon University
-
作者：Vaisbourd, Yakov; Choksi, Rustum; Goodwin, Ariel; Hoheisel, Tim; Schonlieb, Carola-Bibiane
作者单位：McGill University; University of Cambridge
摘要：We explore a method of statistical estimation called Maximum Entropy on the Mean (MEM) which is based on an information-driven criterion that quantifies the compliance of a given point with a reference prior probability measure. At the core of this approach lies the MEM function which is a partial minimization of the Kullback-Leibler divergence over a linear constraint. In many cases, it is known that this function admits a simpler representation (known as the Cram & eacute;r rate function). V...
-
作者：Marumo, Naoki; Okuno, Takayuki; Takeda, Akiko
作者单位：University of Tokyo; Seikei University; RIKEN
摘要：Minimizing the sum of a convex function and a composite function appears in various fields. The generalized Levenberg-Marquardt (LM) method, also known as the prox-linear method, has been developed for such optimization problems. The method iteratively solves strongly convex subproblems with a damping term. This study proposes a new generalized LM method for solving the problem with a smooth composite function. The method enjoys three theoretical guarantees: iteration complexity bound, oracle ...
-
作者：Fujishige, Satoru; Kitahara, Tomonari; Vegh, Laszlo A.
作者单位：Kyoto University; Kyushu University; University of London; London School Economics & Political Science
摘要：We consider the minimum-norm-point (MNP) problem over polyhedra, a well-studied problem that encompasses linear programming. We present a general algorithmic framework that combines two fundamental approaches for this problem: active set methods and first order methods. Our algorithm performs first order update steps, followed by iterations that aim to 'stabilize' the current iterate with additional projections, i.e., find a locally optimal solution whilst keeping the current tight inequalitie...
-
作者：Boob, Digvijay; Deng, Qi; Lan, Guanghui
作者单位：Southern Methodist University; Shanghai Jiao Tong University; University System of Georgia; Georgia Institute of Technology
摘要：We present a new feasible proximal gradient method for constrained optimization where both the objective and constraint functions are given by summation of a smooth, possibly nonconvex function and a convex simple function. The algorithm converts the original problem into a sequence of convex subproblems. Formulating those subproblems requires the evaluation of at most one gradient-value of the original objective and constraint functions. Either exact or approximate subproblems solutions can b...
-
作者：Weninger, Noah; Fukasawa, Ricardo
作者单位：University of Waterloo
摘要：In the minimum spanning tree (MST) interdiction problem, we are given a graph G=(V,E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G=(V,E)$$\end{document} with edge weights, and want to find some X subset of E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage...
-
作者：Huang, Kun; Pu, Shi; Nedic, Angelia
作者单位：The Chinese University of Hong Kong, Shenzhen; Arizona State University; Arizona State University-Tempe
-
作者：Huang, Lei; Nie, Jiawang
作者单位：University of California System; University of California San Diego
摘要：This paper studies the matrix Moment-SOS hierarchy for solving polynomial matrix optimization. Our first result is to show the finite convergence of this hierarchy, if the nondegeneracy condition, strict complementarity condition and second order sufficient condition hold at every minimizer, under the Archimedean property. A useful criterion for detecting the finite convergence is the flat truncation. Our second result is to show that every minimizer of the moment relaxation must have a flat t...
-
作者：Das Gupta, Shuvomoy; Freund, Robert M.; Sun, Xu Andy; Taylor, Adrien
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Centre National de la Recherche Scientifique (CNRS); Universite PSL; Inria
摘要：We propose a computer-assisted approach to the analysis of the worst-case convergence of nonlinear conjugate gradient methods (NCGMs). Those methods are known for their generally good empirical performances for large-scale optimization, while having relatively incomplete analyses. Using our computer-assisted approach, we establish novel complexity bounds for the Polak-Ribi & egrave;re-Polyak (PRP) and the Fletcher-Reeves (FR) NCGMs for smooth strongly convex minimization. In particular, we con...
-
作者：Toint, Philippe L.
作者单位：University of Namur
摘要：The adaptive regularization algorithm for unconstrained nonconvex optimization was shown in [7, 20] to require, under standard assumptions, at most O(& varepsilon;(3/(3-q))) evaluations of the objective function and its derivatives of degrees one and two to produce an & varepsilon;-approximate critical point of order q is an element of{1,2}. This bound was shown to be sharp in [5, 6] for q=1 and in [11] for arbitrary q is an element of{1,2}. This note revisits these results and shows that the ...
