Нахождение максимума в обратной параболе итеративно

Question

У меня есть массив, представляющий обратную параболу, и я хочу найти максимум, который может быть где угодно в массиве. В моем приложении я не могу взять производную, и я должен пройти через массив. Я реализовал это, перебирая массив, начиная слева и до тех пор, пока не получу значение ниже, чем на предыдущей итерации:

import numpy as np 

def simulation(n):
    # create inverse parabola
    num = 21
    parabola= np.linspace(-8, 12, num=num)
    parabola= -np.abs(parabola) ** 2
    return parabola[n]


previous_iteration = -1000 # some initialization
for n in range(num):

    # Configure the entire system
    # Run simulation

    # simulation(n) - a function returning simulation result with configuration "n"
    simulation_result = simulation(n)

    if previous_iteration < simulation_result :
        previous_iteration = simulation_result 
    else:
        best_iteration = n-1
        break

print(best_iteration)
print(previous_iteration)

Есть ли более быстрый способ сделать это?

Edit: Фактическая реализация будет на FPGA, и для каждой итерации мне нужно настроить систему и запустить симуляцию, чтобы каждая итерация стоила много времени. Если я запустлю симуляцию со всеми возможными конфигурациями, я получу вектор параболы, но это займет много времени и будет очень неэффективным. Я ищу способ найти максимальное значение, генерируя как можно меньше очков. К сожалению, цикл for должен остаться, потому что это представление о том, как работает система. Ключевым моментом здесь является изменение кода внутри цикла for. Я отредактировал код, чтобы лучше объяснить, что я имею в виду.

Answer 1

То, что вы ищете, называется «троичным поиском»: https://en.wikipedia.org/wiki/Ternary_search

Работает, чтобы найти максимум любой функции f (x) , которая имеет увеличивающуюся часть, возможно, за ней следует полностью равная часть, за которой следует уменьшающаяся часть.

Учитывая границы низкий и высокий , выберите 2 балла m1 = низкий + (высокий-низкий) / 3 и м2 = низкий + ( высокий-низкий) * 2/3 . * * 1016

Тогда, если f (m1)> f (м2) , вы знаете, что максимум равен x <= м2 </strong>, потому что м2 не может быть на возрастающей части. Поэтому установите high = m2 и попробуйте снова.

В противном случае вы знаете, что максимум равен x> = m1 , поэтому установите low = m1 и повторите попытку.

повторять до high-low <3 </strong>, а затем просто выбирать, какое из этих значений будет наибольшим.

Answer 2

Обратная парабола (отобранная в равномерно расположенных точках) обладает свойством того, что различия между соседними точками всегда уменьшаются. Максимум - как раз перед тем, как различия становятся отрицательными.

Если разница между первыми двумя точками отрицательна или равна нулю, максимальная точка - это первая точка в массиве.

В противном случае выполните бинарный поиск, чтобы найти наименьшую положительную разницу между двумя соседними точками. Максимум будет вторым из этих двух пунктов.

Answer 3

Я отредактировал пост, надеюсь, теперь проблема прояснилась.

Answer 4

То, что вы хотите сделать, называется поиском по сетке. Вам необходимо определить точки сетки поиска (здесь, в «x») и рассчитать все значения параболы для этих точек (здесь, в «y»). Вы можете использовать np.argmax, чтобы найти индекс аргумента, который дает максимальное значение:

import numpy as np

# Define inverse parabola
parabola = lambda x: -np.abs(x)**2

# Search axis
x = np.linspace(-8, 12, 21)

# Calculate parabola at each point
y = parabola(x)

# Find argument that yields maximum value
xmax = x[np.argmax(y)]
print(xmax)           # Should be 0.0