2017

最新文章

• Cutting planes from extended LP formulations AI翻译
  作者：Bodur, Merve; Dash, Sanjeeb; Gunluk, Oktay
  作者单位：University System of Georgia; Georgia Institute of Technology; International Business Machines (IBM); IBM USA
  摘要：Given a mixed-integer set defined by linear inequalities and integrality requirements on some of the variables, we consider extended formulations of its continuous (LP) relaxation and study the effect of adding cutting planes in the extended space. In terms of optimization, extended LP formulations do not lead to better bounds as their projection onto the original space is precisely the original LP relaxation. However, adding cutting planes in the extended space can lead to stronger bounds. In...
• Smooth strongly convex interpolation and exact worst-case performance of first-order methods AI翻译
  作者：Taylor, Adrien B.; Hendrickx, Julien M.; Glineur, Francois
  作者单位：Universite Catholique Louvain
  摘要：We show that the exact worst-case performance of fixed-step first-order methods for unconstrained optimization of smooth (possibly strongly) convex functions can be obtained by solving convex programs. Finding the worst-case performance of a black-box first-order method is formulated as an optimization problem over a set of smooth (strongly) convex functions and initial conditions. We develop closed-form necessary and sufficient conditions for smooth (strongly) convex interpolation, which prov...
• An algorithm for the weighted stable set problem in claw-free graphs with AI翻译
  作者：Nobili, Paolo; Sassano, Antonio
  作者单位：University of Salento; Sapienza University Rome
  摘要：In this paper we show how to solve the Maximum Weight Stable Set Problem in a claw-free graph G(V, E) with in time . More precisely, in time we check whether or produce a stable set with cardinality at least 4; moreover, if we produce in time a maximum weight stable set of G. This improves the bound of due to Faenza, Oriolo and Stauffer.
• Iteration complexity analysis of block coordinate descent methods AI翻译
  作者：Hong, Mingyi; Wang, Xiangfeng; Razaviyayn, Meisam; Luo, Zhi-Quan
  作者单位：Iowa State University; East China Normal University; Stanford University; The Chinese University of Hong Kong, Shenzhen; University of Minnesota System; University of Minnesota Twin Cities
  摘要：In this paper, we provide a unified iteration complexity analysis for a family of general block coordinate descent methods, covering popular methods such as the block coordinate gradient descent and the block coordinate proximal gradient, under various different coordinate update rules. We unify these algorithms under the so-called block successive upper-bound minimization (BSUM) framework, and show that for a broad class of multi-block nonsmooth convex problems, all algorithms covered by the ...
• Probably certifiably correct k-means clustering AI翻译
  作者：Iguchi, Takayuki; Mixon, Dustin G.; Peterson, Jesse; Villar, Soledad
  作者单位：Air Force Institute of Technology (AFIT); University of Texas System; University of Texas Austin
  摘要：Recently, Bandeira (C R Math, 2015) introduced a new type of algorithm (the so-called probably certifiably correct algorithm) that combines fast solvers with the optimality certificates provided by convex relaxations. In this paper, we devise such an algorithm for the problem of k-means clustering. First, we prove that Peng and Wei's semidefinite relaxation of k-means Peng and Wei (SIAM J Optim 18(1):186-205, 2007) is tight with high probability under a distribution of planted clusters called ...
• Ergodic, primal convergence in dual subgradient schemes for convex programming, II: the case of inconsistent primal problems AI翻译
  作者：Onnheim, Magnus; Gustavsson, Emil; Stromberg, Ann-Brith; Patriksson, Michael; Larsson, Torbjorn
  作者单位：Chalmers University of Technology; University of Gothenburg; Linkoping University
  摘要：Consider the utilization of a Lagrangian dual method which is convergent for consistent convex optimization problems. When it is used to solve an infeasible optimization problem, its inconsistency will then manifest itself through the divergence of the sequence of dual iterates. Will then the sequence of primal subproblem solutions still yield relevant information regarding the primal program? We answer this question in the affirmative for a convex program and an associated subgradient algorit...
• Quantitative stability analysis of stochastic quasi-variational inequality problems and applications AI翻译
  作者：Zhang, Jie; Xu, Huifu; Zhang, Liwei
  作者单位：Liaoning Normal University; University of Southampton; Dalian University of Technology; Dalian University of Technology
  摘要：We consider a parametric stochastic quasi-variational inequality problem (SQVIP for short) where the underlying normal cone is defined over the solution set of a parametric stochastic cone system. We investigate the impact of variation of the probability measure and the parameter on the solution of the SQVIP. By reformulating the SQVIP as a natural equation and treating the orthogonal projection over the solution set of the parametric stochastic cone system as an optimization problem, we effec...
• A stabilized SQP method: superlinear convergence AI翻译
  作者：Gill, Philip E.; Kungurtsev, Vyacheslav; Robinson, Daniel P.
  作者单位：University of California System; University of California San Diego; Czech Technical University Prague; Johns Hopkins University
  摘要：Stabilized sequential quadratic programming (sSQP) methods for nonlinear optimization generate a sequence of iterates with fast local convergence regardless of whether or not the active-constraint gradients are linearly dependent. This paper concerns the local convergence analysis of an sSQP method that uses a line search with a primal-dual augmented Lagrangian merit function to enforce global convergence. The method is provably well-defined and is based on solving a strictly convex quadratic ...
• Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization AI翻译
  作者：de Klerk, Etienne; Laurent, Monique; Sun, Zhao
  作者单位：Tilburg University; Centrum Wiskunde & Informatica (CWI); Tilburg University; Centrum Wiskunde & Informatica (CWI); Universite de Montreal; Polytechnique Montreal
  摘要：We consider the problem of minimizing a continuous function f over a compact set . We analyze a hierarchy of upper bounds proposed by Lasserre (SIAM J Optim 21(3):864-885, 2011), obtained by searching for an optimal probability density function h on which is a sum of squares of polynomials, so that the expectation is minimized. We show that the rate of convergence is no worse than , where 2r is the degree bound on the density function. This analysis applies to the case when f is Lipschitz cont...
• The worst case analysis of strong knapsack facets AI翻译
  作者：Shim, Sangho; Chopra, Sunil; Cao, Wenwei
  作者单位：Robert Morris University; Northwestern University; University System of Georgia; Georgia Institute of Technology
  摘要：In this paper we identify strong facet defining inequalities for the master knapsack polytope. Our computational experiments for small master knapsack problems show that 1 / k-facets for small values of k () are strong facets for the knapsack polytope. We show that this finding is robust by proving that the removal of these facets from the master knapsack polytope significantly weakens the resulting relaxation in the worst case. We show that the 1 / k-facets for are the strongest in that their...