2020

最新文章

• Risk forms: representation, disintegration, and application to partially observable two-stage systems AI翻译
  作者：Dentcheva, Darinka; Ruszczynski, Andrzej
  作者单位：Stevens Institute of Technology; Rutgers University System; Rutgers University New Brunswick
  摘要：We introduce the concept of a risk form, which is a real functional of two arguments: a measurable function on a Polish space and a measure on that space. We generalize the duality theory and the Kusuoka representation to this setting. For a risk form acting on a product of Polish spaces, we define marginal and conditional forms and we prove a disintegration formula, which represents a risk form as a composition of its marginal and conditional forms. We apply the proposed approach to two-stage...
• Applying FISTA to optimization problems (with or) without minimizers AI翻译
  作者：Bauschke, Heinz H.; Bui, Minh N.; Wang, Xianfu
  作者单位：University of British Columbia; North Carolina State University
  摘要：Beck and Teboulle's FISTA method for finding a minimizer of the sum of two convex functions, one of which has a Lipschitz continuous gradient whereas the other may be nonsmooth, is arguably the most important optimization algorithm of the past decade. While research activity on FISTA has exploded ever since, the mathematically challenging case when the original optimization problem has no minimizer has found only limited attention. In this work, we systematically study FISTA and its variants. ...
• Asynchronous parallel algorithms for nonconvex optimization AI翻译
  作者：Cannelli, Loris; Facchinei, Francisco; Kungurtsev, Vyacheslav; Scutari, Gesualdo
  作者单位：Purdue University System; Purdue University; Sapienza University Rome; Czech Technical University Prague
  摘要：We propose a new asynchronous parallel block-descent algorithmic framework for the minimization of the sum of a smooth nonconvex function and a nonsmooth convex one, subject to both convex and nonconvex constraints. The proposed framework hinges on successive convex approximation techniques and a novel probabilistic model that captures key elements of modern computational architectures and asynchronous implementations in a more faithful way than current state-of-the-art models. Other key featu...
• Martingale characterizations of risk-averse stochastic optimization problems AI翻译
  作者：Pichler, Alois; Schlotter, Ruben
  作者单位：Technische Universitat Chemnitz
  摘要：This paper addresses risk awareness of stochastic optimization problems. Nested risk measures appear naturally in this context, as they allow beneficial reformulations for algorithmic treatments. The reformulations presented extend usual dynamic equations by involving risk awareness in the problem formulation. Nested risk measures are built on risk measures, which originate by conditioning on the history of a stochastic process. We derive martingale properties of these risk measures and use th...
• Packing of arborescences with matroid constraints via matroid intersection AI翻译
  作者：Kiraly, Csaba; Szigeti, Zoltan; Tanigawa, Shin-ichi
  作者单位：Eotvos Lorand University; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); University of Tokyo
  摘要：Edmonds' arborescence packing theorem characterizes directed graphs that have arc-disjoint spanning arborescences in terms of connectivity. Later he also observed a characterization in terms of matroid intersection. Since these fundamental results, intensive research has been done for understanding and extending these results. In this paper we shall extend the second characterization to the setting of reachability-based packing of arborescences. The reachability-based packing problem was intro...
• Varying confidence levels for CVaR risk measures and minimax limits AI翻译
  作者：Anderson, Edward; Xu, Huifu; Zhang, Dali
  作者单位：University of Sydney; University of Southampton; Shanghai Jiao Tong University
  摘要：Conditional value at risk (CVaR) has been widely studied as a risk measure. In this paper we add to this work by focusing on the choice of confidence level and its impact on optimization problems with CVaR appearing in the objective and also the constraints. We start by considering a problem in which CVaR is minimized and investigate the way in which it approximates the minimax robust optimization problem as the confidence level is driven to one. We make use of a consistent tail condition whic...
• A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization AI翻译
  作者：Royer, Clement W.; O'Neill, Michael; Wright, Stephen J.
  作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
  摘要：We consider minimization of a smooth nonconvex objective function using an iterative algorithm based on Newton's method and the linear conjugate gradient algorithm, with explicit detection and use of negative curvature directions for the Hessian of the objective function. The algorithm tracks Newton-conjugate gradient procedures developed in the 1980s closely, but includes enhancements that allow worst-case complexity results to be proved for convergence to points that satisfy approximate firs...
• Newton-type methods for non-convex optimization under inexact Hessian information AI翻译
  作者：Xu, Peng; Roosta, Fred; Mahoney, Michael W.
  作者单位：Stanford University; University of Queensland; University of California System; University of California Berkeley
  摘要：We consider variants of trust-region and adaptive cubic regularization methods for non-convex optimization, in which the Hessian matrix is approximated. Under certain condition on the inexact Hessian, and using approximate solution of the corresponding sub-problems, we provide iteration complexity to achieve epsilon-approximate second-order optimality which have been shown to be tight. Our Hessian approximation condition offers a range of advantages as compared with the prior works and allows ...
• Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis AI翻译
  作者：Zhang, Junyu; Ma, Shiqian; Zhang, Shuzhong
  作者单位：University of Minnesota System; University of Minnesota Twin Cities; University of California System; University of California Davis; The Chinese University of Hong Kong, Shenzhen
  摘要：In this paper we study nonconvex and nonsmooth multi-block optimization over Euclidean embedded (smooth) Riemannian submanifolds with coupled linear constraints. Such optimization problems naturally arise from machine learning, statistical learning, compressive sensing, image processing, and tensor PCA, among others. By utilizing the embedding structure, we develop an ADMM-like primal-dual approach based on decoupled solvable subroutines such as linearized proximal mappings, where the duality ...
• The multiproximal linearization method for convex composite problems AI翻译
  作者：Bolte, Jerome; Chen, Zheng; Pauwels, Edouard
  作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Zhejiang University
  摘要：Composite minimization involves a collection of smooth functions which are aggregated in a nonsmooth manner. In the convex setting, we design an algorithm by linearizing each smooth component in accordance with its main curvature. The resulting method, called the Multiprox method, consists in solving successively simple problems (e.g., constrained quadratic problems) which can also feature some proximal operators. To study the complexity and the convergence of this method, we are led to prove ...