Геометрическое программирование

Определение. Функция вида

f(t) = ∑_1≤i≤mu_i(t), t=(t₁,...,t_m), где u_i(t) = c_i t_j^a(i,j), c_i>0, i=1,...,n (4.5.1)

называется позиномом, матрица A={a_ij} называется матрицей экспонент данного позинома.

Простейшим случаем позинома является полином (многочлен) от нескольких переменных. Если в матрице экспонент есть отрицательные элементы, позином не является полиномом.

Геометрическим программированием называется раздел математики, в котором исследуются задачи минимизации позиномов на множествах, заданных при помощи позиномных неравенств:

f₀(t₁,...,t_m) → min
f_k(t₁,...,t_m) ≤ 1, k=1,..., p;
t_j > 0, j=1,...,m. (4.5.2)

где f_k(t) = ∑_{i∈ I(k)} c_i t_j^a(i,j), I(k) = I_k = [m_k, m_k+1,..., n_k], k=0,..., p;

m₀=1, m₁=n₀+1, m_k=n_k-1+1, n_p= n.

Матрица A={a_ij} при этом состоит из матриц экспонент всех позиномов, входящих в задачу, и называется матрицей экспонент задачи (4.5.2).

Введем в задачу переменные u_i = c_i t_j^aij, i = 1,…,n. Получаем (4.5.3)

Введем новые переменные: x_j = ln t_j, j=1,…,m; x_m+i= ln u_i, b_i = - ln c_i, i=1,...,n. (4.5.4)

В этих переменных задачу (4.5.3) можно записать в виде следующей задачи выпуклого программирования: (4.5.5)

Применим теорию двойственности, для чего построим функцию Лагранжа (с учетом того, что λ₀=1):

L(x,λ, μ) = ∑ _i∈I(0) e^x(m+i)+ ∑_1≤k≤p λ_k (∑ _i∈I(k) e^x(m+i) - 1)+∑_1≤i≤n μ_i (∑_1≤j≤ma_ijx_j - x_m+i - b_i).

После перегруппировки слагаемых получаем:

L(x,λ, μ) = ∑_1≤i≤n {λ_k(i) e^x(m+i) - μ_i (x_m+i + b_i)} + ∑_1≤i≤n μ_i ∑_1≤j≤ma_ijx_j - ∑_1≤k≤p λ_k,

где k=k(i) <=> i∈I_k.

Запишем задачу, двойственную к задаче (4.5.5):

ψ(λ, μ) = inf {L(x,λ, μ) | x∈R^n+m} → max. (4.5.6)

Поскольку все слагаемые функции L зависят от разных переменных x, для нахождения inf найдем наименьшее значение каждого слагаемого отдельно.

А) По переменным x_j, j=1,…,m функция L линейна, поэтому по этим переменным inf L > -∞ тогда и только тогда, когда все коэффициенты перед x_j равны нулю:

для всех j=1,…,m выполняется равенство ∑_1≤i≤n μ_i a_ij =0, или A^Tμ=0. (4.5.7)

При выполнении этого условия

L(x,λ, μ) = ∑_1≤i≤n {λ_k(i) e^x(m+i) - μ_i (x_m+i + b_i)} - ∑_1≤k≤p λ_k.

Б) По переменным x_m+i, i=1,…,n: L_x(m+i) = λ_k(i) e ^x(m+i) - μ_i = 0, откуда следует, что для всех i переменные μ_i неотрицательны, причем λ_k(i)=0 <=> μ_i=0.

При λ_k(i)>0 наименьшее значение функции L по переменной x_m+i достигается при x_m+i = ln(μ_i /λ_k(i)).

Таким образом, двойственная задача (4.5.6) имеет вид

ψ(λ, μ) = ∑_1≤i≤nμ_i {1 - ln(μ_i /λ_k(i)) - b_i} - ∑_1≤k≤p λ_k → max, A^Tμ=0, λ, μ ≥ 0. (4.5.8)

Пусть μ_i=vδ_i , v > 0, причем ∑_1≤i≤nδ_i = 1. Тогда (с учетом того, что b_i = - ln c_i)

