Глава 2. ИДЕНТИФИКАЦИЯ ОПТИМАЛЬНОЙ ТОЧКИ

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

Глава начинается с рассмотрения вектора, имеющего исключительное значение в НЛП — вектора

градиента. Мы пользуемся им при выводе необходимых условий для задачи НЛП без ограничений, так и при выводе необходимых условий Куна — Таккера для задачи с ограничениями. Достаточные условия оптимальности точки будут выведены двумя путями: через вогнутые функции и их модификации и через теорию двойственности.

2.1. ВЕКТОР ГРАДИЕНТА

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

Вектор направления. Любой -мерный вектор-столбец может служить направлением. Пусть даны точка и направление При изменении скалярной величины от 0 до точка описывает луч, исходящий из точки х в направлении При изменении от до определяет всю прямую, проходящую через х. Направление где 0 выражает нулевой вектор, также удовлетворяет математическому определению направления как -мерного вектора, хотя нулевое направление лучше всего рассматривать математическую абстракцию, введенную для удобства (см. упр. 2.1).

Градиент. Для любой дифференцируемой функции градиентом в точке х является вектор определяемый через частные производные функции в точке х следующим образом:

Градиент не только является направлением, но чрезвычайно важным направлением. В частности, для произвольно заданного направления выражает мгновенную скорость изменения вдоль направления

Более точно в математическом анализе доказывается, что если дифференцируема, в точке х, то

Следующая теорема показывает, какое следствие вытекает из положительности этой мгновенной скорости изменения. Напомним, что индекс выражает транспонирование.

Теорема 2.1. Пусть дифференцируема в точке х. Предположим, что имеется направление для которого Тогда существует такое, что для всех

Доказательство. Из равенства (2.1)

Из определения предела следует, что должно существовать такое, что для всех

Для доказательства теоремы достаточно выбирать такие которые сохраняют неравенство (2.3).

Интуитивно градиент, если он отличен от нуля, указывает на такое направление, небольшое перемещение по которому будет увеличивать Кроме того, предположим, что задано произвольное указывающее на направление, подобное градиенту в том смысле, что Тогда, как доказано в теореме 2.1, небольшое перемещение в этом направлении также будет увеличивать Теорема 2.1 очень важна; грубо говоря, она утверждает, что градиент указывает «на гору».