Файл: Сахарова Людмила Викторовна, Лукьянова Галина Викторовна Методы оптиизации для машинного обучения учебное пособие.doc

2. Множество точек минимума U* функцииf (x)на множестве U мо­жет быть пустым, состоять из конечного или бесконечного числа то­чек.Например:а) еслиf (x)=ln x, U = (0;1],то U*=Ø;б) еслиf (x)= х², U = [– 1; 1], то U* = {0} – конечное множество;в) если f (x) = sin² x, U = R, то U=Z – бесконечное множество.3. Если U* = Ø, то . Таким образом, точная нижняя грань обобщает понятие минимума функции на случай U* = Ø.Пример 2.1. Точная нижняя грань функции, не имеющей точек минимума.Пусть , U = [1; + ∞). Покажем, что:а) U* = ø, т.е. f (x) не имеет на U точек минимума;б) а) (Доказательство от противного.) Предположим, что U* Ø , т.е. су­ществует хотя бы одна точка х*  [1;+ ∞), такая, чтоf (x*)  f (x) (2.2)для всех х  [1; + ∞). Выберем произвольное число х0 > х*. Очевидно, х0  [1; +∞), причем f (х*) =   = f (x₀), т.е. получаем противоречие с неравенством (2.2). Поэтому исходное предположение неверно и U*= ø.б) Для всех х  [1;+ ∞) имеем: т.е. число 0 удовлетворяет первому из неравенств для точной нижней грани f (x).Далее, пусть > 0. Возьмем произвольное > mах( , 1). Тогда, очевидно, x_  [1;+ ∞) и f (x_) < =0+ , т.е. для числа 0 выполняется и второе нера­венство из определения точной нижней грани. Поэтому .Если множество точек минимума функции

---

f (x) на U – пусто, то задача минимизации f (x) теряет смысл. В этом случае можно ограни­читься поиском точки , в которой значение f (x) с заданной погрешностью приближает точную нижнюю грань функции f (x) на мно­жестве U, т.е. .Широкий класс функций, для которых U* , определяет хорошо известная из математического анализа теорема Вейерштрасса, со­гласно которой непрерывная на замкнутом ограниченном множестве функция достигает на этом множестве своих минимального и макси­мального значений. Таким образом, пример (2.1) с непрерывной целе­вой функцией f (x) всегда имеет решение.

2.1.2. УНИМОДАЛЬНЫЕ ФУНКЦИИ

Если функция f (x) на множестве U имеет, кроме глобального, ло­кальные минимумы, отличные от него, то минимизацияf (x),как правило, сильно затрудняется. В частности, многие методы поиска точки миниму­ма f (x) приспособлены только для функций, у которых каждый локаль­ный минимум является одновременно и глобальным. Этим свойством об­ладают унимодальные функции.Определение 2.1. Функция f (x) называется унимодальной на от­резке [а; b], если она непрерывна на [а; b] и существуют числа  и , , такие, что:1) если а < , то на отрезке [a; ] функция f (x) монотонно убывает;2) если  < b, то на отрезке [; b] функция f (x) монотонно возра­стает;3) при х  [; ] f (x) =f ^* = .Множество унимодальных на отрезке [а; b] функций мы будем обозначать через Q[а; b]. Отметим, что возможно вырождение в точку одного или двух отрезков из [a; ], [; ] и [; b]. Некоторые варианты расположения и вырождения в точку отрезков монотонности и постоянства унимодальной функции показаны на рис. 2.1.

---

Рис. 2.1.Рис. 2.1 Варианты расположения отрезков унимодальности и монотонности функцииИз определения 2.1 вытекают следующие основные свойства уни­модальных функций:1. Любая из точек локального минимума унимодальной функции является и точкой ее глобального минимума на отрезке [а; b].2. Функция, унимодальная на отрезке [а; b], является унимодаль­ной и на любом меньшем отрезке [с; d] [а; b].3. Пусть f (x) Q[а; b] и . Тогда:если , то x^* [a; x₂];если , то x^* [x₁; b],где х* – одна из точек минимума f (x) на отрезке [a; b].

2.1.3. ВЫПУКЛЫЕ ФУНКЦИИ

