Общая задача нелинейного программирования. Метод Нъютона.

Как известно, общая задача математического  программирования формулируется следующим образом: найти вектор

         X=( x_1, x_2,........,  x_n)

 {spoiler=Подробнее}

удовлетворяющей системе ограничений

         g_i (x₁, x₂....., x_n)=b_i,  i=1, 2, ..., k

         g_i (x_1,  x_{2, . ....,}  x_n)<b_i,  i=k+1, k+2, ..., m

и доставляющей, требуемый максимум или минимум функции

         z=f(x_1,   x_{2, .....,}  x_n)®min(max)

При этом предполагается, что известны функции

         g_i (x_1,   x_{2, .....,}  x_n) и f(x_1,   x_{2, .....,}  x_n)

Обычно на некоторые переменные x_1,   x_{2, .....,}  x_n   накладывается условие  неотрицательности. Кроме того, ограничением может служить условие   целочисленности решения для ряда переменных.

                                              n

Если           g_i (x_1,   x_{2, .....,}  x_n)= å  a _ij,x _j,     i=1,2,.....m.      (3)

                                              j=1

                                                 n

и                          Z=f (x_1,   x_{2, .....,}  x_n)= å  c_jx_j,                            (4)

                                                j=1

где a _ij,, c_j -известные константы, то при условие неотрицательности решения получаем задачу линейного  программирования. Любую другую задачу математического программирования не удовлетворяющую условиям (3) и (4) условимся считать нелинейной.

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

Метод Ньютон для решения систем нелинейных алгебраических уравнений

         Требуется найти решение систем нелинейных алгебраических уравнений     f_i (х₁ ,х₂ ,...,х_n)=0 ,i=1,2,3,...,n      (1)

        Пусть известно решение системы (1) в   к - ом шаге

                         x₁^(k) ,x₂^(k),...,x_n^(k)

       необходимо найти (к+1) - ое приближенное решение

                        x₁^(k+1) ,x₂^(k+1) ,...,x_n^(k+1) .

       Для решения  данной задачи введем обозначения:

                          Dx_i^(k) =x_i -x_i^(k)       

        или

                         x­_{i =}x_i^(k)+Dx_i^(k) ,i=1,2, ... ,n.           (2)

        Разлогая функцию f_i(х_1,,х_2,,...,х_n) по степеням Dx_i^k в ряд Тейлора, притом ограничимся с первой производной

          Системы уравнений (3) можем написать таким образом:

         Если написать в матричном виде

         (5)

       Системы уравнений (5) решаем относительно  

               ,       (i=1,n)  и получим

       (6)

 Теперь  обозначая      для определения  приближенного вычисления  в (к+1)- шаге имеем формулу :

   (7)

         Полученная система называется формулой Ньютона в матричном виде

                ,k=0,1,2,...,n.(8)

Здесь ,матрица Якоби или называется Якобианом.

Для модифицированного метода Ньютона  формула (8) имеет следующий вид:

,   k=0,1,2, . . .,n.         (9)

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

{/spoilers}