Задача оптимізації

Poll without page-refresh

Article on other languages:

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

Зада́ча оптиміза́ції — задача знаходження точки (точок) мінімуму, або декількох мінімумів заданої функції.

Формальне визначення

Нехай задано деяку множину X із n-вимірного евклідового простору і функцію f(x), визначену на X. Необхідно знайти точки мінімуму значень функції f(x) на X. Або:

f(x) → min, x ∈ X.

тут f(x) — цільова функція, X — допустима множина, кожна точка x цієї множини — допустима точка задачі.

Також, задачу оптимізації можна сформулювати як пошук максимуму (максимумів) цільової функції:

f(x) → max, x ∈ X.

ця задача еквівалентна попередній задачі мінімізації цільової функції із знаком мінус, в тому сенсі, що множини їхніх розв'язків збігаються.

Розв'язки задачі

Розв'язки задачі можна розділити на дві множини:

глобальні: (глобального мінімуму), це такі допустимі точки x^* в яких цільова функція має найменше значення на всій допустимій області:

f(x^*) ≤ f(x), ∀ x ∈ X;

локальні: (локального мінімуму), це такі допустимі точки x^* в яких цільова функція приймає найменше значення в деякому околі:; f(x^*) ≤ f(x), ∀ x ∈ X ∩ U_ε(x^*),