Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <numeric>
- #include <string>
- #include <cstring>
- #include <set>
- #include <map>
- #include <vector>
- #include <queue>
- #include <iostream>
- #include <iterator>
- #include <cmath>
- #include <cstdio>
- #include <cstdlib>
- #include <sstream>
- using namespace std;
- typedef long long LL;
- typedef vector<int> VI;
- typedef vector<vector<int> > VVI;
- typedef pair<int, int> PII;
- #define FOR(i,x,y) for(LL i=x; i<=y; i++)
- #define REP(i,n) for(LL i=0; i<n; i++)
- #define ALL(c) (c).begin(), (c).end()
- #define SORT(c) sort(ALL(c))
- #define SZ(c) (int)(c).size()
- #define pb push_back
- #define mp make_pair
- #define X first
- #define Y second
- const double eps = 1.0e-11;
- const double pi = acos(-1.0);
- void Print(const vector<double>& x) {
- //cout << "(";
- REP(i, SZ(x)) {
- printf(" %.6llf" + (i == 0), x[i]);
- }
- printf("\n");
- }
- vector<double> MakeVector(double x1, double x2) {
- vector<double> x(2);
- x[0] = x1, x[1] = x2;
- return x;
- }
- class Descent {
- const double angle;
- const double eps;
- const double min_derivative_value;
- public:
- Descent(double ang = 0.0, double e = 0.000001, double mdv = 0.0001) : angle(ang), eps(e), min_derivative_value(mdv) {}
- double Himmelblau(const vector<double>& x) {
- if (x.size() < 2) {
- return 0.0;
- }
- return pow((x[0] * x[0] + x[1] - 11), 2.0) + 100 * pow(x[0] + x[1] * x[1] - 7, 2.0);
- }
- double Rosenbrock(const vector<double>& x) {
- if (x.size() < 2) {
- return 0.0;
- }
- return pow(1 - x[0], 2.0) + 100 * pow(x[1] - x[0] * x[0], 2.0);
- }
- double QuadraticForm(const vector<double>& x) {
- if (x.size() < 2) {
- return 0.0;
- }
- double rotator[2][2] = {cos(angle), sin(angle), -sin(angle), cos(angle)};
- double a[2][2] = {0.1, 0.01, 0.1, 0.5};
- double b[2] = {0.0, -0.0};
- vector<double> rotated_x(2, 0.0);
- REP(i, 2) {
- REP(j, 2) {
- rotated_x[i] += rotator[i][j] * x[i];
- }
- }
- REP(i, 2) {
- REP(j, 2) {
- b[i] += a[j][i] * x[i];
- }
- }
- return b[0] * rotated_x[0] + b[1] * rotated_x[1];
- }
- double UserFunction(double x1, double x2) {
- return Rosenbrock(MakeVector(x1, x2));
- //return Himmelblau(MakeVector(x1, x2));
- //return QuadraticForm(MakeVector(x1, x2));
- //return x1 * x1 + x2 * (x2 + 1);
- }
- double UserFunction(const vector<double>& x) {
- return UserFunction(x[0], x[1]);
- }
- vector<double> Derivative(const vector<double>& x) {
- double first = UserFunction(x);
- double dx = (UserFunction(x[0] + eps, x[1]) - first) / eps;
- double dy = (UserFunction(x[0], x[1] + eps) - first) / eps;
- double lenth = sqrt(dx * dx + dy * dy);
- vector<double> res = MakeVector(dx / lenth, dy / lenth);
- if (abs(res[0]) < min_derivative_value && abs(res[1]) < min_derivative_value) {
- return MakeVector(0.0, 0.0);
- }
- return res;
- }
- double Dichtomy(const vector<double>& x, const vector<double>& der, double l = -100.0, double r = 100.0) {
- double c = (l + r) / 2.0;
- double d = c + eps;
- if (abs(l - r) < 2 * eps) {
- return c;
- }
- if (UserFunction(x[0] + c * der[0], x[1] + c * der[1]) < UserFunction(x[0] + d * der[0], x[1] + d * der[1])) {
- return Dichtomy(x, der, l, c);
- } else {
- return Dichtomy(x, der, c, r);
- }
- }
- pair<double, vector<double> > FastDescent(const vector<double>& x) {
- //if (rand() % 10 == 0)
- Print(x);
- vector<double> der = Derivative(x);
- if (der[0] == 0.0 && der[1] == 0.0) {
- return mp(UserFunction(x), x);
- }
- double best = Dichtomy(x, der);
- if (abs(best) < min_derivative_value) {
- return mp(UserFunction(x), x);
- }
- return FastDescent(MakeVector(x[0] + best * der[0], x[1] + best * der[1]));
- }
- };
- int main() {
- //freopen("output.txt", "w", stdout);
- Descent test(0.0);
- vector<double> d(2, -10.0);
- //cout << test.QuadraticForm(d) << endl;
- pair<double, vector<double> > res = test.FastDescent(d);
- printf("%.5llf\n", res.first);
- Print(res.second);
- return 0;
- }
Add Comment
Please, Sign In to add comment