мане після - го кроку оптимізації, - наперед заданий позитивне число.
Реалізація
Для одновимірної оптимізації будемо використовувати метод дихотомії. Пошук мінімуму функції однієї змінної будемо виробляти на відрізку. За умова зупину приймемо близькість кінців відрізка:, де і - права і ліва межі відрізка відповідно. p> Застосуємо метод покоординатного спуску для вирішення системи
,
де. допомогою методу покоординатного спуску рішення цієї системи
виходить за чотири ітерації.
const double EPS = 1e-7; f (double X, vector values, int pos) {[pos] = X; sqr (fabs (13 * values ​​[0] + 14 * values ​​[1] - 11)) + sqr (fabs (14 * values ​​[0] - 13 * values ​​[1] - 15)) + sqr (fabs (15 * values ​​[2] - 19));
}
// дихотомія для одновимірної оптімізацііbinarySearch (vector & values, int now) {l = - (1 <<30), r = (1 <<30), m1, m2; (; fabs (r - l)> EPS ;) {= l + (r - l)/3; = r - (r - l)/3; (f (m1, values, now) - f (m2, values, now )> EPS) {= m1;
} else {= m2;
}
} [now] = m1;
}
// покоординатного спускCoords (vector & answer) {prevValue = f (answer [0], answer, 0) + 100, nextValue = f (answer [0], answer, 0); i = 0 ; (fabs (nextValue - prevValue)> EPS) {= nextValue; (answer, i); = (i + 1)% answer.sz; = f (answer [0], answer, 0);
}
}
Пакетна реалізація
В В
2. Метод сполучених градієнтів
Метод сполучених градієнтів - ітераційний метод для безумовної оптимізації в багатовимірному просторі. Основною перевагою методу є те, що він вирішує квадратичну задачу оптимізації за кінцеве число кроків. p> Визначення . Два - мірних вектора і називають сполученими по відношенню до матриці (або-сполученими), якщо скалярний твір. Тут - симетрична позитивно певна матриця розміром. p> Передбачається, що квадратична функція має вигляд:
В
Якщо матриця симетрична і позитивно певна, то функція має єдиний мінімум, який досягається в точці, що збігається з рішенням системи лінійних рівнянь.
Ідея методу полягає в послідовному побудові напрямків взаємно сполучених щодо матриці. На кожному кроці напрям виходить як лінійна комбінація градієнтів в точці і попередніх напрямів, причому коефіцієнти лінійної комбінації вибираються так, щоб було зв'язаним до всіх попереднім напрямками. br/>В
Ітерація методу сполучених градієнтів полягає в обчисленні чергового наближення до точного рішення
В
де
- чергове наближення
- наближення, побудоване на попередньому кроці
- скалярний крок
- вектор напрямку.
Алгоритм
Перед виконанням першої ітерації і покладаються рівними нулю, а для вектора встановлюється...
