Минимизация в Python для поиска кратчайшего пути между двумя точками

Я пытаюсь найти кратчайший путь между двумя точками (0,0) и (1000, -100). Путь должен определяться полиномиальной функцией 7-го порядка:

p(x) = a0 + a1*x + a2*x^2 + ... + a7*x^7

Для этого я попытался минимизировать функцию, которая вычисляет общую длину пути из полиномиальной функции:

length = int от 0 до 1000 из {sqrt (1 + (dp (x) / dx) ^ 2)}

Очевидно, что правильным решением будет линейная линия, однако позже я хочу добавить к проблеме ограничения. Это должно было быть первым подходом.

Код, который я реализовал, был:

import numpy as np
import matplotlib.pyplot as plt
import math
import sys
import scipy

def path_tracer(a,x):
     return a[0] + a[1]*x + a[2]*x**2 + a[3]*x**3 + a[4]*x**4 + a[5]*x**5 + a[6]*x**6 + a[7]*x**7


def lof(a):
     upper_lim = a[8]

     L = lambda x: np.sqrt(1 + (a[1] + 2*a[2]*x + 3*a[3]*x**2 + 4*a[4]*x**3 + 5*a[5]*x**4 + 6*a[6]*x**5 + 7*a[7]*x**6)**2)
     length_of_path = scipy.integrate.quad(L,0,upper_lim)

     return length_of_path[0]

a = np.array([-4E-11, -.4146,.0003,-7e-8,0,0,0,0,1000]) # [polynomial parameters, x end point]

xx = np.linspace(0,1200,1200)
y = [path_tracer(a,x) for x in xx]

cons = ({'type': 'eq', 'fun': lambda x:path_tracer(a,a[8])+50})
c = scipy.optimize.minimize(lof, a, constraints = cons)
print(c)

Однако, когда я его запустил, процедура минимизации не работает и возвращает исходные параметры без изменений. Результат:

fun: 1022.9651540965604
     jac: array([  0.00000000e+00,  -1.78130722e+02,  -1.17327499e+05,
        -7.62458172e+07,   9.42803815e+11,   9.99924786e+14,
         9.99999921e+17,   1.00000000e+21,   1.00029755e+00])
 message: 'Singular matrix C in LSQ subproblem'
    nfev: 11
     nit: 1
    njev: 1
  status: 6
 success: False
       x: array([ -4.00000000e-11,  -4.14600000e-01,   3.00000000e-04,
        -7.00000000e-08,   0.00000000e+00,   0.00000000e+00,
         0.00000000e+00,   0.00000000e+00,   1.00000000e+03])

Я что-то делаю не так или распорядок дня просто не подходит для решения такого рода проблем? Если да, то есть ли альтернатива в Python?


python constraints optimization minimization
person Daniel Jaló    schedule 01.09.2017    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Вы можете использовать эту процедуру, но у вашего подхода есть некоторые проблемы:

  • Область полинома должна быть нормирована на что-то разумное, например [0, 1]. Это значительно упрощает оптимизацию. Вы можете отменить это после того, как закончите оптимизацию.

  • Вы можете упростить код, используя polyval и связанные с ним функции

  • Оптимальное решение этой проблемы очевидно -0.1 x, поэтому я не уверен, почему вы чувствуете необходимость в оптимизации.

Решение, которое работает

import numpy as np
import scipy.optimize

x = np.linspace(0, 1, 1000)

def obj_fun(p):
    deriv = np.polyval(np.polyder(p), x)
    return np.sum(np.sqrt(1 + deriv ** 2))

cons = ({'type': 'eq', 'fun': lambda p: np.polyval(p, [0, 1]) - [0, -100]})

p0 = np.zeros(8)
c = scipy.optimize.minimize(obj_fun, p0, constraints = cons)

Где мы можем построить результат

import matplotlib.pyplot as plt
plt.plot(np.polyval(c.x, x), label='result')
plt.plot(-100 * x, label='optimal')
plt.legend()

введите описание изображения здесь

person Jonas Adler    schedule 01.09.2017
comment
Спасибо, сработало. Почему не удалось найти оптимального решения? Я ожидал, что эту проблему будет легко решить для рутины. Что касается того факта, что есть очевидное решение проблемы, я знаю об этом. Я хотел начать с простейшего случая, прежде чем усложнять его (у меня будет 4 пути, радиус кривизны всегда должен быть ниже определенного порога, производные в начальной и конечной точках должны быть равны нулю). - person Daniel Jaló; 01.09.2017