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

A Generalization Result for Convergence in Learning-to-Optimize

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Sucker, Michael Ochs, Peter Department of Mathematics University of Tübingen Tübingen Germany Department of Mathematics and Computer Science Saarland University Saarbrücken Germany

Convergence in learning-to-optimize is hardly studied, because conventional convergence guarantees in optimization are based on geometric arguments, which cannot be applied easily to learned algorithms. Thus, we develop a probabilistic framework that resembles deterministic optimization and allows for transferring geometric arguments into learning-to-optimize. Our main theorem is a generalization result for parametric classes of potentially non-smooth, non-convex loss functions and establishes the convergence of learned optimization algorithms to stationary points with high probability. This can be seen as a statistical counterpart to the use of geometric safeguards to ensure convergence. To the best of our knowledge, we are the first to prove convergence of optimization algorithms in such a probabilistic framework. © 2024, CC BY.

关键词： optimization algorithms

COMPLEXITY AND NUMERICAL EXPERIMENTS OF A NEW ADAPTIVE GENERIC PROXIMAL BUNDLE METHOD

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Guigues, Vincent Monteiro, Renato D.C. Tran, Benoit School of Applied Mathematics FGV Praia de Botafogo Rio de Janeiro Brazil Georgia Institute of Technology AtlantaGA30332-0205 United States

This paper develops an adaptive generic proximal bundle method, shows its complexity, and presents numerical experiments comparing this method with two bundle methods on a set of optimization problems. Copyright ©... 详细信息

关键词： optimization algorithms

NON-MYOPIC MULTIFIDELITY BAYESIAN optimization

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Di Fiore, Francesco Mainini, Laura Politecnico di Torino Italy Massachusetts Institute of Technology Politecnico di Torino United States

Bayesian optimization is a popular framework for the optimization of black box functions. Multifidelity methods allows to accelerate Bayesian optimization by exploiting low-fidelity representations of expensive objective functions. Popular multifidelity Bayesian strategies rely on sampling policies that account for the immediate reward obtained evaluating the objective function at a specific input, precluding greater informative gains that might be obtained looking ahead more steps. This paper proposes a non-myopic multifidelity Bayesian framework to grasp the long-term reward from future steps of the optimization. Our computational strategy comes with a two-step lookahead multifidelity acquisition function that maximizes the cumulative reward obtained measuring the improvement in the solution over two steps ahead. We demonstrate that the proposed algorithm outperforms a standard multifidelity Bayesian framework on popular benchmark optimization problems. Copyright © 2022, The Authors. All rights reserved.

关键词： optimization algorithms

Improved SQP and SLSQP algorithms for Feasible Path-based Process Optimisation

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ma, Yingjie Gao, Xi Liu, Chao Li, Jie Centre for Process Integration Department of Chemical Engineering School of Engineering The University of Manchester ManchesterM13 9PL United Kingdom Department of Chemical Engineering Massachusetts Institute of Technology CambridgeMA02139 United States School of Electronic and Information Engineering Tongji University Shanghai201804 China School of Mechanical and Electrical Engineering Jinggangshan University Jiangxi Ji'an343009 China

Feasible path algorithms have been widely used for process optimisation due to its good convergence. The sequential quadratic programming (SQP) algorithm is usually used to drive the feasible path algorithms towards optimality. However, existing SQP algorithms may suffer from inconsistent quadratic programming (QP) subproblems and numerical noise, especially for ill-conditioned process optimisation problems, leading to a suboptimal or infeasible solution. In this work, we propose an improved SQP algorithm (I-SQP) and an improved sequential least squares programming algorithm (I-SLSQP) that solves a least squares (LSQ) subproblem at each major iteration. A hybrid method through the combination of two existing relaxations is proposed to solve the inconsistent subproblems for better convergence and higher efficiency. We find that a certain part of the dual LSQ algorithm suffers from serious cancellation errors, resulting in an inaccurate search direction or no viable search direction generated. Therefore, the QP solver is used to solve LSQ subproblems in such a situation. The computational results indicates that I-SLSQP is more robust than fmincon in MATLAB, IPOPT, Py-SLSQP and I-SQP. It is also shown that I-SLSQP and Py-SLSQP is superior to I-SQP for ill-conditioned process optimisation problems, whilst I-SQP is more computationally efficient than I-SLSQP and Py-SLSQP for well-conditioned problems. © 2024, CC BY-NC-ND.

关键词： optimization algorithms

Towards optimal hierarchical training of neural networks

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Feischl, Michael Rieder, Alexander Zehetgruber, Fabian Institute of Analysis and Scientific Computing TU Wien Austria

