2023

最新文章

• An augmented Lagrangian method for optimization problems with structured geometric constraints AI翻译
  作者：Jia, Xiaoxi; Kanzow, Christian; Mehlitz, Patrick; Wachsmuth, Gerd
  作者单位：University of Wurzburg; Brandenburg University of Technology Cottbus; University of Mannheim
  摘要：This paper is devoted to the theoretical and numerical investigation of an augmented Lagrangian method for the solution of optimization problems with geometric constraints. Specifically, we study situations where parts of the constraints are nonconvex and possibly complicated, but allow for a fast computation of projections onto this nonconvex set. Typical problem classes which satisfy this requirement are optimization problems with disjunctive constraints (like complementarity or cardinality ...
• Riemannian Optimization via Frank-Wolfe Methods AI翻译
  作者：Weber, Melanie; Sra, Suvrit
  作者单位：University of Oxford; Princeton University; Massachusetts Institute of Technology (MIT)
  摘要：We study projection-free methods for constrained Riemannian optimization. In particular, we propose a Riemannian Frank-Wolfe (RFW) method that handles constraints directly, in contrast to prior methods that rely on (potentially costly) projections. We analyze non-asymptotic convergence rates of RFW to an optimum for geodesically convex problems, and to a critical point for nonconvex objectives. We also present a practical setting under which RFW can attain a linear convergence rate. As a concr...
• Convergence rates of the Heavy-Ball method under the Lojasiewicz property AI翻译
  作者：Aujol, J-F; Dossal, Ch; Rondepierre, A.
  作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universite de Bordeaux; Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Universite Federale Toulouse Midi-Pyrenees (ComUE); Institut National des Sciences Appliquees de Toulouse; Universite de Toulouse; Centre National de la Recherche Scientifique (CNRS)
  摘要：In this paper, a joint study of the behavior of solutions of the Heavy Ball ODE and Heavy Ball type algorithms is given. Since the pioneering work of Polyak (USSR Comput Math Math Phys 4(5):1-17, 1964), it is well known that such a scheme is very efficient for C-2 strongly convex functions with Lipschitz gradient. But much less is known when only growth conditions are considered. Depending on the geometry of the function to minimize, convergence rates for convex functions, with some additional...
• A gradient sampling algorithm for stratified maps with applications to topological data analysis AI翻译
  作者：Leygonie, Jacob; Carriere, Mathieu; Lacombe, Theo; Oudot, Steve
  作者单位：University of Oxford; Universite Cote d'Azur; Inria; Universite Gustave-Eiffel; ESIEE Paris; Institut Polytechnique de Paris; Ecole des Ponts ParisTech; Inria; Institut Polytechnique de Paris
  摘要：We introduce a novel gradient descent algorithm refining the well-known Gradient Sampling algorithm on the class of stratifiably smooth objective functions, which are defined as locally Lipschitz functions that are smooth on some regular pieces-called the strata-of the ambient Euclidean space. On this class of functions, our algorithm achieves a sub-linear convergence rate. We then apply our method to objective functions based on the (extended) persistent homology map computed over lower-star ...
• Hessian averaging in stochastic Newton methods achieves superlinear convergence AI翻译
  作者：Na, Sen; Derezinski, Michal; Mahoney, Michael W.
  作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley; University of Michigan System; University of Michigan
  摘要：We consider minimizing a smooth and strongly convex objective function using a stochastic Newton method. At each iteration, the algorithm is given an oracle access to a stochastic estimate of the Hessian matrix. The oracle model includes popular algorithms such as Subsampled Newton and Newton Sketch, which can efficiently construct stochastic Hessian estimates for many tasks, e.g., training machine learning models. Despite using second-order information, these existing methods do not exhibit s...
• A semismooth Newton based augmented Lagrangian method for nonsmooth optimization on matrix manifolds AI翻译
  作者：Zhou, Yuhao; Bao, Chenglong; Ding, Chao; Zhu, Jun
  作者单位：Tsinghua University; Tsinghua University; Yanqi Lake Beijing Institute of Mathematical Sciences & Applications; Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
  摘要：This paper is devoted to studying an augmented Lagrangian method for solving a class of manifold optimization problems, which have nonsmooth objective functions and nonlinear constraints. Under the constant positive linear dependence condition on manifolds, we show that the proposed method converges to a stationary point of the nonsmooth manifold optimization problem. Moreover, we propose a globalized semismooth Newton method to solve the augmented Lagrangian subproblem on manifolds efficientl...
• An exponential lower bound for Zadeh's pivot rule AI翻译
  作者：Disser, Yann; Friedmann, Oliver; Hopp, Alexander, V
  作者单位：Technical University of Darmstadt; University of Munich; Merck KGaA
  摘要：The question whether the Simplex Algorithm admits an efficient pivot rule remains one of the most important open questions in discrete optimization. While many natural, deterministic pivot rules are known to yield exponential running times, the random-facet rule was shown to have a subexponential running time. For a long time, Zadeh's rule remained the most prominent candidate for the first deterministic pivot rule with subexponential running time. We present a lower bound construction that sh...
• Convergence of augmented Lagrangian methods in extensions beyond nonlinear programming AI翻译
  作者：Rockafellar, R. Tyrrell
  作者单位：University of Washington; University of Washington Seattle
  摘要：The augmented Lagrangian method (ALM) is extended to a broader-than-ever setting of generalized nonlinear programming in convex and nonconvex optimization that is capable of handling many common manifestations of nonsmoothness. With the help of a recently developed sufficient condition for local optimality, it is shown to be derivable from the proximal point algorithm through a kind of local duality corresponding to an optimal solution and accompanying multiplier vector that furnish a local sa...
• Complexity, exactness, and rationality in polynomial optimization AI翻译
  作者：Bienstock, Daniel; Del Pia, Alberto; Hildebrand, Robert
  作者单位：Columbia University; University of Wisconsin System; University of Wisconsin Madison; Virginia Polytechnic Institute & State University
  摘要：We focus on rational solutions or nearly-feasible rational solutions that serve as certificates of feasibility for polynomial optimization problems. We show that, under some separability conditions, certain cubic polynomially constrained sets admit rational solutions. However, we show in other cases that it is NP Hard to detect if rational solutions exist or if they exist of any reasonable size. We extend this idea to various settings including near feasible, but super optimal solutions and de...
• On the robustness of potential-based flow networks AI翻译
  作者：Klimm, Max; Pfetsch, Marc E.; Raber, Rico; Skutella, Martin
  作者单位：Technical University of Berlin; Technical University of Darmstadt
  摘要：Potential-based flows provide a simple yet realistic mathematical model of transport in many real-world infrastructure networks such as, e.g., gas or water networks, where the flow along each edge depends on the difference of the potentials at its end nodes. We call a network topology robust if the maximal node potential needed to satisfy a set of demands never increases when demands are decreased. This notion of robustness is motivated by infrastructure networks where users first make reserva...