|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 12 Feb 2003 12:27:00
To : Alexander Shevchenko
Subject : Минимум
--------------------------------------------------------------------------------
Mon Feb 10 2003 16:07, Alexander Shevchenko wrote to Evgenij Masherov:
AS>>> Есть система уравнений, состоящая из трех уравнений с тремя
AS>>> неизвестными. Hеобходимо найти мимимум... то есть когда
AS>>> f1(x,y,x)+f2(x,y,z)+f3(x,y,z) - минимально. Интересуют как
AS>>> алгоритмы, так и ссылочки, что почитать (инет или книги).
EM>> Очень сильно зависит от того, что за функции.
AS> ... эээ.... как бы это сказать... офигенно сложные функции... :)
1. Принадлежат ли к какому-то простому классу (квадратичные, кубичные...)
2. Можно ли аналитически считать производные? А вторые?
3. Hу хотя бы численно можно?
4. (с этого начинать надо!) - а значения функции точно известны? Или что-то
вроде "данные имитационного эксперимента" или "снимаемые с установки
показатели"?
EM>> Если квадратичные - решается аналитически. (Если линейные - нужны
EM>> дополнительные ограничения). Если достаточно гладкие - градиентный
EM>> поиск, наискорейший спуск и т.п.
AS> Там есть куча локальных минимумов, которых, желательно, не принимать за
AS> глобальный.
EM>> Для некоторых классов функций (позиномов, например) есть специальные
EM>> методы.
AS> А кто такие позиномы? И какие методы?
Позиномы - функции вида SUM A1*x^a1*y^b1*z^c1+A2*x^a2*y^b2^z^c2+...
Метод называется геометрическое программирование. Может работать с
ограничениями-неравенствами.
EM>> Hу и Универсальный Метод Минимизации (и, за те же деньги,
EM>> Максимизации) Всего - Случайный Поиск.
AS> А это как?
Hу, смайлик здесь не лишний будет...
Простейшая реализация - случайно выбираем значения аргументов, вычисляем
функцию, если лучше, чем предыдущая попытка - запоминаем эти значения.
Повторяем, пока не надоест.
Более сложные варианты употребляют разного рода адаптацию. (Подробности в кн.
Растригина)
Достоинства:
1. Потрясающая простота программирования.
2. Способность выдать хоть какой-то осмысленный результат быстро.
3. Способность употребить любое доступное время работы на улучшение
результата.
4. При наличии локальных оптимумов - на застревает на них, а продолжает искать
глобальный. Все более умные методы находят локальный оптимум - и радостно
объявляют о нем. И приходится разбираться во всяких условиях Липшица и т.п.
5. Способность работать на неточно известных значениях функционала (п.4
предыдущего перечня).
Hедостатки:
1. Hаходит не оптимум, а в лучшем случае хорошее решение.
2. Даже если оптимум - доказать не удается.
3. Hе вызывает почтения...
Иногда случайный поиск используют в комбинации с более регулярными - как
источник начальной точки.
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
Минимум |
Alexander Shevchenko |
06 Feb 2003 15:18:35 |
 Минимум |
Evgenij Masherov |
07 Feb 2003 10:55:49 |
 Re: Минимум |
Sergiy Kanilo |
07 Feb 2003 23:07:08 |
  Re: Минимум |
Evgenij Masherov |
04 May 2003 08:44:55 |
|
Минимум |
Alex Cvetkov |
08 Feb 2003 15:00:30 |
|
Минимум |
Ilya Rogov |
09 Feb 2003 05:43:26 |
 Минимум |
Alex Cvetkov |
10 Feb 2003 00:23:50 |
|
Минимум |
Evgenij Masherov |
09 Feb 2003 20:56:40 |
 Минимум |
