Метод конфигураций (циклического покоординатного спуска)

[xdtab]

Срочно нужна помощь в проверке программы (до среды нужно сдать), хотел убедиться правильно работает или есть недочеты.

Программу нужно было написать на Pascal. Код я прикрепил. Теорию можете не читать, если знаете о чем суть. Я ее написал, что бы можно было посмотреть (суть алгоритмов изложил).
Задание:
Методом циклического покоординатного спуска с точностью {\varepsilon }_{1}=0.01 найти решение задачи минимизации. Для решения задачи одномерной минимизации использовать метод дихотомического поиска (с точностью {\varepsilon }_{2}={10}^{-5}).

2{x}^{2}_{1}+{x}^{2}_2-2{x}_{1}{x}_{2}-5{x}_{2}-{x}_{1}\rightarrow min;
\left({x}_{1},{x}_{2} \right)\in {R}^{2}

Алгоритм дихотомического поиска минимума функции одной переменной.
Пусть f(x) - строго квазивыпуклая на \left[{a}_{1},{b}_{1} \right].
Требуется найти {x}^{*} - точку минимума, {x}^{*}\in \left[{a}_{1},{b}_{1} \right].


\lambda =\frac{{a}_{1}+{b}_{1}}{2}-l, \mu =\frac{{a}_{1}+{b}_{1}}{2}+l (1), 0<l<<1.
Если f(\lambda )>f(\mu ), то \left[{a}_{2},{b}_{2} \right]=\left[\lambda,{b}_{1} \right]
Если f(\lambda )\leq f(\mu ), то \left[{a}_{2},{b}_{2} \right]=\left[{a}_{1},\mu \right].
На новом интервале неопределенности \left[{a}_{2},{b}_{2} \right], выберем \lambda и \mu по формуле (1).
Повторяя алгоритм, мы получаем:
\left[{a}_{1},{b}_{1} \right]\supset \left[{a}_{2},{b}_{2} \right]\supset \left[{a}_{3},{b}_{3} \right]\supset ...\supset \left[{a}_{k},{b}_{k} \right]...
Каждый из этих интервалов будет содержать точку {x}^{*}.
И точка {x}^{*} является общим пределом при k\rightarrow \infty для левых и правых концов промежутка, то есть:
{x}^{*}=\lim_{{k }_{\rightarrow \infty }}{a}_{k}=\lim_{{k }_{\rightarrow \infty }}{b}_{k}.
Алгоритм останавливается, когда расстояние между {a}_{k} и {b}_{k} меньше заданного \epsilon.
Алгоритм
Начальный этап
Задаем интервал неопределенности [a,b] и задаем длину конечного интервала неопределенности 0<\epsilon <<1. Задаем константу l=\frac{\epsilon }{10}. Задаем счетчик итераций k=1.
Суть алгоритма описал выше, а это были уточнения.

Алгоритм цикличного покоординатного спуска.
Для любой \bar{{x}}_{0}\in {R}^{n}, \bar{x}_{k+1} = \bar{{x}_{k}}+{\alpha }_{k}\bar{{h}_{k}} (2), {a}_{k} любые, {h}_{k} - выбираются равными единичным ортам.
\bar{{h}_{0}}=\bar{{e}_{1}}=\left(1,0,...,0 \right) ;
\bar{{h}_{1}}=\bar{{e}_{2}}=\left(0,1,...,0 \right) ;
.........
\bar{{h}_{n-1}}={e}_{n}=\left(0,0,...,1 \right);
\bar{{h}_{n}}=\bar{{e}_{1}};
\bar{{h}_{n+1}}=\bar{{e}_{n}}.
Числовые параметры {\alpha }_{k} выбираются с помощью решения задачи одномерной минимизации, то есть {\alpha }_{k} выбирается так, что f\left(\bar{{x}}_{k}+{\alpha }_{k}\bar{{h}}_{k} \right)=\min_{\alpha \in R}f\left(\bar{{x}}_{k}+{\alpha }\bar{{h}}_{k} \right) (4).
Алгоритм (2)-(4) называется методом циклического покоординатного спуска.
Этот метод сходится к стационарной точке в случае дифференцируемости функции. Если функция не дифференцируема, то этот метод может остановиться в любой не стационарной точке.

