1-2期

最新文章

• 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 ...
• 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...
• 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...
• An improved algorithm for the - minimization problem AI翻译
  作者：Ge, Dongdong; He, Rongchuan; He, Simai
  作者单位：Shanghai University of Finance & Economics; City University of Hong Kong
  摘要：In this paper we consider a class of non-Lipschitz and non-convex minimization problems which generalize the - minimization problem. We propose an iterative algorithm that decides the next iteration based on the local convexity/concavity/sparsity of its current position. We show that our algorithm finds an -KKT point within iterations from certain initial points. The same result is also applied to the problem with general linear constraints under mild conditions.
• Robust screening under ambiguity AI翻译
  作者：Pinar, Mustafa C.; Kizilkale, Can
  作者单位：Ihsan Dogramaci Bilkent University
  摘要：We consider the problem of screening where a seller puts up for sale an indivisible good, and a buyer with a valuation unknown to the seller wishes to acquire the good. We assume that the buyer valuations are represented as discrete types drawn from some distribution, which is also unknown to the seller. The seller is averse to possible mis-specification of types distribution, and considers the unknown type density as member of an ambiguity set and seeks an optimal pricing mechanism in a worst...