ψ = v ∑_1≤i≤n{δ_i + δ_iln{c_iλ_k(i) /(v μ_i)} - ∑_1≤k≤p λ_k = v + v ∑_1≤i≤nδ_iln{c_iλ_k(i) / δ_i} - v ln v - ∑_1≤k≤p λ_k. (4.5.9)

Обозначим D=∑_1≤i≤nδ_iln{c_iλ_k(i) / δ_i}. Тогда (4.5.8) запишется в виде

ψ = v(1+D) – v ln v - ∑_1≤k≤p λ_k → max, A^Tδ=0, λ, δ ≥ 0, ∑_1≤i≤nδ_i = 1. (4.5.10)

На переменную v ограничений нет, поэтому найдем максимум по этой переменной:

ψ_v = 1+D – ln v – 1 = D – ln v = 0, откуда v* = e ^D.

ψ(v*) = v*(1+D) – v*D - ∑_1≤k≤p λ_k= v* - ∑_1≤k≤p λ_k = e ^D - ∑_1≤k≤p λ_k = ∏_1≤i≤n(c_iλ_k(i) / δ_i)^δ(i) - ∑_1≤k≤p λ_k

Обозначим σ_k = ∑_i∈I(k) δ_i, тогда ψ(v*) = ∏_1≤i≤n(c_i / δ_i)^δ(i) ∏_1≤k≤pλ_k^σ(k)- ∑_1≤k≤p λ_k.

В итоге двойственная задача переходит в задачу:

ψ = ∏_1≤i≤n(c_i / δ_i)^δ(i) ∏_1≤k≤pλ_k^σ(k)- ∑_1≤k≤p λ_k → max;

A^Tδ=0, λ, δ ≥ 0, = 1, σ_k = ∑_i∈I(k) δ_i. (4.5.11)

Перейдем к вычислению max по переменным λ_r, r >1.

ψ_λ(r) = ∏_1≤i≤n(c_i / δ_i)^δ(i) ∏_1≤k≤pλ_k^σ(k) σ_r / λ_r – 1 = 0. (4.5.12)

Обозначим С = ∏_1≤i≤n(c_i / δ_i)^δ(i) ∏_1≤k≤pλ*_k^σ(k). Тогда из (4.5.12) получаем

λ*_r = С σ_r . (4.5.13)

Подставляя эти значения в определение С, находим:

С = ∏_1≤i≤n(c_i / δ_i)^δ(i) ∏_1≤k≤p(С σ_k )^σ(k) = С ^{∑ σ(k)} ∏_1≤i≤n(c_i / δ_i)^δ(i) ∏_1≤k≤p(σ_k )^σ(k) = С ^{1 - σ(0)} F, или

С^σ(0) = F = ∏_1≤i≤n(c_i / δ_i)^δ(i) ∏_1≤k≤p(σ_k )^σ(k), и в результате, C = F ^1/σ(0)_.

В итоге, получаем:

ψ(λ*) = С - ∑_1≤k≤p λ*_k = С - ∑_1≤k≤pС σ*_k= С σ*₀. (4.5.14)

После подстановки найденного значения для С и тождественных преобразований получаем, что

ψ(λ*) = ∏_1≤i≤n(c_iσ₀ / δ_i)^{δ(i) / σ(0)} ∏_1≤k≤p(σ_k / σ₀ )^{σ(k) / σ(0)}. (4.5.15)

Обозначим α_i = δ_i/σ₀; β_k = ∑_i∈I(k)α_i = σ_k/σ₀.

Окончательный вид двойственной задачи (4.5.6) в этих переменных будет следующим:

ψ =∏_1≤i≤n(c_i / α_i)^α(i) ∏_1≤k≤pβ_k^β(k) → max;

A^Tα = 0, α ≥ 0, β_k = ∑_i∈I(k)α_i, β₀=1. (4.5.16)

По теореме двойственности оптимальные значения задач (4.5.2) и (4.5.16) совпадают: f*₀ = ψ*.

Часто оказывается так, что задачу (4.5.16) можно решить достаточно просто.

Определение. Степенью трудности задачи геометрического программирования называется число линейно независимых решений системы

A^Tα = 0, ∑_i∈I(0)α_i = 1.

Для большинства задач степень трудности вычисляется по формуле d = n – m – 1, где (как и в предыдущих рассуждениях) n – количество слагаемых в позиномах задачи, m – количество переменных.

Для задач с нулевой степенью трудности характерно, что допустимая область двойственной задачи (4.5.16) состоит из единственного варианта, который и является решением.

Предположим, мы нашли решение α* задачи (4.5.16), вычислили соответствующие β*, ψ* = ψ(α*, β*).

По формуле (4.5.13) λ*_r = Сσ_r = Сσ₀ β*_r = ψ* β*_r при r >0 (λ*₀ =1).

δ*_i = σ₀α*_i; где σ₀ можно найти из равенства σ₀ ∑_1≤i≤nα*_i = 1.

μ*_i = v* δ*_i; причем v* находится из формулы ψ* = v* - ∑_1≤k≤p λ*_k.

v* = ψ* + ∑_1≤k≤p λ*_k = ψ* + ∑_1≤k≤p ψ*β*_k = ψ*(1+ ∑_1≤k≤p σ_k / σ₀) = ψ* / σ₀.

Таким образом, μ*_i = v* δ*_I =ψ* / σ₀ σ₀α*_I = ψ*α*_I .

Зная оптимальные значения λ* и μ*, находим оптимальные значения всех слагаемых задачи:

e^x*(m+i) = u*_I = μ*_i / λ*_k(i),

т.е. при k(i)=0 u*_i =ψ*α*_I ; при k(i)≠0 u*_I =α*_I /β*_k(i).

В итоге, значения переменных t* находим, решая систему уравнений

u_i(t) = u*_i, i=1,…,n.

Поиск по сайту: