Преобразование задачи нелинейного программирования при помощи функций штрафов в последовательность задач безусловной оптимизации

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

В общем виде такое преобразование осуществляется при помощи специальным образом сконструированной функции, называемой штрафной функцией (функцией нагружения и т. д.):

Ф(х, cr) = Q(x) + R(х, cr) = Q (X) + сrψ(х). (7.77)

Прочитать остальную часть записи »

Постановка задачи устойчивости предельных режимов

Рассмотрим однородный марковский процесс zt, задаваемый рекуррентным соотношением вида (1.1.5), т. е.

zt+1 = F(zt, ξt), t≥0. (1)

Хотя результаты, приводимые в этой и следующей главах, имеют более общий характер, все же всюду будет считаться, что zt задается именно соотношением вида (1). Будем смотреть на это соотношение как на преобразование «управляющей» последовательности {ξt} и начального состояния z0 в последовательность {zt} (удобно начальное состояние z0 считать, с одной стороны, управляющим параметром, а с другой — управляемым).
Прочитать остальную часть записи »

Использование коллектива независимых стохастических автоматов как некоторой системы поисковой оптимизации

Другой подход к решению задачи локализации точки глобального минимума X* многопараметрической функции Q (x1, x2, …, xn) связан с использованием коллектива независимых стохастических автоматов как некоторой системы поисковой оптимизации.
Прочитать остальную часть записи »

Сходимость и метрики

Материал данного поста является вспомогательным, хотя и весьма важным. Поэтому здесь приводятся доказательства не всех формулируемых утверждений. Кроме того, здесь не будут приводиться обобщения (иногда достаточно содержательные) этих утверждений.

Повсюду в этом посте будем предполагать, что все рассматриваемые случайные величины принимают значения в метрическом пространстве Ψ, наделенном метрикой ρ. В дальнейшем в качестве таких случайных величин будут рассматриваться состояния процесса zt, для которого соответствующие метрики введены в марковских процессах с дискретным временем.
Прочитать остальную часть записи »

Автоматная оптимизация

Рассмотрим обобщение метода F21 поиска точки глобального минимума произвольной кривой с помощью стохастического автомата на случай многопараметрических положительных функций Q (х).

Каждый интервал [0, ci] изменения i-й переменной разделим на Ki отрезков равной длины

ωi = ci/Ki, i =1, 2, …, n. (6.35)

Прочитать остальную часть записи »

Теоремы достижимости и ограниченности

Теорема 1. Если распределение {a(t)}, t ≥ 1, арифметическое с шагом 1, {a(t)}∈NP(N, а), и μ = ∑ta(t) < ∞,то справедлива оценка Прочитать остальную часть записи »

Особенности работы в режиме SQL Server.

В таких СУБД (т.е. в SQL Server) часть функций по управлению базой данных оформляется в виде объектов, хранящихся в самой базе данных, а сервер реализует эти вот возможности в процессе работы.

• Во-первых, для этих целей используются процедуры базы данных, к которым возможно указать права доступа и использования.
Прочитать остальную часть записи »

Обобщение методов оптимальных покрытий на многомерный случай

Будем предполагать, что минимизируемая функция Q(x) в задаче принадлежит классу KL функций, удовлетворяющих условию типа условия Липшица с известной константой L:

|Q(x1) — Q(x2)| ≤ Lρ(x1, x2), x1, x2∈Dx, (6.10)

Прочитать остальную часть записи »

Общие требования к топкам котлов

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

• Быть технологичной в изготовлении
• Быть монтажепригодной (удобство монтажа)
• Обеспечивать удобство эксплуатации и ремонта
• Обеспечивать экономичное сжигание расчетных видов топлив (в заданном диапазоне нагрузок котла)
    • Газ, мазут — 30…100%Dном
    • Твердое топливо + ТШУ — 50…100%Dном
    • Твердое топливо + ЖШУ — 70…100%Dном
Прочитать остальную часть записи »

Оценка скорости сходимости в теореме восстановления