We propose a hierarchical training algorithm for standard feed-forward neural networks that adaptively extends the network architecture as soon as the optimization reaches a stationary point. By solving small (low-dimensional) optimization problems, the extended network provably escapes any local minimum or stationary point. Under some assumptions on the approximability of the data with stable neural networks, we show that the algorithm achieves an optimal convergence rate s in the sense that loss #parameters−s. As a byproduct, we obtain computable indicators which judge the optimality of the training state of a given network and derive a new notion of generalization error. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Investigating layer-selective transfer learning of QAOA parameters for Max-Cut problem

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Venturelli, Francesco Aldo Das, Sreetama Caruso, Filippo Department of Engineering University Pompeu Fabra Tànger 122-140 Barcelona08018 Spain Sesto FiorentinoI-50019 Italy Department of Physics and Astronomy University of Florence Via Sansone 1 Sesto FiorentinoI-50019 Italy University of Florence Via Nello Carrara 1 Sesto FiorentinoI-50019 Italy

Quantum approximate optimization algorithm (QAOA) is a variational quantum algorithm (VQA) ideal for noisy intermediate-scale quantum (NISQ) processors, and is highly successful for solving combinatorial optimization problems (COPs). It has been observed that the optimal variational parameters obtained from one instance of a COP can be transferred to another instance, producing sufficiently satisfactory solutions for the latter. In this context, a suitable method for further improving the solution is to fine-tune a subset of the transferred parameters. We numerically explore the role of optimizing individual QAOA layers in improving the approximate solution of the Max-Cut problem after parameter transfer. We also investigate the trade-off between a good approximation and the required optimization time when optimizing transferred QAOA parameters. These studies show that optimizing a subset of layers can be more effective at a lower time-cost compared to optimizing all layers. © 2024, CC BY.

关键词： optimization algorithms

Functionally Constrained Algorithm Solves Convex Simple Bilevel Problems

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Zhang, Huaqing Chen, Lesi Xu, Jing Zhang, Jingzhao IIIS Tsinghua University China Shanghai Qizhi Institute China Shanghai AI Lab China

This paper studies simple bilevel problems, where a convex upper-level function is minimized over the optimal solutions of a convex lower-level problem. We first show the fundamental difficulty of simple bilevel problems, that the approximate optimal value of such problems is not obtainable by first-order zero-respecting algorithms. Then we follow recent works to pursue the weak approximate solutions. For this goal, we propose a novel method by reformulating them into functionally constrained problems. Our method achieves near-optimal rates for both smooth and nonsmooth problems. To the best of our knowledge, this is the first near-optimal algorithm that works under standard assumptions of smoothness or Lipschitz continuity for the objective functions. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Parameterized algorithms for Optimal Refugee Resettlement

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Chen, Jiehua Schlotter, Ildikó Simola, Sofia TU Wien Austria HUN-REN Centre for Economic and Regional Studies Hungary Budapest University of Technology and Economics Hungary

We study variants of the Optimal Refugee Resettlement problem where a set F of refugee families need to be allocated to a set P of possible places of resettlement in a feasible and optimal way. Feasibility issues emerge from the assumption that each family requires certain services (such as accommodation, school seats, or medical assistance), while there is an upper and, possibly, a lower quota on the number of service units provided at a given place. Besides studying the problem of finding a feasible assignment, we also investigate two natural optimization variants. In the first one, we allow families to express preferences over P, and we aim for a Pareto-optimal assignment. In a more general setting, families can attribute utilities to each place in P, and the task is to find a feasible assignment with maximum total utilities. We study the computational complexity of all three variants in a multivariate fashion using the framework of parameterized complexity. We provide fixed-parameter tractable algorithms for a handful of natural parameterizations, and complement these tractable cases with tight intractability results. © 2024, CC BY.

关键词： optimization algorithms

Anderson Acceleration in Nonsmooth Problems: Local Convergence via Active Manifold Identification

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Li, Kexin Bai, Luwei Wang, Xiao Wang, Hao School of Information Science and Technology ShanghaiTech University Shanghai China Department of AI Computing Peng Cheng Laboratory Shenzhen China

Anderson acceleration is an effective technique for enhancing the efficiency of fixed-point iterations;however, analyzing its convergence in nonsmooth settings presents significant challenges. In this paper, we investigate a class of nonsmooth optimization algorithms characterized by the active manifold identification property. This class includes a diverse array of methods such as the proximal point method, proximal gradient method, proximal linear method, proximal coordinate descent method, Douglas-Rachford splitting (or the alternating direction method of multipliers), and the iteratively reweighted 1 method, among others. Under the assumption that the optimization problem possesses an active manifold at a stationary point, we establish a local R-linear convergence rate for the Anderson-accelerated algorithm. Our extensive numerical experiments further highlight the robust performance of the proposed Anderson-accelerated methods. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms