Invest-currency.ru

Как обезопасить себя в кризис?
1 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

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

Квадратичное программирование

Задачи квадратичного программирования (КП) имеют место, если целевая функция – сумма линейной и квадратичной форм, а все условия линейные.

Например, в задаче с двумя переменными целевая квадратичная функция записывается следующим образом:

линейная форма квадратичная форма

В векторной форме она принимает вид

.

Обобщая на случай многих переменных, получаем:

Матрица С – квадратная, диагонально-симметричная (Cij=Cji).

В целом задача квадратичного программирования ставится в виде:

(8.10)

; (8.11)

. (8.12)

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

Свойства функции определяются матрицей С.Для вогнутости функции необходимо, чтобы матрицаСбыла отрицательно определенной (строгая вогнутость) или отрицательно полуопределенной. Матрица С отрицательно определенная, если для всех ненулевых X справедливо Х T СХ T СХ £ 0. В случае минимизации целевая функция должна быть выпуклой, что имеет место при положительно определенной или положительно полуопределенной матрице С. Практически определить свойство квадратичной функции можно с помощью достаточных условий экстремума: если функция в стационарной точке имеет максимум, она вогнутая, а если минимум, то выпуклая.

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

Для того чтобы вектор Х* являлся решением задачи (8.10)-(8.12), необходимо и достаточно существования таких неотрицательных m-мерных векторов W и L и неотрицательного n-мерного вектора V, которые удовлетворяют следующей системе уравнений:

D + C×X * -A T ×L + V = 0, (8.13)

B — A×X * — W = 0, (8.14)

Покажем, что теорема выводится из условий Куна-Таккера. Функция Лагранжа для рассматриваемой задачи имеет вид

.

Записываем условия (8.5):

.

Введя в это неравенство неотрицательный вектор дополнительных переменных V, получаем (8.13). (8.14) – это исходное условие задачи после приведения его к равенству вводом неотрицательного вектора дополнительных переменных W. Очевидно. что производная , когда дополнительная переменная V>0 и , когда V=0. Таким образом, V играет роль индикатора производной. Поэтому условие дополняющей нежесткости (8.6) принимает вид (8.15). Аналогична взаимосвязь вектора W с производной F по L, и отсюда имеем второе условие дополняющей нежесткости (8.16).

Система уравнений (8.13)-(8.16) – нелинейная, так как нелинейны (8.15) и (8.16). Она содержит (m + n + 2) уравнений и 2×(m + n) неизвестных X*, L, V и W.

Так как и векторы V и X неотрицательны, из (8.15) следует, что по крайней мере n переменных из vj и xj равны 0. Аналогично из (8.16) вытекает, что равны нулю не менее m переменных из wi и li. Таким образом, в решении системы (8.13)-(8.14) положительными могут быть не более (m + n) переменных. Это свойство системы дает ключ к решению.

Действительно, линейная система (8.13), (8.14) содержит n+m уравнений и 2(n + m) неизвестных. Но известно, что в искомом решении число положительных переменных не превышает (m + n). Следовательно, это допустимое базисное решение (опорный план) системы (8.13), (8.14). Поэтому искать решение задачи КП нужно только среди опорных планов этой системы. Такие решения находятся методами линейного программирования. Опорный план системы (8.13), (8.14), удовлетво­ряющий условиям (8.15), (8.16), будет оптимальным решением задачи КП.

Перепишем уравнения (8.13), (8.14) в обычном виде:

(8.17)

Если вектор D – неположительный, а вектор B – неотрицательный, то начальное базисное решение V=-D, W=B удовлетворяет условиям (8.15), (8.16) и, значит, является оптимальным решением задачи КП. Однако, как правило, вектор D имеет положительные компоненты и такое начальное решение оказывается недопустимым. В этом случае, ориентируясь на использование прямого симплекс-метода, строится искусственное начальное решение: в уравнения (8.17) с отрицательной правой частью вводятся искусственные переменные yk и они вместе с неотрицательными vj и wi образуют базисное решение. В качестве критерия линейной задачи принимается сумма искусственных переменных:

Для выполнения условий дополняющей нежесткости (8.15)-(8.16) алгоритм симплекс-метода дополняется правилом ограниченного ввода:

если в базисном решении имеется vj, то не может вводиться xj (с тем жеиндексом) и наоборот;

если в базисном решении имеется wi, то не может вводиться li (с тем жеиндексом) и наоборот.

Иначе говоря, в базисном решении не могут находиться одновременно переменные v, x (w, l) с одинаковыми индексами. Если по оценкам претендентом на ввод является переменная, которую согласно правилу нельзя вводить, в базисное решение вводится другая переменная с положительной оценкой.

Признаком выполнения условий теоремы (8.13)-(8.16) и, следовательно, оптимальности решения задачи КП является равенство нулю всех искусственных переменных или Lиск=0.

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

