Пусть $ f: S \ rightarrow \ mathbb {R} $, где S — непустое выпуклое множество в $ \ mathbb {R} ^ n $, тогда $ f \ left (x \ right) $ называется выпуклым на S если $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left ( x_2 \ right), \ forall \ lambda \ in \ left (0,1 \ right) $.
С другой стороны, пусть $ f: S \ rightarrow \ mathbb {R} $, где S — непустое выпуклое множество в $ \ mathbb {R} ^ n $, тогда говорят $ f \ left (x \ right) $ быть вогнутым на S, если $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ geq \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) ) f \ left (x_2 \ right), \ forall \ lambda \ in \ left (0, 1 \ right) $.
Пусть $ f: S \ rightarrow \ mathbb {R} $, где S — непустое выпуклое множество в $ \ mathbb {R} ^ n $, тогда $ f \ left (x \ right) $ называется строго выпуклым на S если $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) <\ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ right), \ forall \ lambda \ in \ left (0, 1 \ right) $.
Пусть $ f: S \ rightarrow \ mathbb {R} $, где S — непустое выпуклое множество в $ \ mathbb {R} ^ n $, тогда $ f \ left (x \ right) $ называется строго вогнутым на S если $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right)> \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ right), \ forall \ lambda \ in \ left (0, 1 \ right) $.
Примеры
-
Линейная функция является выпуклой и вогнутой.
-
$ f \ left (x \ right) = \ left | x \ right | $ — выпуклая функция.
-
$ f \ left (x \ right) = \ frac {1} {x} $ — выпуклая функция.
Линейная функция является выпуклой и вогнутой.
$ f \ left (x \ right) = \ left | x \ right | $ — выпуклая функция.
$ f \ left (x \ right) = \ frac {1} {x} $ — выпуклая функция.
теорема
Пусть $ f_1, f_2, …, f_k: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ — выпуклые функции. Рассмотрим функцию $ f \ left (x \ right) = \ displaystyle \ sum \ limit_ {j = 1} ^ k \ alpha_jf_j \ left (x \ right) $, где $ \ alpha_j> 0, j = 1, 2,. ..k, $ then $ f \ left (x \ right) $ — выпуклая функция.
доказательство
Поскольку $ f_1, f_2, … f_k $ являются выпуклыми функциями
Следовательно, $ f_i \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda f_i \ left (x_1 \ right) + \ left (1- \ lambda \ right) f_i \ left (x_2 \ right), \ forall \ lambda \ in \ left (0, 1 \ right) $ и $ i = 1, 2, …., k $
Рассмотрим функцию $ f \ left (x \ right) $.
Следовательно,
$ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) $
$ = \ displaystyle \ sum \ limit_ {j = 1} ^ k \ alpha_jf_j \ left (\ lambda x_1 + 1- \ lambda \ right) x_2 \ leq \ displaystyle \ sum \ limit_ {j = 1} ^ k \ alpha_j \ лямбда f_j \ left (x_1 \ right) + \ left (1- \ lambda \ right) f_j \ left (x_2 \ right) $
$ \ Rightarrow f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda \ left (\ displaystyle \ sum \ limit_ {j = 1} ^ k \ alpha _jf_j \ left ( x_1 \ right) \ right) + \ left (\ displaystyle \ sum \ limit_ {j = 1} ^ k \ alpha _jf_j \ left (x_2 \ right) \ right) $
$ \ Rightarrow f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda f \ left (x_2 \ right) \ leq \ left (1- \ lambda \ right) f \ левый (x_2 \ правый) $
Следовательно, $ f \ left (x \ right) $ — выпуклая функция.
теорема
Пусть $ f \ left (x \ right) $ — выпуклая функция на выпуклом множестве $ S \ subset \ mathbb {R} ^ n $, тогда локальные минимумы $ f \ left (x \ right) $ на S — это глобальные минимумы.
доказательство
Пусть $ \ hat {x} $ — локальные минимумы для $ f \ left (x \ right) $, а $ \ hat {x} $ — не глобальные минимумы.
следовательно, $ \ существует \ hat {x} \ в S $ такое, что $ f \ left (\ bar {x} \ right) <f \ left (\ hat {x} \ right) $
Поскольку $ \ hat {x} $ является локальным минимумом, существует окрестность $ N_ \ varepsilon \ left (\ hat {x} \ right) $, такая что $ f \ left (\ hat {x} \ right) \ leq f \ left (x \ right), \ forall x \ in N_ \ varepsilon \ left (\ hat {x} \ right) \ cap S $
Но $ f \ left (x \ right) $ — выпуклая функция на S, поэтому для $ \ lambda \ in \ left (0, 1 \ right) $
у нас есть $ \ lambda \ hat {x} + \ left (1- \ lambda \ right) \ bar {x} \ leq \ lambda f \ left (\ hat {x} \ right) + \ left (1- \ lambda \ right) f \ left (\ bar {x} \ right) $
$ \ Rightarrow \ lambda \ hat {x} + \ left (1- \ lambda \ right) \ bar {x} <\ lambda f \ left (\ hat {x} \ right) + \ left (1- \ lambda \ справа) f \ left (\ hat {x} \ right) $
$ \ Rightarrow \ lambda \ hat {x} + \ left (1- \ lambda \ right) \ bar {x} <f \ left (\ hat {x} \ right), \ forall \ lambda \ in \ left (0 , 1 \ справа) $
Но для некоторого $ \ lambda <1 $, но близко к 1, мы имеем
$ \ lambda \ hat {x} + \ left (1- \ lambda \ right) \ bar {x} \ in N_ \ varepsilon \ left (\ hat {x} \ right) \ cap S $ и $ f \ left ( \ lambda \ hat {x} + \ left (1- \ lambda \ right) \ bar {x} \ right) <f \ left (\ bar {x} \ right) $
что противоречие.
Следовательно, $ \ bar {x} $ является глобальным минимумом.
Эпиграф
пусть S — непустое подмножество в $ \ mathbb {R} ^ n $, и пусть $ f: S \ rightarrow \ mathbb {R} $, тогда эпиграф из f, обозначаемый epi (f) или $ E_f $, является подмножеством $ \ mathbb {R} ^ n + 1 $, определяемый как $ E_f = \ left \ {\ left (x, \ alpha \ right): x \ in \ mathbb {R} ^ n, \ alpha \ in \ mathbb { R}, f \ left (x \ right) \ leq \ alpha \ right \} $
подграфик
пусть S — непустое подмножество в $ \ mathbb {R} ^ n $, и пусть $ f: S \ rightarrow \ mathbb {R} $, тогда гипограф f обозначается через hyp (f) или $ H_f = \ left \ {\ left (x, \ alpha \ right): x \ in \ mathbb {R} ^ n, \ alpha \ in \ mathbb {R} ^ n, \ alpha \ in \ mathbb {R}, f \ left ( x \ right) \ geq \ alpha \ right \} $
теорема
Пусть S — непустое выпуклое множество в $ \ mathbb {R} ^ n $, и пусть $ f: S \ rightarrow \ mathbb {R} ^ n $, тогда f является выпуклым тогда и только тогда, когда его эпиграф $ E_f $ равен выпуклое множество.
доказательство
Пусть f — выпуклая функция.
Показать $ E_f $ — выпуклое множество.
Пусть $ \ left (x_1, \ alpha_1 \ right), \ left (x_2, \ alpha_2 \ right) \ in E_f, \ lambda \ in \ left (0, 1 \ right) $
Показать $ \ lambda \ left (x_1, \ alpha_1 \ right) + \ left (1- \ lambda \ right) \ left (x_2, \ alpha_2 \ right) \ in E_f $
$ \ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda \ right) x_2, \ lambda \ alpha_1 + \ left (1- \ lambda \ right) \ alpha_2 \ right] \ in E_f $
$ f \ left (x_1 \ right) \ leq \ alpha _1, f \ left (x_2 \ right) \ leq \ alpha _2 $
Следовательно, $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ right) $
$ \ Rightarrow f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda \ alpha_1 + \ left (1- \ lambda \ right) \ alpha_2 $
обратный
Пусть $ E_f $ — выпуклое множество.
Чтобы показать, что f является выпуклым.
то есть, чтобы показать, если $ x_1, x_2 \ in S, \ lambda \ left (0, 1 \ right) $
$ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ право) $
Пусть $ x_1, x_2 \ in S, \ lambda \ in \ left (0, 1 \ right), f \ left (x_1 \ right), f \ left (x_2 \ right) \ in \ mathbb {R} $
Поскольку $ E_f $ является выпуклым множеством, $ \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2, \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) \ справа) f \ left (x_2 \ right) \ in E_f $
Следовательно, $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ right) $