Mathematical Programming

最新文章

• 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 ...
• Second-order variational analysis in second-order cone programming AI翻译
  作者：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...
• Efficient first-order methods for convex minimization: a constructive approach AI翻译
  作者：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. ...
• Distances to lattice points in knapsack polyhedra AI翻译
  作者：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 ...
• Stochastic packing integer programs with few queries AI翻译
  作者：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...
• Minimizing buffered probability of exceedance by progressive hedging AI翻译
  作者：Rockafellar, R. Tyrrell; Uryasev, Stan
  作者单位：University of Washington; University of Washington Seattle; State University System of Florida; University of Florida
  摘要：Stochastic programming problems have for a long time been posed in terms of minimizing the expected value of a random variable influenced by decision variables, but alternative objectives can also be considered, such as minimizing a measure of risk. Here something different is introduced: minimizing the buffered probability of exceedance for a specified loss threshold. The buffered version of the traditional concept of probability of exceedance has recently been developed with many attractive ...
• Convergence rate of inertial Forward-Backward algorithm beyond Nesterov's rule AI翻译
  作者：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...
• Strong mixed-integer programming formulations for trained neural networks AI翻译
  作者：Anderson, Ross; Huchette, Joey; Ma, Will; Tjandraatmadja, Christian; Vielma, Juan Pablo
  作者单位：Alphabet Inc.; Google Incorporated; Rice University; Columbia University; Massachusetts Institute of Technology (MIT)
  摘要：We present strong mixed-integer programming (MIP) formulations for high-dimensional piecewise linear functions that correspond to trained neural networks. These formulations can be used for a number of important tasks, such as verifying that an image classification network is robust to adversarial inputs, or solving decision problems where the objective function is a machine learning model. We present a generic framework, which may be of independent interest, that provides a way to construct s...