-
作者：Morshed, Md Sarowar; Islam, Md Saiful; Noor-E-Alam, Md.
作者单位：Northeastern University
摘要：Randomized Kaczmarz, Motzkin Method and Sampling Kaczmarz Motzkin (SKM) algorithms are commonly used iterative techniques for solving a system of linear inequalities (i.e., Ax <= b). As linear systems of equations represent a modeling paradigm for solving many optimization problems, these randomized and iterative techniques are gaining popularity among researchers in different domains. In this work, we propose a Generalized Sampling Kaczmarz Motzkin (GSKM) method that unifies the iterative met...
-
作者：Huang, Wen; Wei, Ke
作者单位：Xiamen University; Fudan University
摘要：In the Euclidean setting the proximal gradient method and its accelerated variants are a class of efficient algorithms for optimization problems with decomposable objective. In this paper, we develop a Riemannian proximal gradient method (RPG) and its accelerated variant (ARPG) for similar problems but constrained on a manifold. The global convergence of RPG is established under mild assumptions, and the O(1/k) is also derived for RPG based on the notion of retraction convexity. If assuming th...
-
作者：Muir, Christopher; Toriello, Alejandro
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：We propose a dynamic version of the classical node packing problem, also called the stable set or independent set problem. The problem is defined by a node set, a node weight vector, and an edge probability vector. For every pair of nodes, an edge is present or not according to an independent Bernoulli random variable defined by the corresponding entry in the probability vector. At each step, the decision maker selects an available node that maximizes the expected weight of the final packing, ...
-
作者：Yu, Xian; Shen, Siqian
作者单位：University of Michigan System; University of Michigan
摘要：We study multistage distributionally robust mixed-integer programs under endogenous uncertainty, where the probability distribution of stage-wise uncertainty depends on the decisions made in previous stages. We first consider two ambiguity sets defined by decision-dependent bounds on the first and second moments of uncertain parameters and by mean and covariance matrix that exactly match decision-dependent empirical ones, respectively. For both sets, we show that the subproblem in each stage c...
-
作者：Harks, Tobias; Tan-Timmermans, Veerle
作者单位：RWTH Aachen University
-
作者：Fuellner, Christian; Rebennack, Steffen
作者单位：Helmholtz Association; Karlsruhe Institute of Technology
摘要：We propose a new decomposition method to solve multistage non-convex mixedinteger (stochastic) nonlinear programming problems (MINLPs). We call this algorithm non-convex nested Benders decomposition (NC-NBD). NC-NBD is based on solving dynamically improved mixed-integer linear outer approximations of the MINLP, obtained by piecewise linear relaxations of nonlinear functions. Those MILPs are solved to global optimality using an enhancement of nested Benders decomposition, in which regularizatio...
-
作者：Barman, Siddharth; Fawzi, Omar; Ghoshal, Suprovat; Gurpinar, Emirhan
作者单位：Indian Institute of Science (IISC) - Bangalore; Ecole Normale Superieure de Lyon (ENS de LYON); Inria; Centre National de la Recherche Scientifique (CNRS)
摘要：In the classic maximum coverage problem, we are given subsets T-1,..., T-m of a universe [n] along with an integer k and the objective is to find a subset S subset of [m] of size k that maximizes C(S) := vertical bar boolean OR(i is an element of S) T-i vertical bar. It is well-known that the greedy algorithm for this problem achieves an approximation ratio of (1- e(-1)) and there is a matching inapproximability result. We note that in themaximum coverage problem if an element e is an element ...
-
作者：Paat, Joseph; Schloeter, Miriam; Weismantel, Robert
作者单位：University of British Columbia; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：We introduce the integrality number of an integer program (IP). Roughly speaking, the integrality number is the smallest number of integer constraints needed to solve an IP via a mixed integer (MIP) relaxation. One notable property of this number is its invariance under unimodular transformations of the constraint matrix. Considering the largest minor Delta of the constraint matrix, our analysis allows us to make statements of the following form: there exists a number tau(Delta) such that an I...
-
作者：Dahl, Joachim; Andersen, Erling D.
摘要：A new primal-dual interior-point algorithm applicable to nonsymmetric conic optimization is proposed. It is a generalization of the famous algorithm suggested by Nesterov and Todd for the symmetric conic case, and uses primal-dual scalings for nonsymmetric cones proposed by Tuncel. We specialize Tuncel's primal-dual scalings for the important case of 3 dimensional exponential-cones, resulting in a practical algorithm with good numerical performance, on level with standard symmetric cone (e.g.,...
-
作者：Gupta, Anupam; Kumar, Amit; Nagarajan, Viswanath; Shen, Xiangkun
作者单位：Carnegie Mellon University; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Delhi; University of Michigan System; University of Michigan; Yahoo! Inc
摘要：We study stochastic combinatorial optimization problems where the objective is to minimize the expected maximum load (a.k.a. the makespan). In this framework, we have a set of n tasks and m resources, where each task j uses some subset of the resources. Tasks have random sizes X-j, and our goal is to non-adaptively select t tasks to minimize the expected maximum load over all resources, where the load on any resource i is the total size of all selected tasks that use i. For example, when resou...
