2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Метод конфигураций (циклического покоординатного спуска)
Сообщение14.01.2019, 21:54 
Аватара пользователя
Срочно нужна помощь в проверке программы (до среды нужно сдать), хотел убедиться правильно работает или есть недочеты.

Программу нужно было написать на 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)Нормальный получился результат?

 
 
 
 Re: Метод конфигураций (циклического покоординатного спуска)
Сообщение14.01.2019, 22:25 
А вы частные производные и т.д. уже проходили ? Задача решается не приближенно, а точно, в несколько строчек на бумажке. Можете это сделать ?

 
 
 
 Re: Метод конфигураций (циклического покоординатного спуска)
Сообщение15.01.2019, 14:48 
Сейчас обратил внимание, что, судя по упоминанию стационарных точек, ТС уже знает, что такое частные производные, и должен быть способен решить задачу на бумажке. Однако и без частных прозводных вполне можно обойтись, выделением полных квадратов... Короче, ответ на вопрос, "а правильный ли ответ выдала программа", можно найти и самому.

 
 
 
 Posted automatically
Сообщение16.01.2019, 00:03 
 i  Тема перемещена из форума «Программирование» в форум «Карантин»
по следующим причинам:

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

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

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group