2016

最新文章

• 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...
• A deterministic rescaled perceptron algorithm AI翻译
  作者：Pena, Javier; Soheili, Negar
  作者单位：Carnegie Mellon University; University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital
  摘要：The perceptron algorithm is a simple iterative procedure for finding a point in a convex cone . At each iteration, the algorithm only involves a query to a separation oracle for and a simple update on a trial solution. The perceptron algorithm is guaranteed to find a point in after iterations, where is the width of the cone . We propose a version of the perceptron algorithm that includes a periodic rescaling of the ambient space. In contrast to the classical version, our rescaled version finds...
• Constraint aggregation for rigorous global optimization AI翻译
  作者：Domes, Ferenc; Neumaier, Arnold
  作者单位：University of Vienna
  摘要：In rigorous constrained global optimization, upper bounds on the objective function help to reduce the search space. Obtaining a rigorous upper bound on the objective requires finding a narrow box around an approximately feasible solution, which then must be verified to contain a feasible point. Approximations are easily found by local optimization, but the verification often fails. In this paper we show that even when the verification of an approximate feasible point fails, the information ex...
• New analysis and results for the Frank-Wolfe method AI翻译
  作者：Freund, Robert M.; Grigas, Paul
  作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
  摘要：We present new results for the Frank-Wolfe method (also known as the conditional gradient method). We derive computational guarantees for arbitrary step-size sequences, which are then applied to various step-size rules, including simple averaging and constant step-sizes. We also develop step-size rules and computational guarantees that depend naturally on the warm-start quality of the initial (and subsequent) iterates. Our results include computational guarantees for both duality/bound gaps an...