Пример 8.2. Найти решение следующей задачи КП:

Перепише целевую функцию в векторной форме:

По матрице С (гессиану) проверяем достаточные условия: D1=-4 0. Значит, f имеет максимум и строго вогнутая.

Записываем первую систему уравнений (8.17):

Для образования начального базисного решения вводим в первую систему искусственные переменные y1 и y2:

Линейное решение задачи квадратичного программирования Текст научной статьи по специальности «Математика»

Аннотация научной статьи по математике, автор научной работы — Татаренко С. И.

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

Похожие темы научных работ по математике , автор научной работы — Татаренко С. И.

Текст научной работы на тему «Линейное решение задачи квадратичного программирования»

УДК 519.853.3 Дата подачи статьи: 07.05.2014

ЛИНЕЙНОЕ РЕШЕНИЕ ЗАДАЧИ КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ

С.И. Татаренко, к.т.н., доцент (Тамбовский государственный технический университет, ул. Советская, 106, г. Тамбов, 392000, Россия, srgiv@mail.ahp.tstu.ru)

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

Читать еще:  Идентификатор переменной паскаль

Ключевые слова: математическое программирование, оптимизация, нелинейное программирование, квадратичная задача.

LINEAR SOLUTION FOR QUADRATIC PROGRAMMING PROBLEMS Tatarenko S.I., Ph.D. (Engineering), Associate Professor (Tambov State Technical University, Sovetskaya St. 106, Tambov, 392000, Russian Federation, srgiv@mail.ahp.tstu.ru) Аbstract. The work describes a quadric maximum search method on a polyhedral restrictions set. It is based on solving linear equations systems when their dimension no higher than a number of objective function variables. In the beginning, a quadric matrix is worked reduced to a normal view using orthogonal transformations and scaling. Then, using variables replacement, the initial problem is reduced to a problem of searching the minimum distance between an unconditional extremum point and a polyhedral restrictions set. Perpendiculars to different dimension polyhedron sides are constructed to measure the distance. The special order of sides search is developed to reduce the number of studied sides. The subject to research includes only the sides containing the top which is the closest to an unconditional extremum point and seen from this point. If there is not only one closest top, then the side containing all these tops and the sides of lower dimension having not less than two shared closest tops with the first side are investigated.

Keywords: mathematical programming, optimization, nonlinear programming, quadratic problem.

Для решения задачи квадратичного программирования разработаны различные приближенные методы и варианты квадратичного симплекс-метода, основанные на методе Лагранжа [1—4]. Но приближенные методы не способны дать точное решение, а симплекс-метод требует введения дополнительных переменных и учета нелинейных условий дополнительной нежесткости, что услож-

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

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

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

Пусть имеется задача квадратичного программирования с целевой функцией от n переменных и замкнутой областью ограничений из m линейных неравенств:

z(X) = XTAX + BX ^ max, (1)

CX > D; X > 0, где X = (x, x2, . xn)T — вектор переменных; A -матрица квадратичной формы размерности nxn; B = (bb b2, . bn) — вектор линейной формы; D = (d1, d2, . dm)T — вектор констант ограничений; C — матрица коэффициентов ограничений размерности mxn.

Пусть матрица A невырождена, отрицательно определена и точка решения задачи безусловного максимума X* = — (A+AT)-1BT = -A-1BT /2 находится вне области ограничений. Тогда решение задачи (1) следует искать на границе области ограничений [6].

Первым этапом решения является масштабирование задачи, заключающееся в замене переменных и приведении матрицы квадратичной формы к нормальному виду. Сначала методом ортогональных преобразований [7, 8] приведем матрицу квадратичной формы A к каноническому виду. Обозначим матрицу этого преобразования S, тогда в результате преобразований матрица F = STAS станет диагональной, причем, по закону инерции квадратичной формы, все ее диагональные элементы будут отрицательны и равны собственным числам матрицы A. Затем приведем квадратичную форму к нормальному виду с помощью масштабирующей диагональной матрицы W:

в итоге матрица квадратичной формы превратится в отрицательную единичную матрицу WTSTASW= =-Е, а алгебраическая форма целевой функции после замены переменных X=SWY примет вид z(Y)=:Z(->>I2+ЛyI)^.max, /е[1, п], где P=BSW, Y= =W-1S-1X.

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

