Задание к зачету Оптмизация Рудковский А.М.-12-2021. Задание к зачету(оптимизация)-2 Рудковский Анатолий-12-2021. Факультет 6 Аэрокосмический Кафедра 604 Информационное и программноалгоритмическое обеспечение движения и управления аэрокосмическими системами

• Название: Факультет 6 Аэрокосмический Кафедра 604 Информационное и программноалгоритмическое обеспечение движения и управления аэрокосмическими системами
• Анкор: Задание к зачету Оптмизация Рудковский А.М.-12-2021
• Дата: 13.06.2022
• Размер: 84.54 Kb.
• Имя файла: Задание к зачету(оптимизация)-2 Рудковский Анатолий-12-2021.docx
• Тип: Документы; #589098

Министерство образования и науки РФ Федеральное государственное бюджетное образовательное учреждение
	высшего профессионального образования "Московский авиационный институт" (национальный исследовательский университет) факультет №6 Аэрокосмический
Кафедра 604 «Информационное и программно-алгоритмическое обеспечение движения и управления аэрокосмическими системами»
Специальность 24.04.03 «Баллистика и гидроаэродинамика»

Задание к зачету

по курсу " Интеллектуальные технологии и оптимизация информационных спутниковых систем "

Вариант 7

	Работу выполнила: Студент группы М6О-110М-21 Рудковский Анатолий Михайлович Работу принял д.т.н, доцент кафедры 604: Старков Александр Владимирович
		(Старков А.В.)
		(Рудковский А.М.)

Москва-2021

Аналитическое решение

1. Постановка задачи

Работа посвящена аналитическим методам решения задач условной оптимизации целевых функций с ограничениями типа неравенств, накладываемых на векторный аргумент, то есть:

f (x)

(1)

Где х – вектор аргументов (параметров), имеющий в общем случае размерность [n1], f(x) – скалярная унимодальная дифференцируемая функция, Х – множество допустимых значений аргументов х, заданное совокупностью ограничений типа неравенств:

(2)

Где g_j(x) - дифференцируемая функция векторного аргумента,
j - число ограничивающих функций.

Задача (1) считается поставленной корректно, если ограничения 
g_j(x)≤0, j=1,…,m совместимы и образуют непустое множество Х, на котором существует целевая функция f(x) .

Аналитическое решение задачи условной оптимизации следует найти с помощью необходимых условий оптимальности – теоремы Куна и Таккера.

В результате аналитического решения задачи должен быть получен набор локальных условных минимумов, из которых путем сравнения выбирается решение. Кроме того, полученное решение необходимо сопроводить графической иллюстрацией, т.е. построить линии уровня целевой функции, ограничения и найденных точек глобального и локальных минимумов.

Для аналитического решения задачи типа (1, 2) предлагается использовать методику, в основе которой лежит теорема Куна и Таккера, представляющая собой в общем случае необходимые условия минимума целевой функции при наличии ограничений типа неравенств на множество допустимых значений векторного аргумента функции (см.(2)).
В рассматриваемом приложении эту методику целесообразно представить в виде следующего расширенного алгоритма:

1. Формирование функции Лагранжа

Исходя из обозначений принятых в постановке (1, 2), функция Лагранжа будет иметь вид:

F(x, ) = f (x) + T g(x)

(3)

где  - вектор множителей Лагранжа размерности [m1], соответствующей количеству ограничений

2. Применение необходимых условий (НУ) в форме Куна и Таккера для определения условных стационарных точек для задачи (1, 2).

В компактной форме для случая минимизации функции условия Куна и Таккера могут быть записаны в виде:

(4)

Где - координаты стационарных точек.

При рассмотрении конкретных задач, в которых количестве ограничений более одного, то есть при m >1 возможны различные сочетания активных и пассивных ограничений:

(5)

Где I₁ – множество номеров индексов активных ограничений,
I₂ – множество номеров индексов пассивных ограничений (сумма элементов этих множеств, всегда равна m).

Очевидно, что в этих случаях НУ (4) должны быть применены при всех возможных сочетаниях активных и пассивных ограничений, включая крайние случаи:

• 
  когда множество номеров активных ограничений I₁ пусто (=0), то есть фактически рассматривается задача безусловной оптимизации;
  
• 
  когда количество активных ограничений, то есть количество элементов множества I₁ равно размерности вектора х – [n1] (так называемые «угловые» точки), тогда эта точка фиксируется активными ограничениями и не допускает вариации целевой функции (имеется ввиду корректная постановка задачи (1, 2)).
  

В результате применения НУ для всех возможных сочетаний активных ограничений будут получены варианты стационарных точек - , в которых могут оказаться условные локальные минимумы и, в конечном итоге, - условный глобальный минимум, являющийся решением поставленной задачи.

