检索结果-内蒙古大学图书馆

Technical Report: Pose Graph optimization over Planar Unit Dual Quaternions: Improved Accuracy with Provably Convergent Riemannian optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Warke, William D. Ramos, J. Humberto Ganesh, Prashant Brink, Kevin M. Hale, Matthew T. Mechanical and Aerospace Engineering University of Florida GainesvilleFL United States Mechanical and Aerospace Engineering University of Florida ShalimarFL United States Principal Research Engineer EpiSci Science Incorporated San DiegoCA United States Air Force Research Laboratory Eglin Air Force Base FL United States Electrical and Computer Engineering Georgia Institute of Technology AtlantaGA United States

It is common in pose graph optimization (PGO) algorithms to assume that noise in the translations and rotations of relative pose measurements is uncorrelated. However, existing work shows that in practice these measurements can be highly correlated, which leads to degradation in the accuracy of PGO solutions that rely on this assumption. Therefore, in this paper we develop a novel algorithm derived from a realistic, correlated model of relative pose uncertainty, and we quantify the resulting improvement in the accuracy of the solutions we obtain relative to state-of-the-art PGO algorithms. Our approach utilizes Riemannian optimization on the planar unit dual quaternion (PUDQ) manifold, and we prove that it converges to first-order stationary points of a Lie-theoretic maximum likelihood objective. Then we show experimentally that, compared to state-of-the-art PGO algorithms, this algorithm produces estimation errors that are lower by 10% to 25% across several orders of magnitude of correlated noise levels and graph sizes. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Two Timescale EXTRA for Smooth Non-convex Distributed optimization Problems

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Peng, Zeyu Farokhi, Farhad Pu, Ye Department of Electrical and Electronic Engineering Melbourne University Australia

Distributed non-convex optimization over multi-agent networks is a growing area of interest. In this paper, we propose a decentralized algorithm called Two Time Scale EXTRA (TT-EXTRA), which can be considered as a modified version of the well-known EXTRA algorithm. EXTRA is very general and is closely related to gradient tracking-based algorithms, such as DIGGING, as well as the Primal-Dual Gradient algorithm in distributed settings. It has been established that EXTRA achieves sublinear convergence to an exact minimizer in the convex case and linear convergence in the strongly convex case. However, a convergence analysis of EXTRA for non-convex scenarios remains absent in the current literature. We address this gap by proving that TT-EXTRA converges to a set of consensual first-order stationary points for non-convex distributed optimization problems. © 2024, CC BY-NC-SA.

关键词： optimization algorithms

Batch Bayesian optimization via Expected Subspace Improvement

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Zhan, Dawei Zeng, Zhaoxi Wei, Shuoxiao Wu, Ping School of Computing and Artificial Intelligence Southwest Jiaotong University Chengdu China

Extending Bayesian optimization to batch evaluation can enable the designer to make the most use of parallel computing technology. Most of current batch approaches use artificial functions to simulate the sequential Bayesian optimization algorithm’s behavior to select a batch of points for parallel evaluation. However, as the batch size grows, the accumulated error introduced by these artificial functions increases rapidly, which dramatically decreases the optimization efficiency of the algorithm. In this work, we propose a simple and efficient approach to extend Bayesian optimization to batch evaluation. Different from existing batch approaches, the idea of the new approach is to draw a batch of subspaces of the original problem and select one acquisition point from each subspace. To achieve this, we propose the expected subspace improvement criterion to measure the amount of the improvement that a candidate point can achieve within a certain subspace. By optimizing these expected subspace improvement functions simultaneously, we can get a batch of query points for expensive evaluation. Numerical experiments show that our proposed approach can achieve near-linear speedup when compared with the sequential Bayesian optimization algorithm, and performs very competitively when compared with eight state-of-the-art batch algorithms. This work provides a simple yet efficient approach for batch Bayesian optimization. A Matlab implementation of our approach is available at https://***/zhandawei/Expected_ Subspace_Improvement_Batch_Bayesian_optimization. © 2024, CC BY.

关键词： optimization algorithms

Penalty-based Methods for Simple Bilevel optimization under Hölderian Error Bounds

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Chen, Pengyu Shi, Xu Jiang, Rujun Wang, Jiulin School of Data Science Fudan University China

This paper investigates simple bilevel optimization problems where we minimize an upper-level objective over the optimal solution set of a convex lower-level objective. Existing methods for such problems either only guarantee asymptotic convergence, have slow sublinear rates, or require strong assumptions. To address these challenges, we propose a penalization framework that delineates the relationship between approximate solutions of the original problem and its reformulated counterparts. This framework accommodates varying assumptions regarding smoothness and convexity, enabling the application of specific methods with different complexity results. Specifically, when both upper- and lower-level objectives are composite convex functions, under an α-Hölderian error bound condition and certain mild assumptions, our algorithm attains an (∈, ∈β)-optimal solution of the original problem for any β > 0 within O (√1/∈max{α,β})iterations. The result can be improved further if the smooth part of the upper-level objective is strongly convex. We also establish complexity results when the upper- and lower-level objectives are general nonsmooth functions. Numerical experiments demonstrate the effectiveness of our algorithms. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Improved Sample Complexity for Private Nonsmooth Nonconvex optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Kornowski, Guy Liu, Daogao Talwar, Kunal Weizmann Institute of Science University of Washington United States Apple United States

We study differentially private (DP) optimization algorithms for stochastic and empirical objectives which are neither smooth nor convex, and propose methods that return a Goldstein-stationary point with sample complexity bounds that improve on existing works. We start by providing a single-pass (Ε, δ)-DP algorithm that returns an (α, β)-stationary point as long as the dataset is of size (Equation presented), which is Ω(√d) times smaller than the algorithm of Zhang et al. [2024] for this task, where d is the dimension. We then provide a multi-pass polynomial time algorithm which further improves the sample complexity to (Equation presented), by designing a sample efficient ERM algorithm, and proving that Goldstein-stationary points generalize from the empirical loss to the population loss. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ahn, Kwangjun Magakyan, Gagik Cutkosky, Ashok Microsoft Research United States MIT United States Boston University United States

This work investigates the effectiveness of schedule-free methods, developed by A. Defazio et al. (NeurIPS 2024), in nonconvex optimization settings, inspired by their remarkable empirical success in training neural networks. Specifically, we show that schedule-free SGD achieves optimal iteration complexity for nonsmooth, nonconvex optimization problems. Our proof begins with the development of a general framework for online-to-nonconvex conversion, which converts a given online learning algorithm into an optimization algorithm for nonconvex losses. Our general framework not only recovers existing conversions but also leads to two novel conversion schemes. Notably, one of these new conversions corresponds directly to schedule-free SGD, allowing us to establish its optimality. Additionally, our analysis provides valuable insights into the parameter choices for schedule-free SGD, addressing a theoretical gap that the convex theory cannot explain. © 2024, CC BY.

关键词： optimization algorithms

Capacity Provisioning Motivated Online Non-Convex optimization Problem with Memory and Switching Cost

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Vaze, Rahul Nair, Jayakrishnan

An online non-convex optimization problem is considered where the goal is to minimize the flow time (total delay) of a set of jobs by modulating the number of active servers, but with a switching cost associated with changing the number of active servers over time. Each job can be processed by at most one fixed speed server at any time. Compared to the usual online convex optimization (OCO) problem with switching cost, the objective function considered is non-convex and more importantly, at each time, it depends on all past decisions and not just the present one. Both worst-case and stochastic inputs are considered;for both cases, competitive algorithms are derived. © 2024, CC BY-NC-ND.

关键词： optimization algorithms

Deep Memetic Models for Combinatorial optimization Problems: Application to the Tool Switching Problem

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Amaya, Jhon Edgar Cotta, Carlos Fernández-Leiva, Antonio J. García-Sánchez, Pablo San Cristóbal Venezuela Dept. Lenguajes y Ciencias de la Computación ETSI Informática University of Malaga Campus de Teatinos Malaga29071 Spain Dept. de Ingeniería Informática ESI University of Cádiz Campus de Puerto Real Cádiz11519 Spain

Memetic algorithms are techniques that orchestrate the interplay between population-based and trajectory-based algorithmic components. In particular, some memetic models can be regarded under this broad interpretation as a group of autonomous basic optimization algorithms that interact among them in a cooperative way in order to deal with a specific optimization problem, aiming to obtain better results than the algorithms that constitute it separately. Going one step beyond this traditional view of cooperative optimization algorithms, this work tackles deep meta-cooperation, namely the use of cooperative optimization algorithms in which some components can in turn be cooperative methods themselves, thus exhibiting a deep algorithmic architecture. The objective of this paper is to demonstrate that such models can be considered as an efficient alternative to other traditional forms of cooperative algorithms. To validate this claim, different structural parameters, such as the communication topology between the agents, or the parameter that influences the depth of the cooperative effort (the depth of meta-cooperation), have been analyzed. To do this, a comparison with the state-of-the-art cooperative methods to solve a specific combinatorial problem, the Tool Switching Problem, has been performed. Results show that deep models are effective to solve this problem, outperforming metaheuristics proposed in the literature. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

An online optimization algorithm for tracking a linearly varying optimal point with zero steady-state error

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Wu, Alex Petersen, Ian R. Ugrinovskii, Valery Shames, Iman The CIICADA Lab School of Engineering The Australian National University CanberraACT2601 Australia The School of Engineering and IT UNSW Canberra CanberraACT2600 Australia

In this paper, we develop an online optimization algorithm for solving a class of nonconvex optimization problems with a linearly varying optimal point. The global convergence of the algorithm is guaranteed using the circle criterion for the class of functions whose gradient is bounded within a sector. Also, we show that the corresponding Lurétype nonlinear system involves a double integrator, which demonstrates its ability to track a linearly varying optimal point with zero steady-state error. The algorithm is applied to solving a time-of-arrival based localization problem with constant velocity and the results show that the algorithm is able to estimate the source location with zero steady-state *** Codes 93D09 © 2024, CC BY-NC-ND.

关键词： optimization algorithms