Методы оптимизации - теормин (1125564), страница 2

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

Текст из файла (страница 2)

Сильнополиномиальный методМетод, имеющий полиномиальную алгебраическую сложность.51. Теорема о границах решенийДля любой целочисленной матрицы D введем параметрmax∆ =||{ ′−квадратная подматрица }[A|b] – матрица, полученная приписыванием справа к А столбца b.ТеоремаЕсли озЛП размерности (n, m) с целыми коэффициентами разрешима, то у нее⁄существует рациональное решение x* в шаре | | ≤∆([ | ]) и значением озЛПd* = <c, x*> является рациональное число t/s со знаменателем, ограниченнымвеличиной (А).52. ε-приближенное решение системы ЛНТочка xε называется ε-приближенным решением системы неравенств, если< , > ≤ + ∀ = 1, , где аi – i-ая строка матрицы А.53.

Теорема о мере несоместностиЕсли ЛН имеет ε1-приближенное решение дляразрешима, то есть имеет точное решение.= 1⁄[( + 2)∆( )], то эта система54. ε-приближенное решение озЛПТочка ∗ называется ε-приближенным решением озЛП, если она является εприближенным решением системы ЛН и реализует максимум с ε-точностью:<,∗>≤+ ;< ,∗>≥−55. Теорема о мере несоместности*Если озЛП имеет ε2-приближенное решение дляимеет точное решение.= 1⁄(2∆ ( )), то эта задача56.

Следствие разрешимой системы ЛНЛинейное неравенство <c, x> ≤ d является следствием разрешимой системы ЛН, еслидля x, удовлетворяющего системе, выполнено <c, x> ≤ d.57. Лемма Фаркаша (аффинная)Линейное неравенство <c, x> ≤ d является следствием разрешимой в вещественныхпеременных системы ЛН тогда т только тогда, когда существует вектор λ ∈ R :=;≥∈;≥0 ∀ ∈∈58. Лемма Фаркаша о неразрешимостиСистема ЛН Ax ≤ b неразрешима тогда и только тогда, когда разрешима система= 0;∈≤ −1;≥0 ∀ ∈∈59. Двойственная задачаДвойственной к задаче ЛП на максимум с ограничениями неравенствами в формеозЛП называется следующая задача ЛП с ограничениями в канонической форме:min {∑ ∈| ∑∈= ;≥ 0 ∀ ∈ } или кратко min < λ, b >,60. Теорема о двойственности ЛПЗадача ЛП разрешима тогда и только тогда, когда разрешима двойственная к ней.

Вслучае разрешимости оптимальные значения целевых функций совпадают.61. УтверждениеЗадача ЛП оптимизации эквивалентна решению системы ЛН.62. УтверждениеЗадача ЛП эквивалентна решению системы линейных уравнений в неотрицательныхпеременных.63. УтверждениеЗадача ЛП эквивалентна поиску неотрицательного ненулевого решения однороднойсистемы линейных уравнений.64. Метод Крамакара65.

Классификация задач МПЗМП – задачи с вещественными переменными.1) Условные задачи ⊂2) Безусловные =По свойствам целевой функции ЗПМ делятся на1) Задачи ЛП2) Задачи выпуклого программирования3) Гладкие и негладкие и др.С точки зрения численных методовЛокальная и глобальная оптимизация66. Точка локального минимума в ЗМП∈ называется точкой локалького минимума в ЗМП, если∃ > 0: ( ) ≤ ( ) ∀ ∈ ∩ ( )67. УтверждениеЦЛН ∝ ЗМП68. Выпуклая функцияФункция f(x) называется выпуклой на X, если ее надграфик= {( , )| ≥ ( ), ∈ } – выпуклое множество.

Функция называетсявыпуклой, если она выпукла на всей области определения.Множество называется выпуклым, если для любых двух своих точек оно содержитотрезок, их соединяющий.69. УтверждениеЛюбая точка локального минимума выпуклой функции является точкой ееглобального минимума.70. Преимущества выпуклого случая1) Задача поиска ε-приближенного решения задачи выпуклого программированияполиномиально разрешима2) Для острых задач – когда функция цели убывает в окрестности минимума немедленнее некоторой линейной функции, можно найти точное решение.71.

Направление убывания функцииВектор ℎ ∈называется вектором убывания f в точке x, если ( + ℎ) < ( ) для достаточно малых > 072. УтверждениеПусть f дифференцируема в X. Тогда, если < grad ( ), ℎ > < 0, то h – направлениеубывания f в точке x. Если h – направление убывания f в точке x, то< grad ( ), ℎ > ≤ 073. Градиентный метод оптимизации= − grad ( ) ∀ ∈Выбор :1) Пассивные способы – выбираются заранее2) Адаптивные способы – зависит от реализующейся итерации (методскорейшего спуска, метод дробления шага, правило Армихо)74. Метод проекции градиента={−grad ( )} ∀∈75. Дифференцируемая по Адамару функцияФункция называется дифференцируемой по Адамару в точкевектор ∇ ( ) ∈ , такой что ∀ ∈выполнено∈, если существует( ,lim)→(( +)− ( ), )=< ∇ ( ),>76. Контингентный конусКонтингентным конусом ко множеству X в точке x называется множество векторов( , ) = { | ∃{( ,)}: ( ,) → (+0, );+∈∀ }77.

Общий вид необходимых условий локального минимумаПусть f дифференцируема по Адамару, ⊂ , ≠ ∅, – точка лоального минимумаf. Тогда ∀ ∈ ( , ) < ∇ ( ), > ≥ 078. Регулярное множествоJ( ) = { ∈ | ( ) = 0} – множество активных ограничений.( ) = { ∈ | < ∇ ( ), > ≤ 0 ∀ ∈ J( )Множество X для ограничений неравенств называется регулярным в точке x ∈ X,если ( ) ⊆ ( , )79.

Необходимые условия локального минимума с ограничениями-неравенствамиПусть ,∀ ∈ дифференцируемы по Адамару, ≠ ∅, – точка локальногоминимума f и X регулярно в x0. Тогда ∃≥ 0: ∇ ()+∑∈ ()() =080. Принцип оптимальности ЛагранжаВ предположениях теоремы из пункта 79 существует неотрицательный вектормножителей Лагранжа ≥ 0, такой что для x0 выполнены условия оптимальности∇(, )=081. Теорема Куна-ТаккераЕсли функции , ∈ ( ) выпуклы и множество X регулярно в любой точке, то x* –точка оптимума в этой задаче тогда и только тогда, когда в ней выполнены условияоптимальности для ≥ 082. Вполне унимодулярная матрицаМатрица называется унимодулярной, если определительн любой ее невыожденнойквадратной подматрицы равен по модулю 1..

Характеристики

Список файлов ответов (шпаргалок)