софт для глобальной оптимизации

[allchemist]

Хочу протестировать свой велосипед на тему глобальной оптимизации (роевые модели) на задачах большой размерности.

Допустим, есть такая тестовая задача:

оптимизируемая функция:
$f(\vec{x})=\sum\limits_{i=0}^n(x_i-1)^2 - \sum\limits_{i=1}^n(x_ix_{i-1})$,
n - размерность вектора x (число аргументов), путь равно 100.
стартовое значение $\forall x_i = 0$, поиск в диапазоне $n^2=10000$

Хочется узнать, насколько хорошо такую задачу решит качественный софт (интересует что-нибудь большее, чем отжиг, например, ГА).

Поэтому вопрос. Чем стоит воспользоваться, чтобы не особо мучиться с компилянием, чтением манов и т.д. Да, что-нибудь открытое/свободное хотелось бы, матлабом не владею.

Нашел в сети кучу поделий на эту тему, в виде Си-кода или скриптов для matlab (=> scilab), R и проч., но все они либо не работают, либо тестовая функция прибита в коде множеством гвоздей.

Хотелось бы что-нибудь такое, где можно просто вбить функцию и насладиться результатом. :)

[dmd]

allchemist в сообщении #335831 писал(а):

оптимизируемая функция:
$f(\vec{x})=\sum\limits_{i=0}^n(x_i-1)^2 - \sum\limits_{i=1}^n(x_ix_{i-1})$,

min, max, minimax, maximin?

allchemist в сообщении #335831 писал(а):

стартовое значение $\forall x_i = 0$, поиск в диапазоне $n^2=10000$

$\forall i ~ x_i \in [0,10000]$?

[yk2ru]

"MOPSO-CD" - такое было среди находок?

[Андрей1]

В mathematica встроен очень хороший глобальный оптимизатор Minimize[]

[allchemist]

dmd
минимизация. да, можно для примера ограничиться положительными числами, т.к. решений с отрицательными там не будет.

yk2ru
ух, он скомпилировался с первого раза, да еще и PSO :)
там надо вставлять свою функцию в заголовочный файл и добавлять ее в switch функции evaluate, так?

Андрей1
мои промытые и поgnuтые мозги отказываются воспринимать проприетарный софт, даже и доступный с торрентов :)
кстати, какой там метод используется?

[dmd]

allchemist в сообщении #335831 писал(а):

$f(\vec{x})=\sum\limits_{i=0}^n(x_i-1)^2 - \sum\limits_{i=1}^n(x_ix_{i-1})$,
n - размерность вектора x (число аргументов), путь равно 100.

Заметьте, согласно формуле размерность задачи не $100$, а $101$.

allchemist в сообщении #335831 писал(а):

Хотелось бы что-нибудь такое, где можно просто вбить функцию и насладиться результатом. :)

Мат-ка

S={Sum[(x_i-1)^2,{i,0,100}]-Sum[x_i x_{i-1},{i,1,100}]};X={};
For[i=0,i<=100,i++,S=Join[S,{0<=x_i<=10000}];X=Join[X,{x_i}]];
NMinimize[S,X]

моментально даёт ответ

{-176750.,{x_0\to 101.,x_1\to 200.,x_2\to 297.,x_3\to 392.,x_4\to 485.,x_5\to 576.,x_6\to 665.,x_7\to 752.,x_8\to 837.,x_9\to 920.,x_{10}\to 1001.,x_{11}\to 1080.,x_{12}\to 1157.,x_{13}\to 1232.,x_{14}\to 1305.,x_{15}\to 1376.,x_{16}\to 1445.,x_{17}\to 1512.,x_{18}\to 1577.,x_{19}\to 1640.,x_{20}\to 1701.,x_{21}\to 1760.,x_{22}\to 1817.,x_{23}\to 1872.,x_{24}\to 1925.,x_{25}\to 1976.,x_{26}\to 2025.,x_{27}\to 2072.,x_{28}\to 2117.,x_{29}\to 2160.,x_{30}\to 2201.,x_{31}\to 2240.,x_{32}\to 2277.,x_{33}\to 2312.,x_{34}\to 2345.,x_{35}\to 2376.,x_{36}\to 2405.,x_{37}\to 2432.,x_{38}\to 2457.,x_{39}\to 2480.,x_{40}\to 2501.,x_{41}\to 2520.,x_{42}\to 2537.,x_{43}\to 2552.,x_{44}\to 2565.,x_{45}\to 2576.,x_{46}\to 2585.,x_{47}\to 2592.,x_{48}\to 2597.,x_{49}\to 2600.,x_{50}\to 2601.,x_{51}\to 2600.,x_{52}\to 2597.,x_{53}\to 2592.,x_{54}\to 2585.,x_{55}\to 2576.,x_{56}\to 2565.,x_{57}\to 2552.,x_{58}\to 2537.,x_{59}\to 2520.,x_{60}\to 2501.,x_{61}\to 2480.,x_{62}\to 2457.,x_{63}\to 2432.,x_{64}\to 2405.,x_{65}\to 2376.,x_{66}\to 2345.,x_{67}\to 2312.,x_{68}\to 2277.,x_{69}\to 2240.,x_{70}\to 2201.,x_{71}\to 2160.,x_{72}\to 2117.,x_{73}\to 2072.,x_{74}\to 2025.,x_{75}\to 1976.,x_{76}\to 1925.,x_{77}\to 1872.,x_{78}\to 1817.,x_{79}\to 1760.,x_{80}\to 1701.,x_{81}\to 1640.,x_{82}\to 1577.,x_{83}\to 1512.,x_{84}\to 1445.,x_{85}\to 1376.,x_{86}\to 1305.,x_{87}\to 1232.,x_{88}\to 1157.,x_{89}\to 1080.,x_{90}\to 1001.,x_{91}\to 920.,x_{92}\to 837.,x_{93}\to 752.,x_{94}\to 665.,x_{95}\to 576.,x_{96}\to 485.,x_{97}\to 392.,x_{98}\to 297.,x_{99}\to 200.,x_{100}\to 101.}}

