约束优化的近似方法
proxmin的Python项目详细描述
最近极小化
此包中的方法为约束优化问题提供了求解器。它们都使用近端算子来处理非光滑罚函数。
算法：
- adam及其导数：用于单块和多块优化的具有梯度自适应梯度步长的前向后分裂。需要近端子迭代。
- 交替方向乘法器方法（admm）：两个潜在非光滑函数的rachford-douglas分裂。我们利用它的线性化形式来求解罚函数中的附加线性映射。
- 乘法器同时方向法（sdmm）：几个罚函数线性化admm的推广。
- 块乘法器同步方向法（bsdmm）：sdmm的扩展，用于处理多个参数中的凸目标函数。这是块坐标下降法的近端版本。
两块pgm或bsdmm用作非负矩阵分解（nmf）的后端解算器。由于我们的算法允许任何可循环函数作为每个矩阵因子的约束，所以我们更喜欢术语约束矩阵因子分解。
详细信息可以在“乘数-块同时定向法”中找到，这是Fred Moolekamp和Peter Melchior的多约束非凸问题的近端原对偶分裂算法。我们要求使用此软件包的任何已出版作品引用：
@ARTICLE{proxmin,
author="{Moolekamp}, Fred and {Melchior}, Peter",
title="Block-simultaneous direction method of multipliers: a proximal primal-dual splitting algorithm for nonconvex problems with multiple constraints",
journal="Optimization and Engineering",
year="2018",
month="Dec",
volume=19,
issue=4,
pages={871-885},
doi="10.1007/s11081-018-9380-y",
url="https://doi.org/10.1007/s11081-018-9380-y"
archivePrefix="arXiv",
eprint={1708.09066},
primaryClass="math.OC"
}
另外，让我们知道（例如@peter_melchior），我们很好奇。
安装和依赖项
pip install proxmin
对于最新的开发版本，克隆此存储库并执行python setup.py install。
代码在python>；2.7上运行，需要numpy和scipy。
接近
基于梯度的方法pgm和adam需要两个回调函数：一个用于计算梯度，另一个用于计算步长。在前一种情况下，步长被限制在0到2/L之间，其中L是梯度的lipschitz常数。
罚函数给出了近似映射：^ {< CD2>}。
可分析构造许多邻近算子，如^ {A7}。我们在proxmin.operators中提供了一些常见的。一类重要的约束是凸集的指标函数，其中，近点算子，给定某点^ {STR 1 } $ x< /强>，在集合中的欧几里得范数中，将闭合点返回到^ {STR 1 } $ x<强>。
示例：在二维单位圆上查找移位抛物线的最小值
importnumpyasnpimportproxmindX=np.array([1.,0.5])radius=1deff(X):"""Shifted parabola"""returnnp.sum((X-dX)**2,axis=-1)defgrad_f(X):return2*(X-dX)defstep_f(X,it=0):L=2.# Lipschitz constant of grad freturn1/Ldefprox_circle(X,step):"""Projection onto circle"""center=np.array([0,0])dX=X-center# exclude everything other than perimeter of circlephi=np.arctan2(dX[1],dX[0])returncenter+radius*np.array([np.cos(phi),np.sin(phi)])X=np.array([-1.,-1.])# or whereeverconverged=proxmin.pgm(X,grad_f,step_f,prox=prox_circle)
由于目标函数是光滑的，并且只有一个约束，因此可以简单地执行一个forward backward步骤的序列：沿梯度方向执行步骤，然后投影到约束子集上。这就是近端梯度法的本质。
如果第一个函数不平滑，可以使用admm。它允许满足两个函数（目标函数和一个惩罚函数），但它分别对待它们。与pgm不同，该约束只在优化结束时满足，并且只在一定的误差容限内。
继续上面的示例，通过在内部执行渐变步骤并返回更新的位置，smooth函数变为proxed函数：
defprox_gradf(X,step):"""Proximal gradient step"""returnX-step*grad_f(X)convergence=proxmin.admm(X,prox_gradf,step_f,prox_g=prox_circle,e_rel=1e-3,e_abs=1e-3)
约束矩阵分解（cmf）
矩阵分解寻求近似的目标矩阵{{CD4}}，作为{{CD5>}的乘积。如果这些约束只是非负的，那么方法是已知的N为NMF。
我们已经通过允许强制执行任意数量的约束，大大扩展了功能。如上所述，约束和目标函数将仅通过其近端运算符访问。
对于解算器，您只需执行以下操作：
fromproxminimportnmf# PGM-like approach for each factorprox_A=...# a single constraint on A, solved by projectionprox_S=...# a single constraint on S, solved by projectionA0,S0=...# initializationA,S=nmf(Y,A0,S0,prox_A=prox_A,prox_S=prox_S)# for multiple constraints, solved by ADMM-style splitproxs_g=[[...],# list of proxs for A[...]]# list of proxs for SA,S=nmf(Y,A0,S0,proxs_g=proxs_g)# or a combinationA,S=nmf(Y,A0,S0,prox_A=prox_A,prox_S=prox_S,proxs_g=proxs_g)
一个完整的和实用的例子在本文中的{A8}的高光谱解混研究中给出。
欢迎加入QQ群-->： 979659372
