Задача: есть нелинейная система уравнений и целевая фунция, нужно найти ее минимум на решениях системы.
Особенности задачи таковы: размер системы нелинейных уравнений очень большой (>= 1000 уравнений), система почти всегда недоопределенная (переменных больше, чем уравнений), сами уравнения обычно квадратичные и не очень сложные, т.е. можно считать, что в каждое уравнение входит не более k переменных (k<=10 - типичный случай), целевая функция очень проста и имеет вид: (x1-x10)^2 + .. + (xk-xk0)^2, где xi0 - константы и в типичном случае k <= 10.
Какие есть способы решения такой задачи? И какие из них будут наиболее эффективными, учитывая особенности задачи?

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

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

А можно поподробнее, пожалуйста, про то, как задачи минимизации при ограничениях решаются с помощью диф. уравнений?
Добавлено @ 12:37
podval, честно говоря в MatLab я не силен. Идея ваша показалась интресной, попробую поставить и поразбираться.
А все-таки, как вы это себе представляете ввод системы из 1000 уравнений в MatLab? Или это можно будет делать через простой текстовый файл (собственно все данные о системе и целевой функции хранятся у меня в файле, но в своем тесктовом формате)?

Естественно, ввод через файл. В Матлабе всё делается в матричном виде и он справится с размерностями более 1000.
Ничего сложного там нет, язык - почти что С.

а это не методы оптимизации нужны случайно ? там функция Лагранжа и все такое ?

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

Это сообщение отредактировал(а) kamre - 31.3.2006, 09:12

podval, опять обращаюсь к вам. Установил MatLab7, более или менее разобрался с m-файлами. У меня теперь есть вопросы по запуску оптимизации с ограничениями. Создаю файл с целевой функцией:

"..." - это целевая функция из моего файла.
Правильно ли я понимаю (после прочтения help), что при такой реализации MatLab в методах оптимизации не использует аналитические производные функции myObj?
Аналогичная ситуация с ограничениями. Файл:

"...,...,..."-уравнения (обычно квадратичные) из моего файла.
В этом случае также получается, что MatLab при оптимизации не использует аналитические производные для этих уравнений?
Такие вопросы появились от того, что MatLab7 не смог решить мою задачу (3 m-файла в attachment, запускать myOpt).
Что можно сделать, чтобы в процессе оптимизации использовались аналитические производные в myObj и myConstr (если они уже не используются)? Можно ли их как-то автоматически, с помощью MatLab, добавить в функции myObj и myConstr?

Присоединённый файл ( Кол-во скачиваний: 1 )
 myMatLabMinimization.zip 2,13 Kb