Определение 2.2. Функция f (x), заданная на отрезке [a; b], называ­ется выпуклой на этом отрезке, если для всех х', х" [а; b] и произ­вольного числа [0; 1] выполняется неравенствоf  [x'+(1– )x"]  f (x')+(l – )f (x"). (2.4)Перечислим основные свойства выпуклых функций. 1. Если функция f (x) выпукла на [a; b], то на любом отрезке [х'; х"]  [a; b] ее график расположен не выше хорды, проведенной через точки графика с абсциссами х' и х" (рис. 2.2). Рис. 2.2. Взаимное расположение .Пусть х' и х"– произвольные точки отрезка [a; b], причем х' < х". Легко проверить, что при любом   [0;1] точка x_ = x^’ + (1–)x" лежит на отрезке [

---

x’; х"] и при непрерывном изменении  от 0 до 1 пробегает этот отрезок от точки х" (при  = 0) до точки x' (при  = 1).Рассмотрим хорду графика f (x),проходящую через точки (х',f (х')) и (х",f (х")).Ордината y_ точки этой хорды, соответствующая абсциссе c, равна. Поэтому неравенство (2.4) графика выпуклой функции и хорды означает, что f (x_)y_ , т.е. при любом расположении x_, на отрезке [х'; х"] точка графика функции f (x) лежит не выше соответствую­щей точки хорды. 2. Из курса математического анализа известны следующие усло­вия выпуклости функции:а) для того чтобы дифференцируе­мая на отрезке [а; b] функцияf (x) была выпуклой на этом отрезке, необходимо и достаточно, чтобы производная f '(x) не убывала на [а; b];б Рис. 2.3.) для того чтобы дважды дифференцируемая на отрезке [а; b] функция f (x) была выпуклой на этом отрезке, необходимо и достаточно, чтобы при всех х[а; b] выполнялось неравенство f "(x) 0. 3 Условие выпуклости для дифференцируемой на отрезке [а; b] функции f (x) означает, что на этом отрезке любая касательная к графику f (x) лежит не выше этого графика.Рис. 2.3. Вогнутый график функцииУравнение касательной к графику f (х) в точке (x₀ , f (x₀)), x₀ [а; b] имеет вид: у(х)=f (x₀)+f ’(x₀)(x–x₀). По формуле конечных приращений для любого х[а; b] имеем:f (х)=f (x₀)+f ’()(x–x₀), где точка  лежит междуxи x₀. Поэтомуf (х) – у(х)=[f ’() – f ’(x₀)](x–x₀), х[а; b] ,откуда с учетом того, что производная f ’(x) выпуклой функции не убывает, получаем:f (x)–y(x) 0 (2.5)для всех х[а; b].4. Если f (x) – выпуклая дифференцируемая на отрезке [а; b] функция и в точке х* [а; b] выполняется равенствоf ’(x^*) = 0 (2.6)то х* является точкой глобального минимума f (х

---

) на [а; b].

С учетом (2.6) уравнение касательной у(х)=f (х₀)+f ’(х₀)(х–х₀) кграфику f (x) для точки x0=х* принимает вид у(х) =f (x*). Поэтому из (2.5) следует, чтоf (x) f (x*) для всех х[а; b], т.е. х* – точка глобального минимума f (x).

Благодаря свойству 3 выпуклых функций данное свойство приобретает простой геометрический смысл: поскольку касательная к графику f (x) в точке с абсциссой х* горизонтальна, а этот график распо­ложен не ниже касательной, то х* есть точка минимума f (x) (рис. 2.3).

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

5. Можно показать, что всякая выпуклая непрерывная на отрезке [а; b] функция является и унимодальной на этом отрезке. Обратное, вообще говоря, неверно (рис. 2.4).


Рис. 2.4. График унимодальной, но не выпуклой функции
Таким образом, кроме перечис­ленных свойств, выпуклые функции обладают также и всеми свойствами унимодальных функций.

Замечание. При исследовании выпуклости функций на практике неравенство (2.4) удается использовать только в редких случа­ях. Поэтому для дифференцируемых достаточное число раз функций обычно применяют дифференциальные критерии выпуклости (см. свой­ство 2 выпуклых функций).

Непосредственная проверка унимодальности с помощью определения 2.1 также в большинстве случаев вызывает затруднения, и для обоснования унимодальности достаточно гладких функций часто используют те же критерии выпуклости. Если функция оказывается выпуклой, то можно утверждать (см. свойство 5), что она унимодальна. Разумеется, при отрицательном результате проверки функции на выпуклость нельзя сделать вывод о том, что она не унимодальна.

2.1.4. УСЛОВИЕ ЛИПШИЦА

Применение некоторых методов одномерной минимизации воз­можно только в случае, если скорость изменения целевой функции f (х) на любом участке отрезка [а

---