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

f(x)≥f(Θ)+(f ′(Θ),x)+c||x||2≥α–|(f ′(Θ),x)|+c||x||2≥ ≥ α + c||x||2 – ||f ′(Θ)|| · ||x|| = α + ||x||(c||x|| – ||f ′(Θ)||) > α.

Заключение теоремы теперь следует из теоремы о разрешимости задачи безусловной оптимизации.

Замечание. Для выпуклой (и даже для строго выпуклой) функции утверждение теоремы в общем случае не верно.

Теорема единственности для строго выпуклой функции.

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

Д о к а з а т е л ь с т в о. В предположении существования двух точек минимума x* и x** (очевидно тогда, что f(x*) = f(x**)), в силу строгой выпуклости, получим противоречащее равенству x* = argmin f(x) неравенство

f ( x* + x** 2 )  <  f(x*) 2  +  f(x**) 2  = f(x*).

2. Методы одномерной оптимизации

2.1. Введение в одномерную оптимизацию

2.1.1. Основные определения

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

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

Постановка задачи и методы исследования существенно зависят от свойств целевой функции и той информации о ней, которая может считаться доступной в процессе решения, а также которая известна априори (до опыта, заранее; здесь - до начала решения задачи).

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

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

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

решать такие задачи.

 Для одномерных методов

Определения. Пусть задано множество ХÌRn и функция f(x)=f(x1,x2,...,xn), определенная на множестве Х.
Точка х*ÎХ называется точкой локального минимума функции f(x) на множестве Х, если существует шар Ue(x*)={x: ||x-x*||<=e} такой, что для любого хÎUe(x*) выполняется неравенство

f(х*)≤f(x).    (1)

Если неравенство (1) выполняется как строгое (при х¹x*), то говорят, что x* - точка строгого локального минимума.
Точка х*ÎХ называется точкой глобального минимума функции f(x) на множестве Х, если неравенство (1) выполняется для любого х из множества Х.

Аналогично определяются точки локального и глобального максимума функции f(x) на множестве Х.
Точки локального максимума и минимума функции f(x) называют точками экстремума этой функции.
Задача отыскания всех локальных минимумов (максимумов) функции f(x), если множество Х совпадает со всем n-мерным пространством, т. е. Х=Rn, называется задачей безусловной оптимизации, а функция f(x) - целевой функцией.
Задачу отыскания точек локального минимума целевой функции f(x) символически записывают так:

f(x) →min,  х ÎRn.  (2)

Аналогично задачу отыскания точек локального максимума функции f(x) символически записывают следующим образом:

f(x) →mах,  х ÎRn.  (3)

Задача (3) эквивалентна задаче

-f(x) →min,  х ÎRn

в том смысле, что множества локальных и глобальных решений этих задач соответственно совпадают.
 

 Для многомерных методов

Определения. Пусть требуется решить задачу (2):

f(x) →min,  х ÎRn.  (4)

В двумерном пространтсве R2 решению такой задачи можно дать геометрическую иллюстрацию. Пусть точка х =(х1,х2) лежит на плоскости Ох1х2. Введем третью координату х3 так, чтобы ось координат Ох3 была перпендикулярна плоскости Ох1х2 (рис.1). Уравнению х3 = f(х1,х2) соответствует поверхность в трехмерном пространстве.
Если функция f(х) достигает локального минимума в точке х*Î R2, то поверхность в некоторой окрестности точки х*  имеет форму чаши (рис.1).

Рис.1

Напомним, что линиями уровня функции f(х1,х2) называют семейство линий плоскости R2, на которых функция принимает постоянное значение. Неявным уравнением линии уровня является уравнение f(x1,x2)=C. Если функция f(x) имеет в R2 единственную точку локального минимума  х* (х*1, х*2 ), то такая функция называется мономодальной. Взаимное расположение ее линий уровня имеет  вид, изображенный на рис. 2. 

Рис. 2

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

F(x) = (x12+x2-11)2+(x1+x22-7)2,

имеющая четыре изолированные точки минимума.

Чтобы найти точку х* локального минимума функции f(х),  составляют последовательность точек (приближений к решению)  {х(k)} (k=0,1, ...) , сходящуюся к точке  х*  (k=0,1,...).

Последовательность значений функции f(х(k)) должна быть  монотонно убывающей и ограниченной снизу:

f(x(0))≥f(x(1)) ≥ . . . ≥f(x(k)) ≥ . . . ≥f(x(*)).

Геометрический образ решения задачи (2)  для случая  двух переменных напоминает спуск на дно чаши. Это мотивирует названия методов решения задачи (2) -  «методы спуска».
Для различных методов спуска сначала выбирают начальную точку последовательности х(0). Дальнейшие приближения  х(k) определяются соотношениями

x(k+1)=x(k)+t(k)S(k)  (k= 0, 1, 2, . . .),  (5)

где S(k) - вектор направления спуска; скалярная величина  t(k) является решением задачи одномерной минимизации

f(x(k)+tS(k) →  min,  t ÎR.  (6)

Таким образом, задача поиска минимума функции нескольких переменных сводится к последовательности задач одномерной минимизации (6) по переменной t на отрезках n-мерного пространства, проходящих через точки х(k)  в направлении векторов S(k)).
Методы спуска различаются выбором вектора спуска и способом  решения задачи одномерной минимизации.
При решении последовательности задач (5) можно ограничиться методом сканирования для поиска минимума функции одной переменной. Выбрав произвольно начальную точку х(0) и размер начальюго шага h по переменной t, в методе сканирования можно  получить различные точки минимума мультимодальной функции.
Если функция f(x) мономодальна, то независимо от выбора начальной точки траектория поиска должна привести к единственной точке локального минимума этой функции.
 
   Пример. Задача о наилучшей консервной банке