z(Y) = Z(y, -p^^min, /е [1, n ].

Поскольку Y* = W-1S-1X*

нальна, то есть S 1 = ST,

матрица S ортого-матрица W-1 диагональная то W-1S-1A-1S-1W-1 = -Е, следовательно, Y* = Рт/2 и полученная целевая функция представляет собой квадрат расстояния между текущей точкой Y и точкой безусловного экстремума Y , а поверхности равного уровня являются концентрическими гиперсферами с центром в точке Y .

Объединим ограничения неравенства с ограничениями неотрицательности переменных и получим систему из 1=п+т ограничений:

Таким образом, задача (1) превратилась в задачу (2), (3), представляющую собой задачу поиска точки границы многогранного множества и, описываемого неравенствами (3), ближайшей к точке безусловного экстремума Y = Рт/2.

Вторым этапом решения является исследование элементов границы области и и отыскание ближайшей точки методами аналитической геометрии. Ограничения (3) образуют в п-мерном пространстве выпуклый многогранник (полиэдр), граница которого состоит из вершин и граней различных размерностей от 1 до п—1 [9]. Разделим ограничения задачи на две группы. В одну группу включим ограничения, которым удовлетворяет точка безусловного экстремума GIY > ц,, грани множества и размерности п-1, расположенные на соответствующих опорных гиперплоскостях, будут невидимыми из точки Y . Здесь GI — строка матрицы G; ц, — элемент вектора констант ограничений Q. В другую группу включим ограничения, которым не удовлетворяет точка Y , то есть для которых GIY |Y -VI, дальнейшее исследование грани не выполняется. Если г = |Y -VI, решением задачи является вершина V. Если г д,;

V/ : GI■V = д, является общим уравнением прямой линии в п-мерном пространстве. Направляющий вектор Т=(и1, и2, • . ип) линии ребра можно найти из условий ортогональности его ко всем нормальным векторам плоскостей ограничений, образующих ребро, то есть равенства нулю п-1 скалярных произведений: п-1 = 0; /е[1, 1].

Для решения этой системы одну из координат вектора Т можно задать произвольно.

Читать еще:  Программирование дифференциальных уравнений

Поскольку вершина V=(v1, у2, •. уп) принадлежит исследуемому ребру, координаты точки пересечения линии ребра и перпендикуляра к ребру, опущенному из точки Y , определяются из системы уравнений, включающей канонические уравнения линии ребра, проходящей через точку V, и уравнения п-1-мерной плоскости с нормальным вектором Т, содержащей точку Y :

(У1 — V!) / ¿1 =(У2 — V2) / ¿2 = ••• = (Уп — Vn) / ¿п;

Если решение этой системы удовлетворяет всем ограничениям (3), оно является решением задачи (2), (3); если удовлетворены не все ограничения, перпендикуляр к ребру попадает на продолжение линии ребра и следует исследовать другие ребра.

Грани размерности от k=n-2 до £=2 исследуются с помощью дополнительных ортогональных гиперплоскостей размерности от п-1 до п-£+1.

Гиперплоскость размерности п-£ является совместным решением £ уравнений из системы ограничений (3), причем, как и для грани размерности п-1, ограничения должны быть активными для V и хотя бы одно должно быть из числа видимых из Y*: £ ^У=д,; /е[1, /]; 3/ : GIY *

Задача квадратического программирования

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

В качестве основной в квадратичном программировании рассматривается задача минимизации функции

,

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

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

Функция Лагранжа в данном случае имеет вид:

.

Найдем стационарные точки функции Лагранжа:

С учетом ориентации и применяя теорему Куна-Таккера:

(10.1)

(10.2)

Преобразуем систему (10.1) к системе уравнений:

Тогда систему уравнений (10.2) можно записать в виде:

. (10.3)

Чтобы учесть условие (10.3) при решении ЗНП надо следить за тем, чтобы среди базисных переменных не было u и x с одним и тем же индексом, аналогично λ и v.

Далее задача решается методом искусственного базиса.

Задача.Минимизировать функцию при ограничениях:

Составим функцию Лагранжа:

.

Составим локальные условия Куна-Таккера:

Преобразуем полученную систему ограничений к допустимому виду канонической формы:

Далее решаем задачу методом искусственного базиса, учитывая условие (10.3):

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

.

Ответ: , .

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

Тема 11. Метод динамического программирования

1. Общая постановка задачи динамического программирования (ЗДП)

2. Принцип оптимальности. Функциональные уравнения Беллмана

3. Задача оптимального распределения инвестиций

4. Задача о замене оборудования

Дата добавления: 2014-12-03 ; просмотров: 13 ; Нарушение авторских прав

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

Дипломная работа содержит 78 страниц, 2 приложения, 1 рисунок.

Список ключевых слов: программирование, квадратичное, параметрическое.

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

TOC o «1-3» 1. Введение. GOTOBUTTON _Toc379719392 4

2.Аналитический обзор. GOTOBUTTON _Toc379719393 9

3. Теоретическая часть. GOTOBUTTON _Toc379719394 11

3. Задача квадратичного программирования (непараметрический случай). GOTOBUTTON _Toc379719395 11

3.1 Постановка задачи. GOTOBUTTON _Toc379719396 11

3.2 Условия оптимальности в задаче (3.2). GOTOBUTTON _Toc379719397 12

3.3. Базис задачи квадратичного программирования. Оптимальный и невырожденный базисы. GOTOBUTTON _Toc379719398 15

3.4. Метод субоптимизации на многообразиях. Выпуклый случай. GOTOBUTTON _Toc379719399 18

3.5 Метод субоптимизации на многообразиях. Задача квадратичного программирования. GOTOBUTTON _Toc379719400 26

3.6. Метод субоптимизации на многообразиях в задаче квадратичного программирования. Теоретическое обоснование. GOTOBUTTON _Toc379719401 34

3.7. Вычислительная схема алгоритма субоптимизации для задачи квадратичного программирования. GOTOBUTTON _Toc379719402 44

3.8. Некоторые особенности вычислительной схемы метода субоптимизации на многообразиях для задачи квадратичного программирования. GOTOBUTTON _Toc379719409 47

4. Задача квадратичного программирования с параметром в правых частях ограничений. GOTOBUTTON _Toc379719411 51

4.1 Постановка задачи. GOTOBUTTON _Toc379719412 51

4.2 Некоторые свойства решения параметрической задачи квадратичного программирования. GOTOBUTTON _Toc379719413 51

4.3 Применение метода субоптимизации на многообразиях к решению параметрической задачи квадратичного программирования. GOTOBUTTON _Toc379719414 54

5.Экономическая часть. GOTOBUTTON _Toc379719415 56

6.Библиография. GOTOBUTTON _Toc379719416 63

7.Приложение 1. 65

8.ПРиложение 2. 67

1. Введение

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

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

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

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

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

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

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

Читать еще:  Рнр язык программирования

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

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

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

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

Показано, что такое разбиение состоит из конечного числа отрезков, и конечного числа точек переключения траектории решения.

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

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

Составлена и отлажена программа на языке С++, функционирующая в среде операционных систем UNIX (AIX, Solaris) а также Microsoft Windows, реализующая описанные алгоритмы. Указанная программа применена к решению задачи о поиске оптимальных инвестиций в задаче о портфеле ценных бумаг, данные решения и текст программы приведен в приложениях.

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

2.Аналитический обзор

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

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

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

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

3. Теоретическая часть

3. Задача квадратичного программирования (непараметрический случай).

3.1 Постановка задачи:

Задачей квадратичного программирования будем называть задачу следующего вида:

Последовательное квадратичное программирование

Последовательное квадратичное программирование (англ. Sequential quadratic programming (SQP)) — один из наиболее распространённых и эффективных оптимизационных алгоритмов общего назначения [1] , основной идеей которого является последовательное решение задач квадратичного программирования, аппроксимирующих данную задачу оптимизации. Для оптимизационных задач без ограничений алгоритм SQP преобразуется в метод Ньютона поиска точки, в которой градиент целевой функции обращается в ноль. Для решения исходной задачи с ограничениями-равенствами метод SQP преобразуется в специальную реализацию ньютоновских методов решения системы Лагранжа.

Содержание

Основные сведения

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

Лагранжиан задачи примет следующий вид:

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

На итерации основного алгоритма определяются соответствующие направления поиска как решение следующей подзадачи квадратичного программирования:

См. также

Примечания

  1. Трифонов А. Г. Optimization Toolbox 2.2 Руководство пользователя // Softline Co.

Литература

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

Wikimedia Foundation . 2010 .

Смотреть что такое «Последовательное квадратичное программирование» в других словарях:

Оптимизация (математика) — У этого термина существуют и другие значения, см. Оптимизация. Оптимизация в математике, информатике и исследовании операций задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного … Википедия

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

Симплекс-метод — Не путать с «симплекс методом» методом оптимизации произвольной функции. См. Метод Нелдера Мида Симплекс метод алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в… … Википедия

Градиентные методы — численные методы решения с помощью градиента задач, сводящихся к нахождению экстремумов функции. Содержание 1 Постановка задачи решения системы уравнений в терминах методов о … Википедия

Генетический алгоритм — (англ. genetic algorithm) это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих… … Википедия

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

Метод сопряжённых градиентов — Метод сопряженных градиентов метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в минимум находится за шагов. Содержание 1 Основные понятия … Википедия

Метод золотого сечения — метод поиска значений действительно значной функции на заданном отрезке. В основе метода лежит принцип деления в пропорциях золотого сечения. Наиболее широко известен как метод поиска экстремума в решении задач оптимизации Содержание 1 Описание… … Википедия

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

Алгоритм Гомори — алгоритм, который используется для решения полностью целочисленных задач линейного программирования. Алгоритм включает в себя: Решение задачи одним из методов группы симплекс методов или группы методов внутренней точки без учёта требования… … Википедия

Ссылка на основную публикацию
ВсеИнструменты 220 Вольт
Adblock
detector