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

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

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

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

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

Целью изобретения является расширение функциональных возможностей прототипа за счет учета ограничений на норму аргументов целевой функции. Таким образом, оно позволяет решать экстремальные задачи выпуклого программирования с ограничениями типа шара
F(x) F(x₁, x₂, x_n)f(x_i) __→ min (1) при
≅ R (2)
Предлагаемое устройство реализует процедуру минимизации выпуклой функции с использованием метода проекции градиента. В основе метода проекции градиента лежит релаксационный процесс отыскания последовательности векторов решения Х^(m), где m номер шага (m ), таких, что каждый последующий вектор принадлежит области ограничений (2) и каждое последующее значение целевой функции (1) не превосходит предыдущего.

Очередной шаг оптимизации включает:
1. Определение направления движения из точки Х^(m) к минимуму целевой функции, т.е. вычисление значения градиента функции в данной точке
▿ (X^(m)) grad F(Х^(m)).

Нахождение частных производных целевой функции предлагается методом разделенных разностей
=
В качестве начального приближения решения на так называемом "нулевом" шаге можно принять любые значения переменных (в том числе и нулевые, т.е. х_i⁽⁰⁾= 0, i ) удовлетворяющие ограничениям (2).

2. Нахождение последующего вектора решения без учета ограничений, т.е. шаг в направлении антиградиента
= x(i

^m)-h* где h коэффициент, определяющий длину шага в выбранном направлении.

3. Учет ограничений на аргументы путем проектирования вектора на область ограничений (2) по формуле
x(i

^m+1)= R где R ограничение на норму аргументов.

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

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

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

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

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

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

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

К входам накапливающего сумматора 9 подключены выходы блоков умножения 8/2 второй группы, а выход подключен к входу блока извлечения квадратного корня 16, вход которого подключен к выходу накапливающего сумматора 9, а выход подключен к входу делителя блока деления 15. Вход делимого блока 15 подключен к выходу блока задания ограничения 14, вход делителя к выходу блока извлечения квадратного корня 16, а выход к входам блоков умножения 8/3 третьей группы, первые входы которых подключены к выходам третьего регистра 5/3, вторые входы подключены к выходу блока деления 15, выходы их подключены к первым входам ключей 2/4 четвертой группы.

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

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

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

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

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

Исходные значения вектора аргументов Х_i^(m) i c первого регистра 5/1 поступают на входы блоков вычисления значения функции 7/1 первой группы, вычисленные значения функции f(Х_i^(m)), i поступают на входы вычитаемого сумматоров-вычитателей 11/1 первой группы.

Сигналом С₁ с первого выхода линии задержки 3, поступающим на управляющие входы ключей 2/2 второй группы, значения вектора аргументов Х_i^(m), i с первого регистра 5/1 переписываются на второй регистра 5/2. С выходов второго регистра 5/2 значения Х_i^(m) поступают на входы первого слагаемого сумматоров 10/1 первой группы, на входы второго слагаемого которых поступают единичные приращения с выхода блока задания приращения аргументов 6. С выходов сумматоров 10/2 первой группы значения аргументов, получивших приращение, Х_i^(m)+1 поступают на входы блоков вычисления значения функции 7/2 второй группы, с выходов которых значения f(Х_i^(m)+1) поступают на входы уменьшаемого сумматоров-вычитателей 11/1 первой группы. С выходов сумматоров-вычитателей 11/1 первой группы разделенные разности функции в качестве значений составляющих градиента функции подаются на входы вторых сомножителей блоков умножения 8/1 первой группы, где умножаются на величину коэффициента длины шага h, поступающего с блока задания коэффициентов 12, и поступают на входы вычитаемого сумматоров-вычитателей 11/2 второй группы. На входы уменьшаемого сумматоров-вычитателей 11/2 второй группы поступают значения вектора аргументов Х_i^(m), i с выходов второго регистра 5/2. К моменту поступления сигнала С₂ со второго выхода линии задержки 3 на информационных входах ключей 2,3 третьей группы присутствуют последующие значения вектора аргументов , i без учета ограничений. По сигналу С₂, поступающему на управляющие входы ключей 2/3 третьей группы, значения переписываются в третий регистр 5/3.

