Задачи по оптимизации решаются различными математическими методами, в основе которых лежат теория вероятностей и математическая статистика, линейная алгебра, нелинейное программирование и, в частности, его простейшая форма — квадратичное программирование, а также стохастическое и динамическое программирования и, наконец, матричное исчисление. [c.18]
Нелинейное программирование - обобщение случая линейного программирования, когда критерий — нелинейная функция решений с нелинейными ограничениями. Общих методов решения здесь не существует. Более или менее приемлемые способы решения имеются для случая, когда функция критерия К и ограничения — вогнутые функции и когда К — квадратичная функция решений, а ограничения линейны (квадратичное программирование). [c.308]
Так, в работе [9] учитывались нелинейная зависимость затрат от района-поставщика, глубины переработки, технологии и т. п. Модель представлялась в виде задачи квадратичного программирования, которая решалась методом последовательных приближений. [c.95]
Проблема нахождения этих эффективных портфелей во многом сходна с проблемой, с которой мы столкнулись в разделе 6—4. Там мы хотели распределить ограниченный объем капитала среди группы проектов, чтобы получить наиболее высокую совокупную чистую приведенную стоимость. Здесь мы также намерены распределить ограниченный объем капитала, чтобы получить наиболее высокую ожидаемую доходность при данном стандартном отклонении. В принципе обе задачи могут быть решены методом подбора - но только в принципе. Чтобы решить проблему ограниченности капитала на практике, мы можем прибегнуть к методам линейного программирования для выбора портфелей мы можем применить вариант линейного программирования, известный как квадратичное программирование. Если мы вычислим ожидаемую доходность и стандартное отклонение для каждой акции на рисунке 8-5, а также коэффициент корреляции между каждой парой акций, тогда мы сможем использовать стандартную компьютерную программу квадратичного программирования для определения группы эффективных портфелей. [c.171]
Из задач выпуклого программирования подробно разработаны задачи квадратичного программирования, в которых требуется найти максимум (или минимум) квадратичной функции при условии, что ее переменные удовлетворяют некоторой системе линейных уравнений. [c.104]
После того как были оценены ожидаемые доходности, дисперсии и ковариаций, необходимо ввести эти значения в компьютер. Затем компьютер может приступить к определению эффективного множества, используя алгоритм квадратичного программирования 18. После этого оптимальный портфель инвестора может быть подобран с помощью определения точки касания кривых безразличия инвестора с эффективным множеством. [c.228]
Для определения необходимости пересмотров в отношении тех или иных бумаг приходится применять сложные методы (например, квадратичное программирование) с тем, чтобы сравнить необходимые затраты и возможные выгоды. К счастью, совершенствование методик и резкое сокращение стоимости компьютерных работ сделали экономически доступными такие пересмотры для многих инвестиционных менеджеров. [c.860]
Переменными в этой усредненной задаче является вектор движущих сил X. Так как задача (2.26), (2.27) выпуклая, то ее решение соответствует постоянству искомых переменных (см. гл.9), а значит, определение X сводится к решению простой задачи квадратичного программирования. [c.57]
Существуют и другие частные разделы нелинейного программирования, для которых разработаны точные методы их решения. Это — выпуклое программирование, частный случай которого — квадратичное программирование. [c.116]
В этом случае область возможных значений коэффициентов регрессии должна быть сужена за счет наложения на них ограничения неотрицательности, что может быть достигнуто путем решения следующей задачи квадратичного программирования [c.24]
При ij=0, /=1, --., , задача сводится к задаче квадратичного программирования [c.78]
В общем случае задача представляет собой задачу дробно-квадратичного программирования. Методы анализа таких задач могут быть основаны, например, на результатах работ [79, 96]. [c.78]
Стохастический аналог задачи квадратичного программирования [c.114]
Рассмотрим стохастический аналог общей задачи квадратичного программирования со строго выпуклой целевой функцией и линейными ограничениями [351] [c.114]
Двухэтапную задачу, в которой все случайные компоненты вектора Ь(и) имеют непрерывную функцию распределения, можно приближенно свести к задаче квадратичного программирования. Для этого достаточно заменить случайные величины взвешенными суммами равномерно распределенных случайных величин [c.179]
Естественно, что сведение задачи (3.21) — (3.25) к задаче квадратичного программирования целесообразно лишь в том случае, когда функции распределения случайных величин bi могут быть аппроксимированы ступенчатыми функциями с небольшим числом ступеней. [c.180]
Пусть /С — выпуклый многогранник /С= д Лл й . В этом случае вычисление оператора проектирования сводится к решению задачи квадратичного программирования [c.184]
Алгоритм решения Л-задачи, приведенный в предыдущем параграфе, сводится в нашем случае к решению последовательности задач. параметрического квадратичного программирования вида [c.233]
Юдин Д. Б. Стохастическое квадратичное программирование. — Изв. АН СССР, Техническая кибернетика , 1969, № 3. [c.394]
Далее, решение задачи квадратичного программирования определяет вариацию управления, т. е. набор чисел 8м +1/, , ЪТ. На функцию Ъа(1) было наложено ограничение " ) 8н (t) .
Решение задачи методом проекции градиента. Задачи 1 и 2 были решены методом проекции градиента, подробно описанным в 18. Схема вычислений в этом случае в основном совпадает со схемой вычислений методом последовательной линеаризации. Основное отличие в том, что вариация управления находится решением задачи квадратичного программирования. Задачи решались при тех же управляющих функциях и при тех же значениях входящих в них параметров, что и [c.323]
Эксперимент. Были проведены расчеты с целью выяснить роль того основного элемента, который отличает используемый в расчетах алгоритм решения задачи квадратичного программирования от классического алгоритма строго выпуклого программирования. Речь идет о промежуточной минимизации x (см. 49). Для этого был проведен расчет по той же самой программе и в тех же условиях, что и расчет 4, с единственным изменением в программе решения задачи квадратичного программирования был отключен блок минимизации x , т. е. эта задача решалась стандартным процессом строго выпуклого программирования, сходящимся, как известно, со скоростью геометрической прогрессии. Результат оказался следующим затратив в 1,5 раза больше времени, чем этого потребовал весь расчет 4, удалось выполнить всего 6 итераций. К тому же эти 6 итераций относятся к самому легкому этапу решения задачи варьируется взятая произвольно управляющая функция и ( )=0,1, дополнительные условия F0 а и х1 (T)=R3 грубо нарушены задача квадратичного программирования не имеет решения и при использовании алгоритма 49 это быстро выясняется. Кроме [c.328]
Разумеется, в расчетах е > 0, его назначение и регулирование обсуждаются ниже. Заметим, что в задаче (12), (13) границы s , s (t) не совпадают с s , s (t) в (8). При их вычислении, кроме обычных соображений о малости 8и и выполнении условия 0 и+8цз 7, используется еще одно. Задача (12), (13) есть задача квадратичного программирования, однако в расчетах она решалась итерационным методом, причем на каждой итерации решалась задача линейного программирования (являющаяся линеаризацией (12)) [c.351]
Предостережение. Опыт решения задач оптимального управления методом проекции градиента еще не очень велик, и некоторые детали не совсем ясны. Автор хотел бы предупредить читателя о"возможных осложнениях. Прежде всего, не очень ясен вопрос о назначении величины rj, задающей требуемую относительную точность решения по значению минимизируемой формы (1). В задаче линейного программирования (при S= o) форма (1) имеет простой содержательный смысл — это значение F0 [Su ( )], и назначение ] =0,1 (0,2 или 0,05, если угодно) в особых разъяснениях не нуждается. В задаче квадратичного программирования форма (1) уже не имеет такого простого значения, часто ее значение [c.458]
Поляк Б. Т. Об одном методе решения задач линейного и квадратичного программирования большого объема. — В сб. Вычислительные методы и программирование, М. Изд-во МГУ, 1969, вып. 12. [c.481]
КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ — раздел выпуклого программирования, при котором целевая функция представляет собой многочлен второй степени, а ограничения линейны. [c.120]
Дополнительно в данную модель необходимо добавить ограничения (11.30)— 11.33). Тогда будем иметь задачу квадратичного программирования, решив которую известными методами, получим оптимальный план выпуска товаров и их цены. [c.230]
Как уже обсуждалось в данной главе, концепции эффективного множества н оптимального портфеля инвестора являются основополагающими в современной инвестиционной теории. Но как инвестор может реально оценить эффективное множество и выбрать оптимальный портфель. 3 8 начале 50-х гадов Гарри Марковшд описал решение данных проблем. Используя математический метод, известный как квадратичное программирование, инвестор может обработать ожидаемые доходности, стандартные отклонения и ковариации для определения эффективного множества. (См. приложение А к данной главе.) Имея оценку своих кривых безразличия, отражающую их индивидуальный допустимый риск (см. гл. 24), он может затем выбрать портфель из эффективного множества. [c.199]
Для того чтобы определить состав портфелей из эффективного множества, инвестор должен решить задачу квадратичного программирования . См. книгу Марковича Portfolio Sele tion (ссыл-ка в конце главы), в частности с. 176—185. [c.228]
Квадратичная форма 140 Квадратичная функция 141 Квадратичная целевая функция 385 Квадратичное программирование 141 Квадратная матрица 141 "Квазиденьги" 74 [c.468]
В настоящей главе обсуждаются методы построения решающих правил для одноэтапных задач стохастического программирования, а для отдельных моделей приводятся и явные выражения для решающих правил. В 1 рассматриваются частные модели первого класса, в которых предполагается, что решающие правила — линейные функции случайных составляющих условий задачи. Вычисление параметров решающих правил сводится к задачам выпуклого программирования. Параграф 2 посвящен изучению. М-модели с вероятностным ограничением общего вида. Относительно решающего правила л (со) не делается никаких предположений, кроме того, что л (со)—измеримая вектор-функция на множестве X произвольной структуры, на котором она определена. В 3 метод построения решающих правил из предыдущего параграфа обобщается на М-модель с конечнозначным ограничением — с условием, ограничивающим математическое ожидание случайной функции от х, принимающей конечное число значений. Таким условием может быть аппроксимировано любое статистическое ограничение. В 4 построены решающие правила (точнее, решающие таблицы) дляч Р-мо-дели с вероятностными ограничениями общего вида. В 5 рассматривается стохастическая задача со смешанными ограничениями. Эта модель отличается от задачи 4 дополнительными условиями, которые могут существенно изменить структуру решения. В 6—8 построены решающие правила для одноэтапных задач стохастического программирования со статистическими ограничениями достаточно общего вида. Модель, изученная в 6, представляет собой стохастический аналог общей задачи линейного программирования с двухсторонними ограничениями. Модель из 7 — стохастический аналог общей задачи квадратичного программирования. Модель, исследованная в 8, является стохастическим аналогом частной задачи выпуклого программирования с квадратичной целевой функцией и квадратичными ограничениями. Заключительный параграф главы ( 9) посвящен итеративным методам построения решающих правил одноэтапных задач стохастического программирования. [c.84]
При наличии статистических характеристик Мц случайных параметров условий задачи простая задача (7.11) квадратичного программирования решается без труда. В случае, когда значения Mi заранее не известны, оптимальные значения Я г вычисляются по последовательным реализациям случайной величины gtfj с помощью итерационной процедуры стохастической аппроксимации, учитывающей ограничения Яг О. Оптимальный план х исходной задачи вычисляется через составляющие А,, решения двойственной задачи (7.11) по формуле [c.115]
Для решения задачи предлагается сходящийся итеративный метод. На каждом шаге метода решается конечно-мерная задача квадратичного программирования для выбора возможного направления, вдоль которого можно улучшить значение целевого функционала fo(x), и выбирается рациональная величина шага. В алгоритме используется так называемый antizigzaging прием, исключающий заедание вычислительного процесса и обеспечивающий точность вычислений. Предлагаемый метод представляет собой естественное обобщение метода возможных направлений, разработанного в [126] для решения задач линейного и выпуклого программирования. [c.123]
Итеративная процедур-a продолжается до тех пор, пока мы не придем в некоторую точку л й) с соответствующим значением 8h+i, при которых задача квадратичного программирования (9.9) — (9.11) приводит к оптимальному значению ith+i квадратичной формы (9.9), удовлетворяющему требованию Uh+n 6k+i. Здесь возможны два случая ft+i>0 и Mf +i = 0. Пусть Uft+i>0. Тогда полагаем 6 fe+i = 6/t-H/2 и повторяем (k + + 1)-ю итерацию для б ь+ь находим 4+i и x -h+ и продолжаем вычисления, считая x(k+i) исходной точкой, а б й+i соответствующим значением antizigzaging — параметра. Если же +1=0, то для определения направления спуска заменяем множество Г(х№ б л+i) множеством [c.125]
Используя класс кусочно постоянных управляющих функций на сетке с N малыми временными интервалами, покрывающими [О, Т], приходим к следующей задаче квадратичного программирования в конечномерном пространстве [c.208]
Метод сопряженных градиентов использовался автором не только в серийных расчетах задач оптимального управления (в качестве одного из блоков решения задачи линейного или квадратичного программирования), но и в методических расчетах в условиях сравнительно высокой размерности. В частности, в 48 представлены результаты решения задачи линейного программирования итерационным методом, включающим и метод сопряженных градиентов. Видно, что сходимость метода не соответствует теоретическим предсказаниям, что приводит к определенному (и заметному) перерасходу машинного времени. Были проведены и специальные эксперименты по минимизации формы (Вх, Вх) (G=B B) со случайной матрицей В размером 100x100. Использовалась схема типа III. Алгоритм не давал нужной точности после 300 — 400 шагов. Для уменьшения влияния ошибок округления была применена комбинация схем II и III четыре итерации проводились с вычислением В по схеме III, а каждая пятая — по более громоздкой формуле схемы II. Это привело к улучшению сходимости (выигрыш можно оценить числом л 2), но проблемы не решило. [c.477]
Смотреть страницы где упоминается термин Квадратичное программирование
: [c.1070] [c.55] [c.141] [c.42] [c.177] [c.178] [c.184] [c.396] [c.288] [c.329] [c.457] [c.75] [c.159]Экономико-математический словарь Изд.5 (2003) -- [ c.141 ]
Популярный экономико-математический словарь (1973) -- [ c.120 ]