Математическая оптимизация или отыскание корней

Уравнения имеют левую и правую части. Вычитая одну из другой, получаем уравнение, одна из частей которого равна нулю. Отыскивая корни уравнения, вы хотите узнать, какие значения независимой переменной (-ных) разрешают это уравнение (это — корни). Найти корни можно с помощью традиционных методов, например методом Ньютона (метод касательных).

Можно сказать, что отыскание корней имеет отношение к математической оптимизации, так как первая производная в точке оптимума функции (т. е. на экстремуме) будет равна 0. Следовательно, вы могли бы заключить, что традиционные методы отыскания корней, например метод Ньютона, можно использовать для решения оптимизационных задач (применение собственно методов оптимизации для отыскания корней уравнения, напротив, чревато обилием трудностей).

Наша дискуссия, однако, будет касаться лишь методов оптимизации, а не методов отыскания корней, как таковых. Сведения о последних можно почерпнуть в таком уникальном источнике, как «Численные методы»*.

Методы оптимизации

Математическую оптимизацию можно вкратце описать следующим образом. У вас есть некая целевая функция (обозначим ее G), зависящая от одного или большего количества независимых переменных (которые мы обозначим f{, ¦¦¦,/,)¦ Вы хотите найти значение (-ния) независимой переменной (-ных), доставляющее минимум (или иногда, как в нашем случае, максимум) целевой функции. Максимизация и минимизация, по сути, являются одним и тем же (то, что для одного равно G, для другого будет — G).

В самом примитивном случае вы можете оптимизировать следующим образом: перебирая все комбинации значений переменных и подставляя их в целевую функцию, искать такую комбинацию, которая дает наилучший результат. Предположим, например, что мы хотим найти оптимальное /для одновременного бросания двух монет с точностью до 0,01. Тогда мы могли бы неизменно проводить расчеты для монеты 1 на значении 0,0, в то время как для монеты 2 переходить от 0,0 к 0,01 к 0,02 и так далее, пока не дойдем до 1,0. После этого мы могли бы вернуться к монете 1 и, просчитывая ее на значении 0,01, опробовать все возможные значения для монеты 2. Действуя таким образом и далее, мы придем к тому, что значения обеих переменных окажутся на их максимумах, то есть станут равны 1,0. Поскольку у каждой переменной в данном случае имеется по 101 возможному значению (от 0 до 1,0 включительно с шагом 0,01), то мы должны опробовать 101 * 101 комбинаций, то есть целевая функция должна быть рассчитана 10201 раз.

При желании, мы могли бы потребовать большей точности, чем 0,01. Тогда у нас стало бы 1001 * 1001 комбинаций, подлежащих опробованию, то есть целевую функцию пришлось бы рассчитать 1002001 раз. Если бы мы собрались взять три переменных вместо двух и потребовали бы точности 0,001, то нам пришлось бы вычислить целевую функцию 1001 * 1001 * 1001 раз, что равно 1003003001, то есть нам пришлось бы вычислить целевую функцию более одного миллиарда раз. А ведь мы используем всего лишь три переменных и требуем лишь 0,001 точности!

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