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

An exponentially stable discrete-time primal-dual algorithm for distributed constrained optimization

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Ren, Xiaoxing Bin, Michelangelo Notarnicola, Ivano Parisini, Thomas Department of Electrical and Electronic Engineering Imperial College London London United Kingdom Department of Electrical Electronic and Information Engineering University of Bologna Italy Department of Electronic Systems Aalborg University Denmark Department of Engineering and Architecture University of Trieste Trieste Italy

This paper studies a distributed algorithm for constrained consensus optimization that is obtained by fusing the Arrow-Hurwicz-Uzawa primal-dual gradient method for centralized constrained optimization and the Wang-Elia method for distributed unconstrained optimization. It is shown that the optimal primal-dual point is a semiglobally exponentially stable equilibrium for the algorithm, which implies linear convergence. The analysis is based on the separation between a slow centralized optimization dynamics describing the evolution of the average estimate toward the optimum, and a fast dynamics describing the evolution of the consensus error over the network. These two dynamics are mutually coupled, and the stability analysis builds on control theoretic tools such as time-scale separation, Lyapunov theory, and the small-gain principle. Our analysis approach highlights that the consensus dynamics can be seen as a fast, parasite one, and that stability of the distributed algorithm is obtained as a robustness consequence of the semiglobal exponential stability properties of the centralized method. This perspective can be used to enable other significant extensions, such as time-varying networks or delayed communication, that can be seen as "perturbations" of the centralized *** Codes 65K05, 93A14, 93A16, 90C25, 90C30, 90C35, 93D05, 93D23 © 2025, CC BY-NC-ND.

关键词： optimization algorithms

SPLD POLYNOMIAL optimization AND BOUNDED DEGREE SOS HIERARCHIES

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Jiao, Liguo Lee, Jae Hyoung Thao, Nguyen Bui Nguyen Academy for Advanced Interdisciplinary Studies Northeast Normal University Jilin Province Changchun130024 China Shanghai Zhangjiang Institute of Mathematics Shanghai201203 China Department of Applied Mathematics Pukyong National University Busan48513 Korea Republic of Department of Pedagogy University of Dalat Viet Nam

In this paper, a new class of structured polynomials, which we dub the separable plus lower degree (SPLD in short) polynomials, is introduced. The formal definition of an SPLD polynomial, which extends the concept of the SPQ polynomial (Ahmadi et al. in Math Oper Res 48:1316–1343, 2023), is defined. A type of bounded degree SOS hierarchy (BSOS-SPLD) is proposed to efficiently solve the optimization problems with SPLD polynomials, and several numerical examples are performed much better than the bounded degree SOS hierarchy (Lasserre et al. in EURO J Comput Optim 5:87–117, 2017). An exact SOS relaxation for a class of convex SPLD polynomial optimization problems is proposed. Finally, an application of SPLD polynomials to polynomial regression problems in statistics is presented. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

Structured Preconditioners in Adaptive optimization: A Unified Analysis

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Xie, Shuo Wang, Tianhao Reddi, Sashank Kumar, Sanjiv Li, Zhiyuan Toyota Technological Institute Chicago United States Google Research United States

We present a novel unified analysis for a broad class of adaptive optimization algorithms with structured (e.g., layerwise, diagonal, and kronecker-factored) preconditioners for both online regret minimization and offline convex optimization. Our analysis not only provides matching rate to several important structured preconditioned algorithms including diagonal AdaGrad, full-matrix AdaGrad, and AdaGrad-Norm, but also gives an improved convergence rate for a one-sided variant of Shampoo over that of original Shampoo. Interestingly, more structured preconditioners (e.g., diagonal Adagrad, AdaGrad-Norm which use less space and compute) are often presented as computationally efficient approximations to full-matrix Adagrad, aiming for improved optimization performance through better approximations. Our unified analysis challenges this prevailing view and reveals, perhaps surprisingly, that more structured preconditioners, despite using less space and computation per step, can outperform their less structured counterparts. To demonstrate this, we show that one-sided Shampoo, which is relatively much cheaper than full-matrix AdaGrad could outperform it both theoretically and experimentally. © 2025, CC BY.

关键词： optimization algorithms

FEATURE-BASED EVOLUTIONARY DIVERSITY optimization OF DISCRIMINATING INSTANCES FOR CHANCE-CONSTRAINED optimization PROBLEMS

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Ahouei, Saba Sadeghi Antipov, Denis Neumann, Aneta Neumann, Frank Optimisation and Logistics School of Computer and Mathematical Sciences The University of Adelaide Adelaide Australia LIP6 Sorbonne University Paris France

Algorithm selection is crucial in the field of optimization, as no single algorithm performs perfectly across all types of optimization problems. Finding the best algorithm among a given set of algorithms for a given problem requires a detailed analysis of the problem’s features. To do so, it is important to have a diverse set of benchmarking instances highlighting the difference in algorithms’ performance. In this paper, we evolve diverse benchmarking instances for chance-constrained optimization problems that contain stochastic components characterized by their expected values and variances. These instances clearly differentiate the performance of two given algorithms, meaning they are easy to solve by one algorithm and hard to solve by the other. We introduce a (µ+1) EA for feature-based diversity optimization to evolve such differentiating instances. We study the chance-constrained maximum coverage problem with stochastic weights on the vertices as an example of chance-constrained optimization problems. The experimental results demonstrate that our method successfully generates diverse instances based on different features while effectively distinguishing the performance between a pair of algorithms. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

Concentration Inequalities for the Stochastic optimization of Unbounded Objectives with Application to Denoising Score Matching

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Birrell, Jeremiah Department of Mathematics Texas State University San MarcosTX78666 United States

We derive novel concentration inequalities that bound the statistical error for a large class of stochastic optimization problems, focusing on the case of unbounded objective functions. Our derivations utilize the following tools: 1) A new form of McDiarmid’s inequality that is based on sample-dependent one-component-difference bounds and which leads to a novel uniform law of large numbers result for unbounded functions. 2) A Rademacher complexity bound for families of functions that satisfy an appropriate local-Lipschitz property. As an application of these results, we derive statistical error bounds for denoising score matching (DSM), an application that inherently requires one to consider unbounded objective functions, even when the data distribution has bounded support. In addition, our results establish the benefit of sample-reuse in algorithms that employ easily-sampled auxiliary random variables in addition to the training data, e.g., as in DSM, which uses auxiliary Gaussian random variables. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

Multiple-gain Estimation for Running Time of Evolutionary Combinatorial optimization

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Huang, Min Chen, Pengxiang Huang, Han He, Tongli Zhang, Yushan Hao, Zhifeng

The running-time analysis of evolutionary combinatorial optimization is a fundamental topic in evolutionary computation. Its current research mainly focuses on specific algorithms for simplified problems due to the challenge posed by fluctuating fitness values. This paper proposes a multiple-gain model to estimate the fitness trend of population during iterations. The proposed model is an improved version of the average gain model, which is the approach to estimating the running time of evolutionary algorithms for numerical optimization. The improvement yields novel results of evolutionary combinatorial optimization, including a briefer proof for the time complexity upper bound in the case of (1+1) EA for the Onemax problem, two tighter time complexity upper bounds than the known results in the case of (1+λ) EA for the knapsack problem with favorably correlated weights and a closed-form expression of time complexity upper bound in the case of (1+λ) EA for general k-MAX-SAT problems. The results indicate that the practical running time aligns with the theoretical results, verifying that the multiple-gain model is more general for running-time analysis of evolutionary combinatorial optimization than state-of-the-art methods. Copyright © 2025, The Authors. All rights reserved.

关键词： optimization algorithms

An Improved Gorilla Troops Algorithm for Real-World Engineering Problems 5

学校读者我要写书评

暂无评论

An Improved Gorilla Troops Algorithm for Real-World Engineer...

5th Asia Conference on Information Engineering, ACIE 2025

作者： Beskirli, Ayse Karamanoǧlu Mehmetbey University Faculty of Medicine Department of Medical Education and Informatics Karaman Turkey

ISBN: (纸本)9798331528409

There are many meta-heuristic algorithms inspired by nature for solving optimization problems. One of these algorithms is the Gorilla Troop optimization (GTO) algorithm, which has been recently proposed for solving continuous optimization problems and is inspired by the behavior of gorilla troops in nature. GTO includes various mechanisms to utilize the exploration and exploitation processes efficiently. Due to this feature, although the success varies according to the problem size, it is generally known that GTO is a successful algorithm. In this study, levy flight and roulette fitness distance balance (LRFDB) are added to the basic GTO to explore the search space more efficiently. With this method added to GTO, the algorithm is named LRFDB-GTO. Thus, it is aimed to strengthen the global search capability of the algorithm. The performance of LRFDBGTO was analyzed on test functions. Then it was applied to real world problems. The results of LRFDB-GTO and the original GTO are compared in tables. At the same time, the convergence curves and box plots of the algorithms are presented in figures. The experimental results show that the LRFDB-GTO algorithm performs better than the original GTO. © 2025 IEEE.

关键词： optimization algorithms

Local Optimisation Based Detection of Weak Targets in Isolated Forests 24

学校读者我要写书评

暂无评论

Local Optimisation Based Detection of Weak Targets in Isolat...

8th International Conference on Electronic Information Technology and Computer Engineering, EITCE 2024

作者： Hu, Jurong Xing, Yanxiao Li, Yuxiao School of Information Science and Engineering Hohai University Jiangsu Nanjing China School of Computer and Software Hohai University Jiangsu Nanjing China

ISBN: (纸本)9798400710094

Aiming at the problem that the iForest algorithm is not sensitive enough to local anomalies and produces a large number of false alarms in the detection results on some low sea state datasets, this paper proposes the iForest algorithm based on an improved splitting strategy. The algorithm introduces the Gini impurity, incorporates the Gini impurity parameter into the splitting strategy, and is more targeted in the selection of splitting attributes and splitting points, thus better adapting to the problem of detecting weak targets under different sea states, and has an excellent performance of high accuracy, low time duration, and low false alarm rate compared with the traditional methods in anomaly detection. © 2024 Copyright held by the owner/author(s).

关键词： optimization algorithms

Forest Covers and Bounded Forest Covers 50th

学校读者我要写书评

暂无评论

Forest Covers and Bounded Forest Covers

50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025

作者： Gaur, Daya Ram Gorain, Barun Patra, Shaswati Singh, Rishi Ranjan University of Lethbridge Alberta Canada Indian Institute of Technology Bhilai Chattisgarh Raipur India

ISBN: (纸本)9783031826696

We study approximation algorithms for the forest cover and bounded forest cover problems. A probabilistic 2+ϵ approximation algorithm for the forest cover problem is given using the method of dual fitting. A deterministic algorithm with a 2-approximation ratio that rounds the optimal solution to a linear program is given next. The 2-approximation for the forest cover is then used to give a 6-approximation for the bounded forest cover problem. The use of the probabilistic method to develop the 2+ϵ approximation algorithm may be of independent interest. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： optimization algorithms