Цель настоящего примера — показать, как свойство достижимости может быть использовано в несколько необычной ситуации— для оценки скорости сходимости. Пусть {ξi} — последовательность независимых одинаково распределенных случайных величин, принимающих следующие значения:
Sn = ∑ξi, n ≥ 1; a(t) = P {ξi=t}, H(t) = P {ξi≥t}; h(t) = P{∪(Si = t)}, t = 1,2 ..
Прочитать остальную часть записи »

Класс самодвойственных функций и его замкнутость относительно суперпозиции. Критерий самодвойственности. Лемма о несамодвойственной функции.

Определение: Функция, совпадающая со своей двойственной функцией, называется самодвойственной.

Замечание: Если функция f(x1, x2,…,xn) самодвойственна, то функция ¬f также самодвойственна, то есть
(⌈f(x1, x2,…,xn))*=⌈(⌈f(⌈x1,…, ⌈xn))= [функция самодвойственна f=f*] = ⌈f(x1, …, xn).
Прочитать остальную часть записи »

Усиленный закон больших чисел

Поскольку результаты данного поста использоваться далее не будут, мы их приведем без доказательства. Будет рассмотрен лишь случай непрерывного времени. Распространение на дискретное время очевидно.

Пусть μ и μ* — стационарные распределения, рассмотренные в теореме 5.4. Пусть f(z) —некоторая функция, интегрируемая по распределению μ. Рассмотрим последовательность случайных величин (ξn}, где

ξn = ∫f(zt)dt, n ≥ 1, τ0(1) = 0, (1)

Прочитать остальную часть записи »

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

Пусть минимизируемая функция Q (х) зависит от небольшого числа переменных (n ≤ 3). В этом случае для решения задачи поиска глобального минимума x* непрерывной функции Q (х), определенной в n-мерном гиперпараллелепипеде Dx = {x|ai ≤ xi ≤ bi , i = 1, 2,…, n}

min Q(x1, x2, …, xn), (6.1)

Прочитать остальную часть записи »

Ограниченность для КЛП

Приведем сначала вариант теоремы 3.1 для процессов с непрерывным временем. Здесь, как и раньше, через ηQ обозначим момент первого достижения множества Q⊂Z, а через θR — момент первого выхода из множества {||z|| < R}. Прочитать остальную часть записи »

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

При решении задачи оптимального проектирования часто приходится иметь дело с математическими моделями, в которых не имеется аналитических выражений для первых производных минимизируемой функции Q(х). В связи с чем поиск оптимального решения х* приходится вести по результатам вычислений функции Q (х). Методы, которые используют для выбора точки очередного испытания хr информацию только о значениях функции Q (х), называются методами прямого поиска (методами нулевого порядка, методами минимизации без вычисления производных).
Прочитать остальную часть записи »

Достижимость для КЛП

Мы сохраним в этом посте основные обозначения принятые ранее. Именно, будет рассматриваться случайный момент времени ηQ* первого достижения множества Q, определяемый формулой

ηQ = inf {t:zt∈Q, t>0}.

Прочитать остальную часть записи »

Квазиньютоновские методы минимизации

Рассмотрим класс алгоритмов, которые основаны на квадратичной аппроксимации минимизируемой функции Q (х) в Δ-окрестности каждого приближения xr разложением в ряд Тейлора. В связи с тем, что для определения очередного приращения Δr эти алгоритмы требуют вычисления первых и вторых производных функций Q (х), они получили название методов второго порядка.
Прочитать остальную часть записи »

Ограниченность для процессов с дискретным временем

Если в предыдущем посте изучались некоторые свойства времени первого возвращения траекторий zt, то здесь будут анализироваться свойства, связанные со значениями, принимаемыми процессом zt, хотя эти свойства и тесно связаны между собой.
Прочитать остальную часть записи »

Градиентные методы спуска

Определение минимального значения многопараметрической функции Q (х), заданной в n-мерном евклидовом пространстве связано с решением задачи безусловной оптимизации:

min Q(x1, х2,…, xn). (5.1)

Здесь каждая переменная xi, i= 1, 2, …, n, может принимать значения от -∞ до +∞. Предположим, что функция Q (х) является унимодальной функцией, для которой в каждой точке х может быть получено с помощью градиента ∇Q(х)= {∂Q/∂x1, …, ∂Q/∂xn), а при необходимости и гессиана (матрицы вторых производных)
Прочитать остальную часть записи »

Достижимость для процессов с дискретным временем

Пусть Q — некоторое подмножество Z. Обозначим через ηQ момент первого достижения множества Q траекторий рассматриваемого процесса zt, т. е.

ηQ = min{t: zt∈Q, t>0}; (1)

Отметим, что с формальной точки зрения вместо момента первого достижения можно было бы рассматривать момент первого выхода, поскольку ηQ = θZ\Q. Однако, как было сказано во введении, изучение указанных случайных величин приводит к различным прикладным задачам.
Прочитать остальную часть записи »

Автомат Буша-Мостеллера

Стратегия поиска точки глобального минимума х* по алгоритму F20*с помощью автомата Буша—Мостеллера сводится к следующей последовательности действий.

1. Задаются одинаковые значения вероятностей выбора состояний автомата pj(r) = 1/М, j = 1,2, …, М, и принимается Qj* = A для всех j = 1, 2, …, М, где A — положительное большое число.
Прочитать остальную часть записи »

Равномерно интегрируемые случайные величины

Рассмотрим некоторое множество Ψ действительных случайных величин. Общий элемент этого множества обозначим ξ. Поскольку нас будут интересовать лишь маргинальные (частные) распределения случайных величин ξ∈Ψ, то безразлично, заданы эти величины на одном вероятностном пространстве или нет. Предположим, что у всех ξ∈Ψ существуют конечные средние Мξ.
Прочитать остальную часть записи »

Поиск глобального минимума кривой с помощью стохастических автоматов

Рассмотрим класс алгоритмов, поиск точки глобального минимума X* в которых основан на теории автоматов.

Под автоматом будем понимать динамическую систему, которая в дискретные моменты времени r = 1, 2 ,3, …, воспринимая на входе сигнал у(r), изменяет свое внутреннее состояние S (r) согласно уравнению:

S(r) = φ1[у(r), S (r — 1)] S(0) = S0. (4.75)

Прочитать остальную часть записи »

Схема резервирования с конечным временем переключения элементов

Пример схемы резервирования с конечным временем переключения элементов.

Рассмотрим следующую систему (рис. 5), состоящую из n идентичных элементов.



В полностью исправном состоянии в системе имеются m элементов, находящихся на рабочих местах («рабочих» элементов), n—m элементов, находящихся в нагруженном (горячем) резерве («резервных» элементов). При выходе какого-либо рабочего элемента из строя он мгновенно поступает на одно из r ремонтных мест, r ≤ n, если имеется свободное, либо становится в очередь на ремонт. Замена отказавших элементов происходит следующим образом. Если в наличии есть хотя бы один резервный элемент, а общее количество работающих и подключаемых элементов меньше m, то этот резервный элемент немедленно начинает переключаться с резервного места на рабочее. Время переключения каждого отдельного элемента — случайная величина с функцией распределения 1—е-vx. Дополнительно предположим, что число одновременно переключаемых элементов не может превышать некоторого числа s. Элементы системы являются ненадежными и могут отказывать как на рабочих местах, так и в резерве и в состоянии переключения. Будем называть элемент исправным, если он находится в одном из этих трех состояний: рабочем, резервном и переключения. Время пребывания элемента в исправном состоянии является, по предположению, случайной величиной с функцией распределения 1-е-λx. Время ремонта отдельного элемента также случайно и имеет функцию распределения 1-е-μx. Все перечисленные случайные величины независимы в совокупности.
Прочитать остальную часть записи »

Метод кусочно-кубической и кусочно-линейной аппроксимации.

Процедура поиска точки глобального минимума х* аппроксимирующей модели может быть упрощена, если в качестве математической модели использовать кусочно-кубическую кривую SN(х), проходящую через точки испытаний (xi, Q(xi)), i = 1, 2, …, N, и моделирующую поведение функции Q (х) на отдельных отрезках интервала |a, b| полиномами третьей степени Р3(х) = ∑αkixk. В этом случае поиск точки глобального минимума х* произвольной кривой Q (х) может быть осуществлен с помощью метода кусочно-кубической аппроксимации F15, в котором точки испытаний на каждом k-м шаге выбираются независимо от информации о поведении функции Q(x) и равномерно располагаются на интервале [a, b]:

xi(k) = a + i(b-a)/(Nk-1), i = 0, 1, …, Nk — 1.

Прочитать остальную часть записи »

Пример — ненагруженное дублирование с восстановлением

Ненагруженное дублирование с восстановлением.

Данный пример можно рассматривать как развитие предыдущего примера в силу сделанного в конце его замечания.

Итак, рассмотрим дублированную систему, описанную в конце предыдущего примера. Опишем сначала работу такой системы в виде КЛП без непрерывного вмешательства случая. Поскольку функционирование системы рассматривается лишь до момента первого отказа, то будем для простоты считать «отказовые» состояния поглощающими. Но, очевидно, до момента первого отказа работа рассматриваемой системы эквивалентна работе однолинейной системы обслуживания с ожиданием, если отождествить попарно следующие понятия: отказ работающего элемента и поступление в систему очередного требования, длительность ремонта и длительность обслуживания, отказ системы и наличие в системе обслуживания более одного требования. Поэтому в качестве КЛП, описывающего изучаемую дублированную систему, можно взять КЛП примера 1.4.4, положив в нем N = 1, В = G и, считая состояния v > 1 поглощающими, объединить их в одно поглощающее состояние v = 2, |2| = 0. Тогда дополнительные координаты имеют следующий смысл:
Прочитать остальную часть записи »

Построение аппроксимирующих моделей минимизируемой функции

Рассмотрим класс алгоритмов, поиск глобального минимума по которым сводится к следующей последовательности действий:

1) проводятся испытания в точках xi, i = 1, 2,…, N, расположенных определенным образом на интервале [a, b];

2) по полученным значениям (xi, Q (xi)), i = 1,2,…, N, строится математическая модель, аппроксимирующая функцию Q (х) на интервале [a, b];
Прочитать остальную часть записи »

Укрупненная архитектура имитационной системы

Система имитационного моделирования может рассматриваться как машинный аналог сложного реального процесса.

На рис. 2.1 представлена укрупненная архитектура имитационной системы. Имитационная система должна иметь интеллектуальный интерфейс, т.е. обеспечивать удобное и эффективное взаимодействие широкого пользователя с ЭВМ.
Такой интеллектуальный интерфейс должен содержать средства дающие возможность:
Прочитать остальную часть записи »

Оценки в случае непрерывного времени

В этом посте мы обобщим результаты, полученные ранее, на случай кусочно-линейных процессов. Вновь Q будет обозначать открытое множество в пространстве состояний Z, а θQ — момент первого выхода из указанного множества. Как было доказано ранее (это доказательство без изменений переносится и на непрерывное время), при τ = θQ∧u имеет место равенство

Mz[1 — χQ(zτ)] = PzQ≤u}.

Прочитать остальную часть записи »

Параллельные методы, комбинирующие пассивные и последовательные стратегии поиска

Многопроцессорные ЭВМ открывают возможность одновременной оценки нескольких независимых значений функции Q (х) путем распараллеливания вычислений. В связи с чем для минимизации унимодальных функций могут быть построены параллельные алгоритмы поиска, в которых на каждом i-м шаге часть испытаний ni ≤ N проводится одновременно в заданной совокупности точек х1, х2, …, хn.
Прочитать остальную часть записи »





Статистика

Рейтинг@Mail.ru