1. Многомерные задачи оптимизации.

Пусть f(x₁, x₂,…, x_n) – целевая функция. Задача поиска максимума этой функции сводится к минимизации функции - f(x₁, x₂,…, x_n), поэтому будем рассматривать задачу поиска минимума. Наибольшие трудности поиска минимума f(x) возникают, когда размерность n вектора x велика, поэтому важнейшей проблемой является уменьшение размерности вектора целевой функции на этапе построения математической модели. В модели следует сохранить только те x_i, которые сильнее других влияют на изменение целевой функции.

Линиями уровня f(x₁, x₂) называют семейство линий плоскости R², на которых функция принимает постоянное значение.

Неявным уравнением линии уровня является уравнение вида f(x₁, x₂)=с.

Если функция f(x) имеет единственную точку минимума x^*(x₁^*, x₂^*), то функция называется мономодальной и линии уровня имеют следующий вид:

Метод покоординатного спуска

Идея всех методов спуска состоит в том, чтобы из начального приближения точки x⁽⁰⁾=(x₁⁽⁰⁾, x₂⁽⁰⁾,…, x_n⁽⁰⁾) перейти в точку x⁽¹⁾=(x₁⁽¹⁾, x₂⁽¹⁾,…, x_n⁽¹⁾) такую, чтобы f(x⁽⁰⁾)> f(x⁽¹⁾).

Пусть в области D задано нулевое приближение x⁽⁰⁾. Фиксируем значение x₂⁽⁰⁾,x₃⁽⁰⁾,…, x_n⁽⁰⁾ и рассматриваем функцию f(x₁, x₂⁽⁰⁾,…, x_n⁽⁰⁾) как функцию одной переменной x₁. Находим минимум этой функции . Пусть x₁⁽¹⁾ доставляет минимум этой функции. f(x₁⁽¹⁾, x₂⁽⁰⁾,…, x_n⁽⁰⁾)≤ f(x₁⁽⁰⁾, x₂⁽⁰⁾,…, x_n⁽⁰⁾).

Далее фиксируем значения x₃⁽⁰⁾,x₄⁽⁰⁾,…, x_n⁽⁰⁾ и рассматриваем функцию

f(x₁⁽¹⁾, x₂,x₃⁽⁰⁾,…, x_n⁽⁰⁾) как функцию одной переменной x₂ и т.д.

После n шагов получим f(x₁⁽¹⁾, x₂⁽¹⁾,x₃⁽¹⁾,…, x_n⁽¹⁾)≤ f(x₁⁽⁰⁾, x₂⁽⁰⁾,x₃⁽⁰⁾,…, x_n⁽⁰⁾).

В результате первого шага покоординатного спуска происходит переход из начальной точки x₀ в точку x₁.

1) если f(x⁽⁰⁾)= f(x⁽¹⁾), то x⁽⁰⁾ – точка минимума f(x).

2) если f(x⁽⁰⁾)> f(x⁽¹⁾), то выполняется следующий шаг покоординатного спуска, в котором за начальную точку принимается x⁽¹⁾.

Этот процесс продолжается до тех пор, пока f(x^(k+1))-f(x^(k))<ε, где ε – заданная точность.

Метод градиентного спуска

Численные методы отыскания минимума состоят в построении последовательности векторов {x^(k)}, удовлетворяющих условию f(x⁽⁰⁾)> f(x⁽¹⁾)>…> f(x^(k)). В этих методах элементы последовательности вычисляются по формуле x^(k+1)=x^(k)+h_k* ^(k), где ^(k) – направление спуска, h_k – длина шага в этом направлении.

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

Используя антиградиент в качестве направления спуска, приходим к итерационному процессу вида:

(1)

Все методы спуска, в которых вектор ^(k) совпадает с антиградиентом, называются градиентными методами.

Для минимизации функции используется метод градиентного спуска с дроблением шага. Процесс (1) с дроблением шага протекает следующим образом: выбираем некоторое значение x⁽⁰⁾, затем выбираем h_k=h=const и на каждом шаге процесса выбираем условие монотонности f(x^(k+1))<f(x^(k)). Если это условие нарушается, то h дробим до тех пор, пока монотонность не восстановится.

Для окончания счета можно использовать критерии:

Наиболее важным моментом в этом методе - это выбор шага. Формула (1) с постоянным шагом практически не применяется.

Метод наискорейшего спуска

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

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

,

т.е. на каждом шаге решается задача минимизации.

2. Ограничения методологии RAD.

Применение методологии RAD наиболее эффективно при создании сравнительно небольших ИС, разрабатываемых для вполне определенного предприятия.

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

Методология RAD неприменима также для построения сложных расчетных программ, ОС и программ управления сложными инженерно-техническими объектами, т.е. программ, требующих написания большого объема уникального кода.

Методология RAD не может быть использована для разработки приложений, в которых интерфейс пользователя является вторичным, т.е. отсутствует наглядное определение логики работы ИС. Примеры таких приложений: драйверы (служебные программы, обеспечивающие взаимодействие системы с конкретным устройством: драйвер мыши, драйвер клавиатуры, драйвер видеокарты, . . .), службы (системные программы, обеспечивающие функции ОС: служба доступа к папкам и файлам – служба ОС Windows ) приложения реального времени (регулятор громкости на рабочем столе).

Совершенно неприемлема методология RAD для разработки ИС, связанных с обеспечением безопасности жизнедеятельности людей, например, системы управления транспортом или АЭС. (Итеративный подход, лежащий в основе RAD, предполагает неполную работоспособность первых версий ИС и, следовательно, возможность катастроф.)