АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Постановка задачи и основные определения

Читайте также:
  1. B. Основные принципы исследования истории этических учений
  2. I Определения
  3. I Психологические принципы, задачи и функции социальной работы
  4. I. 1.1. Пример разработки модели задачи технического контроля
  5. I. 1.2. Общая постановка задачи линейного программирования
  6. I. 2.1. Графический метод решения задачи ЛП
  7. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  8. I. Дайте определения следующих правовых категорий.
  9. I. ЗАДАЧИ ПЕДАГОГИЧЕСКОЙ ПРАКТИКИ
  10. I. Значение и задачи учета. Основные документы от реализации продукции, работ, услуг.
  11. I. ОСНОВНЫЕ ПОНЯТИЯ (ТЕРМИНЫ) ЭКОЛОГИИ. ЕЕ СИСТЕМНОСТЬ
  12. I. ОСНОВНЫЕ СПОСОБЫ ПЕРЕДВИЖЕНИЯ И ПРЕОДОЛЕНИЯ ПРЕПЯТСТВИЙ

Тема 1.8. Многомерная оптимизация

 

 

Постановка задачи и основные определения

 

Задача, требующая нахождения оптимального значения функции m переменных f(Х)=f(x1, x2, …, xm), называется задачей многомерной оптимизации. Так же, как и для случая одномерной оптимизации, задача нахождения максимума функции сводится к задаче нахождения минимума путем замены целевой функции f на -f.

Пусть функция f(Х) = f(x1, x2, …, xm) определена на некотором множестве ХÎRm. Если Х=Rm (т.е. ограничения на переменные x1, x2, …, xm отсутствуют), принято говорить о задаче безусловной минимизации. В противном случае, когда Х ¹Rm, говорят о задаче условной минимизации.

Методы решения задачи безусловной минимизации являются основой для перехода к изучению более сложных методов решения задач условной минимизации.

В постановке задачи безусловной оптимизации для f(Х)=f(x1, x2, …, xm) требуется найти хотя бы одну точку минимума Х* и вычислить f*=f(Х*). Точка Х*ÎRm называется точкой глобального минимума функции fна множестве Х, если для всех ХÎRm выполняется неравенство f(Х*)£f(Х). В этом случае значение f(Х*) называется минимальным значением функции fна Rm.

Точка Х*ÎRm называется точкой локального минимума функции f, если существует такая d - окрестность Ud этой точки (d>0), что для всех ХÎХd Ud выполняется неравенство f(X*)£f(X).

Подавляющее большинство методов решения задачи безусловной минимизации в действительности являются методами поиска точек локальных минимумов, среди которых затем выделяют глобальный минимум, являющийся наименьшим. Этот способ очень трудоемок, поэтому чаще используют другой: местоположение точки глобального минимума определяют в ходе анализа решаемой задачи, а затем для его уточнения с заданной точностью применяют один из методов поиска точки локального минимума.

Рассмотрим функцию нескольких переменных и введем для нее основные определения.

Множество точек, для которых целевая функция принимает постоянное значение f(x1, x2, …, xm) = c, называется поверхностью уровня. Для функции двух переменных (m = 2) это множество называется линией уровня.

Функция f(x1,x2) задает в трехмерном пространстве некоторую поверхность U=f(x1,x2) (рис. 1.8.1-1), низшая точка которой и дает решение задачи минимизации. Для того чтобы изобразить рельеф этой поверхности, проведем несколько плоскостей
(U = const): U=c1, U=c2, U=c3. Проекции на плоскость Ох1х2 линий пересечений этих плоскостей с поверхностью и дают линии уровня.

Рис. 1.8.1-1

 

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

или .

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

Вектор - называется антиградиентом и показывает направление наискорейшего убывания функции.

Равенство нулю градиента в точке Х является необходимым условием того, чтобы внутренняя для множества Хi (i = 1, 2,…m) точка Х была точкой локального минимума дифференцируемой функции f. Точка Х, для которой выполняется равенство f’(X) = 0, называется стационарной точкой функции.

Это равенство представляет собой систему из m нелинейных уравнений относительно компонент х1, х2, …, хm, вектора X, где m – количество переменных.

 

 

Для функции двух переменных Q(x, y)это условие имеет вид:

 

 

Однако не всякая стационарная точка является точкой минимума. Для всякой непрерывно дифференцируемой функции f достаточным условием того, чтобы стационарная точка Х была точкой локального минимума, является положительная определенность матрицы вторых производных (матрицы Гессе):

 

 

Согласно критерию Сильвестра, для того чтобы матрица была положительно определена, необходимо, чтобы все угловые миноры были положительны:

 

 

Для функции двух переменных Q(x, y) матрица Гессе имеет вид:

 

,

 

а достаточное условие существования минимума:

Алгоритм решения задачи оптимизации функции двух переменных Q(x,y) аналитическим (классическим) методом следующий:

1. Составляется и решается система уравнений

 

 

из которой находятся (x*, y*).

 

2. Проверяются достаточные условия существования минимума

 

.

 

Если (x*, y*) – единственное решение и в этой точке выполняются достаточные условия, то это точка минимума. Если хотя бы в одном из неравенств получается знак “<”, то минимума не существует. В случае появления знака “ = ” необходимо исследовать производные высших порядков.

 


1 | 2 | 3 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)