-
作者：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...
-
作者：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 ...
-
作者：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...
-
作者：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...
-
作者：Cornuejols, Gerard; Lee, Dabeen; Li, Yanjun
作者单位：Carnegie Mellon University; Purdue University System; Purdue University
摘要：We study the following problem: given a rational polytope with Chvatal rank 1, does it contain an integer point? Boyd and Pulleyblank observed that this problem is in the complexity class NP boolean AND\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\cap $$\end{document} co-NP, an indication that it is probably not...
-
作者：Buchbinder, Niv; Feldman, Moran; Filmus, Yuval; Garg, Mohit
作者单位：Tel Aviv University; Open University Israel; Technion Israel Institute of Technology; University of Haifa; Universita della Svizzera Italiana
摘要：The Submodular Welfare Maximization problem (SWM) captures an important subclass of combinatorial auctions and has been studied extensively. In particular, it has been studied in a natural online setting in which items arrive one-by-one and should be allocated irrevocably upon arrival. For this setting, Korula et al. (SIAM J Comput 47(3):1056-1086, 2018) were able to show that the greedy algorithm is 0.5052-competitive when the items arrive in a uniformly random order. Unfortunately, however, ...
-
作者：Yang, Wenzhuo; Sim, Melvyn; Xu, Huan
作者单位：National University of Singapore; National University of Singapore; University System of Georgia; Georgia Institute of Technology
摘要：Motivated by the binary classification problem in machine learning, we study in this paper a class of decision problems where the decision maker has a list of goals, from which he aims to attain the maximal possible number of goals. In binary classification, this essentially means seeking a prediction rule to achieve the lowest probability of misclassification, and computationally it involves minimizing a (difficult) non-convex, 0-1 loss function. To address the intractability, previous method...
