Минимизация функции

← →
Myrs (2004-02-21 01:14) [0]

Нужно минимизировать функцию. Существуют ли какие-нибудь компоненты/алгоритмы для этого?
Заранее спасибо.

← →
Defunct © (2004-02-21 01:18) [1]

> Нужно минимизировать функцию.
Какую функцию минимизировать?
Булевую?

> Существуют ли какие-нибудь компоненты/алгоритмы для этого?
Этим занимается не Delphi а теория цифровых автоматов.
Методы Квайна, неопред. коэффициентов и т.п.

← →
YurikGl (2004-02-21 08:06) [2]

Самое простое - берешь начальную точку (например 0), делаешь шаг влево, шаг вправо. Там где функция будет меньше - фиксируешься и повторяешь заново (шаг влево - шаг вправо). Когда с обоих сторон значение функции больше чем в середине - найден минимум. Здесь можно, например, уменьшить шаг (раз в 10). И повторить алгоритм. Так повторяем до получения необходимой точности.

Кстати, логично сначала проверять шаг в ту сторону, куда был шаг до этого :)

Есть гораздо более быстрые методы.

Все это работает если у функции один минимум или если заранее известна область глобального минимума. Все градиентные и т.п. спуски так-же имеют этот недостаток. Если функция имеет много минимумов - тебе нужен генетический алгоритм. У него такого недостатка нет.

Кстати, пошукай в примерах. Может что есть.

P.S. Будешь искать - найдешь...

← →
Defunct © (2004-02-21 08:47) [3]

> берешь начальную точку (например 0), делаешь шаг влево, шаг вправо. Там где функция будет меньше - фиксируешься и повторяешь заново (шаг влево - шаг вправо). Когда с обоих сторон значение функции больше чем в середине - найден минимум.

Какое отношение имеет поиск локальных минимумов функции к минимизации самой функции?

← →
YurikGl (2004-02-21 08:58) [4]

А когда мы минимизируем функцию, мы что по твоему делаем?

← →
Defunct © (2004-02-21 09:08) [5]

Ищем МД(К)НФ: сокращаем количество входных импликант. Кто не в танке: сокращается число булевых операций.

Например:

F = (X1 and X2 and X3) Or (X1 And X2 And (Not X3))

После минимизации примет вид:

F = (X1 And X2)

← →
YurikGl (2004-02-21 09:16) [6]

А по моему, шла речь о минимизации непрерывных функций подбором соответсвующих коэффициентов функции.
Например:

F = (X1 and X2 and X3) Or (X1 And X2 And (Not X3))

После минимизации примет вид:

F = (X1 And X2)

Это - не минимизация, а приведение к нормальной конъюнктивной или дизъюнктивной форме. Для этого существуют общие универсальные алгоритмы.

← →
Defunct © (2004-02-21 09:32) [7]

Вы поняли, что только что написали? Помните чем отличаются Д(К)НФ от СД(К)НФ(Сокращенная) и МД(К)НФ(Минимальная)?

Минимизация булевой функции - это поиск МД(К)НФ.

>>А по моему, шла речь о минимизации непрерывных функций подбором соответсвующих коэффициентов функции.
>Myrs (21.02.04 01:14)
> Нужно минимизировать функцию.

Помоему шла речь о минимизации функции. Я знаю только методы минизации булевых функций. Если Вы знаете как можно "минимизировать" непрерывную функцию, поделитесь знаниями пожалуйста.

← →
YurikGl (2004-02-21 09:52) [8]

Как правило, это означает что подбор каким-либо образом коэффициентов минимизируемой функции F так, что ее интеграл на заданном промежутке был минимален. Например, если слегка абстрагироваться. Расход бензина=F(скорость[, количество оборотов двигателя]). Скорость - переменная, число оборотов - минимизируемый параметр. Нужно подбрать количество оборотов двигателя такое, что при любой скорости расход в среднем был бы минимален (АКП). Это число - константа. Начальный период разгона от скорости 0 не учитываем. Водители ездят с разной скоростью. Задача сводится к элементарному поиску минимума.
Sorry, но на некоторое время должен покинуть рабочее место. С удовольсвием продолжу дискуссию. Можно по e-mail YurikGl@newmail.ru

← →
KSergey © (2004-02-21 10:17) [9]

"У кого что болит - тот о том и..." ;)
Автор, ау!! Так о чем речь? Народ чуть не подрался ;)

← →
Defunct © (2004-02-21 10:19) [10]

;>
2 Myrs
Зайдите на www.rambler.ru, напишите в строке поиска "Минимизация функции". найдет столько разных алгоритмов и примеров - ужас.

2 YurikGl
Ну как видите, автору просто надо было указать какую функцию он собирается минимизировать. А так похоже он вообще пропал куда-то. А мы тут спорим.

← →
YurikGl (2004-02-21 10:29) [11]

Да ладно. Всегда приятно поговорить с умными людьми. :)

P.S. Это я пока Inet у людей настраиваю - отвечаю.

← →
KSergey © (2004-02-21 10:37) [12]

Т.е. не понял: умные - это кто?

← →
YurikGl (2004-02-21 10:44) [13]

Поименный список?

← →
Myrs (2004-02-21 16:42) [14]

Неточно выразился, наверное... Мне нужен компонент/алгоритм типа надстройки в Excel "Поиск решений". Т.е., например, функция вида x^2+y^2+xy при огрничениях x+y<1, x>0, y>0. В общем, квадратичное программирование...

Уравнение что-ли решить?

Или найти минимум при этих ограничениях?

← →
Myrs (2004-02-21 17:58) [17]

Найти минимум (максимум)...

Методом пошагового спуска, как я и описал. Просто при спуске просматриваешь что-бы текущая точка не выходила за допустимые границы. Советую алгорим запускать несколько раз с разных углов области. Что-бы исключить вероятность нахождения локального минимума.
P.S. Надеюсь у тебя область одна и не сильно угловатая...

Да этих методов - туева хуча! Неужели трудно инет читнуть или любой учебник?
Метод Ньютона, сплайнов, равномерного обхода сетки, метод случайного поиска (последние 2 - для глобального поиска), генетический алгоритм (моден сейчас на западе и для большого числа переменных дайет действительно хорошие результаты)

Минимизация функции Найти похожие ветки