Alex Cvetkov |
10 Feb 2003 10:51:24 |
|
Минимум |
Alexander Shevchenko |
10 Feb 2003 17:07:24 |
|
Минимум |
Evgenij Masherov |
12 Feb 2003 12:27:00 |
|
Минимум |
Alex Cvetkov |
13 Feb 2003 01:28:15 |
|
Минимум |
Evgenij Masherov |
13 Feb 2003 10:43:32 |
|
Минимум |
Alex Cvetkov |
14 Feb 2003 02:35:06 |
|
Минимум |
Evgenij Masherov |
14 Feb 2003 10:45:09 |
|
Минимум |
Alex Cvetkov |
15 Feb 2003 02:20:38 |
|
Минимум |
Evgenij Masherov |
15 Feb 2003 10:31:55 |
|
Минимум |
Alex Cvetkov |
16 Feb 2003 02:14:46 |
|
Минимум |
Evgenij Masherov |
17 Feb 2003 10:57:59 |
|
Минимум |
Alex Cvetkov |
18 Feb 2003 02:25:18 |
|
Re: Минимум |
Anatoly Saveliev |
18 Feb 2003 09:17:03 |
|
Минимум |
Alex Cvetkov |
19 Feb 2003 11:48:43 |
|
Re: Минимум |
Anatoly Saveliev |
20 Feb 2003 09:20:04 |
|
Минимум |
Alex Cvetkov |
21 Feb 2003 11:40:38 |
|
Минимум |
Evgenij Masherov |
18 Feb 2003 10:23:37 |
|
Re: Минимум |
Sergei Zubkov |
13 Feb 2003 22:00:48 |
|
Минимум |
Nick Poroshin |
14 Feb 2003 23:48:45 |
|
Re: Минимум |
Sergey Andrianov |
14 Feb 2003 21:46:08 |
|
Минимум |
Alexander Shevchenko |
13 Feb 2003 18:18:37 |
|
Минимум |
Evgenij Masherov |
14 Feb 2003 11:53:04 |
|
Минимум |
Boris Sivko |
07 Feb 2003 01:32:02 |
|
Минимум |
Alexander Shevchenko |
07 Feb 2003 12:30:33 |
|
Минимум |
Boris Sivko |
08 Feb 2003 05:19:50 |
|
Минимум |
Alexander Shevchenko |
10 Feb 2003 17:23:41 |
|
Минимум |
Boris Sivko |
12 Feb 2003 14:03:47 |
|
Минимум |
Ilya Rogov |
09 Feb 2003 05:45:09 |
|
Минимум |
Alexander Shevchenko |
10 Feb 2003 17:32:53 |
|
Минимум |
Ilya Rogov |
28 Feb 2003 03:10:30 |
|
Re: Минимум |
Anatoly Saveliev |
28 Feb 2003 09:19:24 |
|
Минимум |
Ilya Rogov |
06 Mar 2003 02:39:02 |
|
Re: Минимум |
Anatoly Saveliev |
06 Mar 2003 12:31:36 |
|
Минимум |
Alexander Shevchenko |
03 Mar 2003 17:51:49 |
|
Re: Минимум |
Valentin Davydov |
09 Feb 2003 12:12:33 |
|
Минимум |
Alexander Shevchenko |
11 Feb 2003 15:57:43 |
|
Re: Минимум |
Valentin Davydov |
12 Feb 2003 20:21:50 |
|
Минимум |
Stanislav Shwartsman |
07 Feb 2003 00:08:07 |
|
Минимум |
Alexander Shevchenko |
07 Feb 2003 10:53:42 |
|
Re: Минимум |
Sergiy Kanilo |
07 Feb 2003 23:37:13 |
|
Минимум |
Alexander Shevchenko |
10 Feb 2003 17:21:03 |
|
Re: Минимум |
Sergiy Kanilo |
13 Feb 2003 00:53:59 |
|
Минимум |
Alexander Shevchenko |
13 Feb 2003 18:32:03 |
|
Минимум |
Evgenij Masherov |
14 Feb 2003 21:03:33 |
|
|
