Wikiszótár

Karmarkar-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈkɒrmɒrkɒrɒlɡoritmuʃ]

Főnév

Karmarkar-algoritmus

  1. (matematika)

Karmarkar-algoritmus

A Karmarkar-algoritmus egy lineáris programozási (LP) módszer, amelyet a lineáris egyenlőtlenségekkel korlátozott optimalizálási problémák megoldására használnak. Az algoritmus egy belső pont módszer, amely iteratívan közelíti meg az optimális megoldást, és hatékony alternatívát kínál a simplex módszerrel szemben.


Elmélet

Lineáris programozás

A lineáris programozási probléma általános alakja: [ c^T x ] [ Ax b, x ] ahol: - (x): változók vektora, - (c): költségtényező vektor, - (A): mátrix, amely korlátozza a megoldást, - (b): a korlátok vektora.

Karmarkar-algoritmus főbb jellemzői

  1. Belépés a belső pontba:
    • Az algoritmus a megoldási tér belsejében halad az optimális megoldás felé, nem pedig a széleken, mint a simplex módszer.
  2. Projektált gradiens lépés:
    • Egy projektált gradiensirányban halad, amely maximalizálja a célfüggvény csökkenését.
  3. Iteratív lépések:
    • Minden iterációban egy belső ponti megoldást frissítünk, majd a projektált térre vetítjük.

Időkomplexitás

  • A Karmarkar-algoritmus futási ideje (O(n^{3.5} L)), ahol (n) a változók száma, (L) pedig a bemeneti adatok bitmérete.


Pszeudokód

Karmarkar(A, b, c, ε):
    Kezdeti belső pont x₀
    iteráció = 0

    amíg a célfüggvény javulása > ε:
        1. Skálázd a mátrixot és a megoldást a belső pontban.
        2. Számítsd ki a projektált gradienst.
        3. Optimalizáld a lépéshosszt a belső térben.
        4. Frissítsd a megoldást: x_{k+1} = x_k + lépésirány.
        5. Normalizáld az új megoldást.

        iteráció += 1

    térj vissza xₖ, mint a közelítő megoldás.

Python implementáció

A Karmarkar-algoritmus implementációja egy egyszerű példán keresztül: 

import numpy as np

def karmarkar(A, b, c, epsilon=1e-6, max_iter=1000):
    # Kezdeti megoldás (belsejében legyen a megoldási térnek)
    n = len(c)
    x = np.ones(n) / n  # Normalizált kezdőpont

    for _ in range(max_iter):
        # Skálázás és projektált gradiens
        D = np.diag(x)
        A_tilde = A @ D
        c_tilde = D @ c

        # Normált keresési irány (gradienselemzés)
        pseudo_inv = np.linalg.pinv(A_tilde @ A_tilde.T)
        y = pseudo_inv @ A_tilde @ c_tilde
        d = -c_tilde - A_tilde.T @ y

        # Optimalizált lépéshossz
        alpha = min(1, min(-x[d < 0] / d[d < 0]))

        # Lépés frissítése
        x += alpha * d
        x /= np.sum(x)  # Normalizálás

        # Ellenőrzés: célfüggvény javulása
        if np.linalg.norm(c @ x) < epsilon:
            break

    return x

# Példa bemenet
A = np.array([
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 10]
])
b = np.array([6, 15, 25])
c = np.array([1, 2, 3])

solution = karmarkar(A, b, c)
print("Optimalizált megoldás:", solution)

C++ implementáció

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

vector<double> karmarkar(const vector<vector<double>>& A, const vector<double>& b, const vector<double>& c, double epsilon = 1e-6, int max_iter = 1000) {
    int n = c.size();
    vector<double> x(n, 1.0 / n);  // Kezdeti normalizált megoldás

    for (int iter = 0; iter < max_iter; ++iter) {
        // Skálázás mátrix
        vector<vector<double>> D(n, vector<double>(n, 0.0));
        for (int i = 0; i < n; ++i) {
            D[i][i] = x[i];
        }

        // A_tilde = A * D
        vector<vector<double>> A_tilde(A.size(), vector<double>(n, 0.0));
        for (int i = 0; i < A.size(); ++i) {
            for (int j = 0; j < n; ++j) {
                A_tilde[i][j] = A[i][j] * D[j][j];
            }
        }

        // Gradiens irány számítása
        vector<double> grad(n, 0.0);
        for (int i = 0; i < n; ++i) {
            grad[i] = -c[i];  // Egyszerű lineáris példa
        }

        // Lépéshossz számítása
        double alpha = 1.0;
        for (int i = 0; i < n; ++i) {
            if (grad[i] < 0) {
                alpha = min(alpha, -x[i] / grad[i]);
            }
        }

        // Lépés frissítése
        for (int i = 0; i < n; ++i) {
            x[i] += alpha * grad[i];
        }

        // Normalizálás
        double sum_x = 0.0;
        for (double val : x) sum_x += val;
        for (int i = 0; i < n; ++i) {
            x[i] /= sum_x;
        }

        // Ellenőrzés
        double norm_grad = 0.0;
        for (double val : grad) {
            norm_grad += val * val;
        }
        if (sqrt(norm_grad) < epsilon) break;
    }

    return x;
}

int main() {
    vector<vector<double>> A = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 10}
    };
    vector<double> b = {6, 15, 25};
    vector<double> c = {1, 2, 3};

    vector<double> solution = karmarkar(A, b, c);
    cout << "Optimalizált megoldás:" << endl;
    for (double val : solution) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Összegzés

  • Előnyök:
    • Hatékony nagy dimenziós problémák megoldására.
    • Belép a megoldási tér belső pontjaira, ami stabil numerikus viselkedést biztosít.
  • Hátrányok:
    • Az implementáció bonyolultabb, mint a simplex módszeré.
    • A projektált gradiens és normalizáció növeli a számítási költséget.

A Karmarkar-algoritmus a modern optimalizálási technikák fontos eszköze, különösen a lineáris programozás és más konvex optimalizálási problémák területén.


Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Karmarkar-algoritmus&oldid=3479502”