» ГЛАВНАЯ > К содержанию номера
 » Все публикации автора

Журнал научных публикаций
«Наука через призму времени»

Июнь, 2022 / Международный научный журнал
«Наука через призму времени» №6 (63) 2022

Автор: Арсланова Юлия Викторовна, студент
Рубрика: Физико-математические науки
Название статьи: Метод линеаризации для задач нелинейного программирования

Статья просмотрена: 96 раз
Дата публикации: 10.06.2022

Метод линеаризации для задач нелинейного программирования

Арсланова Юлия Викторовна   

студент

ФГБОУ ВО

 

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

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

 

Постановка задачи:           Рассмотрим задачу нелинейного программирования.

            Требуется минимизировать функцию  ,  на множестве Х, которое представляет собой совокупность неравенств и равенств.

,                                               (1)

                                                                        

 где  непрерывно дифференцируемы ,  – конечные индексные множества, Х – допустимое множество.

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

            Итак, далее будем рассматривать задачу следующего вида

                

    ,                                            (2)

              

Введем понятия глобального решения задачи (2) и локального решения задачи (2).

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

            1) точкой глобального минимума функции f₀(x) на множестве X, или глобальным решением задачи (2) если

           

              2) точкой локального минимума функции f₀(x) на множестве Х, или локальным решением задачи (2), если

             

 

Введем в рассмотрение функцию Лагранжа

(линейная комбинация функции f_i(x) с коэффициентами u_i)

            Определение.  Точка  удовлетворяющая при некотором векторе  условию

                                                                                          

называется стационарной точкой задачи (2).

 

 Условие оптимальности

 

Пусть - непрерывно дифференцируемые функции, а Х – выпуклое множество.

Пусть  - решение задачи (1`).

Введем в рассмотрение множество

           

Тогда справедлива следующая теорема:

 

Теорема. Для того чтобы точка  была решением задачи (2), необходимо, чтобы нашлись не равные нулю одновременно числа , такие что

Где   - множители Лагранжа.

Основные предположения.

Введем обозначения

                                                  

 В силу ранее сделанного предположения  при .

 Предположим, что существуют такие константы , что

            а) множество

ограничено.

            Обозначим

           

            б) градиенты функций ,  в удовлетворяют условию Липшица, т.е.(L>0)

                                      

            в) задача квадратичного программирования 

                                                                         (3)

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

            Решение задачи (3) - , а множители Лагранжа – через .

            Формулировка алгоритма.

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

1.     Решаем вспомогательную задачу (3) при , находим ее решение – вектор.

2.     Находим очередное приближение , где ,

а i₀  наименьшее из , при котором будет впервые  выполнено

неравенство

.

            Таким образом, на каждом шаге выполняется следующее неравенство:

 Свойства метода линеаризации.

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

2. Сходимость алгоритма.

Сходимость алгоритма следует из утверждения

Теорема. При выполнении сделанных выше предположений процесс обладает следующими свойствами:

            а)  при ;

            б) в любой предельной точке последовательности , выполняется необходимые условия минимума.

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

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

            Построим двойственную задачу для задачи (3). Двойственной задачи имеет вид  (4)

               (4)                                                                                          где  А – симметричная матрица и состоит из элементов

           

(i-я компонента вектора d равна )

а

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

                                  (5)

 дает вектор  - решение исходной задачи.

 Алгоритм

            Опишем теперь алгоритм метода линеаризации. Пусть выбраны произвольное начальное приближение , точность решения исходной задачи  (2) , точность решения вспомогательной задачи (4)  и величины .

            Общий  шаг алгоритма. Пусть точка  и числа  построены.

1.     Строим множество  и задачу (4).

2.     Решаем задачу (4). Ее решение – множители Лагранжа .  Если задача (4) неразрешима, то полагаем

      

И  возвращаемся к 1.

3. Если решение задачи (4) получено и

, то .

В противном случае

.

4. Вычисляем   вектор направления движения

.

5. Если 

,                    

то  решение задачи (2).

6. Если  не выполняется, то полагаем

где  выбирается равным , а наименьшее из целых чисел наименьшее из целых чисел q=0,1,…., для которого выполняется соотношение

Возвращаемся к 1.

Примеры. Найти минимум

           

при ограничениях

Начальная точка . Минимум в точке  

и значение .

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

Заменим в точке x₀ ( нач.прибл.) все ограничения (1)  и  на линейные, линеаризовав  в точке x₀. В результате получится некоторая задача линейного программирования. Естественно было бы решение линеаризованной задачи взять в качестве следующего приближения, как это делается в методе Ньютона для решения систем нелинейных уравнений. Но прямо этот путь не приводит к цели, так как обычно вспомогательная задача линейного программирования не имеет решения. Поэтому наложим некоторые ограничения на приращения вектора x точке x₀, чтобы решение линеаризованной задачи в точке x₀ не уходило слишком далеко от x₀, оставаясь в такой окрестности x₀, в которой линеаризация еще справедлива. Для этого будет добавлен квадратичный член к линеаризованной целевой функции.

Список литературы:

1. Гавурин М.К., Малозёров В.Н. Экстремальные задачи с линейными ограничениями. Л.: Изд-во ЛПУ, 1984, 176 с.
2. Пшеничный Б.Н. Метод линеаризации. – М.: Наука. Главная редакция физико-математической литературы – 1983 г. – 136 с.



Комментарии:

Фамилия Имя Отчество:
Комментарий: