2013

最新文章

• A 3-approximation algorithm for the facility location problem with uniform capacities AI翻译
  作者：Aggarwal, Ankit; Louis, Anand; Bansal, Manisha; Garg, Naveen; Gupta, Neelima; Gupta, Shubham; Jain, Surabhi
  作者单位：University System of Georgia; Georgia Institute of Technology; University of Delhi; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Delhi; Alphabet Inc.; Google Incorporated; Alphabet Inc.; Google Incorporated
  摘要：We consider the facility location problem where each facility can serve at most U clients. We analyze a local search algorithm for this problem which uses only the operations of add, delete and swap and prove that any locally optimum solution is no more than 3 times the global optimum. This improves on a result of Chudak and Williamson who proved an approximation ratio of for the same algorithm. We also provide an example which shows that any local search algorithm which uses only these three ...
• Nonsmooth optimization via quasi-Newton methods AI翻译
  作者：Lewis, Adrian S.; Overton, Michael L.
  作者单位：Cornell University; New York University
  摘要：We investigate the behavior of quasi-Newton algorithms applied to minimize a nonsmooth function f, not necessarily convex. We introduce an inexact line search that generates a sequence of nested intervals containing a set of points of nonzero measure that satisfy the Armijo and Wolfe conditions if f is absolutely continuous along the line. Furthermore, the line search is guaranteed to terminate if f is semi-algebraic. It seems quite difficult to establish a convergence theorem for quasi-Newton...
• On some dynamic thermal non clamped contact problems AI翻译
  作者：Adly, Samir; Chau, Oanh
  作者单位：Universite de Limoges; University of La Reunion
  摘要：We study a class of dynamic thermal sub-differential contact problems with friction, for long memory visco-elastic materials, without the clamped condition, which can be put into a general model of system defined by a second order evolution inequality, coupled with a first order evolution equation. We present and establish an existence and uniqueness result, by using general results on first order evolution inequality, with monotone operators and fixed point methods. Finally a fully discrete s...
• A perfect example for the BFGS method AI翻译
  作者：Dai, Yu-Hong
  作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
  摘要：Consider the BFGS quasi-Newton method applied to a general non-convex function that has continuous second derivatives. This paper aims to construct a four-dimensional example such that the BFGS method need not converge. The example is perfect in the following sense: (a) All the stepsizes are exactly equal to one; the unit stepsize can also be accepted by various line searches including the Wolfe line search and the Arjimo line search; (b) The objective function is strongly convex along each se...
• Randomized first order algorithms with applications to l1-minimization AI翻译
  作者：Juditsky, Anatoli; Karzan, Fatma Kilinc; Nemirovski, Arkadi
  作者单位：Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); Carnegie Mellon University; University System of Georgia; Georgia Institute of Technology
  摘要：In this paper we propose randomized first-order algorithms for solving bilinear saddle points problems. Our developments are motivated by the need for sub-linear time algorithms to solve large-scale parametric bilinear saddle point problems where cheap online assessment of the solution quality is crucial. We present the theoretical efficiency estimates of our algorithms and discuss a number of applications, primarily to the problem of l(1) minimization arising in sparsity-oriented signal proce...
• Stability analysis of stochastic programs with second order dominance constraints AI翻译
  作者：Liu, Yongchao; Xu, Huifu
  作者单位：Dalian Maritime University; University of Southampton
  摘要：In this paper we present a stability analysis of a stochastic optimization problem with stochastic second order dominance constraints. We consider a perturbation of the underlying probability measure in the space of regular measures equipped with pseudometric discrepancy distance (Romisch in Stochastic Programming. Elsevier, Amsterdam, pp 483-554, 2003). By exploiting a result on error bounds in semi-infinite programming due to Gugat (Math Program Ser B 88:255-275, 2000), we show under the Sla...
• The GUS-property of second-order cone linear complementarity problems AI翻译
  作者：Yang, Wei Hong; Yuan, Xiaoming
  作者单位：Fudan University; Hong Kong Baptist University
  摘要：The globally uniquely solvable (GUS) property of the linear transformation of the linear complementarity problems over symmetric cones has been studied recently by Gowda et al. via the approach of Euclidean Jordan algebra. In this paper, we contribute a new approach to characterizing the GUS property of the linear transformation of the second-order cone linear complementarity problems (SOCLCP) via some basic linear algebra properties of the involved matrix of SOCLCP. Some more concrete and che...
• Computing the conjugate of convex piecewise linear-quadratic bivariate functions AI翻译
  作者：Gardiner, Bryan; Lucet, Yves
  作者单位：University of British Columbia; University of British Columbia Okanagan
  摘要：We present a new algorithm to compute the Legendre-Fenchel conjugate of convex piecewise linear-quadratic (PLQ) bivariate functions. The algorithm stores a function using a (primal) planar arrangement. It then computes the (dual) arrangement associated with the conjugate by looping through vertices, edges, and faces in the primal arrangement and building associated dual vertices, edges, and faces. Using optimal computational geometry data structures, the algorithm has a linear time worst-case ...
• Certifying convergence of Lasserre's hierarchy via flat truncation AI翻译
  作者：Nie, Jiawang
  作者单位：University of California System; University of California San Diego
  摘要：Consider the optimization problem of minimizing a polynomial function subject to polynomial constraints. Atypical approach for solving it globally is applying Lasserre's hierarchy of semidefinite relaxations, based on either Putinar's or Schmudgen's Positivstellensatz. A practical question in applications is: how to certify its convergence and get minimizers? In this paper, we propose flat truncation as a certificate for this purpose. Assume the set of global minimizers is nonempty and finite....
• Fast alternating linearization methods for minimizing the sum of two convex functions AI翻译
  作者：Goldfarb, Donald; Ma, Shiqian; Scheinberg, Katya
  作者单位：Columbia University; University of Minnesota System; University of Minnesota Twin Cities; Lehigh University
  摘要：We present in this paper alternating linearization algorithms based on an alternating direction augmented Lagrangian approach for minimizing the sum of two convex functions. Our basic methods require at most iterations to obtain an -optimal solution, while our accelerated (i.e., fast) versions of them require at most iterations, with little change in the computational effort required at each iteration. For both types of methods, we present one algorithm that requires both functions to be smoot...