Контрольная работа по Информатике

            copyVector(N, x, xout);

          //  cout<<"k = M"<<endl;

            q = 1;

            }

        if(q==0){

            if (k==0)

                copyVectorMinus(N, grx, pk);

            else{

                beta = norm / normpr;

                for(int j=0; j < N; j++)

                    pk[j]=- grx[j] + beta * pk[j];

                           

                }

            if (pow(norm, 0.5)<eps){

                copyVector(N, x, xout);

         //       cout<<"||f'(x)|| < eps"<<endl;

                q=1;

                }

            if(k>=M){

                copyVector(N, x, xout);

            //    cout << "k = M" << endl;

                q = 1;

                }

            if(q == 0){

                if (k==0) copyVectorMinus(N, grx, pk);

                else{

                    beta = norm/normpr;

                    for(int j=0; j < N; j++)

                        pk[j]=-grx[j]+beta*pk[j];

                    }

                normpr = 0;

                //cout << "\n______________________\n";

                for(int j=0; j < N; j++) {

                    normpr += grx[j] * grx[j];

                    }

                alfa_k = MDP(N, pk, x, r_shtraf);

                for(int j=0; j < N; j++) 

                    x[j] -= alfa_k * pk[j];

                double delta_x = 0;

                for(int i = 0; i<N; i++)

                    delta_x += (x[i] - xin[i])*(x[i] - xin[i]);

                          

                if(((pow(delta_x, 0.5))<eps)&&(abs(f(N, x, r_shtraf)-f(N, xin, r_shtraf)))<eps){

                    copyVector(N, x, xout);

                    q = 1;

                    }

                copyVector(N, x, xin);

                }

            }

        for(int j = 0; j <N; j++)

        ++k;

        }

    while(q == 0);

   

    }

 

void copyVector(int razmer, double *istochnik, double *priemnik){

    for (int i = 0; i < razmer; i++)

        priemnik[i] = istochnik[i];

    }

void copyVectorMinus(int razmer, double *istochnik, double *priemnik){

    for (int i = 0; i < razmer; i++)

        priemnik[i] = -istochnik[i];

    }

//производная по i-ой переменной

double Grad(const int n, double *x, int i, double r_shtraf){

    double h = 0.1e-7, ly, *lx;

    lx = new double [n];

    for(int j = 0; j<n; j++)

        lx[j] = x[j];

    ly = f(n, x, r_shtraf);

    lx[i] = lx[i] - h;

    ly = (ly - f(n, lx, r_shtraf)) / h;

    return ly;

    }

 

//находим оптимальное alfa_k

double MDP(const int n, double *pk, double *x, double r_shtraf){

    double a, b, ll, delta;

    double e=0.00001, l=0.0001, t=1.0, kk=1;

    double alfa_k=0, alfa_p=0, alfa_xk=0, alfa_yk=0;

    int p=0;

    //алгоритмом Свена находим отрезок локализации

    double *x0, *x1, *x2, *xp, *xk, *yk;

    x0 = new double [n];

    x1 = new double [n];

    x2 = new double [n];

    xp = new double [n];

    xk = new double [n];

    yk = new double [n];

 

    for(int j = 0; j < n; j++){

      // cout << pk[j] << "_______________x[j]" << x[j] << endl;

        x0[j] = x[j]-alfa_k*pk[j];

        x1[j] = x[j]-(alfa_k-t)*pk[j];

        x2[j] = x[j]-(alfa_k+t)*pk[j];

        }

 

    double f0 = f(n, x0, r_shtraf);

    double f1 = f(n, x1, r_shtraf);

    double f2 = f(n, x2, r_shtraf);

   

    if (f1 >= f0 && f2 >= f0){

        a = alfa_k-t;

        b = alfa_k+t;

        p = 1;

        }

 

    if (f1 <= f0 && f2 <= f0){

        cout << "Funkziya ne unimodal'na " << endl ;

        p=1;

        }

 

    alfa_p = alfa_k;

 

    if (f1 > f0 && f0 > f2){

        delta=t;

        a=alfa_k ;

        alfa_k += t;

        }

   

    if (f1 < f0 && f0 < f2){

        delta=-t;

        b=alfa_k ;

        alfa_k=alfa_k-t;

        }

   

    double fp ;

    while (p != 1){        

        for(int j = 0; j < n; j++){

            x0[j] = x[j]-alfa_k*pk[j];

            xp[j] = x[j]-alfa_p*pk[j];

            }

        f0 = f(n, x0, r_shtraf);

        fp = f(n, xp, r_shtraf);

 

        if (f0 < fp )

            if(delta*t >0)

                a=alfa_p;

            else

                b=alfa_p;

        if (f0 > fp){

            if(delta*t >0)

                b=alfa_k;

            else if(delta*t<0)

                a=alfa_k;

            p=1;

            }

        kk++;

        alfa_p = alfa_k;

        alfa_k = alfa_p + pow(2.0, kk) * delta;

        }

    do{

        // методом деления пополам (методом дихотомии) находим alfa_k

        alfa_xk = (a + b)/2 - e;

        alfa_yk = (a + b)/2 + e;

        for(int j = 0; j < n; j++){

            xk[j] = x[j]-(alfa_xk)*pk[j];

            yk[j] = x[j]-(alfa_yk)*pk[j];

            }

        double fxk = f(n, xk, r_shtraf);

        double fyk = f(n, yk, r_shtraf);

 

        if (fyk >= fxk)

            b = alfa_yk;

        if (fyk < fxk)

            a = alfa_xk;

        ll = b-a;

        }

    while(l < ll);

    return (a + b) / 2.0;

    }

 

 

