用最小迭代量找到所需方向的算法



这个问题有三个组成部分:

  1. 一个三维向量A
  2. A";光滑的";函数F
  3. 所需向量B(也是三维的(

我们想找到一个向量a,当它通过F时,将产生向量B

F(A) = B

F可以是以某种方式转换或扭曲A的任何东西。重点是,我们希望迭代调用F(A(,直到生成B

问题是:

我们如何做到这一点,但在找到等于B的向量(在合理的阈值内(之前,对F调用最少?

我假设;光滑的";等于是可微分的。由于光滑性的概念只在有理/实数中有意义,我还假设你正在解决一个基于浮点的问题。

在这种情况下,我将把这个问题表述为一个非线性规划问题。即最小化给出的f(A(和B之间的差的平方范数

(F(A)_1 -B_1)² + (F(A)_2 - B_2)² + (F(A)_3 - B_3)²

应该清楚的是,当且仅当f(A(=B时,该表达式为零,否则为正。因此,您希望将其最小化。

例如,您可以使用scipy优化套件中内置的求解器(可用于python(:

from scipy.optimize import minimize
# Example function
f = lambda x : [x[0] + 1, x[2], 2*x[1]]
# Optimization objective
fsq = lambda x : sum(v*v for v in f(x))
# Initial guess
x0 = [0,0,0]
res = minimize(fsq, x0, tol=1e-6)
# res.x is the solution, in this case
# array([-1.00000000e+00,  2.49999999e+00, -5.84117172e-09])

二进制搜索(如上所述(只有当函数是1-d时才有效,这是而不是这里的情况。您可以通过将method="name"添加到对minimize的调用中来尝试不同的优化方法,请参阅API。在不了解函数性质的情况下,并不总是清楚哪种方法最适合您的问题。根据经验,提供给解算器的信息越多越好。如果可以显式计算F的导数,则将其传递给解算器将有助于减少所需的求值次数。如果F具有Hessian(即,如果它是可微的两倍(,那么提供Hessian也会有所帮助。

或者,您可以直接通过res = least_squares(f, x0)F上使用least_squares函数。这可能会更快,因为求解器可以处理这样一个事实,即你正在求解最小二乘问题,而不是一般的优化问题。

从更普遍的角度来看,恢复产生给定值的函数自变量的问题被称为反问题。这些问题已经得到了广泛的研究。

假设F(A(=B,F,B是已知的,而A仍然未知,您可以从一个简单的梯度搜索开始:

F(A)~= F(C) + F'(C)*(A-C)~=B

其中F'(C)是在点C中计算的F((的梯度。我假设你现在可以解析计算这个梯度。

所以,你可以选择一个点C,你估计它离解决方案不远,然后迭代:

C= Co;
While(true)
{
Ai = inverse(F'(C))*(B-F(C)) + C;
convergence = Abs(Ai-C);
C=Ai;
if(convergence<someThreshold)
break;
}

如果F((的梯度不能解析计算,你可以估计它。设Ei, i=1:3为正态向量,则

Fi'(C) = (F(C+Ei*d) - F(C-Ei*d))/(2*d);
F'(C) = [F1'(C) | F2'(C) | F3'(C)];

并且CCD_ 11可以被选择为固定的或者作为收敛值的函数。

这些算法存在局部最大值、零梯度区域等问题,因此为了使其工作,起点(Co(必须离函数F((表现为单调的解不远

您似乎可以尝试一种元启发式方法。遗传算法(GA(可能是最好的解决方案。你可以启动一个数量为a的向量来初始化一个种群,并使用GA对你的种群进行进化,这样你就会有更好的一代,他们有更好的向量,F(Ax(更接近B。你的适应度函数可以是一个比较F(Ai(和B的简单函数你可以选择每一代人如何变异你的种群。

关于GA的一个简单例子可以在这里找到链接

最新更新