УСТРОЙСТВО ДЛЯ НАХОЖДЕНИЯ ЭКСТРЕМУМА ФУНКЦИИ МЕТОДОМ ДИХОТОМИИ Российский патент 2004 года по МПК G06F17/10 

Изобретение относится к вычислительной технике и может быть использовано для поиска экстремума функции одного аргумента методом дихотомии.

Известно устройство для нахождения координаты экстремума функции (Авт. св-во СССР №1603399, кл. G 06 F 15/36, 1990), содержащее блок задания параметров функции, генератор тактовых импульсов, ключи, элементы сравнения, блоки памяти, элементы задержки, счетчики адреса, блоки деления, регистры, накапливающие сумматоры, умножители, вычитатели, логарифмический преобразователь, экспоненциальный преобразователь, блок регистрации [1]. Устройство предназначено для нахождения экстремумов функций при произвольных начальных точках. Недостатком его является то, что в нем решается задача математического программирования, но без учета ограничений на аргументы.

Известно устройство для нахождения экстремума аддитивной функции многих переменных с ограничением на норму аргументов (Патент РФ №2050589, кл. G 06 F 17/18, 1991), содержащее триггер, ключ, линию задержки, генератор тактовых импульсов, четыре группы ключей, три регистра, три группы блоков умножения, накапливающий сумматор, блок деления, блок задания приращения аргументов, блок задания ограничения, блок задания коэффициентов, одну группу сумматоров, две группы сумматоров-вычитателей, кольцевой счетчик, две группы блоков вычисления значения функции, блок извлечения квадратного корня [2]. Устройство предназначено для нахождения экстремума аддитивной функции многих переменных с ограничением на норму аргументов. Недостатком его является то, что оно работает с функциями многих переменных и, соответственно, обладает избыточной сложностью.

Кроме того, известно устройство для нахождения экстремума аддитивной функции многих переменных с ограничением на сумму аргументов - прототип (Авт. св-во СССР №1765830 А1, кл. G 06 F 15/31, 1990), содержащее триггер, ключ, линию задержки, генератор импульсов, четыре группы ключей, три регистра, блок задания приращения аргументов, две группы блоков вычисления значения функции, группу блоков умножения, накапливающий сумматор, две группы сумматоров, сумматор-вычитатель, две группы сумматоров-вычитателей, блок задания коэффициентов, кольцевой счетчик, блок задания ограничения, блок задания количества аргументов, блок деления [3]. Устройство предназначено для нахождения экстремума аддитивной функции многих переменных с ограничением на сумму аргументов. Недостатком его, как и предыдущего, является тоже избыточная сложность для решения простой задачи.

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

f(x)→min (1)

при х∈[а, b]. (2)

Предлагаемое устройство реализует процедуру минимизации выпуклой функции с использованием метода дихотомии [4]. В основе метода дихотомии лежит итерационный процесс деления пополам области определения функции одной переменной с последующим выбором той половины, в которой находится искомый экстремум.

Очередной m-й шаг оптимизации включает следующие действия:

1. Найти середину отрезка

2. Вычислить производную функции в данной точке f’(c^(m)).

3. Если производная функции в середине отрезка больше нуля, то правую границу сдвигаем в середину, если производная функции меньше нуля, то в середину сдвигаем левую границу:

f’(c^(m))>0a^(m+1)=a^(m), b^(m+1)=c^(m),

f’(c^(m))<0a^(m+1)=c^(m), b^(m+1)=b^(m).

В качестве начального приближения решения на так называемом "нулевом" шаге можно принять значения границ заданного интервала согласно ограничениям (2).

Процесс решения прекращается после выполнения заданного количества шагов М.

В качестве решения принимается середина последнего отрезка:

В устройствах подобного типа [2, 3] производную целевой функции обычно вычисляют численным методом разделенных разностей [4]:

Как следует из описания очередного шага оптимизации, решение о выборе той или иной половины отрезка принимается на основании знака производной функции в его центре. А знак производной исследуемой функции, в свою очередь, определяется знаком числителя выражения (3). Поэтому, учитывая, что, как правило, Δх=const, для упрощения схемы устройства предлагается не вычислять значение производной функции на каждом шаге, а ограничиться сравнением значений функции в соседних точках, то есть f(x^(m)) и f(х^(m)+Δх).

