自动差异化优化工具箱™

本专栏由优化工具箱文档的作者Alan Weiss撰写。把它拿走，艾伦。

嗨,各位。你可能知道，当你有函数的梯度时，解决一个优化问题，也就是找到一个函数最小的点会更容易。这很容易理解:梯度指向上坡，所以如果你朝相反的方向移动，你通常会到达最小值。优化工具箱算法基于比这更复杂的算法，而这些更复杂的算法也受益于梯度。

如何在函数的同时给解算器一个梯度?直到最近，你还必须将梯度作为一个单独的输出来计算，这将带来所有的痛苦和错误的可能性。然而，对于R2020b，基于问题的方法使用自动微分来计算一般非线性优化问题的问题梯度。我会解释所有这些词的意思。简而言之，只要你的函数是由多项式、三角函数和指数等初等函数组成的，优化工具箱就会自动计算和使用你的函数的梯度，而不需要你付出任何努力。

“一般非线性”短语意味着自动微分适用于以下问题fmincon而且fminunc这是一般的约束或无约束最小化，与线性规划或最小二乘或其他需要其他专门求解器的问题类型相反。

自动微分，也称为AD，是一种符号导数，它将函数转换为代码，计算特定点的函数值和导数值。这个过程是透明的;你不需要编写任何特殊的代码来使用AD。实际上，稍后您将看到，为了不让求解器使用AD，必须指定一些名称-值对。

内容

具体问题具体分析优化

基于问题的优化方法是用优化变量和表达式来编写问题。例如，为了最小化测试函数${\rm fun}(x,y) = 100(y-x^2)^2 + (1-x)^2$在单元盘$x^2+y^2\le 1$内，您首先创建优化变量。

