Модифицированный поиск Хука-Дживса

Метод Хука-Дживса нетрудно модифицировать и для учета ограничений.

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

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

В тексте программы модифицированного метода прямого поиска Хука-Дживса сделана попытка реализовать такую процедуру. Рассматриваемая задача формулируется следующим образом:

минимизировать f(x₁, x₂) = 3x₁²+4x₁x₂+5x₂²

при ограничениях x₁³ 0, x₂³ 0, x₁+x₂³ 4.

Минимум, равный 44, достигается в точке (3; 1) при ограничении х₁+х₂=4

Для начальной точки (4;3) и при длине шага, равной единице, программой успешно решена задача минимизации.

Для начальной точки (3;4) и длины шага =1 программой также успешно решена задача минимизации.

Для начальной точки (5;6) и длины шага =1 задача не решена, так как программа остановилась в точке (1;3), т.е. на активном ограничении, и выдала неверный результат.

Аналогичные неутешительные результаты были получены для начальной точки (5;6) и длины шага =0,5. Неверное решение было найдено в точке (1,5;2,5). Для начальной точки (4;3) и длины шага 0,5 программа работала нормально, но было получено неверное решение в точке (2,5;1,5).

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