Таким образом, предлагаемое устройство позволяет найти экстремум функции одного аргумента на заданном отрезке, например оптимизировать распределение по двум направлениям однородных ресурсов, суммарное количество которых ограничено, а эффект от их использования описывается гладкой унимодальной функцией.

Поставленная цель достигается тем, что в устройство, содержащее триггер, ключ, линию задержки, генератор импульсов, четыре группы ключей, регистр, блок задания приращения аргумента, два блока вычисления значения функции, два сумматора, кольцевой счетчик, блок деления, введен блок сравнения, выход "больше" которого подключен к управляющим входам второй группы ключей, а выход "меньше" подключен к управляющим входам третьей группы ключей.

Сравнение заявляемого решения с другими техническими решениями показывает, что данные блоки известны [1, 2, 3]. Однако при введении их указанной связи с остальными элементами схемы в заявляемое устройство для нахождения экстремума функции методом дихотомии оно проявляет новые свойства, что обеспечивает решение экстремальной задачи выпуклого программирования с ограничениями.

На фиг.1 представлена структурная схема устройства.

Устройство содержит триггер 1, ключ 2, четыре группы ключей 2, линию задержки 3, генератор импульсов 4, регистр 5, блок 6 задания приращения аргумента, два блока 7 вычисления значения функции, блок 8 деления, блок 9 сравнения, два сумматора 10, кольцевой счетчик 11.

В устройстве к первому входу триггера 1 подключен вход кольцевого счетчика 11 и на него подается сигнал "Пуск", ко второму входу подключен выход кольцевого счетчика 11, а выход триггера 1 подключен к первому входу ключа 2, к первому входу которого подключен выход триггера 1, ко второму входу ключа 2 подключен выход генератора импульсов 4, а выход подключен к входу линии задержки 3, к входу которой подключен выход ключа 2, первый выход линии задержки 3 подключен к вторым входам ключей 2/4 четвертой группы, второй выход подключен к второму входу кольцевого счетчика 11; выход генератора импульсов 4 подключен к второму входу ключа 2; к первому входу кольцевого счетчика 11 подключен первый вход триггера 1, ко второму входу подключен второй выход линии задержки 3, выход кольцевого счетчика 11 подключен к второму входу триггера 1; на первые (управляющие) входы ключей 2/1 первой группы подается сигнал "Пуск", на вторые (информационные) входы ключей 2/1 первой группы поступают исходные значения границ области определения функции, а выходы подключены к входам регистра 5, к входам которого подключены выходы ключей 2/1 первой группы, а выходы подключены к входам сумматора 10/1 и к вторым входам ключей 2/2 второй и 2/3 третьей групп; к входам сумматора 10/1 подключены выходы регистра 5, а выход его подключен к входу блока деления 8, к входу которого подключен выход сумматора 10/1, а выход его подключен к входу блока вычисления значения функции 7/1, к первому входу сумматора 10/2 и к вторым входам ключей 2/2 второй и 2/3 третьей групп; к входу блока вычисления значения функции 7/1 подключен выход блока деления 8, а выход подключен к первому входу блока сравнения 9; выход блока 6 задания приращения аргументов подключен к второму входу сумматора 10/2, на первый вход которого подключен выход блока деления 8, на второй вход подключен выход блока 6 задания приращения аргументов, а выход подключен к входу блока вычисления значения функции 7/2, к входу которого подключен выход сумматора 10/2, а выход подключен ко второму входу блока сравнения 9, к первому входу которого подключен выход блока вычисления значения функции 7/1, к его второму входу подключен выход блока вычисления значения функции 7/2, выход "больше" которого подключен к первым (управляющим) входам ключей 2/2 второй группы, а выход "меньше" подключен к первым (управляющим) входам ключей 2/3 третьей группы; к первым (управляющим) входам ключей 2/2 второй группы подключен выход "больше" блока сравнения 9, к вторым (информационным) входам подключены выходы регистра 5, а выходы подключены к вторым входам ключей 2/4 четвертой группы, к первым (управляющим) входам которых подключен первый выход линии задержки 3, к вторым (информационным) входам подключены выходы ключей 2/2 второй и 2/3 третьей групп, а выходы подключены к входам регистра 5.

