ℐ ℒ ℓ ℕ ℘ ℙ ℚ ℛ ℜ    
нужны не абстрактные доказательства - в 99.9% случаев решаются задачи "оптимизировать" или "построить модель" (которые основаны на ранее доказанных вещах, да)


  • меры
  • нормы
  • банаховы пространства
  • аффинные преобразования
  • аппроксимация Тайлора
  • conic problem
  • semidefinite program (SDP)
  • Lagrange dual problem
  • оптимизация Чебышева
  • оптимизация ошибок
  • оптимизация штрафов
  • оптимизация Тихонова
  • KKT

  • выпуклая оптимизация

    применяется, если LSS, LNS и LP терпят фиаско - а именно: когда оптимизируемая функция нелинейна, или когда граничные условия содержат нелинейные функции

    * * *

    подмножество S ⊂ ℝⁿ называется выпуклым, если вместе с любыми двумя своими точками оно содержит соединяющий их отрезок

    или: подмножество S ⊂ ℝⁿ называется выпуклым, если для любых k точек из S линейная комбинация Σλi*xi (0<λi<1, Σλi=1) также принадлежит S

    пусть задано подмножество S ⊂ ℝⁿ. выпуклой оболочкой S называется пересечение всех выпуклых подмножеств ℝⁿ, содержащих S

    симплексом в ℝⁿ называется выпуклая оболочка множества {x0..xn} из n+1 точек в ℝⁿ. такой симплекс называется натянутым на точки x0..xn

    гранью размерности k называется выпуклая оболочка k+1 точек из {x0,..,xn}

    кольцо полиэдров (многогранников) есть кольцо подмножеств в ℝⁿ, порожденное замкнутыми симплексами. многогранником называется элемент этого кольца. вырожденный симплекс есть симплекс, лежащий в какой-то гиперплоскости. вырожденный многогранник есть элемент кольца подмножеств, порожденного вырожденными симплексами. триангуляция многогранника есть разрезание его на симплексы

    гиперплоскость

    гиперплоскостью пространства называют { x | y⁺ • x = b },     x,y ∈ ℝn,   b ∈ ℝ

    если есть два непересекающиеся выпуклых пространства, то существует гиперплоскость, которая их разделяет

    через любую граничную точку выпуклого пространства можно построить касательную гиперплоскость

    симплектическое пространство невырожденно, если его можно разложить в прямую сумму гиперплоскостей. такое возможно только для пространств четной размерности. матричное представление таких пространств есть симплектическая группа SL(2l,K) = { x ∈ GL(2l,K) | x⁺ * G * x = G } , где G - матрица Грамма, для любого поля K. это группа изометрий симплектического пространства. такие пространства называются расщипимыми: V = H ⊞ H ... ⊞ H (всего l слагаемых)

    границы inf и sup

    пусть M – частично упорядоченное множество, а S – его подмножество

    верхняя граница sup S есть элемент m ∈ M, который удовлетворяет m > s для каждого s ∈ S

    точная верхняя граница sup S есть такая верхняя граница m ∈ M, что для любой другой верхней границы m' имеем m ≤ m'

    аналогично определяется нижняя граница inf S и точная нижняя граница

    существование точных границ не гарантировано

    меры

    пусть задано множество S. множество всех подмножеств S обозначается 2S. пусть U ⊂ 2S - некоторый набор подмножеств S

    U называется кольцом, если для любых A,B ∈ U, объединение A ∪ B, пересечение A ∩ B и дополнение A\B принадлежит U

    отображение µ : U → ℝ называется конечно-аддитивной мерой (аддитивной функцией множества или валюацией), если для любых A,B ∈ U выполняется µ(A ∪ B) = µ(A) + µ(B) − µ(A ∩ B)

    в этих предположениях, пусть X ⊂ S любое подмножество

    определим внешнюю меру µ(X) как µ(X) = inf Σµ(Ai) где инфимум берется по всем счетным наборам {Ai} ⊂ U, покрывающим X. мера µ называется σ-аддитивной, если µ(A) = µ(A) для любого A ∈ U

    пусть U ⊂ 2ℝⁿ некоторое кольцо множеств

    два подмножества называются конгруэнтными, если одно в другое можно перевести движением

    конечно-аддитивная мера µ : U → R называется инвариантной, если µ(A) = µ(B) для конгруэнтных подмножеств A,B ⊂ ℝⁿ

    конечно-аддитивная мера есть инвариантная функция µ : U → ℝ на кольце многогранников, которая равна нулю на всех вырожденных многогранниках

    мера Жордана

              n
          Δ = ∏ (bi - ai)
             i=1
     

    мера Лебега

        µ(M) = inf Σ ℓ(Ik) 
    
    на непересекающихся интервалах I совпадает с мерой Жордана

    мера Лебега конечно-аддитивна: µ(A ∐ B) = µ(A) + µ(B)

    мера Лебега монотонна: для A ⊂ B, имеем µ(A) ≤ µ(B)

    неизмеримые по Лебегу множества все неконструктивны и строятся с помощью аксиомы выбора

    мера Бореля

    рассмотрим σ-алгебру, порожденную открытыми подмножествами ℝⁿ. ее элементы называются борелевскими подмножествами

    алгебра борелевских множеств – это сигма-алгебра, порожденная открытыми подмножествами. множество называется "измеримым по Борелю", если оно лежит в этой алгебре, то есть получено счетными объединениями и пересечениями открытых и замкнутых множеств. "борелевская мера" есть счетно-аддитивная мера на этой сигма-алгебре

    нормы

    норма - это мера линейных пространств

    пусть V - линейное пространство. функция || : V → ℝ+ называется нормой если ∀ x ∈ V и ∀ λ ∈ ℝ выполняются:

    1. |λ * x| = |λ| * |x|
    2. |x + y| ≤ |x| + |y|
    3. |x| = 0 ⇔ x = 0

    полное пространство - если последовательность в нем сходится к пределу, то предел является частью пространства

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

    для каждого нормированного пространства существует оператор из него в борелево B(ℓ₂(X)), где X - некоторое множество

    ℓ₁-норма

    определим ℓ₁-норму на пространстве функций формулой |f|₁ = ∫µ|f|. она принимает значения в [0,∞[

    определим ℓ₁-метрику формулой d(f,g) = |f − g|

    по Th Хана-Банаха если пространство V функций полно относительно ℓ₁-нормы, то пространство - банахово и на нем существуют ограниченные (aka непрерывные) функционалы V → ℝ

    банаховы пространства

    банахово пространство — нормированное векторное пространство, полное по метрике, порождённой нормой

    гильбертовы пространства

    гильбертово пространство — векторное пространство над полем ℝ или ℂ, такое, что:

    гильбертово пространство использует евклидову норму ℓ₂ : |x| = √ x*x

    любое гильбертово пространство является банаховым. обратное утверждение - неверно, поскольку норма в банаховом пространстве может быть и неевклидовой. несколько примеров расположения точек пространства ℝ², одинаково удаленных от точки (0,0) при различных нормах:

    |x|p = (Σ |xi|p) 1/p       |x| = max |xi|

    * * *

    всякое нормированное пространство конечной размерности n топологически изоморфно ℂⁿ

    любые два нормированные пространства одной и той же размерности топологически изоморфны

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

    аффинные преобразования

    aффинным называют преобразование векторного пространства вида:

    y = M * x + p

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

     
       ( y₁     ( a b       ( x₁       ( p₁         ( a * x₁  +  b * x₂  +  p₁  
         y₂  =    c d )  *    x₂ )  +    p₂ )  =      c * x₁  +  d * x₂  +  p₂ )
    

    это отличается от линейного преборазования, а именно:

       M * x * α + M * y * β + p    ≠    α (M * x + p) + β (M * y + p)
    

    p не скалируется при таком преобарзовании вовсе и появляется в формуле результа лишь единожды - преобразование явно нелинейно

    предположим, что пара ((M1 , p1) , (M2 , p2)) является (M1 * M2 , M1 * p2 + p1) и приложим такой оператор к вектору x:

      (M1 * M2 , M1 * p2 + p1) x = M1 * M2 * x  +  M1 * p2 + p1
    

    это правило композиции для двух aффинных отображений

    аффинное отображение - отображение, сохраняющее выпуклость

    если функция отображает линейный сегмент в линейный сегмент - она скорее всего аффинная, но это - всего лишь эвристика

    эвристика на выпуклость пространства: рандомно выбираем из него две точки и проверяем, что точка .5 * x₁ + .5 * x₂ принадлежит пространству. делаем много таких проверок и если ни одного отрицательного результата - считаем, что пространство выпуклое

    пересечение двух выпуклых пространств - всегда выпуклое пространство

    протестировать функцию f(x) на выпуклость можно показав, что ∇²f(x) >= 0

    выпуклыми являются

    теперь - все ограничения для выпуклых оптимизаций должны быть аффинными преобразованиями


    пример с рационом

        c⁺ * x < d , xi > 0 , ci > 0 , d > 0
        A * x = b  , aij > 0 , bi > 0
    
                 
      

      
    #!/home/guest/.nix-profile/bin/octave
    
    %%      жиры белки углеводы в рационе при ограничении стоимости пайка
    
    %%  c    цена продукта          c1 c2 
    %%  d    стоимость продукта     d1 d2
    %%  b    minimum                жиры, белки, углеводы 
    %%  A    строки - сколько чего-то одного (жиры, белки или углеводы) в каждом продукте
    
    %%     необходимо найти вектор x  - суммарный продукт в количестве x1 x2 
         
    A = [  2.0  2.0 ; 3.0  4.0 ; 1.0  5.0 ] ;
    
    b = [ 3.0 ; 2.0 ; 3.0 ];
    
    c = [ 1.1  ;  1.2 ] ;
    
    d = input ("ресурс денег :") ; 
    
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    
    %% todo
    
    printf ("для сертификации решения должно быть близко к нулю : %f\n" , 0) ;
    printf ("покупаем продуктов в количестве : %f\t%f\t на общую сумму : %f\n", 0 , 0 , d) ;
    
    display ("\nнужно достичь ") ; b
    display ("\nдостигли ") ; % A * x
    


    аппроксимация Тайлора

    любая локально оптимальная точка выпуклой задачи является и глобально оптимальной

    поэтому аппроксимация Тайлора всегда дает нижнюю оценку для выпуклых функций и эта оценка - глобальна


    conic problem

    minimize      c⁺ * x
    subject to    F * x + g < 0
                  A * x = b
    

    semidefinite program (SDP)

    minimize     c⁺ * x
    subject to   F₁ * x₁ + .. + Fₙ * xₙ + G < 0  , F,G in SLₙ
                 A * x = b
    
    таким образом это задача LMI - linear matrix inequality
    
    LP  :  minimize  c⁺ * x   subject to        A * x < b
    SDP :  minimize  c⁺ * x   subject to   diag(A * x - b) < 0
    

    Lagrange dual problem

        
    maximize      g(l, v)
    subject to    l > 0
    
    
    l,v are dual feasible if l > 0 , (l,v) in dom g
    

    example: inequality form LP

    primal problem
    
        minimize     c⁺ * x
        subject to   A * x =< b
    
    dual function
    
        g(l) = inf ( (c + A⁺ * l)⁺ * x  -  b⁺ * l ) =
            if A⁺ * l + c = 0 :  -b⁺ * l 
            otherwise         :  -infinity
    
    dual problem
    
        maximize     -b⁺ * l
        subject to   A⁺ * l + c = 0, l >= 0
    

    example: quadratic program

    primal problem
    
       minimize      x⁺ * P * x  , P - positive-definite matrix
       subject to    A * x =< b
    
    dual function
    
       g(l) = inf ( x⁺ * P * x + l⁺ * (A * x - b)) = -1/4 * l⁺ * A * P⁻ * A⁺ * l  -  b⁺ * l
    
    dual problem
    
       maximize    -1/4 * l⁺ * A * P⁻ * A⁺ * l  -  b⁺ * l
       subject to  l >= 0
    


    оптимизация Чебышева

    A * x = b оптимизируется по норме | |

    
                  minimize      1⁺ * t,   t ∈ ℝ
    
                  subject to    b  -  t * I    ≤   A * x     ≤   b  +  t * I 
    


    оптимизация ошибок

    A * x = b оптимизируется по норме | |₁;

                  minimize     I * t,   t ∈ ℝ
    
                  subject to   b  -  t * I  ≤   A * x   ≤  b  +  t * I
    


    оптимизация штрафов

    A * x = b

                  minimize     Σ  φ₁ (r₁) ,   r ∈ ℝⁿ
    
                  subject to   A * x  -  b   =   r 
    
    
         if φ(u) = u²                     : квадратичная оптимизация штрафов
    
         if φ(u) = max (0 , |u| - c)      : оптимизация штрафов "мертвой зоны"
    
         if φ(u) = -c * log (1 - (u/c)²)  : лог-барьерная оптимизация штрафов  
    


    оптимизация Тихонова

    A * x = b
            minimize     |A * x - b|²   +   σ * |x|²    in    L₂
    
    
      LSS:               | (    A               ( b   |²
                         |   √σ * I )  *  x  -    0 ) |
    
    


    KKT

    условия Каруша — Куна — Таккера (Karush — Kuhn — Tucker) — необходимые условия решения задачи нелинейного программирования

    чтобы решение было оптимальным, должны быть выполнены некоторые условия регулярности. метод является обобщением метода множителей Лагранжа

                   minimize f(X) 
                   gi (X) ≤ 0
                   xi > 0
    
    если Xmin - решение задачи, то найдётся вектор множителей Лагранжа λ ∈ Rm такой, что для функции Лагранжа L (X) = f (X) + σ λi * gi (X) выполняются условия: