-
作者：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...
-
作者：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...
-
作者：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 ...
-
作者：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 ...
-
作者：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 ...
-
作者：Hang, Nguyen T. V.; Mordukhovich, Boris S.; Sarabi, M. Ebrahim
作者单位：Wayne State University; Vietnam Academy of Science & Technology (VAST); Peoples Friendship University of Russia; University System of Ohio; Miami University
摘要：The paper conducts a second-order variational analysis for an important class of nonpolyhedral conic programs generated by the so-called second-order/Lorentz/ice-cream cone Qis always twice epi-differentiable and apply this result to characterizing the uniqueness of Lagrange multipliers together with an error bound estimate in the general second-order cone programming setting involving twice differentiable data. On the other hand, we precisely calculate the graphical derivative of the normal c...
-
作者：Drori, Yoel; Taylor, Adrien B.
作者单位：Alphabet Inc.; Google Incorporated; Centre National de la Recherche Scientifique (CNRS); Universite PSL; Ecole Normale Superieure (ENS); Inria
摘要：We describe a novel constructive technique for devising efficient first-order methods for a wide range of large-scale convex minimization settings, including smooth, non-smooth, and strongly convex minimization. The technique builds upon a certain variant of the conjugate gradient method to construct a family of methods such that (a) all methods in the family share the same worst-case guarantee as the base conjugate gradient method, and (b) the family includes a fixed-step first-order method. ...
-
作者：Aliev, Iskander; Henk, Martin; Oertel, Timm
作者单位：Cardiff University; Technical University of Berlin
摘要：We give an optimal upper bound for the l(infinity)-distance from a vertex of a knapsack polyhedron to its nearest feasible lattice point. In a randomised setting, we show that the upper bound can be significantly improved on average. As a corollary, we obtain an optimal upper bound for the additive integrality gap of integer knapsack problems and show that the integrality gap of a typical knapsack problem is drastically smaller than the integrality gap that occurs in a worst case scenario. We ...
-
作者：Maehara, Takanori; Yamaguchi, Yutaro
作者单位：University of Osaka; RIKEN
摘要：We consider a stochastic variant of the packing-type integer linear programming problem, which contains random variables in the objective vector. We are allowed to reveal each entry of the objective vector by conducting a query, and the task is to find a good solution by conducting a small number of queries. We propose a general framework of adaptive and non-adaptive algorithms for this problem, and provide a unified methodology for analyzing the performance of those algorithms. We also demons...
-
作者：Apidopoulos, Vassilis; Aujol, Jean-Francois; Dossal, Charles
作者单位：Universite de Bordeaux; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI)
摘要：In this paper we study the convergence of an Inertial Forward-Backward algorithm, with a particular choice of an over-relaxation term. In particular we show that for a sequence of over-relaxation parameters, that do not satisfy Nesterov's rule, one can still expect some relatively fast convergence properties for the objective function. In addition we complement this work by studying the convergence of the algorithm in the case where the proximal operator is inexactly computed with the presence...
