如何高效优化具有两个局部最小值的函数?

huangapple go评论72阅读模式
英文:

How to efficiently optimize a function with two local minima?

问题

I want to minimize a function that I know it has two local minima, but using scipy to optimize it I don't get the global minimum.
我想要最小化一个函数,我知道它有两个局部最小值,但使用scipy来优化它时,我无法得到全局最小值。

I want to know of a way to do it that is fast, as I have to do it thousands of times.
我想知道一种快速的方法来做这件事,因为我需要重复执行成千上万次。

I have functions to compute a result from two vectors of 3 components (v1 and v2) and an angle theta:
我有函数可以从两个具有3个分量的向量(v1v2)和一个角度theta计算结果:

def get_v_theta(v, theta):
    vx = v[0]
    vy = v[1]
    vz = v[2]
    v_theta = (vx + vy)/2 + (vx - vy)/2*np.cos(2*theta) + vz*np.sin(2*theta)
    return v_theta

def get_result(v1_theta, v2_theta):
    v_max = max(v1_theta, v2_theta)
    v_min = min(v1_theta, v2_theta)
    v_med = (v_max + v_min)/2
    v_alt = (v_max - v_min)/2
    if v_med > 0:
        result = (v_alt/100 + v_med/400)**(-1)
    else:
        result = 100/v_alt
    return result

def get_result_theta(theta, v1, v2):
    v1_theta = get_v_theta(v1, theta)
    v2_theta = get_v_theta(v2, theta)
    result = get_result(v1_theta, v2_theta)
    return result

I want to find the angle theta that minimizes result, given two vectors.
我想找到使result最小化的角度theta,给定两个向量。

For example, if my vectors are:
例如,如果我的向量是:

import numpy as np

v1 = np.array([2.91931, 0.758059, 0.10201])
v2 = np.array([-1.29405, 7.76101, -1.75803])

I can plot result vs theta and see that the theta that minimizes result should be around -1.4.
我可以绘制resulttheta的图表,看到最小化resulttheta应该在-1.4左右。

import matplotlib.pyplot as plt

thetas = np.arange(-np.pi/2, np.pi/2, np.pi/100)
result = []
for theta in thetas:
    result.append(get_result_theta(theta, v1, v2))
plt.plot(thetas, result)

But if I use scipy to find that value, it returns 0.147.
但是,如果我使用scipy来找到这个值,它会返回0.147。

from scipy import optimize

res = optimize.minimize_scalar(get_result_theta, args=(v1, v2), method='bounded', bounds=(-np.pi/2, np.pi/2))

How can I get the global minimum instead of a local one, without taking much longer (I have to do this computation thousands of times), knowing that there should be only 2 local minima?
我如何获取全局最小值而不是局部最小值,而不需要花费更多时间(我必须重复进行这个计算数千次),知道应该只有2个局部最小值?

英文:

I want to minimize a function that I know it has two local minima, but using scipy to optimize it I don't get the global minimum.
I want to know of a way to do it that is fast, as I have to do it thousands of times.

I have functions to compute a result from two vectors of 3 components (v1 and v2) and an angle theta:

def get_v_theta(v, theta):
    vx = v[0]
    vy = v[1]
    vz = v[2]
    v_theta = (vx + vy)/2 + (vx - vy)/2*np.cos(2*theta) + vz*np.sin(2*theta)
    return v_theta


def get_result(v1_theta, v2_theta):
    v_max = max(v1_theta, v2_theta)
    v_min = min(v1_theta, v2_theta)
    v_med = (v_max + v_min)/2
    v_alt = (v_max - v_min)/2
    if v_med > 0:
        result = (v_alt/100 + v_med/400)**(-1)
    else:
        result = 100/v_alt
    return result


def get_result_theta(theta, v1, v2):
    v1_theta = get_v_theta(v1, theta)
    v2_theta = get_v_theta(v2, theta)
    result = get_result(v1_theta, v2_theta)
    return result

I want to find the angle theta that minimizes result, given two vectors.
For example, if my vectors are:

import numpy as np

v1 = np.array([2.91931, 0.758059, 0.10201])
v2 = np.array([-1.29405, 7.76101, -1.75803])

I can plot result vs theta and see that the theta that minimizes result should be around -1.4.

import matplotlib.pyplot as plt

thetas = np.arange(-np.pi/2, np.pi/2, np.pi/100)
result = []
for theta in thetas:
    result.append(get_result_theta(theta, v1, v2))
plt.plot(thetas, result)

如何高效优化具有两个局部最小值的函数?

But if I use scipy to find that value, it returns 0.147.

from scipy import optimize

res = optimize.minimize_scalar(get_result_theta, args=(v1, v2), method='bounded', bounds=(-np.pi/2, np.pi/2))

How can I get the global minimum instead of a local one, without taking much longer (I have to do this computation thousands of times), knowing that there should be only 2 local minima?

答案1

得分: 0

你可以通过分析方法来解决这个问题,而且方程还有一些很好的简化。首先,为了方便讨论,你可以最大化倒数,而不是最小化结果。

现在注意,对于任何pq,我们有max(p, q) + min(p, q) = p + qmax(p, q) - min(p, q) = |p - q|

函数V(Θ)的形式是线性三角函数

A cos(2Θ) + B sin(2Θ) + C

所以Vmed也是这种形式,而Valt分段线性三角函数,其中系数在满足以下条件时会改变符号

(A' - A") cos(2Θ) + (B' - B") sin(2Θ) + (C' - C") = 0。

有明确的公式来获得这些Θ,以及Vmed的零点(给出max(Vmed, 0),另一个分段LT函数)。

最后,通过组合区间,你可以得到result的倒数作为一个分段线性三角函数,并且通过在每个分段中取消第一导数并保留最大极值来找到稳定点。

英文:

You can solve this problem analytically, and there are some nice simplifications of the equations. First, for ease of the discussion, instead of minimizing the result, you can maximize the inverse.

Now note that for any p, q we have max(p, q) + min(p, q) = p + q and max(p, q) - min(p, q) = |p - q|.

The functions V(Θ) are of the form linear-trigonometric

A cos(2Θ) + B sin(2Θ) + C

So Vmed is of that form and Valt is piecewise linear-trigonometric, with the the coefficients changing sign where

(A' - A") cos(2Θ) + (B' - B") sin(2Θ) + (C' - C") = 0.

There are explicit formulas to obtain these Θ, as well as the zeroes of Vmed (giving max(Vmed, 0), another piecewise LT function).

Finally, by combining the intervals you get the inverse of result as a piecewise linear-trigonometric function, and you find the stationary points by canceling the first derivative in every piece and keeping the maximum maximorum.

huangapple
  • 本文由 发表于 2023年6月29日 01:56:56
  • 转载请务必保留本文链接:https://go.coder-hub.com/76575650.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定