näraoptimal

Näraoptimal är ett begrepp inom optimering som beskriver lösningar eller planer som är mycket nära det optimala värdet för ett givet problem. En näraoptimal lösning utvärderas med hänsyn till hur nära den är optimal i förhållande till ett definierat toleransområde eller felmått. Begreppet används inom många områden som algoritmdesign, operationsforskning och kontrollteori.

Formellt kan näraoptimalitet beskrivas på flera sätt. För ett maximizeringsproblem där f* är det optimala värdet och f(x) är värdet för en given lösning x, säger man ofta att x är ε-näraoptimal om f(x) ≥ (1−ε) f* för ett litet ε>0. För minimizeringsproblem säger man att x är ε-näraoptimal om f(x) ≤ (1+ε) f* där f* är det optimala (minsta) värdet. Ett annat vanligt mått är absolut felmargin: |f(x) − f*| ≤ δ. Olika sammanhang använder olika definitioner, men alla syftar till att ange hur nära lösningen kommer optima.

Näraoptimalitet är centralt i studiet av approximationstekniker. Det innebär ofta att man strävar efter algoritmer som garanterar ett fel mindre än en viss ε eller som ger en garanti på hur nära lösningen är till optimal inom rimlig tidsramar. Termer som epsilon-approximation, PTAS (polynomial-tid för varje ε) och FPTAS (polynomial tid i både inputstorlek och 1/ε) används för att beskriva sådana garantier. Exempelvis finns närmeoptimalitetslösningar och därpå baserade metoder för problem som är NP-svåra, där exakta lösningar är oönskade eller opraktiska att beräkna.

Användningsområden inkluderar heuristik, relaxationstekniker, Lagrange-relaxationer, lokala sökstrategier och förstärkt inlärning, där mål är att uppnå tillräckligt bra resultat utan fullständig optimering. Närmeoptimalitet används också inom styrning och kontroll, där man ofta arbetar med nära optimal prestanda under praktiska begränsningar.

Se även: approximation, epsilon-optimal, PTAS, FPTAS, paretooptimalitet, närmeoptimal kontroll, policy.