Минимизация многомерной функции итераций цикла

Я пытаюсь минимизировать функцию f из ~80 переменных, хранящихся в файле array. Функция определяется двумя вложенными циклами: внешний цикл индексирует array на i, а внутренний цикл выполняется array[i] раз и добавляет результат вычисления к промежуточной сумме. Вычисление зависит от некоторых условий x и y и немного меняется каждый раз, когда оно выполняется, поэтому мне нужна структура цикла. Вот минимальный рабочий пример на Python:

def f[array]:
    total = 0
    x = 0
    y = 0
    for i in range(len(array)):
        for j in range(array[i]):
            result = 2*x + y
            total = total + result
            x = x+1
        x = 0
        y = y+1
    return total

Так, например, print f([2,1]) возвращает 3, поскольку [(2*0) + 0] + [(2*1) + 0] + [(2*0) + 1] = 0+2+1 = 3.

Я хочу найти записи array, которые минимизируют значение f. Однако, когда я говорю (например) Mathematica свести к минимуму f([x1, x2, ..., x80]) и выдать минимизатор array, программа жалуется, потому что она не может выполнить циклы, определяющие f неопределенное количество раз.

В связи с этим мой вопрос следующий:

Как свести к минимуму многомерную функцию, параметры которой описывают количество итераций заданного цикла?

Первоначально я пытался реализовать это в системе Mathematica, но обнаружил, что не могу определить f с помощью описанной выше процедуры. Лучшее, что я мог сделать, это сказать Mathematica, чтобы она выполнила описанные выше циклы, а затем определила f[array_] := total после того, как total было вычислено. Когда я запустил свой код, Mathematica, естественно, заявила, что не может вычислить f, выдав ошибку еще до того, как выполнила мою команду на NMinimize[{f[array] array ϵ Integers}, array]. Тот факт, что Mathematica пытается вычислить f перед вызовом в NMinimize, указывает на то, что я не совсем понимаю, как работают функции в Mathematica. Любая помощь в распутывании этой ситуации будет принята с благодарностью!


person David Grabovsky    schedule 03.06.2017    source источник
comment
Во-первых, вы можете взглянуть на эту страницу Википедии об оптимизации функций. Учитывая, что функцию дифференцировать нельзя, масса возможных приемов оказывается неприменимой, а жаль.   -  person ForceBru    schedule 03.06.2017
comment
Если бы вы могли создать конкретный пример задачи, которая, возможно, в десять или двадцать раз проще, чем ваша реальная проблема, но которая сохраняет основной характер вашей проблемы, и вы могли бы отредактировать свой пост, включив в него полное определение и детали примера задачи, тогда кто-нибудь могут скопировать ваш пример в свой блокнот, немного изменить нотацию и определение и показать один или два способа минимизировать пример. Тогда вы, возможно, сможете сопоставить эту технику с вашей реальной проблемой.   -  person Bill    schedule 03.06.2017
comment
@ForceBru Да, целочисленные ограничения исключают многие числовые методы, но в целом меня беспокоит то, как заставить программу выполнять более или менее любой вызов функции для f, поскольку ее параметры становятся переменными числами цикла итерации.   -  person David Grabovsky    schedule 03.06.2017
comment
@Bill Я отредактировал свой пост, включив в него минимальный рабочий пример. Моя реальная проблема — это серьезная оптимизация в атомной физике, которая включает в себя минимизацию интегральной квадратичной ошибки магнитных полей из-за сложного расположения катушек — приведенный выше код — это всего лишь костяк того, что мне нужно понять.   -  person David Grabovsky    schedule 03.06.2017
comment
Эта функция тривиально минимизируется, когда все элементы array равны 0. Внутренний цикл никогда не выполняется, и возвращается 0. Я что-то упускаю?   -  person JaminSore    schedule 03.06.2017
comment
Извините, я должен упомянуть, что записи array должны быть целыми числами, большими или равными 1. Тем не менее, на самом деле не имеет значения, что такое result; на самом деле функция может быть произвольно сложной. Моя проблема по-прежнему связана с реализацией фактического алгоритма минимизации, который принимает в качестве входных данных различные количества итераций внутреннего цикла в array.   -  person David Grabovsky    schedule 04.06.2017
comment
вам следует решить, какой язык вас интересует, и уточнить вопрос.   -  person agentp    schedule 04.06.2017
comment
Не могли бы вы привести другой пример, который больше похож на проблему, которую вы пытаетесь решить? Из вашего описания и примера кажется, что оптимальным решением будет массив из 1 с.   -  person JaminSore    schedule 04.06.2017


Ответы (1)


Как написано, ваша функция имеет аналитический минимум, и нет необходимости в численной оптимизации. К сожалению, StackOverflow не позволяет мне показать математику этого (если вы спросите об этом на MathExchange, я могу предоставить вывод), но с учетом массива A = [a0 a1 ... an], где каждое ai является положительным целым числом, и массива Y = [0 1 ... n] функция, которую вы разместили, сводится к следующее матричное умножение A * (A - 1 + Y)', где ' обозначает транспонирование матрицы, а * обозначает матричное умножение. Таким образом, тривиально функция минимизируется, когда минимизируется каждое ai. Итак, если это часть более крупной оптимизации, ваша задача должна быть сосредоточена на поиске минимума каждого элемента A, если сами элементы ограничены.

person JaminSore    schedule 03.06.2017