OPTPV_20141202 01

Zhrnutie prednášky

Prednáška predstavuje celočíselné a binárne optimalizačné problémy, kde okrem spojitých premenných vystupujú aj celočíselné rozhodovacie premenné. Vysvetľuje sa, že celočíselnosť premenných spôsobuje nekonvexnosť úlohy, čo výrazne sťažuje jej riešenie, aj keď účelová funkcia a obmedzenia sú samy osebe konvexné. Ukazuje sa, že v takom prípade je možné dosiahnuť globálne optimum vyskúšaním všetkých kombinácií celočíselných premenných (extenzívna enumerácia), pretože pre pevné hodnoty deltas sa úloha redukuje na konvexný problém. Ďalej sa preberá prevod celočíselných premenných na binárne pomocou binárneho a unárneho kódovania, pričom sa porovnáva ich efektívnosť nie podľa počtu binárnych premenných, ale podľa počtu prípustných kombinácií, ktoré musí riešič preskúmať.

• - Celočíselné optimalizačné úlohy obsahujú spojité premenné x aj celočíselné premenné delta s hornou hranicou.
• - Celočíselnosť premenných robí úlohu nekonvexnou, aj keď je účelová funkcia a obmedzenia konvexné.
• - Pri konvexnej účelovej funkcii a obmedzeniach možno extenzívnou enumeráciou (vyskúšaním všetkých kombinácií deltas) garantovať nájdenie globálneho optima.
• - Pre nekonvexné funkcie neexistuje žiadna garancia nájdenia globálneho optima.
• - Binárne optimalizačné úlohy sú špeciálnym prípadom, kde delta nadobúda len hodnoty 0 alebo 1, a možno nimi kódovať aj všeobecné celé čísla.
• - Existujú dva spôsoby kódovania celých čísel do binárnych premenných: binárne (log2) a unárne kódovanie.
• - Zložitosť riešenia problému nezávisí len od počtu binárnych premenných, ale hlavne od počtu prípustných kombinácií, ktoré treba preskúmať — unárne kódovanie môže byť efektívnejšie napriek vyššiemu počtu premenných.

Zhrnutie pripravené s pomocou AI z prepisu videa.