2021

最新文章

• Convergence rates of an inertial gradient descent algorithm under growth and flatness conditions AI翻译
  作者：Apidopoulos, Vassilis; Aujol, Jean-Francois; Dossal, Charles; Rondepierre, Aude
  作者单位：University of Genoa; Universite de Bordeaux; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Universite Federale Toulouse Midi-Pyrenees (ComUE); Institut National des Sciences Appliquees de Toulouse; Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse
  摘要：In this paper we study the convergence properties of a Nesterov's family of inertial schemes which is a specific case of inertial Gradient Descent algorithm in the context of a smooth convex minimization problem, under some additional hypotheses on the local geometry of the objective function F, such as the growth (or Lojasiewicz) condition. In particular we study the different convergence rates for the objective function and the local variation, depending on these geometric conditions. In thi...
• Quadratic optimization with switching variables: the convex hull for n=2 AI翻译
  作者：Anstreicher, Kurt M.; Burer, Samuel
  作者单位：University of Iowa
  摘要：We consider quadratic optimization in variables (x, y) where 0 <= x <= y, and y is an element of {0, 1}(n). Such binary variables are commonly referred to as indicator or switching variables and occur commonly in applications. One approach to such problems is based on representing or approximating the convex hull of the set {(x, xx(T,) yy(T)) : 0 <= x <= y is an element of{0, 1}(n)}. A representation for the case n = 1 is known and has been widely used. We give an exact representation for the ...
• Characterization of Filippov representable maps and Clarke subdifferentials AI翻译
  作者：Bivas, Mira; Daniilidis, Aris; Quincampoix, Marc
  作者单位：University of Sofia; Bulgarian Academy of Sciences; Universidad de Chile; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universite de Bretagne Occidentale
  摘要：The ordinary differential equation (x) over dot(t) = f (x(t)), t >= 0, for f measurable, is not sufficiently regular to guarantee existence of solutions. To remedy this we may relax the problem by replacing the function f with its Filippov regularization F-f and consider the differential inclusion (x) over dot(t) is an element of F-f (x(t)) which always has a solution. It is interesting to know, inversely, when a set-valued map Phi can be obtained as the Filippov regularization of a (single-va...
• Hypergraph k-cut in randomized polynomial time AI翻译
  作者：Chandrasekaran, Karthekeyan; Xu, Chao; Yu, Xilin
  作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Yahoo! Inc
  摘要：For a fixed integer the hypergraph k-cut problem asks for a smallest subset of hyperedges whose removal leads to at least k connected components in the remaining hypergraph. While graph k-cut is solvable efficiently (Goldschmidt and Hochbaum in Math. Oper. Res. 19(1):24-37, 1994), the complexity of hypergraph k-cut has been open. In this work, we present a randomized polynomial time algorithm to solve the hypergraph k-cut problem. Our algorithmic technique extends to solve the more general hed...
• Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling AI翻译
  作者：Chakrabarty, Deeparnab; Khanna, Sanjeev
  作者单位：Dartmouth College; University of Pennsylvania
  摘要：Given a non-negative n xm real matrix A, the matrix scaling problem is to determine if it is possible to scale the rows and columns so that each row and each column sums to a specified positive target values. The Sinkhorn-Knopp algorithm is a simple and classic procedure which alternately scales all rows and all columns to meet these targets. The focus of this paper is the worst-case theoretical analysis of this algorithm. We present an elementary convergence analysis for this algorithm that i...
• Compactness and convergence rates in the combinatorial integral approximation decomposition AI翻译
  作者：Kirches, Christian; Manns, Paul; Ulbrich, Stefan
  作者单位：Braunschweig University of Technology; Technical University of Darmstadt
  摘要：The combinatorial integral approximation decomposition splits the optimization of a discrete-valued control into two steps: solving a continuous relaxation of the discrete control problem, and computing a discrete-valued approximation of the relaxed control. Different algorithms exist for the second step to construct piecewise constant discrete-valued approximants that are defined on given decompositions of the domain. It is known that the resulting discrete controls can be constructed such th...
• Statistical robustness in utility preference robust optimization models AI翻译
  作者：Guo, Shaoyan; Xu, Huifu
  作者单位：Dalian University of Technology; Chinese University of Hong Kong
  摘要：Utility preference robust optimization (PRO) concerns decision making problems where information on decision maker's utility preference is incomplete and has to be elicited through partial information and the optimal decision is based on the worst case utility function elicited. A key assumption in the PRO models is that the true probability distribution is either known or can be recovered by real data generated by the true distribution. In data-driven optimization, this assumption may not be ...
• Adaptive regularization with cubics on manifolds AI翻译
  作者：Agarwal, Naman; Boumal, Nicolas; Bullins, Brian; Cartis, Coralia
  作者单位：Alphabet Inc.; Google Incorporated; Princeton University; Toyota Technological Institute - Chicago; University of Oxford
  摘要：Adaptive regularization with cubics (ARC) is an algorithm for unconstrained, non-convex optimization. Akin to the trust-region method, its iterations can be thought of as approximate, safe-guarded Newton steps. For cost functions with Lipschitz continuous Hessian, ARC has optimal iteration complexity, in the sense that it produces an iterate with gradient smaller than epsilon in O(1/epsilon 1.5) iterations. For the same price, it can also guarantee a Hessian with smallest eigenvalue larger tha...
• The salesman's improved tours for fundamental classes AI翻译
  作者：Boyd, Sylvia; Sebo, Andras
  作者单位：University of Ottawa; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
  摘要：Finding the exact integrality gap a for the LP relaxation of the metric travelling salesman problem (TSP) has been an open problem for over 30 years, with little progress made. It is known that 4/3 = alpha = 3/2, and a famous conjecture states alpha = 4/3. It has also been conjectured that the integrality gap is achieved for half-integer basic solutions of the linear program. For this problem, essentially two fundamental classes of instances have been proposed. This fundamental property means ...
• Fully asynchronous stochastic coordinate descent: a tight lower bound on the parallelism achieving linear speedup AI翻译
  作者：Cheung, Yun Kuen; Cole, Richard; Tao, Yixin
  作者单位：Singapore University of Technology & Design; New York University
  摘要：We seek tight bounds on the viable parallelism in asynchronous implementations of coordinate descent that achieves linear speedup. We focus on asynchronous coordinate descent (ACD) algorithms on convex functions which consist of the sum of a smooth convex part and a possibly non-smooth separable convex part. We quantify the shortfall in progress compared to the standard sequential stochastic gradient descent. This leads to a simple yet tight analysis of the standard stochastic ACD in a partial...