Лекция 4

Алгоритм метода ломаных Шаг 0. Задать точность $\epsilon >0$ Шаг 1. Найти $x_0,y_0$ по формулам $(\ast )$. Определить пару $(x,p)$, положив $x=x_0$, $p=y_0$. Шаг 2. Сравнивая значения $p$ введённых в рассмотрение пар $(x,p)$, найти пару $(x^{\ast },p^{\ast })$, у которой это значение минимально. Найти $\Delta =\frac{1}{2L}(f(x^{\ast })-p^{\ast })$ Шаг 3. Проверка на окончание поиска. Если $f(x^{\ast })-p^{\ast }\le \epsilon$, то положить, что $x^{\ast }$ - точка минимума функции $f(x)$, а $f^{\ast }=f(x^{\ast })$ - минимум функции $f(x)$. И поиск завершить. Шаг 4. Положить $x^{\prime }=x^{\ast }+\Delta ,x^{\prime \prime }=x^{\ast }+\Delta ,p=\frac{1}{2}(f(x^{\ast })+p^{\ast })$. Ввести в рассмотрение пары $(x^{\prime },p)$ и $(x^{\prime \prime },p)$. Исключить из рассмотрения пару $(x^{\ast },p^{\ast })$. Перейти к шагу 2.

“Важно, что целевая функция хоть и многомодальна, но удовлетворяет условию Липшица с константой $L>0$ (?)”

Минимизация функций многих переменных

В самом общем виде имеем дело с такой задачей: $f(x){\to }_{x\in U}\min$ Полагаем, что $x=(x_1,\dots ,x_n{)}^T,U\subset {\mathbb{R}}^n$.

Будем полагать, что в ${\mathbb{R}}^n$ определено скалярное произведение: $\forall x=(x_1,\dots ,x_n{)}^T\forall y=(y_1,\dots ,y_n)(x,y)={\sum }_{j=1}^n{x}_j{y}_j$.

Под нормой вектора будем понимать евклидову норму: $\forall x=(x_1,\dots ,x_n{)}^T$, $||x||=\sqrt{{\sum }_{j=1}^n{x}_j^2}$

Глобальный минимум функции многих переменных

Точку $x^{\ast }\in U$ называют точкой (глобального) минимума функции $f(x)$ на множестве $U$, если $\forall x\in Uf(x)\ge f(x^{\ast })$

Локальный минимум функции многих переменных

Точку $\tilde{x}\in U$ называют точкой локального минимума функции $f(x)$, если $\exists \epsilon >0\forall x:||x-\tilde{x}||<\epsilon ⟹f(x)\ge f(\tilde{x})$

Выпуклые множества

Пусть $x,y\in {\mathbb{R}}^n$, тогда отрезком, соединяющим точки $x,y$, называют множество точек, описываемых формулой $z=\alpha x+(1-\alpha )y$, где $\alpha \in [0,1]$.

Выпуклое множество

Множество $U\subset {\mathbb{R}}^n$ называют выпуклым, если $\forall x,y\in U$ отрезок, соединяющий $x$ и $y$, целиком содержится в $U$.

---

Примеры выпуклых множеств:

Пример 1

$U={\mathbb{R}}^n$

Пример 2

$U=\{x\in {\mathbb{R}}^n:⟨a,x⟩=b,a\in {\mathbb{R}}^n\setminus \{0\},b\in \mathbb{R}\}$ - гиперплоскость

Обоснование $x,y\in U$, то есть $(a,x)=b,(a,y)=b$. Рассмотрим точки $z=\alpha x+(1-\alpha )y$, где $\alpha \in [0,1]$:

Пусть

$(a,z)=$ $=(a,\alpha x+(1-\alpha )y)=$ $=\alpha (a,x)+(1-\alpha )(a,y)=$ $=\alpha b+(1-\alpha )b$ $=b$ $⟹$ $z\in U\forall \alpha \in [0,1]$

Пример 3

$U=\{x\in {\mathbb{R}}^n:||x-a||\le r,a\in {\mathbb{R}}^n,r>0\}$ - шар

