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

Global minimization of a minimum of a finite collection of functions

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Van Dessel, Guillaume Glineur, François 4 Avenue Georges Lemaitre Louvain-la-Neuve Belgium UCLouvain CORE 34 Voie du Roman Pays Louvain-la-Neuve Belgium

We consider the global minimization of a particular type of minimum structured optimization problems wherein the variables must belong to some basic set, the feasible domain is described by the intersection of a large number of functional constraints and the objective stems as the pointwise minimum of a collection of functional pieces. Among others, this setting includes all non-convex piecewise linear problems. The global minimum of a minimum structured problem can be computed using a simple enumeration scheme by solving a sequence of individual problems involving each a single piece and then taking the smallest individual minimum. We propose a new algorithm, called Upper-Lower optimization (ULO), tackling problems from the aforementioned class. Our method does not require the solution of every individual problem listed in the baseline enumeration scheme, yielding potential substantial computational gains. It alternates between (a) local-search steps, which minimize upper models, and (b) suggestion steps, which optimize lower models. We prove that ULO can return a solution of any prescribed global optimality accuracy. According to a computational complexity model based on the cost of solving the individual problems, we analyze in which practical scenarios ULO is expected to outperform the baseline enumeration scheme. Finally, we empirically validate our approach on a set of piecewise linear programs (PL) of incremental difficulty. © 2024, CC BY.

关键词： optimization algorithms

SHS: Scorpion Hunting Strategy Swarm Algorithm

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Singh, Abhilash Mousavi, Seyed Muhammad Hossein Gaurav, Kumar Fluvial Geomorphology and Remote Sensing Laboratory Indian Institute of Science Education and Research Bhopal India PARS-AI Tehran Iran

We introduced the Scorpion Hunting Strategy (SHS), a novel population-based, nature-inspired optimisation algorithm. This algorithm draws inspiration from the hunting strategy of scorpions, which identify, locate, and capture their prey using the alpha and beta vibration operators. These operators control the SHS algorithm’s exploitation and exploration abilities. To formulate an optimisation method, we mathematically simulate these dynamic events and behaviors. We evaluate the effectiveness of the SHS algorithm by employing 20 benchmark functions (including 10 conventional and 10 CEC2020 functions), using both qualitative and quantitative analyses. Through a comparative analysis with 12 state-of-the-art meta-heuristic algorithms, we demonstrate that the proposed SHS algorithm yields exceptionally promising results. These findings are further supported by statistically significant results obtained through the Wilcoxon rank sum test. Additionally, the ranking of SHS, as determined by the average rank derived from the Friedman test, positions it at the forefront when compared to other algorithms. Going beyond theoretical validation, we showcase the practical utility of the SHS algorithm by applying it to six distinct real-world optimisation tasks. These applications illustrate the algorithm’s potential in addressing complex optimisation challenges. In summary, this work not only introduces the innovative SHS algorithm but also substantiates its effectiveness and versatility through rigorous benchmarking and real-world problem-solving scenarios. © 2024, CC BY-NC-ND.

关键词： optimization algorithms

Two Completely Parameter-Free Alternating Gradient Projection algorithms for Nonconvex-(strongly) Concave Minimax Problems

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Yang, Junnan Zhang, Huiling Xu, Zi Department of Mathematics Shanghai University Shanghai200444 China Academy of Mathematics and Systems Science Chinese Academy of Sciences Beijing100190 China Newtouch Center for Mathematics of Shanghai University Shanghai University Shanghai200444 China

Due to their importance in various emerging applications, efficient algorithms for solving minimax problems have recently received increasing attention. However, many existing algorithms require prior knowledge of the problem parameters in order to achieve optimal iteration complexity. In this paper, we propose two completely parameter-free alternating gradient projection algorithms, i.e., the PF-AGP-NSC algorithm and the PF-AGP-NC algorithm, to solve the smooth nonconvex-strongly concave and nonconvex-concave minimax problems respectively using a backtracking strategy, which does not require prior knowledge of parameters such as the Lipschtiz constant L or the strongly concave constant µ. Moreover, we show that the total number of gradient calls of the PF-AGP-NSC algorithm and the PF-AGP-NC algorithm to obtain an Ε-stationary point is upper bounded by O(Lκ3Ε−2) and O(L4Ε−4) respectively, where κ is the condition number. As far as we know, the PF-AGP-NSC algorithm and the PF-AGP-NC algorithm are the first completely parameter-free algorithms for solving nonconvex-strongly concave minimax problems and nonconvex-concave minimax problems respectively. Numerical results validate the efficiency of the proposed PF-AGP algorithm. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Stochastic Approximation and Brownian Repulsion based Evolutionary Search

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Dutta, Rajdeep Varma, T. Venkatesh Sarkar, Saikat Mamajiwala, Mariya Awad, Noor Jayavelu, Senthilnath Roy, Debasish 138632 Singapore Faculty of Mechanical Engineering Technion–Israel Institute of Technology Haifa32000 Israel Department of Civil Engineering Indian Institute of Technology Delhi Hauz Khas New Delhi110016 India Department of Computer Science University of Sheffield United Kingdom Machine Learning Lab University of Freiburg Germany Centre of Excellence in Advanced Mechanics of Materials Indian Institute of Science Bangalore India

Many global optimization algorithms of the memetic variety rely on some form of stochastic search, and yet they often lack a sound probabilistic basis. Without a recourse to the powerful tools of stochastic calculus, treading the fine balance between exploration and exploitation could be tricky. In this work, we propose an evolutionary algorithm (EA) comprising two types of additive updates. The primary update utilizes stochastic approximation to guide a population of randomly initialized particles towards an optimum. We incorporate derivative-free Robbins-Monro type gains in the first update so as to provide a directional guidance to the candidate solutions. The secondary update leverages stochastic conditioning to apply random perturbations for a controlled yet efficient exploration. Specifically, conceptualized on a change of measures, the perturbation strategy discourages two or more trajectories exploring the same region of the search space. Our optimization algorithm, dubbed as SABRES (Stochastic Approximation and Brownian Repulsion based Evolutionary Search), is applied to CEC-2022 benchmark functions on global optimization. Numerical results are indicative of the potentialities of SABRES in solving a variety of challenging multi-modal, non-separable, and asymmetrical benchmark functions. © 2024, CC BY-NC-ND.

关键词： optimization algorithms

An Optimal Convergent Collatz Algorithm

学校读者我要写书评

暂无评论

SSRN

SSRN 2024年

作者： Riano-Rojas, Juan Carlos Departamento de Matemáticas y Estadística Universidad Nacional de Colombia Caldas Manizales Colombia Colombia

This study presents an optimal algorithm for the Collatz conjecture, examining its convergence properties and connecting it to the original conjecture through an equation that calculates the steps needed for the Collatz sequence to reach 1. Additionally, the algorithm identifies the values of n that yield the maximum sequence value and those with the longest sequence within a specified interval. The proposed theory is rigorously proven and extensively validated through numerous examples and various visualization methods, including regions where the conjecture's validity is contested. © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Linear Convergence in Hilbert's Projective Metric for Computing Augustin Information and a Rényi Information Measure

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Tsai, Chung-En Wang, Guan-Ren Cheng, Hao-Chung Li, Yen-Huan Department of Computer Science and Information Engineering National Taiwan University Taiwan Graduate Institute of Networking and Multimedia National Taiwan University Taiwan Department of Electrical Engineering Graduate Institute of Communication Engineering National Taiwan University Taiwan Department of Mathematics National Taiwan University Taiwan Center for Quantum Science and Engineering National Taiwan University Taiwan Physics Division National Center for Theoretical Sciences Taiwan Quantum Computing Centre Taiwan

Consider the problems of computing the Augustin information and a Rényi information measure of statistical independence, previously explored by Lapidoth and Pfister (IEEE Information Theory Workshop, 2018) and Tomamichel and Hayashi (IEEE Trans. Inf. Theory, 64(2):1064-1082, 2018). Both quantities are defined as solutions to optimization problems and lack closed-form expressions. This paper analyzes two iterative algorithms: Augustin's fixed-point iteration for computing the Augustin information, and the algorithm by Kamatsuka et al. (arXiv:2404.10950) for the Rényi information measure. Previously, it was only known that these algorithms converge asymptotically. We establish the linear convergence of Augustin's algorithm for the Augustin information of order α ∈ (1/2, 1) ∪ (1, 3/2) and Kamatsuka et al.'s algorithm for the Rényi information measure of order α ∈ [1/2, 1) ∪ (1,∞), using Hilbert's projective metric. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Extended convexity and smoothness and their applications in deep learning

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Qi, Binchuan Gong, Wei Li, Li College of Electronics and Information Engineering Tongji University Shanghai201804 China National Key Laboratory of Autonomous Intelligent Unmanned Systems Tongji University Shanghai201210 China Shanghai Research Institute for Intelligent Autonomous Systems Tongji University Shanghai201210 China

