优化|流形优化系列(一)

简介流形优化是非线性优化的一个分支,它主要关注在特定的几何结构下进行优化。在流形优化中,优化问题通常是在黎曼流形上进行的,而非欧几里得空间。黎曼流形是带有黎曼度量的流形,该度量为流形上的每个点都定义了一个内积。

优化|流形优化系列(一)

简介

流形优化是非线性优化的一个分支,它主要关注在特定的几何结构下进行优化。在流形优化中,优化问题通常是在黎曼流形上进行的,而非欧几里得空间。黎曼流形是带有黎曼度量的流形,该度量为流形上的每个点都定义了一个内积。这种内积结构提供了流形上测量长度和角度的方式,这在优化过程中非常重要,因为它允许我们定义梯度和Hessian等概念,并进行相应的优化操作。在流形优化的背景下,流形通常是解的约束集。例如,当解必须是正交矩阵、单位范数向量或其它特殊结构时,这些集合都可以被看作流形。对于连续优化,讨论多面体是考虑线性优化问题的基础,而在欧几里得空间中的微积分被用于发展非线性欧几里得优化理论。同样地,黎曼流形上的微积分,借助微分几何学(尤其是黎曼几何学)得以促进,对于黎曼流形上的优化是至关重要的。

流形优化相对于传统欧几里得空间上的优化方法,优势在于:

  1. 在黎曼流形上迭代,减少建模误差,提高一些非线性问题的表示能力;
  2. 充分利用目标函数的内在几何结构,通过选取合适的黎曼度量可将一些非凸优化问题转化为凸优化问题;
  3. 保持最优化问题的尺度不变性。

在各个应用领域的需求牵引下,相关学者的研究工作极大地促进了黎曼流形优化理论的发展与工程应用,如Hermitian 特征值问题、自适应正则化、迹范数、相机位姿估计、经济负载分配、对称特征值问题、低秩矩阵填充等,其技术成果已成功应用于相关学科,如航空航天、理论物理、无线通信、医学成像、自动控制、计算机视觉等。

推荐感兴趣的同学阅读参考文献中的书目。

流形优化基础知识

优化|流形优化系列(一)

常见流形

以下是一些在流形优化中常用的流形例子:

  1. 球面流形 (Sphere Manifold):
优化|流形优化系列(一)

基础概念

当我们考虑流形优化问题时,特别是在黎曼流形上,优化的算法需要考虑流形的几何结构。为此,我们引入一些特定的概念,如黎曼梯度、收缩映射(retraction)和向量传输(vector transport)。以下是这些概念的定义:

  1. 黎曼梯度 (Riemannian Gradient):
优化|流形优化系列(一)

优化|流形优化系列(一)

优化|流形优化系列(一)

常见算法

优化|流形优化系列(一)

流形上的梯度下降法的关键在于如何正确地“移动”在流形上。由于流形的几何约束,我们不能简单地进行线性更新,而是需要利用流形的几何结构进行更新。黎曼梯度和收缩映射是这个过程中的核心组成部分。

近年来多种传统优化算法已成功地被扩展到流形优化领域,包括梯度下降,共轭梯度法,随机梯度下降法,牛顿法,信赖域法,内点法,BFGS和ADMM等。需要注意的区别是,流形上的梯度及Hessian矩阵信息也与流形本身有关(黎曼梯度和黎曼Hessian矩阵),同时更新过程也将依赖于收缩映射和传输,这些操作确保算法在流形的几何约束内进行迭代,并保持算法的稳定性和收敛性。因此,对流形及其相关知识的深入了解和熟悉变得尤为重要。

流形优化计算工具

Manopt

Manopt 是一个专门为研究人员和工程师设计的优化工具箱,旨在简化和推动定义在流形上的优化问题的解决过程。Manopt 提供了一系列工具和算法,帮助用户轻松地在各种流形结构上设置和解决优化问题。Manopt 的优势在于它的灵活性和易用性。它支持多种流形结构,如正定对称矩阵、Stiefel流形和球面流形等。此外,它的设计目标是为用户提供一个简单、直观的接口,使用户无需深入了解流形优化的复杂性就可以轻松应用。此外,Manopt 还拥有丰富的文档和教程,帮助新手快速上手,同时为经验丰富的研究者提供高级功能和自定义选项。

PyManopt是Manopt的Python版本,Manopt.jl是为Julia编程语言设计的Manopt版本。

实例

优化|流形优化系列(一)

优化|流形优化系列(一)

以下是使用Manopt 中的信赖域法解决这个优化问题的代码:

 % 生成随机问题数据
    n = 1000;
    A = randn(n);
    A = .5*(A+A.');

    % 创建问题结构
    manifold = spherefactory(n);
    problem.M = manifold;

    % 定义问题成本函数及其欧几里得梯度。
    problem.cost  = @(x) -x'*(A*x);
    problem.egrad = @(x) -2*A*x;% 注意 'e' 在 'egrad' 中代表欧几里得

    % 数值检查梯度一致性(可选)
    checkgradient(problem);

    % 解决
    [x, xcost, info, options] = trustregions(problem);

    % 显示一些统计数据
    figure;
    semilogy([info.iter], [info.gradnorm], '.-');
    xlabel('迭代次数');
    ylabel('f 的梯度的范数');

运行结果:

优化|流形优化系列(一)

优化|流形优化系列(一)

在之后的系列中,我们会对上述提到的流形优化中的常见基本概念和算法进行详细的分析。

参考文献

  1. Absil P A, Mahony R, Sepulchre R. Optimization algorithms on matrix manifolds[M]. Princeton University Press, 2008.
  2. Boumal N. An introduction to optimization on smooth manifolds[M]. Cambridge University Press, 2023.
  3. Sato H. Riemannian optimization and its applications[M]. Berlin: Springer, 2021.
  4. 潘汉,黎曼流形优化及其应用, 北京, 科学出版社, 2020
  5. 刘浩洋, 户将, 李勇锋,文再文,最优化:建模、算法与理论, 第二版草稿, 7.4 流形约束优化算法

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://itzsg.com/80009.html

(0)

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

联系我们YX

mu99908888

在线咨询: 微信交谈

邮件:itzsgw@126.com

工作时间:时刻准备着!

关注微信