超出经典复杂度界限的高阶方法:不准确的高阶近点方法
Masoud Ahookhosh1, Yurii Nesterov2
1Department of Mathematics, University of Antwerp, Middelheimlaan 1, 2020 Antwerp, Belgium.
概括
我们提出了一个双层优化 (BiOPT) 框架,用于最小化凸函数的和. 这种新的方法通过优化近位数和使用不准确的高阶方法,为特定问题提供了超快的方法.
科学领域:
- 优化理论 优化理论
- 凸的分析 凸的分析
- 数字分析 数字分析
背景情况:
- 缩小凸函数的和是优化的一个基本问题.
- 对于复杂的目标函数,现有的方法可能缺乏效率.
- 高阶方法为更快的融合提供了潜力,但可能是计算密集的.
研究的目的:
- 引入一个灵活的双层优化 (BiOPT) 框架.
- 开发一种加速的不准确的高阶近接点方法.
- 在特定问题上实现一个2q级的方法,其收率为O{\displaystyle O}1/k^2q).
主要方法:
- 将目标规范化为一个pth级近接项.
- 设计一个通用的不准确的pth顺序近点方案与加速.
- 使用较低级别的非欧几里德方法解决辅助问题,包括复合梯度方案.
- 采用估计序列技术进行加速.
主要成果:
- BiOPT框架允许灵活选择近位数顺序 (p) 和较低级别的溶解器.
- 为上层开发了一种加速的不准确的第五阶近点方法.
- 将加速的上层方法与低层非欧几里德复合梯度方案相结合,可以得到2q级方法.
- 导出的收率是O(1/k^2q),为某些问题类提供超快的收率.
结论:
- 生物OPT框架为凸优化提供了一种多功能和高效的方法.
- 拟议的方法实现了高度的趋同,在特定问题上优于现有的技术.
- 这项研究为在各种科学领域开发更快的优化算法开辟了道路.
相关概念视频
Accuracy, limits, and approximation
441
Accuracy, limits, and approximations are common in many fields, especially in engineering calculations. These concepts are imperative for ensuring that a given value is as close as possible to its true value.
Accuracy is defined as the closeness of the measured value to the true or actual value. In engineering mechanics, repeated measurements are taken during theoretical or experimental analyses to ensure that the result is precise and accurate.
The accuracy of any solution is based on the...
Accuracy is defined as the closeness of the measured value to the true or actual value. In engineering mechanics, repeated measurements are taken during theoretical or experimental analyses to ensure that the result is precise and accurate.
The accuracy of any solution is based on the...
441
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
44
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
44
Theorems of Pappus and Guldinus: Problem Solving
708
Pappus and Guldinus's theorems are powerful mathematical principles that are used for finding the surface area and volume of composite shapes. For example, consider a cylindrical storage tank with a conical top. Finding the surface area or volume can be challenging for such complex shapes. These theorems are particularly useful in calculating the volume and surface area of such systems. Here, the cylindrical storage tank with a conical top can be broken down into two simple shapes: a...
708
Routh-Hurwitz Criterion II
194
In the application of the Routh-Hurwitz criterion, two specific scenarios can arise that complicate stability analysis.
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
194
Propagation of Uncertainty from Random Error
654
An experiment often consists of more than a single step. In this case, measurements at each step give rise to uncertainty. Because the measurements occur in successive steps, the uncertainty in one step necessarily contributes to that in the subsequent step. As we perform statistical analysis on these types of experiments, we must learn to account for the propagation of uncertainty from one step to the next. The propagation of uncertainty depends on the type of arithmetic operation performed on...
654
One-Compartment Open Model: Wagner-Nelson and Loo Riegelman Method for ka Estimation
403
This lesson introduces two critical methods in pharmacokinetics, the Wagner-Nelson and Loo-Riegelman methods, used for estimating the absorption rate constant (ka) for drugs administered via non-intravenous routes. The Wagner-Nelson method relates ka to the plasma concentration derived from the slope of a semilog percent unabsorbed time plot. However, it is limited to drugs with one-compartment kinetics and can be impacted by factors like gastrointestinal motility or enzymatic degradation.
On...
On...
403


