Минимизация пиковой разницы элементов двух списков с учетом некоторых ограничений

Я хочу минимизировать пиковую разницу list1[i] - list2[i], используя метод scipy.optimize.minimize. Элементы в list1 и list2 являются числами с плавающей запятой.

Например:

список1 = [50, 50,5, 52, 53, 55, 55,5, 56, 57, 60, 61]

Как минимизировать list1[i] - list2[i], учитывая, что у меня есть два ограничения:

<сильный>1. список2 = список1[0]

<сильный>2. список2[i+1]-список2[i]‹=1,5

По сути, два последовательных элемента в списке2 не могут быть разделены более чем на 1,5, а первый элемент списка2 является первым элементом списка1.

Может быть, есть другой способ, кроме scipy.optimize.minimize, но я не знаю, как это сделать. Я думаю, что оптимальные значения для list2 могут быть следующими: list2 = [50, 50,5, 52, 53, 54,5, 55,5, 56, 57, 58,5, 60]

В этом случае пиковая разница составляет 1,5. Но, возможно, алгоритм находит более оптимальное решение, где разница между элементами list1 и list2 меньше.

Вот что я пробовал, но потерпел неудачу:

import numpy as np
from scipy.optimize import minimize

list1 = [50, 50.5, 52, 53, 55, 55.5, 56, 57,60, 61]
list2 = [list1[0]]

#Define objective
def peakDifference(*args):
    global list2
    peak_error = []
    for list1_i, list2_i in zip(list1, list2):
        peak_error.append(list1_i-list2_i)
    return max(peak_error)

peak_error = peakDifference()

#Define constraints
def constraint1(*args):
    for x in range(len(list2) - 1):
        return list2[x+1] - list2[x] - 1.5

con1 = {'type': 'ineq', 'fun': constraint1}

#Optimize
sol = minimize(peakDifference,list2, constraints=con1)



Traceback (most recent call last):   File "C:/Users/JumpStart/PycharmProjects/anglesimulation/venv/asdfgh.py", line 27, in <module>
    sol = minimize(peakDifference,list2, constraints=con1)   File "C:\Users\JumpStart\anaconda3\lib\site-packages\scipy\optimize\_minimize.py", line 625, in minimize
    return _minimize_slsqp(fun, x0, args, jac, bounds,   File "C:\Users\JumpStart\anaconda3\lib\site-packages\scipy\optimize\slsqp.py", line 412, in _minimize_slsqp
    a = _eval_con_normals(x, cons, la, n, m, meq, mieq)   File "C:\Users\JumpStart\anaconda3\lib\site-packages\scipy\optimize\slsqp.py", line 486, in _eval_con_normals
    a_ieq = vstack([con['jac'](x, *con['args'])   File "C:\Users\JumpStart\anaconda3\lib\site-packages\scipy\optimize\slsqp.py", line 486, in <listcomp>
    a_ieq = vstack([con['jac'](x, *con['args'])   File "C:\Users\JumpStart\anaconda3\lib\site-packages\scipy\optimize\slsqp.py", line 284, in cjac
    return approx_derivative(fun, x, method='2-point',   File "C:\Users\JumpStart\anaconda3\lib\site-packages\scipy\optimize\_numdiff.py", line 426, in approx_derivative
    return _dense_difference(fun_wrapped, x0, f0, h,   File "C:\Users\JumpStart\anaconda3\lib\site-packages\scipy\optimize\_numdiff.py", line 497, in _dense_difference
    df = fun(x) - f0 TypeError: unsupported operand type(s) for -: 'NoneType' and 'NoneType'

Process finished with exit code 1

scipy optimization minimize mathematical-optimization scipy-optimize-minimize
person Meysam    schedule 04.02.2021    source источник
comment
(1) Это задача линейного программирования. Возможно, лучше использовать LP-решатель. (2) Разница должна использовать abs(list1[i]-list2[i])? (3) Минимизируйте передачу x в виде массива. Вы должны использовать этот x в объекте и ограничениях. (4) Вы можете отлаживать вещи, распечатывая. Добавьте print(con,list2) и print(obj,list2) к цели и ограничению, чтобы увидеть, что происходит,   -  person Erwin Kalvelagen    schedule 04.02.2021

Ответы (1)


arrow_upward
1
arrow_downward

модель НЛП

Вот рабочая версия модели НЛП. Модель не может быть надежно решена таким образом, так как она недифференцируема.

import numpy as np
from scipy.optimize import minimize

list1 = np.array([50, 50.5, 52, 53, 55, 55.5, 56, 57,60, 61])
list1_0 = list1[0]
n = len(list1)

# our x variable will have one element less (first element is fixed)
list1x  = np.delete(list1,0)  # version with 1st element dropped
nx = len(list1x)

# objective function
# minimize the the maximum difference
# Notes:
#   - x excludes first element (they are the same by definition)
#   - this is non-differentiable so likely to be non-optimal
def maxDifference(x):
    return np.max(np.abs(list1x - x))

# n-1 constraints
def constraint1(x):
    return  1.5 - np.diff(np.insert(x,0,list1_0),1)

con1 = {'type': 'ineq', 'fun': constraint1}

#Optimize
x = 55*np.ones(nx)  # initial value
sol = minimize(maxDifference, x, constraints=con1)
sol

# optimal is: x = [51.25,51.25,52.75,54.25,54.75,56.25,57.75,59.25,60.25]
# obj = 0.75

Результат:

     fun: 5.0
     jac: array([0., 0., 0., 0., 0., 0., 0., 0., 0.])
 message: 'Optimization terminated successfully'
    nfev: 20
     nit: 2
    njev: 2
  status: 0
 success: True
       x: array([51.5, 53. , 54.5, 55. , 55. , 55. , 55. , 55. , 56. ])

Это неоптимально: цель равна 5 (вместо 0,75).

модель LP

Модель LP найдет проверенное оптимальное решение. Это гораздо надежнее. Например.:

import pulp as lp

list1 = [50, 50.5, 52, 53, 55, 55.5, 56, 57,60, 61]
n = len(list1)

model = pulp.LpProblem("Min_difference", pulp.LpMinimize)
x = lp.LpVariable.dicts("x",(i for i in range(n)))
z = lp.LpVariable("z")

# objective
model += z

# constraints
for i in range(n):
    model += z >= x[i]-list1[i]
    model += z >= list1[i]-x[i]
    
for i in range(n-1):
    model += x[i+1] - x[i] <= 1.5
    
model += x[0] == list1[0]

model.solve()
print(lp.LpStatus[model.status])
print("obj:",z.varValue)
print([x[i].varValue for i in range(n)])

Это показывает:

Optimal
obj: 0.75
[50.0, 51.25, 52.75, 53.75, 55.25, 56.25, 56.75, 57.75, 59.25, 60.25]
person Erwin Kalvelagen    schedule 05.02.2021