Квадратичное программирование. Исходники

[Konstantin]

Господа, приветствую вас!

Срочно необходим алгоритм решения задач квадратичного программирования, реализованный на Delphi. Может кто выручит и скинет исходники (или ссылки)?

Заранее спасибо за помощь,
Константин.

[Игорь Акопян]

вроде не 1-ое апреля
помню одно обсуждение - там добазарились до диагонального программирования )

[RoKon]

Ага, про диагональное помню :-) , а штоб квадратичное. Че правда штоли есть?

[LAngel]

Напомните вообще как они решаются?
А то что-то из школьных знаний только слово "дискриминант" осталось...

[Konstantin]

Как вы, наверное, знаете есть линейное (ЛП) и нелинейное (НП) программирование.... Занимаются они нахождением минимума (или максимумма) целевой функции при каких-либо ограничениях... Целевые функции бывают разные: бывают линейные (ЛП), бывают нелинейные (НП). Так вот подклассом класса задач НП являются задачи, где целевая функция является полиномом второго порядка, то есть квадратичной функцией, и называются такие задачи задачами квадратичного программирования.
Задачи ЛП и НП широко применяются в экономике и финансах.
И у меня сейчас как раз такой случай, когда необходима программная реализация решения задачи квадратичного программирования на Delphi, чтобы я с ее помощью мог решать более сложные и прикладные задачи (которые так же необходимо реализовать на Delphi, но это уж я сам).

Очень надеюсь на вашу помощь,
с уважением,
Константин.

[Romeo]

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

[AiK]

Ужас какой. Я видимо отстал от жизни . Может кто-нибудь в нормальных математических терминах изложить суть задачи? В моё время в математике слово программирование не применялось. В любом случае фраза "запрограммировать квадратичное программирование" звучит для меня дико. Хотя автор и постарался сгладить фразу, использовав словосочетание "программная реализация", но суть от этого не изменилась...

[Romeo]

AiK, хочется теории, пожалуйста

Постановка: даны M линейных неравенств от N переменных (M >= N, а чаще всего M >> N). Также есть отдельная функция (линейная или не линейная), от этих же переменных, которая называется целевой функцией. Эту функцию нужно либо минимизировать, либо максимизировать.

В такой постановке задача называется задачей линийного/нелинейного программирования.

В случае двух переменных задача тривиальна и имеет простое графическое решение. Оно сводидится к построению M прямых, каждая из которых разделяет декартову плоскость на две полуплоскости, и установке в начало координат вектора целевой функции. После этого сразу становиться видно в какой точке целевая функция достигнет минимума (максимума) (это одна из точек пересечения прямых либо +-INF в вырожденном случае).

[Konstantin]

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

..........................

Но мне нужен общий случай: когда две и более переменных. И решение не графическое, а аналитическое. Причем реализованное на Delphi. Неужели, этим никто не занимался?

[AiK]

Эту функцию нужно либо минимизировать, либо максимизировать.

У нас это всю жизнь называлось поиском условного экстремума (оптимума), или экстермальной задачей (задачей оптимизации).
Делали мы эту фигню на вычметодах. Ищи в Яндексе по ключевым словам: метод градиентного спуска, метод покоординатного спуска он же метод Гаусса-Зейделя.

З.Ы: прикладники, блин