如何数值求解变分问题?

计算科学 优化 约束优化 变分微积分
2021-11-28 14:53:53

例如,如何解决众所周知的等周长问题(即用固定长度的曲线包围最大面积)?

我们可以稍微简化一下,将曲线的两端固定在[a,0],[b,0],那么问题是

maximizeaby(x)dxsubject toab1+y(x)2dx=L

如何在不应用欧拉-拉格朗日方程的情况下直接求解?这是一个经典的优化问题,对吧?快速搜索导致 Euler 的有限差分法和 Ritz 的方法,以及一些具有固定端约束的示例。所以我想固定长度的约束应该通过拉格朗日乘数来处理。

有没有“更好”、更先进的方法?是否还有可以采用整体目标和一些任意约束的数值包,并在没有太多用户干预的情况下为您提供解决方案?

2个回答

在您询问的具体问题中(与理查德更一般的答案不同),事实证明您可以放松=约束成在不改变最优值的情况下,由此产生的问题可以用 Richard 提到的 CVX 软件来解决。


细节:直观地说,松弛是可能的,因为如果函数的弧长严格小于L,你可以把它放大到有弧长L确切地说,但是按比例放大函数必然会增加积分。因此,如果我们解决优化问题更换=在约束中,最优值和函数y(x)是一样的。

事实证明,由此产生的问题在参数中是凸的y(x),尽管是无限维的。目标是线性的。此外,函数1+y(z)2=(1,y(z))2是 y(x) 的凸函数,作为线性函数的范数(导数是线性的)。因此,由于凸泛函族的积分是凸的,映射是凸的。然后约束是凸的,因为它要求位于 y(x) 的凸函数的子级别y(x)y(x)y(x)ab1+y(x)2dxy(x)y(x)

以下 Python 代码给出了使用 Richard 提到的 CVXPY 软件解决此问题的示例:

import numpy as np
import cvxpy as cp

# Problem Data
n = 101 # points in interval [0,1] to discretize y at
L = 1.5

y = cp.Variable(n) # y[i] = y(i/n) for i=0,1,...,n
x = np.arange(n) / n
dy = y[1:] - y[:-1]
dx = x[1:] - x[:-1]

# Construct Optimization Problem
objective = (cp.sum(y[:-1]) + cp.sum(y[1:])) / 2 / n
constraints = [
    y[0] == 0, y[-1] == 0,
    cp.sum(cp.norm2(cp.vstack([dy, dx]), axis=0)) <= L,
]

prob = cp.Problem(cp.Maximize(objective), constraints)

# Solve Problem
prob.solve(verbose=True)

解决方案(在 找到y.value)如下:

等周长问题的数值解。

正如理查德指出的那样,您不能希望能够为这个问题添加通用约束并继续使用简单和/或高效的求解器。不过,您可以以一种非常简单的方式添加像这个弧长这样的凸约束,而不会带来太多麻烦。例如,如果我现在添加约束 ,则以下给出相同优化问题的输出:y(1/2)0.55

中点约束等周长问题的数值解。

我认为你的问题的实质是:

是否有可以采用整体目标和一些任意约束并为您提供解决方案的数值包?

答案是:大多数情况下,不会。

但是,一些软件包,例如GPOPSJuMPPyOMO,具有用于此功能的功能,如果您的问题是正确的形式,这些功能有时会起作用。

对于特定类别的问题,有出色的求解器,但任意约束允许您实际上很容易地在问题中构建相当多的复杂性。例如,考虑奇异控制问题。

例如,如果您将一个变量约束为一个集合,那么您的问题就变成了一个整数程序这些属于 NP 复杂性类,因此我们没有也可能不会有解决所有实例的良好通用算法。

如果您正在积分的函数以错误的方式从凸程序(通常很容易解决)转移到非凸程序,那么再次,没有通用算法。或者,如果你有一个基于案例的函数,那么你可能不再有平滑或连续的导数。

即使你的问题恰好属于我们有很好算法的一类实例,你也必须向计算机解释。像 cvxpy 这样的包要求你使用一个规范的函数库来编写你的问题,这不仅限制你使用可解决的实例,而且实际上构成了求解器遵循的秘诀。