lab3_mo.js

gistfile1.txt

// Dependencies
const readline = require('readline');

// Нелдер–Мид: минимизатор функции g(x)
function nelderMead(g, x0, opts = {}) {
  const maxIter = opts.maxIter || 500;
  const tol = opts.tol || 1e-6;
  const n = x0.length;
  const alpha = 1, gamma = 2, rho = 0.5, sigma = 0.5;

  // Инициализация симплекса
  let simplex = [{ point: x0.slice(), value: g(x0) }];
  for (let i = 0; i < n; i++) {
    const pt = x0.slice(); pt[i] += 1;
    simplex.push({ point: pt, value: g(pt) });
  }

  for (let iter = 0; iter < maxIter; iter++) {
    // Сортировка по значению
    simplex.sort((a, b) => a.value - b.value);
    const best = simplex[0].value;
    const worst = simplex[n].value;

    // Проверка сходимости
    if (Math.abs(worst - best) < tol) break;

    // Вычисление центроида без худшей точки
    const centroid = new Array(n).fill(0);
    for (let i = 0; i < n; i++)
      for (let j = 0; j < n; j++)
        centroid[j] += simplex[i].point[j];
    for (let j = 0; j < n; j++) centroid[j] /= n;

    // Отражение
    const xr = centroid.map((c, j) => c + alpha * (c - simplex[n].point[j]));
    const fr = g(xr);
    if (fr < simplex[0].value) {
      // Расширение
      const xe = centroid.map((c, j) => c + gamma * (xr[j] - c));
      const fe = g(xe);
      simplex[n] = fe < fr ? { point: xe, value: fe } : { point: xr, value: fr };
    } else if (fr < simplex[n - 1].value) {
      simplex[n] = { point: xr, value: fr };
    } else {
      // Сжатие
      const xc = centroid.map((c, j) => c + rho * (simplex[n].point[j] - c));
      const fc = g(xc);
      if (fc < simplex[n].value) {
        simplex[n] = { point: xc, value: fc };
      } else {
        // Редукция
        for (let i = 1; i < simplex.length; i++) {
          simplex[i].point = simplex[0].point.map((v, j) => v + sigma * (simplex[i].point[j] - v));
          simplex[i].value = g(simplex[i].point);
        }
      }
    }
  }

  // Возвращаем лучшее решение
  simplex.sort((a, b) => a.value - b.value);
  return { x: simplex[0].point, fx: simplex[0].value };
}

// Метод штрафных функций
function penaltyMethod(f, constraints, r0, factor, tol, maxOuter, nmOpts, x0) {
  let r = r0;
  let x = x0;
  for (let k = 0; k < maxOuter; k++) {
    // Штрафная функция
    const F = (xx) => {
      let sum = 0;
      for (const g of constraints) {
        const v = g(xx);
        if (v > 0) sum += v * v;
      }
      return f(xx) + r * sum;
    };
    // Минимизация F
    const res = nelderMead(F, x, nmOpts);
    x = res.x;
    // Проверка точности ограничений
    const maxViolation = Math.max(...constraints.map(g => Math.max(0, g(x))));
    if (maxViolation < tol) break;
    r *= factor;
  }
  return { x, fx: f(x) };
}

// Метод барьерных функций (для неравенства h(x)<=0)
function barrierMethod(f, inequalities, mu0, factor, tol, maxOuter, nmOpts, x0) {
  let mu = mu0;
  let x = x0;
  for (let k = 0; k < maxOuter; k++) {
    // Барьерная функция (-sum log(-h))
    const B = (xx) => {
      let sum = 0;
      for (const h of inequalities) {
        const v = h(xx);
        if (v >= 0) return Infinity; // вне области
        sum -= Math.log(-v);
      }
      return f(xx) + mu * sum;
    };
    // Минимизация B
    const res = nelderMead(B, x, nmOpts);
    x = res.x;
    // Проверка параметра mu
    if (mu < tol) break;
    mu *= factor;
  }
  return { x, fx: f(x) };
}

// Задачи
const tasks = {
  a: {
    f: (v) => 4 * (v[1] - v[0])**2 + 3 * (v[0] - 1)**2,
    constraints: [ (v) => (v[1] - v[0] + 1) ], // y - x +1 <= 0
    equality: null
  },
  b: {
    f: (v) => 4 * (v[1] - v[0])**2 + 3 * (v[0] - 1)**2,
    constraints: [],
    equality: (v) => v[1] - v[0] - 1 // =0
  }
};

// CLI
(async () => {
  const rl = readline.createInterface({ input: process.stdin, output: process.stdout });
  const ask = (q) => new Promise(res => rl.question(q, res));

  while (true) {
    console.log("\n1) Штрафная (задача a)");
    console.log("2) Штрафная (задача b)");
    console.log("3) Барьерная (задача a)");
    console.log("4) Выход");
    const choice = await ask('Выберите пункт: ');
    if (choice === '4') break;

    // Параметры общие
    const r0 = parseFloat(await ask('Начальный штрафной коэффициент (r0): '));
    const factor = parseFloat(await ask('Множитель коэффициента (factor): '));
    const tol = parseFloat(await ask('Точность по ограничениям (tol): '));
    const outerIter = parseInt(await ask('Макс. внешних итераций: '), 10);
    const nmTol = parseFloat(await ask('Точность Nelder-Mead (tol): '));
    const nmIter = parseInt(await ask('Макс. итераций Nelder-Mead: '), 10);
    const x0x = parseFloat(await ask('Начальное x: '));
    const x0y = parseFloat(await ask('Начальное y: '));
    const nmOpts = { tol: nmTol, maxIter: nmIter };
    let result;

    if (choice === '1') {
      result = penaltyMethod(tasks.a.f, tasks.a.constraints, r0, factor, tol, outerIter, nmOpts, [x0x, x0y]);
    } else if (choice === '2') {
      // Равенство переводим в две неравенства
      const eq = tasks.b.equality;
      const constr = [
        (v) => eq(v),
        (v) => -eq(v)
      ];
      result = penaltyMethod(tasks.b.f, constr, r0, factor, tol, outerIter, nmOpts, [x0x, x0y]);
    } else if (choice === '3') {
      result = barrierMethod(tasks.a.f, tasks.a.constraints, r0, factor, tol, outerIter, nmOpts, [x0x, x0y]);
    } else {
      console.log('Неверный выбор');
      continue;
    }

    console.log(`\nРешение: x=${result.x[0].toFixed(6)}, y=${result.x[1].toFixed(6)}, f=${result.fx.toFixed(6)}`);
  }

  rl.close();
})();