9905

Нелинейное программирование

Реферат

Информатика, кибернетика и программирование

Нелинейное программирование § 1. Общая задача нелинейного программирования Как известно, общая задача математического программирования формулируется следующим образом: найти вектор Х=(х1, х2, ..., хn) удовлетворяющий системе ограничений gi (х1, х2, ...

Русский

2013-03-18

80.5 KB

72 чел.

Нелинейное программирование

§ 1. Общая задача нелинейного программирования

Как известно, общая задача математического программирования формулируется следующим образом: найти вектор Х=(х1, х2, ..., хn) удовлетворяющий системе ограничений

gi (х1, х2, ..., хn)=bi, i=l, 2, ..., k;

gi(х1, х2, ..., хn)bi, i=k+l, k+2, ..., m   (2.1)

и доставляющий экстремум функции

Z=f(х1, х2, ..., хn).      (2.2)

При этом предполагается, что известны функции gi(х1, х2, ..., хn) и f(х1, х2, ..., хn). Обычно на некоторые переменные х1, х2, ..., хn накладывается условие неотрицательности.

Кроме того, ограничением может служить условие целочисленности решения для ряда переменных. Если

gi(х1, х2, ..., хn)=, i=1, 2, ..., m,    (2.3)

и

Z=f(х1, х2, ..., хn) =.     (2.4)

где aij и Cj - известные константы, то при условии неотрицательности решения получаем задачу линейного программирования. Любую другую задачу математического программирования, не удовлетворяющую условиям (2.3) и (2.4), условимся считать нелинейной.

Класс задач нелинейного программирования шире класса задач линейного программирования. Подробное изучение практических задач, которые условились считать линейными, показывает, что они в действительности являются нелинейными. Возникает задача нахождения эффективных методов решения задач нелинейного программирования. Существующие методы позволяют решать узкий класс задач, ограничения которых имеют вид (2.3), а целевая функция сепарабельная (является суммой n функций j(xj)) или квадратическая. Даже если область допустимых решений выпуклая, то в ряде задач целевая функция может иметь несколько локальных экстремумов. С помощью большинства же вычислительных методов можно найти точку локального оптимума, но нельзя установить, является она точкой глобального (абсолютного) оптимума или нет. Если в задачах линейного программирования точка экстремума является вершиной многогранника решений, то в задачах нелинейного программирования она может лежать в вершине многогранника, на ребре (грани) или внутри области. Если задача содержит нелинейные ограничения, то область допустимых решений не является выпуклой, и кроме глобального оптимума могут существовать точки локального оптимума.


§ 2. Метод множителей Лагранжа

Пусть задана задача математического программирования: максимизировать функцию

Z = f(х1, х2, ..., хn)      (2.5)

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

gi(х1, х2, ..., хn) = 0, i=1, 2. ..., m.     (2.6)

Ограничения в задаче заданы уравнениями, поэтому для ее решения можно воспользоваться классическим методом отыскания условного экстремума функций нескольких переменных. При этом полагаем, что функции f(х1, х2, ..., хn) и gi(х1, х2, ..., хn) (i=1, 2, ..., m) непрерывны вместе со своими первыми частными производными. Для решения задачи составим функцию

F(x1,x2,...,xn,1,2,...,m)=f(х1,х2,...,хn)+  (2.7)

Определим частные производные  (j=1,2, ...,n),  (i=1,2,...,m) и приравняем их нулю. В результате получим систему уравнений

      (2.8)

Функция (2.7) называется функцией Лагранжа, а числа i - множителями Лагранжа. Если функция Z= f(х1,х2,..., хn) в точке X(0)=(x1(0), x2(0), ..., xn(0)) имеет экстремум, то существует такой вектор (0)=(1(0), 2(0), ..., m(0)), что точка (x1(0), x2(0), ..., xn(0), 1(0), 2(0), ..., m(0)) является решением системы (2.8). Следовательно, решая систему (2.8), получаем множество точек, в которых функция Z может иметь экстремальные значения. При этом неизвестен способ определения точек глобального минимума или максимума. Однако если решения системы найдены, то для определения глобального максимума (минимума) достаточно найти значения функции в соответствующих точках. Если для функций Z=f(х1,х2,...,хn) и gi(х1, х2, ..., хn), i=1, 2, ..., m, существуют вторые частные производные и они непрерывны, то можно вывести достаточное условие существования локального экстремума функции в точке, являющейся решением системы (2.8). Однако практическое значение этого условия невелико.

Метод множителей Лагранжа имеет ограниченное применение, так как система (2.8), как правило, имеет несколько решений. Рассмотрим пример применения метода множителей Лагранжа.


Пример 1. Найти точку условного экстремума функции Z=x1x2+x2x3 при ограничениях

Решение. Составим функцию Лагранжа

F(х1,х2,х3,2,2)=х1х2+х2х3+1(х1+х2-2)+2(х2+х3-2)

и продифференцируем ее по переменным х1, х2, х3, 1 и 2. Приравнивая полученные выражения нулю, получим следующую систему уравнений:

Из первого и третьего уравнения следует, что 1=2= -х2; тогда

Решая данную систему, получим: х1 = х2 = х3 = 1, Z=2.


§ 3. Выпуклые и вогнутые функции

В дальнейшем часто используются так называемые выпуклые и вогнутые функции. Приведем ряд определений. Пусть задано n-мерное линейное пространство En. Функция f(X), заданная на выпуклом множестве ХEn, называется выпуклой, если для любых двух точек X(1) и X(2) из Х и любого 01 выполняется соотношение

f[X(2)+(1-)X(1)]f(X(2))+(1+)f(X(1)).    (2.9)

Часто множество Х совпадает с En или является неотрицательным октантом.

Функция f(X), заданная на выпуклом множестве X, называется вогнутой, если для любых двух точек X(1) и X(2) из Х и любого 01 выполняется соотношение

f[X(2)+(1-)X(1)]f(X(2))+(1-)f(X(1)).   (2.10)

Если f(X) - выпуклая функция, то - f(X) - вогнутая функция, и наоборот.

Геометрически это означает, что если Z=f(X) - выпуклая поверхность, то отрезок, соединяющий любые две ее точки, лежит на поверхности или выше нее.

Следует отметить, что выпуклость и вогнутость функций определяется только относительно выпуклых множеств в En, так как, по определению, вместе с любыми точками X(1) и X(2) множеству принадлежат точки X(2) и (1-)X(1) при всех 01. Последнее справедливо только тогда, когда множества выпуклые.

Если неравенства (2.9) и (2.10) считать строгими и они выполняются при 01, то функция f(X) является строго выпуклой (строго вогнутой). Геометрически это означает, что отрезок, соединяющий любые две точки поверхности, лежит выше (ниже) этой поверхности.

Утверждение 1. Если f(X)=, где fj(X) - выпуклые функции на некотором выпуклом множестве ХEn, то функция f(X) также выпуклая на X.

Утверждение 2. Сумма вогнутых функций есть вогнутая функция.

Теорема 1. Если f(X) - выпуклая функция, заданная на неотрицательном октанте пространства Еn, то множество V всех точек, удовлетворяющих условиям f(X)b, Х0, выпукло (если оно не пусто).

Доказательство: Покажем, что множество V вместе с точками X(1) и X(2) при любом 01 содержит точку Х(0)=X(2)+(1-)X(1), при этом Х(0)0. Так как f(X) - выпуклая функция, то

f(X(0))=f[X(2)+(1-)X(1)]f(X(2))+(1-)f(X(1))

Для точек X(1) и X(2) выполняются условия f(X(1))b и f(X(2))b. Тогда для всех 01

f(X(2))b, (1-)f(X(1))(1-)b.

Следовательно,

f(X(2)) + (1-)f(X(1))  b+(1-)b = b  и  f(X(0))  b,

что и требовалось доказать.


Теорема 2. Пересечение выпуклых множеств выпукло.

Доказательство:  выполнить самостоятельно.

Теорема 3. Непустое множество всех точек W, удовлетворяющих условиям fj(X){}bi, i=1,2,..., m; Х0, выпукло, если в неравенствах со знаком «» fi - выпуклые функции, а в неравенствах со знаком «» fi - вогнутые функции для Х0.

Доказательство: выполнить самостоятельно.

При определении выпуклости и вогнутости функции не требовалось, чтобы функция была непрерывной или дифференцируемой. Если же f(X) непрерывна и дифференцируема во внутренних точках множества Х и выпукла на нем, то можно получить следующий результат. Из (2.9) для 01 находим

;

тогда, по формуле Тейлора,

f[X(1)+(X(2)-X(1))]=f[X(1)+(X(2)-X(1))](X(2)-X(1)),

где f[X(1)+(X(2)-X(1))]= - градиент функции f, вычисленный в точке [X(1)+(X(2)-X(1))], 01. Переходя к пределу при 0, получим

f(X(1))(X(2)-X(1))f(X(2))-f(X(1)).        (2.11)

Это условие выполняется для любых внутренних точек X(1) и X(2) и является необходимым и достаточным условием выпуклости f(X). Если функция f непрерывна вместе с частными производными первого порядка и вогнута на X, то

f(X(1))(X(2)-X(1))f(X(2))-f(X(1)).    


Рассмотрим некоторые свойства выпуклых и вогнутых функций.

Теорема 4. Пусть f(X) - выпуклая функция, заданная на замкнутом выпуклом множестве ХEn; тогда любой локальный минимум f(X) на Х является и глобальным.

Доказательство. Предположим, что в точке Х(0) функция f(X) имеет локальный минимум, в то время как глобальный минимум достигается в точке X*, причем f(X(0))> f(X*). Так как f(X) -выпуклая функция, то для любого 01 справедливо соотношение

f[X*+(1-)X(0)]f(X*)+(1-)f(X(0)).   (2.12)

Множество X выпукло, поэтому точка X*+(1-)X(0) при 01 принадлежит ему. Неравенство (2.12) можно усилить, если вместо f(X*) подставить f(X(0)). Имеем

f[X*+(1-)X(0)]<f(X(0)).

Значение можно выбрать так, чтобы точка

X*+(1-)X(0) 

была расположена как угодно близко к X(0). Тогда полученное неравенство противоречит тому, что точка X(0) является точкой локального минимума, так как в этом случае в близкой к X(0) точке функция принимает значение меньшее, чем в точке X(0). Теорема доказана.

Следствие 1. Если глобальный минимум достигается в двух различных точках, то он достигается и в любой точке отрезка, соединяющего данные точки.

Следствие 2. Если f(X) - строго выпуклая функция, то ее глобальный минимум на выпуклом множестве Х достигается в единственной точке.

Теорема 5. Пусть f(X) - выпуклая функция, заданная на выпуклом множестве X, и, кроме того, она непрерывна вместе со своими частными производными первого порядка во всех внутренних точках X. Пусть X(0) - точка, в которой f(X(0))=0. Тогда в точке X(0) достигается локальный минимум, совпадающий с глобальным минимумом.

Доказательство. Пусть Х - произвольная точка множества X. Из необходимого и достаточного условия выпуклости (2.11), полагая X(0)=X(1), а Х=X(2) получим

f(X(0))(X -X(0))  f(X) - f(X(0)),

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

Можно показать, что если Х - замкнутое, ограниченное снизу, выпуклое множество, то глобальный максимум выпуклой функции f(X) достигается на нем в одной или нескольких крайних точках (при этом предполагается, что в точке Х значение функции f(X) конечно). Применяя при решении таких задач процедуру перебора крайних точек, можно получить точку локального максимума, но нельзя установить, является ли эта точка точкой глобального максимума.

Для вогнутых функций рассмотренные результаты можно сформулировать следующим образом. Пусть f(X) - вогнутая функция, заданная на замкнутом выпуклом множестве ХЕn. Тогда любой локальный максимум f(X) на X является глобальным. Если глобальный максимум достигается в двух различных точках множества, то он достигается и на бесконечном множестве точек, лежащих на отрезке, соединяющем эти точки. Для строго вогнутой функции существует единственная точка, в которой она достигает глобального максимума.

Градиент вогнутой функции f(X) в точках максимума равен нулю, если f(X) - дифференцируемая функция. Глобальный минимум вогнутой функции, если он конечен, на замкнутом ограниченном снизу множестве должен достигаться в одной или нескольких его крайних точках, если функция f(X) конечна в каждой точке этого множества.

§ 5. Теорема Куна-Таккера

Центральное место в теории нелинейного программирования занимает теорема Куна-Таккера. Пусть дана задача нелинейного программирования:

найти максимальное значение функции Z=f(х1, х2, ..., хn) при ограничениях

gi(х1, х2, ..., хn)0, i=1, 2, ..., m,     (2.13)

х1, х2, ..., хn0.

Составим функцию Лагранжа для данной задачи:

.    (2.14)

Если выполняется условие регулярности (существует по крайней мере одна точка X, для которой gi(X)>0 для всех i), то имеет место следующая теорема.

Теорема 6. Вектор X(0) тогда и только тогда является оптимальным решением задачи (2.13), когда существует такой вектор (0), что при X(0)0 и (0)0 для всех X0 и 0

F(X,(0)) F(X(0), (0)) F(X(*),)   (2.15)

Точка (X(0), (0)) называется седловой точкой для функции F(X,), а теорема называется теоремой о седловой точке. Докажем достаточность условий (2.15).

Доказательство. Пусть X(0)>0 и (0)>0 - седловая точка функции F(X,). Если в (2.15) вместо F(X,) подставить ее значение (2.14), то получим

при X0, 0.

Правое неравенство справедливо при любом 0, поэтому

gi(X)0, .

Тогда из левого неравенства получим

Так как при этом , то f(X(0))>f(X).

Таким образом, точка X(0) удовлетворяет (2.13) и во всех других точках, удовлетворяющих (2.13), функция принимает значение меньшее, чем в X(0). Это утверждение приводит решение задачи НЛП к отысканию седловых точек функции Лагранжа F(X,).

Доказательство необходимости условий (2.15) ввиду его сложности не рассматривается.

Если f(X) и gi(X)—дифференцируемые функции, то (2.15) эквивалентны следующим локальным условиям Куна-Таккера:

,    ,    xj(0)0, j=1, 2, ..., n; (2.16)

,    ,    i(0)0, j=1, 2, ..., m; (2.17)

Выражение  означает, что значение частной производной функции Лагранжа берется в точке (X(0), (0)), где X(0)=(х1(0), х2(0), ..., хn(0)), (0)=(1(0), 2(0), ..., n(0)). Эти условия можно записать в векторной форме:

; ,  X(0)0; (2.16`)

; ;   (0)0; (2.17`)

Пример. Найти max Z=-x12-x22 при ограничениях

 x10,  x20.

Покажем, что существует (0)0, при котором в точке оптимума выполняются условия Куна-Таккера (2.16), (2.17) для функции F(X,):

F(X,)=-x12-x22+1(2x1+x2-2)+2(8-2x1-x2)+3(6-x1-x2).

Находим:

=-2x1+21-3; =-2x2+1-2-3;

=2x1+x2-2; =8-2x1-x2; =6-x1-x2.

Согласно условиям (2.17) 2 и 3 должны принимать нулевые значения, так как подставляя x1=0.8 и x2=0.4 в выражения  и  имеем значения, большие нуля, а по условию, . Согласно условию 1 может принимать ненулевое значение, так как .

В соответствии с (2.16) производная  (j=1, 2) должна принимать нулевые значения, так как координаты вектора X(0) отличны от нуля. Находим 1=0,8. Следовательно, в точке (X(0), (0)) выполняются условия Куна-Таккера и она действительно является точкой экстремума.


 

А также другие работы, которые могут Вас заинтересовать

18075. АНТЕНИ СИСТЕМ СУПУТНИКОВОГО РАДІОЗВ’ЯЗКУ 1.3 MB
  ЛЕКЦІЯ №2 з навчальної дисципліни ПРИКЛАДНІ ПИТАННЯ АНТЕННИХ ПРИСТРОЇВ ТЕМА 1: АНТЕНИ РТС ПЕРЕДАЧІ ІНФОРМАЦІЇ. ЗАНЯТТЯ 2: антенИ систем супутникового радіозв’язку 1. НАВЧАЛЬНІ ПИТАННЯ Вимоги до антен системи супутникового ра
18076. АНТЕНИ РАДІОРЕЛЕЙНИХ ЛІНІЙ 284 KB
  ЛЕКЦІЯ №3 з навчальної дисципліни ПРИКЛАДНІ ПИТАННЯ АНТЕННИХ ПРИСТРОЇВ ТЕМА 1: АНТЕНИ РТС ПЕРЕДАЧІ ІНФОРМАЦІЇ. ЗАНЯТТЯ 4: антенИ радіоРЕЛЕЙНИХ ЛІНІЙ 1. НАВЧАЛЬНІ ПИТАННЯ Вимоги до антен радіорелейних ліній. 2. Особли
18077. АНТЕНИ СИСТЕМ КОРОТКОХВИЛЬОВОГО ЗВ’ЯЗКУ ТА РАДІОМОВЛЕННЯ 258.5 KB
  ЛЕКЦІЯ №4 з навчальної дисципліни ПРИКЛАДНІ ПИТАННЯ АНТЕННИХ ПРИСТРОЇВ ТЕМА 1: АНТЕНИ РТС ПЕРЕДАЧІ ІНФОРМАЦІЇ. ЗАНЯТТЯ 5: антенИ систем короткохвильового зв’язку та радіомовлення. 1. НАВЧАЛЬНІ ПИТАННЯ Вимоги до антен коротк...
18078. ЧАСТОТНО НЕЗАЛЕЖНІ АНТЕНИ 365.5 KB
  ЛЕКЦІЯ №5 з навчальної дисципліни ПРИКЛАДНІ ПИТАННЯ АНТЕННИХ ПРИСТРОЇВ ТЕМА 2: Частотні властивості антен. ЗАНЯТТЯ 1: Частотно незалежні антени 1. НАВЧАЛЬНІ ПИТАННЯ Принцип створення частотно незалежних антен. 2. Пр
18079. АКТИВНІ ПЕРЕДАВАЛЬНІ АНТЕНИ 351 KB
  ЛЕКЦІЯ №7 з навчальної дисципліни ПРИКЛАДНІ ПИТАННЯ АНТЕННИХ ПРИСТРОЇВ ТЕМА 3: Активні антени. ЗАНЯТТЯ 1: Активні передавальні антени. 1. НАВЧАЛЬНІ ПИТАННЯ Загальні відомості про активні передавальні антени. Ант...
18080. АКТИВНІ ПРИЙМАЛЬНІ АНТЕНИ 408.5 KB
  PAGE 32 ЛЕКЦІЯ №8 з навчальної дисципліни ПРИКЛАДНІ ПИТАННЯ АНТЕННИХ ПРИСТРОЇВ для студентів 5 курсу ТЕМА 3: Активні антени. ЗАНЯТТЯ 2: Активні прИЙМАльні антени. 1. НАВЧАЛЬНІ ПИТАННЯ Загальні відомості про активні приймальні ан...
18081. АНТЕНИ ТА ЕЛЕКТРОМАГНІТНА СУМІСНІСТЬ (ЕМС) 384 KB
  ЛЕКЦІЯ №10 з навчальної дисципліни ПРИКЛАДНІ ПИТАННЯ АНТЕННИХ ПРИСТРОЇВ ТЕМА 4: Антени та ЕМС. Моделювання та проектування антеннофідерних пристроїв ЗАНЯТТЯ 1: Антени та електромагнітна сумісність ЕМС 1. НАВЧАЛЬНІ ПИТАННЯ ...
18082. Работа со строками в Java 311.5 KB
  Лабораторная работа 5 Работа со строками в Java. Цель работы Целью работы является приобретение навыков программирования с использованием строк языка Java. Состав рабочего места. Оборудование: IBMсовместимый персональный компьютер ПК. Программное...
18083. Программирование апплетов в Java 364 KB
  Лабораторная работа 303 Программирование апплетов в Java 1. Цель работы Целью работы является приобретение навыков программирования апплетов Java с использованием средств AWT. 2. Состав рабочего места 2.1. Оборудование: IBMсовместимый персональный компьютер ПК. ...