70. Метод решения задач выпуклого программирования (условная минимизация) на выбор: метод условного градиента, метод проекции градиента, метод штрафных функций

М н‑во GRn наз‑ся выпуклым, если x1,x2 G и (0,1) выполняется x1+(1‑)x2G. Пустое мн-во и мн-во, состоящее из одной точки считаются выпуклыми.

выпуклое не выпуклое

Ф-ия f(x) наз‑ся выпуклой на выпуклом мн-ве GRn, если x1,x2 G, (0,1) выполняется: f(x1 + (1-)x2)  f(x1) + (1-)f(x2). Ф‑ия наз‑ся строго выпуклой, если неравенство – строгое.

П остановка задачи выпуклого программирования: задача мат. программирования вида наз‑ся задачей выпуклого программирования, если f(x) – выпуклая ф‑ия и DRn – выпуклое мн‑во.

М етод штрафных функций решает задачу условной минимизации

D = {xRn: fi(x)bi, i=1,…,m}

М етод сводит решение исходной задачи к последовательному решению задач безусловной минимизации.

Положим

Методы заключаются в следующем:

в ыбирается числовая последовательность {k}, k=0,1,… такая, что k > 0 k, .

Н а k-ом шаге метода строится вспомогательная функция и в качестве точки xk выбирается точка минимума ф‑ии на всем пр‑ве Rn.

Все методы этого класса отл‑ся дгур от друга способом задания штрафных ф‑ий. Эти методы сходящиеся.

доминирующих над др. дележами (с-ядро) или множеству не доминирующих друг над другом дележей, которые в совокупности

доминируют над всеми остальными дележами (решения по Нейману - Моргенштерну) или к множеству дележей, в которых в некотором смысле минимизируется «недовольство» коалиций (n-ядро) и т. д. Некоторые из принципов оптимальности не всегда реализуются; другие реализуются иногда неоднозначно. Нахождение реализаций часто затруднительно. Т. о., математическая проблема установления оптимального поведения в кооперативных играх является весьма сложной как принципиально, так и технически.

71. Многокритериальная оптимизация. Матричные игры. Кооперативные игры.

1. Многокритериальная оптимизация.

Часто возникает задача обеспечить оптимальность объекта проектирования одновременно по нескольким критериям оптимальности . Обычно эти критерии противоречивы и оптимизация по каждому из них приводит к различным значениям вектора варьируемых параметров . Поэтому выделяется отдельный класс задач многокритериальной оптимизации.

Постановка задачи многокритериальной оптимизации.

Будем называть каждый из скалярных критериев оптимальности частным критерием оптимальности. Совокупность частных критериев оптимальности будем называть векторным критерием оптимальности. Положим, что ставится задача минимизации каждого из частных критериев оптимальности ф1(X), ф2(X), ... , фs(X) в одной и той же области допустимых значений . Решение задачи многокритериальной оптимизации в общем случае не является оптимальным ни для одного из частных критериев, а оказывается некоторым компромиссом для вектора в целом. Задачу многокритериальной оптимизации будем записывать в виде Где — множество допустимых значений вектора варьируемых параметров Х. Прежде, чем применить тот или иной метод решения задачи (1), обычно производят нормализацию частных критериев, приводя все частные критерии оптимальности к одному масштабу. Чаще всего при этом используют относительные отклонения частных критериев от их минимальных значений:

Где

Метод относится к классу стохастических методов оптимизации

Сохраним за нормализованными частными критериями оптимальности обозначения .