3. Исключение всех стационарных точек, не удовлетворяющих пассивным ограничениям

То есть:

( )<0, j  1,m

(6)

4. Исключение стационарных точек, не удовлетворяющих условиям не отрицательности множителей Лагранжа

Из оставшегося числа вариантов стационарных точек необходимо исключить все точки, не удовлетворяющие условиям не отрицательности соответствующих множителей Лагранжа - , в которых согласно НУ не могут находиться условные локальные минимумы целевой функции.

5. Проверка оставшихся стационарных точек на достаточные условия локального минимума функции

Все оставшиеся стационарные точки, за исключением «угловых» точек, должны быть проверены с помощью достаточных условий (ДУ), подтверждающих или опровергающих наличие в них условного локального минимума.

Одним из широко распространенных вариантов ДУ нахождения в исследуемой стационарной точке условного локального минимума является положительная определенность матрицы Гессе, размера [nn] (матрицы вторых частных производных) для функции Лагранжа F(х, ) по вектору х – [n1].

H(x)(х, ) =

(7)

Известно, что матрица положительно определена, если составленная с ее помощью квадратичная форма положительно определена [1], то есть:

(8)

Где H(x)(х, ) - матрица Гессе (Гессиан) по вектору х; y – любой вектор с фиксированными значениями , размера [n1].

Для проверки положительной определенности квадратичной формы (8) предлагается применить критерий Сильвестра. Суть его заключается в следующем:

Для того, чтобы квадратичная форма (8) была положительно определенной, необходимо и достаточно, чтобы матрица имела все положительные угловые миноры, нарастающие вдоль главной ее диагонали, то есть были бы положительными определители матриц:

∆1= h11>0;∆2=  >0;…; ∆n=  > 0

(9)

Где h_ij – элементы матрицы Гессе H(x)(х, ) .

Таким образом, при подтверждении положительной определенности матрицы Гессе в стационарных точках, в которых согласно НУ возможно было нахождение условного локального минимума, то есть при  > 0 , такие стационарные точки переводятся в число точек условного локального минимума целевой функции f(x) при условиях g_j(x) ≤ 0, j=1,…,m :

для номеров «s», удовлетворяющих НУ и ДУ

(10)

6. Определение условного глобального минимума

Сравнение значений целевой функции f(x) в точках условного локального минимума и в «угловых» точках позволяет выявить условный глобальный минимум:

(11)

Где – координаты «угловых» точек, определяемых n активными ограничениями из числа j1,…,m.

Таким образом, условный глобальный минимум целевой функции равняется

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

2. Вариант задания

f(x1, x2)	gi (x1, x2) ≤ 0, i = 1,m
3(х1 – 5)2 + (х2 – 8)2	х1 + 3х2 - 6
	-х1 - 1
	-х2 - 2

3. Решение аналитической части

Безусловный минимум функции



Найдем безусловный минимум функции:

Посчитаем первые частные производные:

Составим систему уравнений и решим ее:

Проверим достаточные условия минимума функции, составив матрицу Гессе и применив критерий Сильвестра:



Оба минора положительные, следовательно, точка (5; 8) точка глобального безусловного минимума.

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

1. 
   Запишем функцию Лагранжа для первого ограничения:
   

Считаем первые частные производные:

Записываем систему уравнений и решаем ее:

Проверим ограничения:

Точка соответствует всем условиям, λ₁>0 отсюда следует, что эта точка может быть точкой глобального минимума

2. 
   Запишем функцию Лагранжа для второго ограничения:
   

Считаем первые частные производные:

Записываем систему уравнений и решаем ее:

λ₂<0 отсюда следует, что эта точка не может быть точкой глобального минимума

Проверим ограничения:

Точка не попадает в заданную область ограничений.

3. 
   Запишем функцию Лагранжа для третьего ограничения:
   

Считаем первые частные производные:

Записываем систему уравнений и решаем ее:

λ₃<0 отсюда следует, что эта точка не может быть точкой глобального минимума

Проверим ограничения:

Точка попадает в заданную область ограничений.

Угловые точки функции

1. Записываем систему уравнений с первым и третьим ограничениями решаем ее:

2. Записываем систему уравнений со вторым и третьим ограничениями и решаем ее:

3. 
   Записываем систему уравнений с первым и вторым ограничениями и решаем ее:
   

Значение функции во всех стационарных точках и глобальный условный минимум

• 
  При получаем
  
• 
  При получаем
  
• 
  При получаем
  
• 
  При получаем
  

Минимальное значение следовательно, глобальный условный минимум достигается при значениях

Ограничения	Точки
	1. глобальный условный минимум 2. угловые точки 3. глобальный безусловный минимум