This paper introduces an optimization framework aimed at providing a theoretical foundation for a class of composite optimization problems, particularly those encountered in deep learning. In this framework, we introduce H()-convexity and H(Φ)-smoothness to generalize the existing concepts of Lipschitz smoothness and strong convexity. Furthermore, we analyze and establish the convergence of both gradient descent and stochastic gradient descent methods for objective functions that are H(Φ)-smooth. We prove that the optimal convergence rates of these methods depend solely on the homogeneous degree of Φ. Based on these findings, we construct two types of non-convex and non-smooth optimization problems: deterministic composite and stochastic composite optimization problems, which encompass the majority of optimization problems in deep learning. To address these problems, we develop the gradient structure control algorithm and prove that it can locate approximate global optima. This marks a significant departure from traditional non-convex analysis framework, which typically settle for stationary points. Therefore, with the introduction of H()-convexity and H(Φ)-smoothness, along with the GSC algorithm, the non-convex optimization mechanisms in deep learning can be theoretically explained and supported. Finally, the effectiveness of the proposed framework is substantiated through empirical experimentation. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

GenJoin: Conditional Generative Plan-to-Plan Query Optimizer that Learns from Subplan Hints

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Sulimov, Pavel Lehmann, Claude Stockinger, Kurt Zurich University of Applied Sciences Switzerland

Query optimization has become a research area where classical algorithms are being challenged by machine learning algorithms. At the same time, recent trends in learned query optimizers have shown that it is prudent to take advantage of decades of database research and augment classical query optimizers by shrinking the plan search space through different types of hints (e.g. by specifying the join type, scan type or the order of joins) rather than completely replacing the classical query optimizer with machine learning models. It is especially relevant for cases when classical optimizers cannot fully enumerate all logical and physical plans and, as an alternative, need to rely on less robust approaches like genetic algorithms. However, even symbiotically learned query optimizers are hampered by the need for vast amounts of training data, slow plan generation during inference and unstable results across various workload conditions. In this paper, we present GenJoin - a novel learned query optimizer that considers the query optimization problem as a generative task and is capable of learning from a random set of subplan hints to produce query plans that outperform the classical optimizer. GenJoin is the first learned query optimizer that significantly and consistently outperforms PostgreSQL as well as state-of-the-art methods on two well-known real-world benchmarks across a variety of workloads using rigorous machine learning evaluations. © 2024, CC BY.

关键词： optimization algorithms

Constraint Preconditioning and Parameter Selection for a First-Order Primal-Dual Method applied to Model Predictive Control

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Chari, Govind M. Yu, Yue Açıkmeşe, Behçet Department of Aeronautics & Astronautics the University of Washington SeattleWA98195 United States Department of Aerospace Engineering and Mechanics the University of Minnesota Twin Cities MinneapolisMN55455 United States Department of Aeronautics & Astronautics the University of Washington SeattleWA98195 United States

Many techniques for real-time trajectory optimization and control require the solution of optimization problems at high frequencies. However, ill-conditioning in the optimization problem can significantly reduce the speed of first-order primal-dual optimization algorithms. We introduce a preconditioning technique and step-size heuristic for Proportional-Integral Projected Gradient (PIPG), a first-order primal-dual algorithm. The preconditioning technique, based on the QR factorization, aims to reduce the condition number of the KKT matrix associated with the optimization problem. Our step-size selection heuristic chooses step-sizes to minimize the upper bound on the convergence of the primal-dual gap for the optimization problem. These algorithms are tested on two model predictive control problem examples and show a solve-time reduction of at least 3.6x. © 2024, CC BY-NC-ND.

关键词： optimization algorithms