В частности, для ограничений типа (2.11), (2.12) целесообразно использовать штрафную функцию следующего вида:

, (2.13)

 

где  R1, R2 - непрерывные функции, которые удовлетворяют условиям:

, если  и , если ,

, если  и , если .

Типичными являются следующие выражения  для функций R1, R2:

 

; ,

 

где p - целое положительное число.

Таким образом, штрафная функция  обычно имеет вид

 

,(2.14)

 

Далее от задачи нелинейного программирования (2.10)-(2.12) переходим к задаче безусловной  оптимизации вспомогательной функции:

минимизировать 

 

, (2.15)

 

где - штрафной коэффициент.

Пусть - непрерывная функция вида (2.13). Обозначим

 

(2.16)

 

Подход, связанный со штрафной функцией, состоит в решении задачи вида:

максимизировать (2.17)

при ограничении 

Справедлива следующая теорема, которая  обосновывает этот метод [1].

Теорема. Пусть задача нелинейного программирования задана в виде (2.10)-(2.12), где - непрерывные на Rn функции.

Предположим, что задача имеет допустимые решения и пусть - непрерывная штрафная функция вида (2.13). Предположим также, что для любого r существует решение xr, задачи минимизации вспомогательной функции и все xr принадлежат некоторому компактному подмножеству X. Тогда справедливо следующее уравнение:

 

(2.18)

 

где определяется в соответствии с (2.16).

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

Эта теорема служит обоснованием метода штрафных функций и из нее следует, что оптимальное значение xr может быть сделано наиблизким к допустимой области при довольно большом r. Кроме того, выбрав r довольно большим, значение можно сделать как угодно близким к оптимальному значению целевой функции исходной задачи f(x).

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

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

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

минимизировать f(x)

при ограничениях , ,

где функции непрерывны.

Начальный этап. Выбрать  . Выбрать начальную точку x1, параметр штрафа и число . Положить и перейти к основному этапу.

Основной этап. Первый шаг. При начальной  точке xk и параметре штрафа решить следующую задачу:

минимизировать

 

,(2.19)

 

где - целое.

Положить xk+1 равным оптимальному решению этой задачи и перейти ко второму шагу.

Второй шаг. Если , то остановиться. В противном случае положить . Заменить k на k+1 и перейти к первому шагу.

Пример. Рассмотрим следующую задачу:

минимизировать  ,

при ограничениях .

В качестве штрафной функции  выберем . Тогда на k-й итерации при заданном значении параметра rk необходимо решать следующую задачу:

 

минимизировать  ,

 

где .

В таблице 2 приведены результаты вычислений по методу штрафных функций. В качестве начальной выбрана точка  , в которой значение целевой функции равно 0. В качестве начального значения штрафа взято , а число . Заметим, что и - неубывающие функции, а - невозрастающая функция параметра .

Процесс остановлен после четырех  итераций, где  . Но, чтобы убедиться, что последовательность стремится к нулю, выполнена еще одна итерация и найдено x6. Можно убедиться, что в точке выполняются условия Куна-Таккера с заданной точностью.

Таблица 2

k
1	0.1	1,4539; 0,7608	0.0935	7.8307	0.7831	0.8766
2	1	1.1687; 0.7407	0.5753	0.3908	0.3908	0.9661
3	10	0.9906; 0.8425	1.5203	0.01926	0.1926	1.7129
4	100	0.9507; 0.8875	1.8917	0.000267	0.0267	1.9184
5	1000	0.9461; 0.8934	1.9405	0,0000028	0.0028	1.9433