障碍函数约束优化中的梯度下降

计算科学 约束优化 凸优化
2021-12-25 02:49:56

这个问题可能太基础了,但我想知道是否可以实现简单的方法,例如梯度下降或其变体,以在约束优化问题中找到障碍函数的最小值。

如果可能,这种方法会出现什么问题,是否推荐?

例如:

minimizef(x1,x2,...,xn)

subject to:h(x1,x2,...,xn)C

应用对数障碍函数,目标函数变为:

P(x1,x2,...,xn)=f(x1,x2,...,xn)log(h(x1,x2,...,xn))

1个回答

非数学观点:

在这种情况下,梯度下降的潜在问题是,你的梯度通常在你的障碍处不连续。让我们以这个案例为例:

最小化:

f(x)=x
受制于:
h(x)=x,h(x)>=0

在这种情况下,您的梯度下降将从正范围走向零x>0并且可能会超过最小值x=0. 为防止这种情况发生,您可以在任何地方引入附加条款x<0,但你仍然有一个不连续性x=0. 然后你可以做一个线搜索,这基本上意味着当你的梯度下降算法尝试下坡并发现它的错误(residuum)没有改善时(即罚球)x<0),它将减小其步长并重试。这样,它可以以越来越小的步长逐渐接近您的最小值,直到满足某些标准。这就像你的头撞到墙上,但每走一步都会将你的速度减半:-) 你会到达墙......慢慢地。

您提出的解决方案是克服不连续性问题的可行选择,请注意,当您介绍该术语时,它会稍微改变最小值。

情节xlog(x)从 0 到 5:

x - log(x) 从 0 到 5 的图

您可以通过对数项前面的参数控制新的最小值偏离多远,但您永远不会达到真正的最小值。(在许多情况下,这完全没问题!)