Mathematical Programming

最新文章

• On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree AI翻译
  作者：Feldmann, Andreas Emil; Konemann, Jochen; Olver, Neil; Sanita, Laura
  作者单位：University of Waterloo; Hungarian Academy of Sciences; HUN-REN; HUN-REN Institute for Computer Science & Control; Charles University Prague; Vrije Universiteit Amsterdam; Centrum Wiskunde & Informatica (CWI)
  摘要：The bottleneck of the currently best -approximation algorithm for the NP-hard Steiner tree problem is the solution of its large, so called hypergraphic, linear programming relaxation (HYP). Hypergraphic LPs are strongly NP-hard to solve exactly, and it is a formidable computational task to even approximate them sufficiently well. We focus on another well-studied but poorly understood LP relaxation of the problem: the bidirected cut relaxation (BCR). This LP is compact, and can therefore be sol...
• Sparse solutions of linear complementarity problems AI翻译
  作者：Chen, Xiaojun; Xiang, Shuhuang
  作者单位：Hong Kong Polytechnic University; Central South University
  摘要：This paper considers the characterization and computation of sparse solutions and least-p-norm solutions of the linear complementarity problem . We show that the number of non-zero entries of any least-p-norm solution of the is less than or equal to the rank of M for any arbitrary matrix M and any number , and there is such that all least-p-norm solutions for are sparse solutions. Moreover, we provide conditions on M such that a sparse solution can be found by solving convex minimization. Appl...
• Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems AI翻译
  作者：Li, Guoyin; Pong, Ting Kei
  作者单位：University of New South Wales Sydney; Hong Kong Polytechnic University
  摘要：We adapt the Douglas-Rachford (DR) splitting method to solve nonconvex feasibility problems by studying this method for a class of nonconvex optimization problem. While the convergence properties of the method for convex problems have been well studied, far less is known in the nonconvex setting. In this paper, for the direct adaptation of the method to minimize the sum of a proper closed function g and a smooth function f with a Lipschitz continuous gradient, we show that if the step-size par...
• Exact quadratic convex reformulations of mixed-integer quadratically constrained problems AI翻译
  作者：Billionnet, Alain; Elloumi, Sourour; Lambert, Amelie
  作者单位：Ecole Nationale Superieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE); heSam Universite; Conservatoire National Arts & Metiers (CNAM)
  摘要：We propose a solution approach for the general problem (QP) of minimizing a quadratic function of bounded integer variables subject to a set of quadratic constraints. The resolution is based on the reformulation of the original problem (QP) into an equivalent quadratic problem whose continuous relaxation is convex, so that it can be effectively solved by a branch-and-bound algorithm based on quadratic convex relaxation. We concentrate our efforts on finding a reformulation such that the contin...
• A game-theoretic approach to computation offloading in mobile cloud computing AI翻译
  作者：Cardellini, Valeria; Persone, Vittoria De Nitto; Di Valerio, Valerio; Facchinei, Francisco; Grassi, Vincenzo; Lo Presti, Francesco; Piccialli, Veronica
  作者单位：University of Rome Tor Vergata; Sapienza University Rome; Sapienza University Rome
  摘要：We consider a three-tier architecture for mobile and pervasive computing scenarios, consisting of a local tier of mobile nodes, a middle tier (cloudlets) of nearby computing nodes, typically located at the mobile nodes access points but characterized by a limited amount of resources, and a remote tier of distant cloud servers, which have practically infinite resources. This architecture has been proposed to get the benefits of computation offloading from mobile nodes to external servers while ...
• Minimum cardinality non-anticipativity constraint sets for multistage stochastic programming AI翻译
  作者：Boland, Natashia; Dumitrescu, Irina; Froyland, Gary; Kalinowski, Thomas
  作者单位：University of Newcastle; International Business Machines (IBM); IBM Australia; IBM Research - Australia; University of Melbourne; University of New South Wales Sydney; University of Newcastle; University System of Georgia; Georgia Institute of Technology
  摘要：We consider multistage stochastic programs, in which decisions can adapt over time, (i.e., at each stage), in response to observation of one or more random variables (uncertain parameters). The case that the time at which each observation occurs is decision-dependent, known as stochastic programming with endogeneous observation of uncertainty, presents particular challenges in handling non-anticipativity. Although such stochastic programs can be tackled by using binary variables to model the t...
• Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm AI翻译
  作者：Needell, Deanna; Srebro, Nathan; Ward, Rachel
  作者单位：Claremont Colleges; Claremont Graduate University; Claremont McKenna College; Toyota Technological Institute - Chicago; University of Texas System; University of Texas Austin
  摘要：We obtain an improved finite-sample guarantee on the linear convergence of stochastic gradient descent for smooth and strongly convex objectives, improving from a quadratic dependence on the conditioning (where is a bound on the smoothness and on the strong convexity) to a linear dependence on . Furthermore, we show how reweighting the sampling distribution (i.e. importance sampling) is necessary in order to further improve convergence, and obtain a linear dependence in the average smoothness,...
• A polyhedral study of production ramping AI翻译
  作者：Damci-Kurt, Pelin; Kucukyavuz, Simge; Rajan, Deepak; Atamturk, Alper
  作者单位：University System of Ohio; Ohio State University; United States Department of Energy (DOE); Lawrence Livermore National Laboratory; University of California System; University of California Berkeley
  摘要：We give strong formulations of ramping constraints-used to model the maximum change in production level for a generator or machine from one time period to the next-and production limits. For the two-period case, we give a complete description of the convex hull of the feasible solutions. The two-period inequalities can be readily used to strengthen ramping formulations without the need for separation. For the general case, we define exponential classes of multi-period variable upper bound and ...
• Decomposition algorithms for two-stage chance-constrained programs AI翻译
  作者：Liu, Xiao; Kucukyavuz, Simge; Luedtke, James
  作者单位：University System of Ohio; Ohio State University; University of Wisconsin System; University of Wisconsin Madison
  摘要：We study a class of chance-constrained two-stage stochastic optimization problems where second-stage feasible recourse decisions incur additional cost. In addition, we propose a new model, where recovery decisions are made for the infeasible scenarios to obtain feasible solutions to a relaxed second-stage problem. We develop decomposition algorithms with specialized optimality and feasibility cuts to solve this class of problems. Computational results on a chance-constrained resource planing p...
• The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent AI翻译
  作者：Chen, Caihua; He, Bingsheng; Ye, Yinyu; Yuan, Xiaoming
  作者单位：Nanjing University; Nanjing University; Stanford University; Hong Kong Baptist University
  摘要：The alternating direction method of multipliers (ADMM) is now widely used in many fields, and its convergence was proved when two blocks of variables are alternatively updated. It is strongly desirable and practically valuable to extend the ADMM directly to the case of a multi-block convex minimization problem where its objective function is the sum of more than two separable convex functions. However, the convergence of this extension has been missing for a long time-neither an affirmative co...