1-2期

最新文章

• 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...
• 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 ...
• 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...
• A rank-corrected procedure for matrix completion with fixed basis coefficients AI翻译
  作者：Miao, Weimin; Pan, Shaohua; Sun, Defeng
  作者单位：National University of Singapore; South China University of Technology; National University of Singapore; National University of Singapore
  摘要：For the problems of low-rank matrix completion, the efficiency of the widely-used nuclear norm technique may be challenged under many circumstances, especially when certain basis coefficients are fixed, for example, the low-rank correlation matrix completion in various fields such as the financial market and the low-rank density matrix completion from the quantum state tomography. To seek a solution of high recovery quality beyond the reach of the nuclear norm, in this paper, we propose a rank...
• The submodular joint replenishment problem AI翻译
  作者：Cheung, Maurice; Elmachtoub, Adam N.; Levi, Retsef; Shmoys, David B.
  作者单位：Cornell University; Columbia University; Massachusetts Institute of Technology (MIT); Cornell University; Cornell University
  摘要：The joint replenishment problem is a fundamental model in supply chain management theory that has applications in inventory management, logistics, and maintenance scheduling. In this problem, there are multiple item types, each having a given time-dependent sequence of demands that need to be satisfied. In order to satisfy demand, orders of the item types must be placed in advance of the due dates for each demand. Every time an order of item types is placed, there is an associated joint setup ...
• Accelerated gradient methods for nonconvex nonlinear and stochastic programming AI翻译
  作者：Ghadimi, Saeed; Lan, Guanghui
  作者单位：State University System of Florida; University of Florida
  摘要：In this paper, we generalize the well-known Nesterov's accelerated gradient (AG) method, originally designed for convex smooth optimization, to solve nonconvex and possibly stochastic optimization problems. We demonstrate that by properly specifying the stepsize policy, the AG method exhibits the best known rate of convergence for solving general nonconvex smooth optimization problems by using first-order information, similarly to the gradient descent method. We then consider an important clas...