но не уверен, глобальный ли оптимум она находит.

[allchemist]

здорово, спасибо.

а расшифровать слегка можете?
что такое x_{}, \to, первая пятизначная цифра, ".,". это целые числа?
кстати, оптимизация проводилась на множестве целых чисел или с плавающей запятой? если с плавающей, то это крутой результат, я так понимаю.

[dmd]

Первое число $-176750.$ - найденное значение целевой функции, дальше следуют значения составляющих оптимального вектора $\vec{x}$. На x_{}, \to не обращайте внимания, это специфичная форма ответа. В числах присутствует точка, следовательно они явно не целые.

[yk2ru]

allchemist в сообщении #336024 писал(а):

ух, он скомпилировался с первого раза, да еще и PSO :)там надо вставлять свою функцию в заголовочный файл и добавлять ее в switch функции evaluate, так?

По аналогии вставить своё, и задать номер для переходов в операторах switch, также вроде границы задаются для переменных.

[mserg]

У меня такое чуйство, что данная квадратичная форма - положительно определенная и локальный минимум совпадает с глобальным, т.е. оптимум найден.

[allchemist]

ок, спасибо всем большое.

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

[mserg]

Есть библиотека задач globallib - несколько сотен нелинейных задач с непрерывными переменными. Думаю что Вы ее найдете без труда. Часть задач имеют доказанные оптимумы.

Хорошо бы, чтобы был ресурс, куда действующие инженеры регистрировали бы свои задачи. Тогда бы разработчики могли ориентироваться на реальную жизнь, а не на выдуманные примеры. Пора бы нам уже организоваться...

[dmd]

mserg в сообщении #336180 писал(а):

У меня такое чуйство, что данная квадратичная форма - положительно определенная и локальный минимум совпадает с глобальным, т.е. оптимум найден.

Видимо, да. В ampl + cplex аналогично решилось:

D:\amplcml>copy allch.mod con
set I := {0..100};
set J := {1..100};

var x {i in I}  >= 0, <= 10000;

minimize f:
         sum {i in I} (x[i]-1)^2 - sum {i in J} x[i]*x[i-1];
Скопировано файлов:         1.

D:\amplcml>ampl
ampl: model allch.mod;
ampl: option solver cplex;
ampl: solve;
CPLEX 11.2.0: optimal solution; objective -176750
9 QP barrier iterations
No basis.
ampl: display x;
x [*] :=
  0  101    15 1376    30 2201    45 2576    60 2501    75 1976    90 1001
  1  200    16 1445    31 2240    46 2585    61 2480    76 1925    91  920
  2  297    17 1512    32 2277    47 2592    62 2457    77 1872    92  837
  3  392    18 1577    33 2312    48 2597    63 2432    78 1817    93  752
  4  485    19 1640    34 2345    49 2600    64 2405    79 1760    94  665
  5  576    20 1701    35 2376    50 2601    65 2376    80 1701    95  576
  6  665    21 1760    36 2405    51 2600    66 2345    81 1640    96  485
  7  752    22 1817    37 2432    52 2597    67 2312    82 1577    97  392
  8  837    23 1872    38 2457    53 2592    68 2277    83 1512    98  297
  9  920    24 1925    39 2480    54 2585    69 2240    84 1445    99  200
 10 1001    25 1976    40 2501    55 2576    70 2201    85 1376   100  101
 11 1080    26 2025    41 2520    56 2565    71 2160    86 1305
 12 1157    27 2072    42 2537    57 2552    72 2117    87 1232
 13 1232    28 2117    43 2552    58 2537    73 2072    88 1157
 14 1305    29 2160    44 2565    59 2520    74 2025    89 1080
;
ampl: exit;

[dmd]

На сервере NEOS можно потестировать разные недогнутые солверы. Если исходную задачу сделать кубической, количество неизвестных увеличить до 10001, добавить 10000 нелинейных ограничений, то с такой задачей справятся только солверы KNITRO и LOQO.

[allchemist]

спасибо всем большое.

> KNITRO и LOQO
а есть ли какие-нибудь свободные аналоги этих двух пакетов?