Mathematical Programming

最新文章

• 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...
• 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.
• Two-stage stochastic variational inequalities: an ERM-solution procedure AI翻译
  作者：Chen, Xiaojun; Pong, Ting Kei; Wets, Roger J-B.
  作者单位：Hong Kong Polytechnic University; University of California System; University of California Davis
  摘要：We propose a two-stage stochastic variational inequality model to deal with random variables in variational inequalities, and formulate this model as a two-stage stochastic programming with recourse by using an expected residual minimization solution procedure. The solvability, differentiability and convexity of the two-stage stochastic programming and the convergence of its sample average approximation are established. Examples of this model are given, including the optimality conditions for ...
• 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...