Подготовительный этап алгоритма:
Выбирается для любой \bar{{x}}_{0}\in {R}^{n}, k=0. Выбираем 0<\epsilon \leq 1 для критериев остановки. Полагаем \bar{{y}}_{1}=\bar{{x}}_{0}, j=1, j - счетчик единичных орт.
Шаг 1
Найти {\alpha }_{j} из решения задачи одномерной минимизации \bar{{e}}_{j}=(0,0,...,1,0,...,0) - единичный орт.
f\left(\bar{{x}}_{k}+{\alpha }_{k}\bar{{h}}_{k} \right)=\min_{\alpha \in R}f\left(\bar{{x}}_{k}+{\alpha }\bar{{h}}_{k} \right). Положить \bar{{y}}_{j+1}=\bar{{y}}_{j}+{\alpha }_{j}\bar{{e}}_{j}.
Если j\leq n, то заменить j=j+1 и вернуться на шаг 1.
Если j>n, то перейти на шаг 2.
Шаг 2
Положить {x}_{k+1}={y}_{n+1}. Если || \bar{{x}}_{k+1}-\bar{{x}}_{k} ||\leq \epsilon и \left|f(\bar{{x}}_{k+1})-f(\bar{{x}}_{k}) \right|\leq \epsilon, то остановиться и \bar{{x}}_{*}=\bar{{x}}_{k+1}.
В противном случае, положить \bar{{y}}_{1}=\bar{{x}}_{k+1}, j=1, k=k+1 и вернуться на шаг 1.

Код моей программы:

const 
n = 2; // Так как R^2
eps=1E-2; // Точность
type 
vector = array[1..n] of real; 
 
function saxpy(a: real; x, y: vector): vector; // Создание векторов
begin 
for var i := 1 to n do 
result[i] := a * x[i] + y[i]; 
end; 
 
function f(x: vector): real; // Моя функция
begin 
result:=2*x[1]*x[1]+x[2]*x[2]-2*x[1]*x[2]-5*x[2]-x[1]; 
end; 
 
function norma(x:vector):real; // Нахождение нормы
begin 
for var i:=1 to n do 
result+=x[i]*x[i]; 
result:=sqrt(result); 
end; 
 
function DH(x, h: vector):real; // Метод дихотомического поиска
const 
eps = 1e-5; 
var 
r, r0, l0, a, b: real; 
begin 
 
a := -10; // Задаю левую границу
b := 10; // Задаю правую границу
 
while abs(b - a) > eps do 
begin 
 
r0 := (a + b) / 2 + eps / 10; // eps/10 - из условия алгоритма
l0 := (a + b) / 2 - eps / 10; 
 
if (f(saxpy(l0, h, x))) < (f(saxpy(r0, h, x))) then 
b := r0 
else 
a := l0; 
end; 
result := (a + b) / 2; 
end; 
 
// Главная часть программы
var k,i,j:integer; 
alfa,max_df:real; 
xn,xk,hk,xn_xk:vector; 
yj:vector; 
begin 
for i:=1 to n do 
xn[i]:=6; // Как я понял x можно любое задавать
repeat 
 
for i:=1 to n do 
xk[i]:=xn[i]; 
 
j:=1; 
 
for i:=1 to n do
 
hk[i]:=0; 
 
hk[j]:=-1; 
 
alfa:=DH(xk,hk); 
 
for i:=1 to n do 
xn[i]:=xk[i]+alfa*hk[i]; 
for i:=1 to n do 
xn_xk[i]:=xn[i]-xk[i]; 
 
k+=1; 
 
until (norma(xn_xk)<eps) and (abs(f(xn)-f(xk))<eps); 
write('Точка минимума = ('); 
for i := 1 to n-1 do 
write(xn[i]:5:5, ','); 
writeln(xn[n]:5:5, ')'); 
writeln('количество итераций равно = ',k); 
writeln('Значение функции в этой точке = ', f(xn)); 
end.

Результат работы программы:

Точка минимума = (3.25000,6.00000)
количество итераций равно = 2
Значение функции в этой точке = -15.1249999999991

Вопросы:
1) Дихотомический поиск я правильно сделал, нужно проверить циклический покоординатный спуск. Так ли он реализовывается, как я в программе написал?
2) Нет ли в коде ошибок?
3)Нормальный получился результат?

[vpb]

А вы частные производные и т.д. уже проходили ? Задача решается не приближенно, а точно, в несколько строчек на бумажке. Можете это сделать ?

[vpb]

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

[Pphantom]

Тема перемещена из форума «Программирование» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);
- для кода воспользуйтесь тэгом подсветки синтаксиса.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.