Обоснование $x,y\in U$, то есть $||x-a||\le r,||y-a||\le r$. Рассмотрим точки $z=\alpha x+(1-\alpha )y$, где $\alpha \in [0,1]$: $||z-\alpha ||=||\alpha x+(1-\alpha )y-a||=|a=\alpha a+(1-\alpha )a|=||\alpha x+(1-\alpha )y-\alpha a-(1-\alpha )a||=$ $=||\alpha (x-a)+(1-\alpha )(y-a)||\le ||\alpha (x-a)||+||(1-\alpha )(y-a)||$ $=\alpha ||x-a||+(1-\alpha )||y-a||\le \alpha r(1-\alpha )r=r$ $⟹$ $z\in U,\forall \alpha \in [0,1]$

Пусть

---

Выпуклая функция

Функцию $f(x)$ называют выпуклой на выпуклом множестве $U\subset {\mathbb{R}}^n$, если $\forall x^1,x^2\in U\forall \alpha \in [0,1]f(\alpha x^1+(1-\alpha )x^2)\le \alpha f(x^1)+(1-\alpha )f(x^2)$

Строго выпуклая функция

Функцию $f(x)$ называют строго выпуклой на выпуклом множестве $U\subset {\mathbb{R}}^n$, если $\forall x_1,x_2\in U{x}_1\ne x_2\forall \alpha \in (0,1)f(\alpha x^1+(1-\alpha )x^2)<\alpha f(x^1)+(1-\alpha )f(x^2)$

Свойства выпуклых функций

Свойство 1

Пусть $f_i(x),i=\overline{1,m}$, выпуклы на выпуклом множестве $U$. Тогда $\forall {\lambda }_i\ge 0$, $i=\overline{1,m}$, функция $f(x)={\sum }_{i=1}^n{\lambda }_i{f}_i(x)$ выпукла на множестве $U$.

Обоснование $\forall x^1,x^2\in U$ $\forall \alpha \in [0,1]$ $f(\alpha x^1+(1-\alpha )x^2)=$ $={\sum }_{i=1}^m{\lambda }_i{f}_i(\alpha x^1+(1-\alpha )x^2)\le {\sum }_{i=1}^m{\lambda }_i(\alpha f_i(x^1)+(1-\alpha )f_i(x^2))=$ $=\alpha {\sum }_{i=1}^m{\lambda }_i{f}_i(x^1)+(1-\alpha )\left({\sum }_{i=1}^m\right({\lambda }_i{f}_i(x^2)))=\alpha (f(x^1))+(1-\alpha )f(x^2)$ $⟹$ $f(x)$ выпукла на $U$.

Свойство 2

Пусть $g(x)$ выпукла на выпуклом множестве $U$. Тогда $\forall b\in \mathbb{R}$ множество $V=\{x\in U:g(x)\le b\}$ выпукло

Обоснование $\forall x^1,x^2\in V$. Это означает то, что $g(x^1)\le b,g(x^2)\le b$. Рассмотрим точки вида $z=\alpha x^1+(1-\alpha )x^2$, где $\alpha \in [0,1]$, и покажем, что $g(z)\le b$ $\forall \alpha \in [0,1]$: $g(z)=g(\alpha x^1+(1-\alpha )x^2)\le \alpha g(x^1)+(1-\alpha )g(x^2)\le \alpha b+(1-\alpha )b=b$. $⟹$ $z\in V\forall \alpha \in [0,1]⟹V$ выпукло.

Рассмотрим

Свойство 3

Пусть $x^0\in U$ - точка локального минимума выпуклой функции $f(x)$, определенной на выпуклом множестве $U$. Тогда $x^0$ - точка глобального минимума функции $f(x)$ на $U$

Обоснование

Доказательство такое же, как для функций одной переменной.

Свойство 4

Пусть функция $f(x)$ строго выпукла на выпуклом множестве $U$ и $x^0\in U$ - точка глобального минимума $f(x)$ на $U$. Тогда других точек глобального минимума у $f(x)$ на множестве $U$ нет.

Обоснование

Доказательство такое же, как для функций одной переменной

Строгая выпуклость функции $f(x)$ на выпуклом множестве $U$ не гарантирует существование точки глобального минимума. Пример: $f(x)=e^{x}U=\mathbb{R}$.

Сильно выпуклая функция

Функцию $f(x)$ называют сильно выпуклой на выпуклом множестве $U\subset {\mathbb{R}}^n$ с константой $\gamma >0$, если $\forall x^1,x^2\in U\forall \alpha \in [0,1]:$ $f(\alpha x^1+(1-\alpha )x^2)\le \alpha f(x^1)+(1-\alpha )f(x^2)-\gamma \alpha (1-\alpha )||x^1-x^2|{|}^2$.