Основные понятия теории оптимизации.

Говорят, что функция F(x) имеет в т. х*(х₁,х₂, … , х_n) локальный максимум (минимум), если существует такая окрестность т. х*, в которой для любого х выполняется неравенство F(x) ≤ F(x*) (F(x) ≥ F(x*)).

 

 

F(x) 1 – точки локального максимума;

1 F_max 2 – точки локального минимума.

2 Точки локального максимума и

локального минимума называют

F_min точками экстремума.

 

 

Необходимое условие экстремума:чтобы F(x) имела в т. х* экстремум необходимо, чтобы ∂F(x*)/∂x_j = 0, .

Достаточное условие экстремума: если F(x) в т. х* имеет ∂F(x*)/∂x_j = 0, , то чтобы в этой точке F(x) имела экстремум достаточно, чтобы квадратичная форма

была положительно (минимум) или отрицательно (максимум) определена.

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

Множество S называется выпуклым, если для любых двух точек этого множества оно содержит и отрезок, соединяющий эти точки:

 

Функция F(x), определенная на выпуклом множестве S, выпукла, если ее график целиком лежит ниже (не выше) отрезка, соединяющего любые две точки графика:

Функция F(x), определенная на выпуклом множестве S, вогнута, если ее график целиком лежит выше (не ниже) отрезка, соединяющего любые две точки графика:

Теорема 1:пересечение выпуклых множеств является выпуклым множеством.

Теорема 2: сумма выпуклых функций является выпуклой функцией,

сумма вогнутых функций – вогнутой функцией.

Теорема 3 (основное свойство выпуклых задач):

Всякий локальный оптимум является глобальным.

Теорема Вейерштрасса:

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

ограниченном множестве, достигает максимума (минимума) по

крайней мере в одной точке этого множества.

Из сказанного можно определить общий принцип решения задач оптимизации: максимум (минимум) F(x) при х, принадлежащих замкнутому допустимому множеству, если оно существует, является либо точкой экстремума, либо граничной точкой допустимого множества, либо и тем и другим одновременно.

При численных расчетах часто необходимо использовать еще два важных понятия.

Вектор, указывающий направление наискорейшего возрастания функции, называется градиентом функции grad F(x) = (∂F/∂x₁, … ,∂F/∂x_n). Противоположный ему вектор называют антиградиентом, он указывает направление наискорейшего убывания функции.

Линией уровня (или линией равного значения) функции F(x) называют геометрическое место точек, координаты которых удовлетворяют уравнению F(x) = Const.Линия уровня и вектор градиент в каждой точке взаимно перпендикулярны.