Устройство работает следующим образом.

Работа устройства начинается по сигналу "Пуск". Данный сигнал взводит триггер 1, который разрешает прохождение сигналов генератора импульсов 4 через ключ 2 на вход линии задержки 3, приводит в исходное состояние (сбрасывает) кольцевой счетчик 11, а также обеспечивает занесение в регистр 5 начальных значений границ области определения функции через ключи 2/1 первой группы.

Триггер 1, ключ 2, линия задержки 3, генератор импульсов 4, кольцевой счетчик 11 представляют собой устройство управления, которое обеспечивает осуществление М шагов итерационного процесса поиска оптимального решения.

Вариант временной диаграммы работы устройства представлен на фиг. 2.

Каждый шаг итерационного процесса осуществляется по алгоритму.

Значения границ области определения функции а и b с регистра 5 поступают на входы сумматора 10/1, где вычисляется их сумма (а+b); далее она поступает на вход блока деления 8, где делится пополам. Полусумма (а+b)/2 поступает на вход блока вычисления значения функции 7/1, на выходе которого получается значение функции в данной точке f((a+b)/2). Эта же полусумма (а+b)/2 поступает и на вход сумматора 10/2, где складывается с приращением аргумента Δх с выхода блока 6 задания приращения аргументов. Новое значение аргумента поступает на вход блока вычисления значения функции 7/2, на выходе которого получается значение функции в точке, сдвинутой относительно середины интервала на Δх, то есть f((a+b)/2+Δх).

Кроме того, полусумма (a+b)/2 с выхода блока деления 8 поступает и на информационные входы первых ключей групп 2/2 и 2/3; на информационный вход второго ключа группы 2/2 поступает величина правой границы интервала b и на информационный вход второго ключа группы 2/3 поступает величина левой границы интервала a.

Значение функции в точке (а+b)/2 и значение функции в точке, сдвинутой относительно середины интервала на Δх, поступают на вход блока сравнения 9. Если f((a+b)/2)>f((a+b)/2+Δх), то левая граница интервала смещается в середину, то есть принимается а=(a+b)/2, b=b. Если f((a+b)/2)<f((a+b)/2+Δх), то правая граница интервала смещается в середину, то есть принимается b=(a+b)/2, a=а. Новые значения границ интервала поступают на информационные входы ключей 2/4 четвертой группы.

Сигналом C₁ с первого выхода линии задержки 3, поступающим на управляющие входы ключей 2/4 четвертой группы, новые значения границ интервала переписываются на регистр 5. Далее они проходят на сумматор 10/1, в блоке деления 8 их сумма делится на 2. Таким образом, на выходе блока деления 8 всегда присутствует очередное приближение решения задачи.

На этом очередной шаг поиска решения заканчивается, со второго выхода линии задержки 3 добавляется единица в кольцевой счетчик 11, генератор импульсов 4 вырабатывает следующий импульс и очередной шаг повторяется. После выполнения М шагов сигналом с кольцевого счетчика 11 триггер 1 сбрасывается и решение заканчивается. С этого момента времени на выходе блока деления 8 содержится оптимальное значение аргумента х*, т.е. решение задачи.

ЛИТЕРАТУРА

1. Авторское свидетельство СССР №1603399, кл. G 06 F 15/36, 1990. Авторы: Брейтман С.М., Литвин Ю.Л., Мартинкевич Ж.К.

2. Патент РФ №2050589, кл. G 06 F 17/18.1991. Авторы: Зубов Н.Н., Зимин В.Н.

3. Авторское свидетельство СССР №1765830 А1, кл. G 06 F 15/31,1990. Авторы: Зубов Н.Н., Зимин В.Н., Шарашкин Ю.Г.

4. Карманов В.Г. Математическое программирование. - М.: Наука, 1980.

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

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