| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Поиск минимума при ограничениях |
| Автор: kamre 24.3.2006, 17:54 |
| Задача: есть нелинейная система уравнений и целевая фунция, нужно найти ее минимум на решениях системы. Особенности задачи таковы: размер системы нелинейных уравнений очень большой (>= 1000 уравнений), система почти всегда недоопределенная (переменных больше, чем уравнений), сами уравнения обычно квадратичные и не очень сложные, т.е. можно считать, что в каждое уравнение входит не более k переменных (k<=10 - типичный случай), целевая функция очень проста и имеет вид: (x1-x10)^2 + .. + (xk-xk0)^2, где xi0 - константы и в типичном случае k <= 10. Какие есть способы решения такой задачи? И какие из них будут наиболее эффективными, учитывая особенности задачи? |
| Автор: Reptor 24.3.2006, 20:29 |
| Смотри нелинейное программирование. Вообще такие задачи (нелинейные) решаются с помощью диф. уравнений. |
| Автор: podval 24.3.2006, 20:35 |
| Попробуй взять MATLAB и решить хотя бы частный пример. Там можно задать вывод всей диагностической информации по ходу решения. По ней будет видно, какой алгоритм выбирается (исходя из размерности). Для больших размерностей там могут использоваться сопряженные градиенты, последовательное квадратичное программирование (SQP) и еще что-то. |
| Автор: kamre 26.3.2006, 12:29 | ||
А можно поподробнее, пожалуйста, про то, как задачи минимизации при ограничениях решаются с помощью диф. уравнений? Добавлено @ 12:37 podval, честно говоря в MatLab я не силен. Идея ваша показалась интресной, попробую поставить и поразбираться. А все-таки, как вы это себе представляете ввод системы из 1000 уравнений в MatLab? Или это можно будет делать через простой текстовый файл (собственно все данные о системе и целевой функции хранятся у меня в файле, но в своем тесктовом формате)? |
| Автор: podval 27.3.2006, 10:31 |
| Естественно, ввод через файл. В Матлабе всё делается в матричном виде и он справится с размерностями более 1000. Ничего сложного там нет, язык - почти что С. |
| Автор: KarboFos 27.3.2006, 23:01 |
| а это не методы оптимизации нужны случайно ? там функция Лагранжа и все такое ? |
| Автор: kamre 27.3.2006, 23:27 | ||
Вообще, честно говоря, метод с функцией Лагранжа и решением квадратной системы размера (n+m) методом ньютона уже реализован. Просто при этом есть несколько проблем. Первая - эффективность, все таки методом ньютона эта система решается очень долго (неприемлимо долго) для больших задач. Второе - это на самом деле метод поиска экстремума, но ни как не минимума, в итоге есть случаи, когда вместо минимума получается максимум, или вообще не понять что. |
| Автор: kamre 31.3.2006, 09:36 | ||||
podval, опять обращаюсь к вам. Установил MatLab7, более или менее разобрался с m-файлами. У меня теперь есть вопросы по запуску оптимизации с ограничениями. Создаю файл с целевой функцией:
"..." - это целевая функция из моего файла. Правильно ли я понимаю (после прочтения help), что при такой реализации MatLab в методах оптимизации не использует аналитические производные функции myObj? Аналогичная ситуация с ограничениями. Файл:
"...,...,..."-уравнения (обычно квадратичные) из моего файла. В этом случае также получается, что MatLab при оптимизации не использует аналитические производные для этих уравнений? Такие вопросы появились от того, что MatLab7 не смог решить мою задачу (3 m-файла в attachment, запускать myOpt). Что можно сделать, чтобы в процессе оптимизации использовались аналитические производные в myObj и myConstr (если они уже не используются)? Можно ли их как-то автоматически, с помощью MatLab, добавить в функции myObj и myConstr? |