С выхода третьего регистра 5/3 значения вектора аргументов поступают на входы обоих сомножителей блоков умножения 8/2 второй группы, с выходов которых значения квадратов аргументов []²поступают на входы накапливающего сумматора 9. С выхода накапливающего сумматора 9 величина []² поступает на вход блока извлечения квадратного корня 16.

C выхода блока извлечения квадратного корня 16 величина поступает на вход делителя блока деления 15, на вход делимого которого поступает величина R с блока задания ограничения 14. С выхода блока деления 15 частное поступает на входы вторых сомножителей блоков умножения 8/3 третьей группы, на входы первых сомножителей которых поступают значения вектора аргументов без учета ограничений с выхода третьего регистра 5/3.

К моменту поступления сигнала С₃ с третьего выхода линии задержки 3 на информационных входах ключей 2) четвертой группы присутствуют значения вектора аргументов на очередном (m+1)-м шаге
x(i

^m+1)= R
По сигналу С₃, поступающему на управляющие входы ключей 2/4 четвертой группы, вычисленные значения вектора аргументов заносятся в первый регистр 5/1.

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

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

УСТРОЙСТВО ДЛЯ НАХОЖДЕНИЯ ЭКСТРЕМУМА АДДИТИВНОЙ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ С ОГРАНИЧЕНИЕМ НА НОРМУ АРГУМЕНТОВ, содержащее первую группу ключей, ключ, линию задержки, генератор тактовых импульсов, два регистра, первую группу блоков умножения, накапливающий сумматор и блок деления, отличающееся тем, что в него введены три группы ключей, кольцевой счетчик, триггер, третий регистр, группа сумматоров, две группы сумматоров-вычитателей, блок задания ограничения, две группы блоков вычисления значения целевой функции, группа квадраторов, блок извлечения корня, вторая группа блоков умножения, блок задания приращения аргументов и блок задания коэффициентов, выход которого подключен к первым входам блоков умножения первой группы, выходы которых подключены к первым входам одноименных сумматоров-вычислителей первой группы, выходы которых соединены с информационными входами одноименных ключей первой группы, выходы которых соединены с входами первого регистра, выходы которого подключены к первым входам блоков умножения второй группы и через квадраторы группы соединены с входами накапливающего сумматора, выход которого через блок извлечения корня подключен к первому входу блока деления, второй вход которого соединен с выходом блока задания ограничения, а выход подключен к вторым входам блоков умножения второй группы, выходы которых соединены с информационными входами одноименных ключей второй группы, выходы которых и выходы ключей третьей группы через схему монтажного ИЛИ подключены к входам второго регистра, выходы которого являются выходами устройства и подключены к входам блоков вычисления значения целевой функции первой группы и информационным входам ключей четвертой группы, выходы которых соединены с выходами третьего регистра, выходы которого подключены к вторым входам сумматоров-вычитателей первой группы и первым входам сумматоров группы, вторые входы которых подключены к выходу блока задания приращения аргументов, а выходы сумматоров группы через одноименные блоки вычисления значения целевой функции второй группы подключены к первым входам соответствующих сумматоров-вычитателей второй группы, вторые входы которых соединены с выходами соответствующих блоков вычисления значения целевой функции первой группы, а выходы сумматоров-вычитателей второй группы подключены к вторым входам одноименных блоков умножения первой группы, информационные входы устройства соединены с информационными входами ключей третьей группы, управляющие входы которых соединены с входом запуска устройства, счетным входом кольцевого счетчика и нулевым входом триггера, прямой выход которого соединен с управляющим входом ключа, информационный вход которого соединен с выходом генератора тактовых импульсов, а выход подключен к входу линии задержки, выходы которых соединены соответственно с управляющими входами ключей первой, второй и четвертой групп и входом обнуления кольцевого счетчика.