X = optimvar(“x”）;Y = optimvar(“y”）;

然后使用这些变量创建优化表达式。

趣味性= 100*(y - x^2)^2 + (1 - x)^2;Unitdisk = x^2 + y^2 <= 1;

在适当的问题字段中使用这些表达式创建一个优化问题。

问题=优化问题(“客观”有趣的,“约束”, unitdisk);

打电话解决问题解决，从x = 0开始，y = 0。

x0。X = 0;x0。Y = 0;Sol = solve(prob,x0)

使用fmincon解决问题。找到满足约束条件的局部最小值。优化完成是因为目标函数在可行方向上不递减，在最优性容差值范围内，约束条件满足在约束容差值范围内。Sol = struct，字段:x: 0.7864 y: 0.6177

的解决函数调用fmincon解决问题。事实上,解决使用AD加快解决过程。让我们更详细地检查解决方案过程，以了解实际情况。但首先，在单位圆盘上画出1加上目标函数的对数，并在解处画一个红圈。

[R,TH] = ndgrid(linspace(0, 1100)，linspace(0,2*pi,200));[X,Y] = pol2cart(TH,R);surf(X,Y,log(1+100*(Y - X ^2))。²+ (1 - x)²，“EdgeColor”，“没有”)色条视图(0,90)轴平等的持有在plot3 (sol.x sol.y 1,“罗”，“MarkerSize”, 10)从

自动分化效应

为了更详细地检查解决过程，再次解决问题，这一次要求更多解决输出。检查求解器所接受的迭代和函数计算的次数。

[sol,fval,exitflag,output] = solve(prob,x0);流('fmincon接受%g次迭代和%g次函数计算。，.．.output.iterations output.funcCount)

使用fmincon解决问题。找到满足约束条件的局部最小值。优化完成是因为目标函数在可行方向上不递减，在最优性容差值范围内，约束条件满足在约束容差值范围内。Fmincon需要24次迭代和34次函数计算。

输出结构显示求解器需要24次迭代和34个函数计数。再次运行该问题，这一次强制求解器不使用AD。

[sol2,fval2,exitflag2,output2] = solve(prob,x0, x0，.．.“ObjectiveDerivative”，“有限差分”，“ConstraintDerivative”，“有限差分”）;流('fmincon接受%g次迭代和%g次函数计算。，.．.output2.iterations,output2.funcCount) plot([1 2]，[输出。funcCount output2.funcCount),的r -，.．.[1 - 2],[输出。funcCount output2.funcCount),“罗”) ylabel (函数计算的xlim([0.8 2.2]) ([0 90])函数计数(越低越好)，“位置”，“西北”) ax = gca;斧子。XTick = [1,2];斧子。XTickLabel = {“广告”，没有广告的}；

使用fmincon解决问题。找到满足约束条件的局部最小值。优化完成是因为目标函数在可行方向上不递减，在最优性容差值范围内，约束条件满足在约束容差值范围内。Fmincon需要24次迭代和84次函数计算。

这一次，求解器接受84个函数计数，而不是34个。产生这种差异的原因是自动微分。

不管有没有AD，解决方案几乎是一样的:

流('溶液差异的范数为%g.\n'、规范([sol.x,索尔。- [sol2.x,sol2.y]))

溶液差异的范数为1.80128e-09。

什么是自动差异化?

AD类似于符号微分:每个函数本质上是符号微分，结果转化为代码，由MATLAB运行来计算导数。查看结果代码的一种方法是使用prob2struct函数。我们试试吧概率．

Problem = prob2struct(probb);problem.objective

ans = function_handle with value: @ generatedobobjective

prob2struct创建一个名为generatedObjective.m．这个函数包含一个自动生成的梯度。查看函数文件的内容。

函数[obj, grad] = generatedobobjective (inputVariables)计算目标函数值和梯度％% OBJ = generatedoobjective (INPUTVARIABLES)计算客观值% OBJ在点INPUTVARIABLES。％% [OBJ, GRAD] = generatedoobjective (INPUTVARIABLES)额外计算%当前点的客观梯度值GRAD。％由prob2struct在06-10-2020 09:01:35自动生成%%变量索引。Xidx = 1;Yidx = 2;将基于求解器的变量映射到基于问题的变量。x = inputVariables(xidx);y = inputVariables(yidx);计算目标函数。Arg1 = (y - x.^2);Arg2 = 100;Arg3 = arg1.^2;Arg4 = (1 - x);Obj = ((arg2 .* arg3) + arg4.^2);计算目标梯度。如果Nargout > 1 arg5 = 1;Arg6 = 0 ([2,1]);arg6 (xidx:) = (- (arg5。* 2 * (arg4 (:)))) + ((-(( arg5。*最长(:))。* 2 * (__arg1(:))))。* 2 * (x (:)));Arg6 (yidx，:) = (arg5.*arg2(:)).*2.*(arg1(:)));Grad = arg6(:);结束结束

虽然这段代码对你来说可能不清楚，但你可以将AD梯度计算与符号表达式进行比较，看看它们是否相同:

美元\微分算符({\ rm乐趣})= [-400 (x ^ 2) x - 2 (1 - x); \ 200 (x ^ 2)]美元

这种方式解决而且prob2struct将优化表达式转换为代码本质上与微积分学生学习的方式相同，取表达式的每个部分并应用微分规则。中解释了计算梯度过程的细节自动判别背景，描述了大多数AD软件使用的“向前”和“向后”过程。目前，优化工具箱只使用“向后”AD。

为了使用这些微分规则，软件必须对目标函数或约束函数中的每个函数具有微分规则。支持的运算符列表包括多项式、三角函数和指数函数及其逆，以及乘法和加法及其逆。看到支持优化变量和表达式的操作．

自动微分法有什么好处?

AD降低了求解器进行函数计算的次数。在没有AD的情况下，非线性求解器通过有限差分来估计梯度，例如$(f(x+\delta e_1) - f(x))/\delta，$其中$e_1$是单位向量(1,0，…，0)。求解器计算n默认为这种形式的有限差分，其中n是问题变量的数量。对于有大量变量的问题，这个过程需要进行大量的函数求值。

有了AD和支持函数，求解者不需要采取有限差分步骤，因此导数估计过程需要的函数计算更少，精度更高。

这并不是说AD总是加快求解器的速度。对于复杂的表达式，求自动导数比求有限差分更费时。一般来说，当问题具有大量变量且稀疏时，AD比有限差分更快。当问题变量少且函数复杂时，AD速度较慢。

不支持的操作怎么办?

到目前为止，我已经讨论了支持操作的自动微分。如果你有一个黑盒函数，它的底层代码甚至可能不在MATLAB中呢?或者，如果您只是有一个不支持基于问题的优化的函数，比如贝塞尔函数，该怎么办?方法将函数转换为优化表达式，以在基于问题的方法中包含此类函数fcn2optimexpr函数。例如，使用besselj函数,

fun2 = fcn2optimexpr (@ (x, y) besselj (1, x ^ 2 + y ^ 2), x, y);

fcn2optimexpr允许您在基于问题的方法中使用不受支持的操作。然而,fcn2optimexpr不支持AD。所以，当你使用fcn2optimexpr，用有限差分来估计目标函数或非线性约束函数的梯度。有关更多信息，请参见基于问题的工作流程中的供给导数．

目前AD不支持高阶导数。换句话说，您不能自动生成二阶或三阶导数的代码。你只能得到一阶导数(梯度)。

最终的想法

AD有助于提高求解仅由受支持函数组成的优化问题的速度和可靠性。然而，在某些情况下，它不能提高速度，目前AD还不能用于非线性最小二乘或方程求解问题。

在我看来，AD最有用的特性是在基于问题的优化中使用它是完全透明的。从R2020b开始，AD自动应用，您无需付出任何努力。如果你觉得它对解决你的优化问题有用，请发表你的评论，让我们知道在这里．

获取MATLAB代码

发布与MATLAB®R2020b