Автоматика и телемеханика, № 5, 2019

Нелинейные системы

(Сколковский институт науки и технологий, Москва),

Е.Н. ГРЯЗИНА, канд. физ.-мат. наук (gryazina@gmail.com)

(Сколковский институт науки и технологий, Москва,

Институт проблем управления им. В.А. Трапезникова РАН, Москва)

ОБЗОР ПОЛУОПРЕДЕЛЕННЫХ РЕЛАКСАЦИЙ

ДЛЯ ПОИСКА ОПТИМАЛЬНЫХ ПОТОКОВ МОЩНОСТИ¹

Дан обзор пяти выпуклых релаксаций для решения задачи AC Optimal

Power Flow (AC OPF): полуопределенной, хордальной, конической, релак-

сации моментами и QC-релаксации. Подробно описано, в чем особенность

AC-формулировки и невыпуклости задачи. Подробно разобрано как за-

писать каждую релаксацию для OPF. Основной интерес представляют

полуопределенная, хордальная и коническая релаксации. Они реализова-

ны на тестовом примере из четырех узлов.

Ключевые слова: энергетические системы, полуопределенное программи-

рование, выпуклые релаксации, потоки в энергетических сетях.

DOI: 10.1134/S0005231019050027

1. Введение

Электроэнергия является одним из важнейших ресурсов в современном

мире, более того, технологический процесс сталкивается со все большей необ-

ходимостью в электроэнергии. Так, за последние несколько лет активно раз-

вивается разработка электромобилей, а растущее население Земли потребля-

ет все больше электричества. Генерация электроэнергии связана с высокими

денежными издержками, кроме того, сохраняется большое число “грязных ге-

нераторов”, на которых сжигается, к примеру, мазут и вырабатывается элек-

троэнергия. Такие станции наносят ощутимый вред экологии Земли, к тому

же зависят от запасов ископаемых ресурсов и цен на них. На смену классиче-

ским приходят генераторы на возобновляемых источниках энергии — ветря-

ные генераторы и фермы солнечных панелей. К сожалению, такие источники

ограничены в своих возможностях и зависят от погодных условий. Все это

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

Одной из таких задач является определение оптимального режима произ-

водства электроэнергии для заданной сети. Для ее решения существуют раз-

личные постановки, но самым распространенным и точным является задача

Optimal Power Flow, которая формулируется на основе физических законов

Кирхгофа и Ома. Наиболее распространенные критерии оптимальности — это

¹ Работа выполнена при финансовой поддержке Российского научного фонда (грант

№ 16-11-10015).

достижение минимальной общей стоимости генерации, или потерь, при удо-

влетворении инженерных ограничений. Отдельно можно выделить подход,

нацеленный на обеспечение устойчивости в работе электросети, так называе-

мый Anti-Blackout подход. Это более сложная задача, в которой требуются

дополнительные ограничения, связанные с физической природой задачи. Как

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

формулировке, поэтому объединение этих двух подходов является актуаль-

ной задачей для отрасли.

Отличительной особенностью задачи Optimal Power Flow (далее в работе

для краткости будет использоваться аббревиатура OPF) в классической по-

становке является ее невыпуклость, что не позволяет напрямую применить

инструментарий выпуклой оптимизации. В связи с этим системные операто-

ры используют линеаризованную версию задачи — DC OPF. Линеаризация

позволяет быстрее и легче решать задачу ценой точности полученного ре-

шения. Поэтому большой интерес представляют методы решения исходной

невыпуклой задачи — AC OPF (далее OPF будет означать именно AC OPF).

Достаточно популярным способом справиться с невыпуклостью задачи яв-

ляются релаксации. С помощью релаксаций можно значительно упростить

сложность задачи и решить ее за приемлемое время с достаточной точностью.

К сожалению, релаксации не всегда дают точное решение, и на сегодняшний

день нет общих формулировок или теорем, которые позволяли бы описать

условия существования точного решения для некоторой общей формулиров-

ки задачи.

Данная работа нацелена на рассмотрение классической задачи Optimal

Power Flow, в частности изучаются различные выпуклые релаксации для ре-

шения задачи. Главная цель — это подробный разбор релаксаций на тестовом

примере из четырех узлов. В разделе 2 работы предлагается основная фор-

мулировка задачи, в разделе 3 приводится обзор существующих релаксаций,

в разделе 4 описаны тестовые примеры и численные эксперименты.

2. Формулировка задачи Optimal Power Flow

Задача OPF впервые была сформулирована в 1962 г. (историю развития

задачи и методов решения можно найти в [1-3] и с тех пор остается важной

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

до сих пор не было получено эффективного алгоритма, который мог бы быст-

ро и эффективно ее решать в общей формулировке для систем с тысячами

узлов. Например, российская сеть включает более 9000 узлов. Связано это,

в первую очередь, с тем, что задача является невыпуклой и NP-сложной. По

этой причине в индустрии используется линеаризованная версия задачи, так

называемая DC OPF [4]. Данный подход позволяет быстро решать задачу

для больших сетей, но ценой точности (в смысле близости к глобальному

оптимуму задачи) полученного решения. В связи с ростом потребления и

производства электроэнергии индустрия все больше и больше нуждается в

точных алгоритмах, так как даже небольшие улучшения в качестве решения

позволяют экономить миллиарды долларов ежегодно.

Задача OPF может быть переформулирована как квадратичная задача

с квадратичными ограничениями (QCQP-формулировка), в такой формули-

ровке и целевая функция, и все ограничения являются квадратичными функ-

циями. К сожалению, при этом задача все еще остается невыпуклой, но в та-

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

ный подход активно развивается в последние годы. Но главным недостатком

остается отсутствие гарантий, что метод сработает и даст точное решение.

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

тод будет работать для одних задач и не будет для других. Далее рассмотрим

стандартную математическую постановку задачи OPF.

Электроэнергетическая сеть представляет собой граф G, в котором вер-

шины N соответствуют генераторам и потребителям, а ребра E — линиям

электропередач. Ребра проводятся только между теми вершинами, между

которыми в действительности существуют линии. В одной вершине может

находиться либо только генератор, либо потребитель, либо оба одновременно.

В основе формулировки задачи OPF лежат законы Кирхгофа (1) и

Ома (2), связывающие электрический ток I, напряжение V , проводимость Y

и мощность S

∑

(1)

I^gj - I^lj =

I_jk

∀j ∈ N,

(j,k)∈E

(2)

I_jk = Y_jk(V_j - V_k

∀(j, k) ∈ E,

где I, V, Y и S - комплексные величины. Здесь и далее верхние индексы g и l

будут обозначать генерацию и нагрузку соответственно².

Мощность вычисляется по формуле

(

)

(3)

S_jk = V_jIHjk = V_jYHjk VHj - V^H

∀(j, k) ∈ E,

где верхний индекс^H означает операцию комплексного сопряжения и транс-

понирования.

Совмещая (1)-(3), получаем формулу для потоков мощностей и форму-

лу для так называемой “Net Power Injection” (NPI) для узла j, или разнице

генерируемой и потребляемой мощностей

(4)

S_jk = YHjkV_jVHj - YHjkV_jVHk

(j, k) ∈ E,

(

) (

)

∑

(5)

s_j = S^gj - S^lj = P^gj - P^l

+i Q^gj -Q^l

S_jk

∀j ∈ N.

(j,k)∈E

Из (4) и (5) выражаем NPI узла через напряжения в сети:

∑ (

)

(6)

s_j =

V_j VHj - V^H

YHjk

∀j ∈ N.

(j,k)∈E

² Далее, если явно не указано иного, одиночный индекс j будет обозначать узел сети

(вершину графа), а пара (j, k) - линию сети (ребро графа).

Формула (6) является квадратичной относительно напряжения, и именно от-

сюда возникает “квадратичность” задачи OPF.

На узлах могут присутствовать ограничения на s_j, связанные с потребле-

нием и производительностью генератора

(7)

s_j ≤ s_j ≤ s_j

∀j ∈ N,

а также ограничения на напряжение на каждом узле

(8)

∀j ∈ N.

V j ≤ |Vj| ≤ V j

Кроме того, вводятся ограничения для линий (9), ограничивающие мак-

симальные допустимые потоки для каждой линии:

(9)

|S_jk| ≤ Smaxjk

∀(j, k) ∈ E,

при нарушении этого ограничения линия может выйти из строя, приведя к

коллапсу всей сети.

Формула (6) позволяет определять объемы генерации на узлах через на-

пряжения, т.е. можно работать только с переменными, отвечающими за на-

пряжение. Набор условий вида (7)-(9) задает множество допустимых режи-

мов в сети. В зависимости от потребностей на конкретной сети могут вво-

диться различные целевые функции. Два наиболее распространенных функ-

ционала - минимизация общих потерь генерации активной мощности

⎛

⎞

∑

(

)

f₁(V ) =

ℜ(s_j) + P^l

= ℜ^⎝

V_j VHj - V^H

YHjk + P^l⎠,

j∈N

k:(j,k)∈E

и минимизация общей стоимости генерации активной мощности с учетом

стоимости генерации c_j для каждого генератора j.

⎛

⎞

∑

(

)

f₂(V ) =

c_jℜ(s_j + P^l)= cjℜ⎝

V_j VHj - V^H

YHjk + P^l⎠.

j∈N

k:(j,k)∈E

Стоимости также могут быть некоторыми функциями, зависящими от объе-

мов генерации, чаще всего квадратичными. В самом простом случае имеем

постоянную стоимость генерации 1 кВт активной мощности.

Здесь f_j(V ) : Cⁿ → R. Оба функционала - квадратичные функции от век-

тора напряжений V = (V₁, · · · , V_n) в сети (здесь и далее ℜ( ) и ℑ( ) использу-

ются для обозначения действительной и мнимой частей комплексного числа

соответственно).

Теперь можно сформулировать проблему полностью:

f (V ) → min,

∑ (

)

s_j ≤

V_j VHj - V^H

YHjk ≤ s_j,

∀j ∈ N,

k:(j,k)∈E

∀j ∈ N,

V j ≤ |Vj| ≤ V j,

|S_jk| ≤ Smaxjk,

∀(j, k) ∈ E.

Здесь функция f(V ) - это любая из функций f₁(V ), f₂(V ) или какой-либо

иной функционал от напряжения, интересующий решающего задачу.

2.1. DC-формулировка

В постановке, описанной выше, все комплексные числа были представлены

в алгебраической форме и далее в работе используются именно в этой фор-

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

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

дополнительные предположения на работу сети, получить линеаризованную

версию задачи - DC OPF.

Комплексная проводимость линии Y_jk состоит из активной G_jk и реактив-

ной B_jk проводимостей, т.е.

(10)

Y_jk = G_jk + iB_jk

∀(j, k) ∈ E.

Комплексное напряжение можно переписать в тригонометрической форме:

(11)

V_j = |V_j|exp(iδ_j

∀j ∈ N.

Подставляем (10)-(11) в формулу для мощности (3) и получаем формулы

для активной (P ) и реактивной (Q) генераций:

(

)

S_jk = V_j VHj - V^H

YHjk =

= |V_j | exp(iδ_j )(|V_j | exp(-iδ_j ) - |V_k| exp(-iδ_k))(G_jk - iB_jk),

(12)

P_jk = ℜ(S_jk) = |V_j|²G_jk + |V_j||V_k|(G_jk cos(δ_j - δ_k) + B_jk sin(δ_j - δ_k

)) ,

(13)

Q_jk = ℑ(S_jk) = -|V_j|²B_jk + |V_j||V_k|(G_jk sin(δ_j - δ_k) - B_jk cos(δ_j - δ_k

)) .

Полученные формулы выражают активные и реактивные потоки по линии

(j, k) через напряжение и проводимость. Опуская технические детали, из (12)

и (13) легко получаются формулы для потребляемой и генерируемой мощно-

стей на узле j:

∑

(14)

P_j =

|V_j ||V_k| (G_jk cos(δ_j - δ_k) + B_jk sin(δ_j - δ_k

)) ,

k:(j,k)∈E

∑

(15)

Q_j =

|V_j ||V_k| (G_jk sin(δ_j - δ_k) - B_jk cos(δ_j - δ_k

)) .

k:(j,k)∈E

Из (14) и (15) легко получить DC-формулировку задачи, сделав инже-

нерные предположения: в стационарном состоянии энергетической системы

верны следующие утверждения:

1) G_jk = 0, ∀(j, k) ∈ E,

2) |V_j | ≈ 1, ∀j ∈ N,

3) (δ_j - δ_k) ≈ 0 ⇒ cos(δ_j - δ_k) ≈ 1, sin(δ_j - δ_k) ≈ δ_j - δ_k.

Следовательно, (14) и (15) упрощаются до

∑

P_j =

B_jk(δ_j - δ_k),

k:(j,k)∈E

∑

(16)

Q_j =

-B_jk

· 1.

k:(j,k)∈E

Из (16) следует, что в DC-формулировке реактивная мощность Q определя-

ется однозначно. Ниже представлена DC-формулировка:

∑

min f(P_j),

j∈N

∑

P^gj = P^lj +

B_jk(δ_j - δ_k),

∀j ∈ N : j - {генератор},

k:(j,k)∈E

здесь f(·) — некоторая линейная функция, зависящая от генерации, напри-

мер (c_j P_j ), где c — вектор цен активной генерации. В такой постановке

OPF является задачей линейного программирования, которую можно решать

очень быстро. Более подробно об инженерной составляющей формулировки

DC OPF см. в [5].

3. Способы решения задачи Optimal Power Flow

В связи со сложностью и особой важностью задачи для индустрии за по-

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

нию. Среди них можно выделить последовательное квадратичное программи-

рование, генетические алгоритмы, подходы, основанные на методе внутрен-

ней точки, а также различные релаксационнные подходы [6]. Большую попу-

лярность набирают полуопределенные релаксации (semidefenite relaxations —

SDP). Идея релаксаций заключается в переформулировке исходной задачи

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

исключения одного невыпуклого условия. После этого решается релаксиро-

ванная задача любым методом для решения выпуклых задач. Если получен-

ное решение удовлетворяет ранее исключенному условию, то получено точное

решение проблемы, в противном же случае релаксация является неточной, но

дает нижнюю оценку для оптимального значения целевого функционала.

Главная проблема заключается в том, что не сформулированы условия,

при которых релаксация была бы точной для общей задачи. Но сформули-

рованы условия, при которых релаксация является точной для радиальных

сетей, т.е. сетей, граф которых - дерево [7]. Бывают ситуации, когда один и

тот же метод может работать для одной задачи и “сломаться” для задачи с

незначительными изменениями в данных, ограничениях или в функционале

такими что они не выводят из класса задачи [8].

Далее будут разобраны некоторые популярные и/или новые релаксирую-

щие методы. Но перед этим необходимо более подробно разобрать, как устрое-

на SDP-релаксация в общем.

3.1. Полуопределенное программирование

Полуопределенная релаксация [9] является достаточно популярной и в то

же время простой техникой решения невыпуклых задач. Лучше всего SDP-ре-

лаксация применяется для квадратичных задач с квадратичными ограниче-

ниями (QCQP), каковой и является задача OPF. Для задач из класса QCQP

SDP релаксация получается естественным образом. Рассмотрим это на при-

мере. Пусть есть исходная задача из класса QCQP

(17)

xTCx → min ,

x∈Rⁿ

xTHx ≥ a,

xTGx = b,

где C, G, H - симметричные матрицы.

Для любой симметричной матрицы A имеем

xTAx = T r(x^TAx) = T r(Axx^T) = T r(AX),

xTAx - скаляр, следовательно, можем использовать матричный след, ничего

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

лу справа, которая тоже является скаляром, где xx^T = X — (n × n)-матрица.

Следовательно, левая часть равна правой, и, заменяя функционал и каждое

ограничение задачи (17), получаем задачу:

(18)

Tr(CX) → min ,

X∈Sⁿ

Tr(HX) ≥ a,

Tr(GX) = b,

X ≽ 0,

rank(X) = 1.

Если матрица X является неотрицательно определенной матрицей (X ≽ 0)

с единичным рангом, то можно однозначно восстановить исходный вектор x

по заданной матрице X (используя разложение по собственным числам). Т.е.

из решения задачи (18) можно однозначно восстановить решение задачи (17).

Значит, задачи эквивалентны.

Проблема заключается в том, что задача (18) также является невыпуклой

из-за условия на ранг. Исключая его, получаем полуопределенную релакса-

цию исходной задачи (17):

(19)

Tr(CX) → min ,

X∈Sⁿ

Tr(HX) ≥ a,

Tr(GX) = b,

X ≽ 0.

К сожалению, численные методы могут сходиться к решениям с рангом

сильно больше 1 (rank(X^∗) >> 1), даже если существует решение с единич-

ным рангом. В таком случае явно восстановить x^∗ невозможно. Существуют

различные эвристики для получения допустимого решения исходной задачи

(две будут приведены далее), но полученное допустимое решение в общем

случае не будет являться оптимальным.

Если полученное решение X^∗ имеет единичный ранг, то у него есть только

одно ненулевое собственное значение (оно также является неотрицательным),

а значит, восстановить оптимальный вектор x^∗ можно по формуле

√

x^∗ =

λu,

где λ и u - собственное значение и соответствующий собственный вектор

матрицы X∗3. Когда решение имеет ранг больше одного, можно использо-

вать максимальное собственное значение λ₁ и соответствующий собственный

вектор u₁, чтобы получить аппроксимацию оптимального решения:

√

λ₁u₁.

Другой способ - рандомизация. Вместо задачи (19) решается стохастиче-

ская задача

(20)

Eξ∼N(0,X)[ξ^TCξ] → min

X∈Sⁿ, X≽0

Eξ∼N(0,X)[ξ^THξ] ≥ a,

Eξ∼N(0,X)[ξ^TGξ] = b.

Так как E[ξ^Tξ] = X, задача (20) эквивалентна задаче (19) (с точностью до

набора ограничений).

К сожалению, полученное таким образом приближенное решение чаще все-

го оказывается недопустимым для исходной задачи, поэтому дополнительно

необходимо спроецировать приближенное решение на допустимую область.

Пример неточной релаксации

Как упоминалось ранее, SDP-релаксация не всегда является точной. Это

можно наглядно продемонстрировать на следующем примере в R².

minx1,

(x₁ - a₁)² + (x₂ - a₂)² ≤ r²¹,

(x₁ - b₁)² + (x₂ - b₂)² ≥ r²²,

x₁ = x₂,

здесь a = (a₁, a₂), b = (b₁, b₂) и r₁, r₂ - центры и радиусы двух окружностей.

³ xx^T = X = uλu^T.

На рис. 1 проиллюстрирован пример для следующих значений параметров:

a = (1;1), b = (2;2), r₁ = 1, r₂ = 1,5.

Оптимальное решение легко найти, не решая задачу, при этом если по-

строить SDP-релаксацию задачи, то ее решение будет отличаться от анали-

тического и ранг решения релаксированной задачи больше одного.

3.2. Эквивалентные релаксации

В этой части будут кратко рассмотрены три эквивалентных релаксации —

полуопределенная, хордальная и коническая. В [10] сформулированы теоре-

мы и условия, при которых релаксации эквивалентны между собой. Для бо-

лее глубокого понимания задачи в AC-формулировке и ее решения с помо-

щью выпуклых релаксаций рекомендуется ознакомится с [11-13]. Для начала

рассмотрим общую идею, которая лежит в основе всех трех релаксаций.

Рис. 2. Граф сети.

В задаче (2) целевыми переменными являются напряжения на каждом

узле V ∈ C^N . Для наглядности рассмотрим пример. Пусть сеть представлена

графом на рис. 2. Сделаем замену W = V V^H.

W_jj = |V_j|²,

∀j ∈ N,

W_jk = V_jVHk,

∀(j, k) ∈ E.

Таким образом, матрица W — это эрмитова частично заполненная матри-

ца, и ее паттерн (заполненная часть матрицы) соответствует графу сети G.

Ниже представлена матрица для данного графа

⎛

⎞

W₁₁

W₁₂

- W₁₇

⎜W21

W₂₂

W₂₃

- W₂₆

⎟

⎜

⎟

⎜

− W₃₂ W₃₃ W₃₄ W₃₅

⎟

⎜

⎟

W =

⎜

−

- W₄₃ W₄₄ W₄₅

⎟

⎜

⎟

⎜

−

- W₅₃ W₅₄ W₅₅ W₅₆

⎟

⎝

⎠

− W₆₂

- W₆₅ W₆₆ W₆₇

W₇₁

- W₇₆ W₇₇

В ней прочерк означает, что элемент не определен, т.е. в графе отсутствует

соответствующее ребро. В [14, 15] приводится способ дополнения частично за-

полненной матрицы до полной матрицы с сохранением знакоопределенности

и ранга.

Теперь можно переписать исходную задачу через новые переменные - эле-

менты матрицы W . Если rank(W ) = 1, то можно однозначно восстановить

значения элементов вектора V . Задача (2) примет вид

∑ ∑

ℜ (W_jj - W_jk) YHjk → min,

j∈N k:(j,k)∈E

∑

sj^≤

(W_jj - W_jk) YHjk ≤ s_j,

∀j ∈ N,

k:(j,k)∈E

V2j ≤ W_jj ≤ V2j,

∀j ∈ N,

W ≽ 0,

rank(W ) = 1.

3.2.1. Полуопределенная релаксация. Данная релаксация самая простая

по своей идее. В ней просто исключено невыпуклое ограничение rank(W ),

и задача решается без него. Если полученное решение W^∗ имеет ранг 1, то

можно восстановить оптимальный режим V^∗, значит, релаксация является

точной. Иначе релаксация является неточной. Здесь и далее под точностью

релаксации понимается возможность восстановить исходное решение, т.е. ес-

ли полученное решение является неотрицательно определенной матрицей с

единичным рангом, то можем восстановить решение, и релаксация будет точ-

ной. Если хотя бы одно из двух условий не выполнено, то восстановить реше-

ние не можем, и релаксация неточная. Ниже представлена возможная фор-

мулировка релаксированной задачи:

f (W ) → min,

∑

s_j ≤

(W_jj - W_jk)YHjk ≤ s_j,

k:(j,k)∈E

(V_j)² ≤ W_jj ≤ (V_j)²,

W ≽ 0.

3.2.2. Хордальная релаксация. Данная релаксация, как и последующая, ме-

нее очевидна для понимания, но обладает преимуществом для больших разре-

женных сетей. Идея заключается в том, что изначальный граф сети заменяет-

ся на его хордальное расширение [16]. Хордальным называется граф, в кото-

ром любой цикл длины четыре и более имеет хорду, соединяющую несмежные

вершины. Хордальное расширение графа, следовательно, является приведе-

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

(на рис. 3 изображен пример хордального расширения графа). Затем вместо

Рис. 3. Хордальное расширение графа.

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

знакоопределенность только нескольких неразреженных подматриц (соответ-

ствующих максимальным кликам хордального графа) значительно меньшего

размера. Максимальной кликой называется такой полный подграф исходного

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

жал оставаться полным. Иными словами, никакая другая клика графа не

содержит в себе максимальную клику целиком.

Получаем следующую матрицу для хордального расширения графа

⎛

⎞

W₁₁

W₁₂

- W₁₆ W

⎜W21

W₂₂

W₂₃

- W₂₆

⎟

⎜

⎟

⎜

⎟

⎜

- W₃₂

W₃₃

W₃₄

W₃₅

W₃₆

⎟

⎜

⎟

W_ch =

⎜

−

- W₄₃

W₄₄

W₄₅

⎟

⎜

⎟

⎜

−

- W₅₃

W₅₄

W₅₅

W₅₆

⎟

⎜

⎟

⎝W₆₁ W₆₂ W₆₃

- W₆₅

W₆₆

W₆₇⎠

W₇₁

- W₇₆

W₇₇

После расширения исходного графа до хордального появляются новые реб-

ра, следовательно, в матрице W должны появиться новые элементы (соот-

ветствующие новым ребрам). Частично заполненную матрицу на основе хор-

дального расширения обозначим через W_ch.

Полученный хордальный граф имеет пять максимальных клик

{1, 6, 7}, {1, 2, 6}, {2, 3, 6}, {3, 5, 6}, {3, 4, 5}. Значит, необходимо проверить

знакоопределенность только пяти подматриц, вместо проверки всей исход-

ной матрицы W_ch. Подматрица для, например, клики {3, 4, 5}:

⎛

⎞

W₃₃

W₃₄

W₃₅

⎜

⎟

W_ch =

⎝^W43 W44 W45

⎠.

W₅₃

W₅₄

W₅₅

Приведем формулировку хордальной релаксации для исходной задачи:

f (W_ch) → min,

W_ch

∑

s_j ≤

([W_ch]_jj - [W_ch]_jk) YHjk ≤ s_j ,

k:(j,k)∈E

(V_j)² ≤ [W_ch]_jj ≤ (V_j)²,

W_ch(C) ≽ 0, ∀C : C - максимальная клика графа W_ch.

Условия W ≽ 0 и rank(W ) = 1 заменились на W_ch(C) ≽ 0 и rank(W_ch(C)) = 1

(последнее условие релаксируется как невыпуклое) по всем максимальным

кликам хордального расширения исходного графа G. Если полученное опти-

мальное решение релаксированной задачи удовлетворяет этим условиям, то

можно однозначно дополнить исходную частично заполненную матрицу до

полной матрицы, которая также будет неотрицательно определенной с еди-

ничным рангом, а значит, можно восстановить оптимальный режим V^∗.

3.2.3. Коническая релаксация. Данная релаксация похожа на предыдущую.

Только теперь вместо клик рассматриваются все ребра e = (j, k) ∈ E и про-

веряется знакоопределенность соответствующих подматриц. Общий вид под-

матрицы для некоторого ребра (j, k) выглядит так:

(

)

jj Wjk

W (e) =

W_kj W_kk

Только здесь rank(W ) = 1 и W ≽ 0 заменяются на rank(W (e)) = 1 и

W (e) ≽ 0, где e = (j, k) ∈ E, так как [W_jj][W_kk] ≥ |W_jk|², ∀e = (j,k) ∈ E со-

гласно следующим выкладкам:

W_jk = V_jVHk,

W_jkWHjk = V_jVHkVHjV_k,

|W_jk|² = W_jjW_kk,

|W_jk|² ≤ W_jjW_kk.

f (W ) → min,

∑

s_j ≤

(W_jj - W_jk)YHjk ≤ s_j,

k:(j,k)∈E

(V_j)² ≤ W_jj ≤ (V_j)²,

W (e) ≽ 0,

∀e ∈ E.

Условие rank(W ) = 1 заменяется на условия rank(W (e)) = 1, ∀e = (j, k) ∈

∈ E. Полученное решение должно удовлетворять условиям на неотрицатель-

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

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

вие для любого цикла (n₁, · · · , n_k) в графе G

∡Wn1,n₂ + ··· + ∡Wn_k,n₁ = 0 mod 2π.

Если эти три условия выполняются, то можно однозначно дополнить частич-

ную матрицу до полной с теми же свойствами (знакоопределенность и ранг)

и восстановить V ^∗.

Более подробно с тремя рассмотренными релаксациями можно ознако-

миться в [17, 18].

3.3. Релаксация моментами

Данный подход рассматривается в [19, 20]. Метод заключается в перефор-

мулировании исходной задачи OPF (2) с помощью специально сконструиро-

ванных матриц таким образом, что полученная задача становится так назы-

ваемой Generalized Moment Problem. Если говорить конкретно о задаче OPF,

то она превращается в минимизацию некоторого выпуклого функционала с

набором условий, состоящим из неотрицательно определенных матриц.

Формулу (6) можно переписать немного иначе, разбив s_j отдельно на дей-

ствительную и мнимую части. Обозначим через V^dj, V^qj действительную и

мнимую части напряжения V соответственно, аналогично разобьем матрицу

проводимости Y_adm = G + iB. Тогда

∑(

)

∑(

)

(21)

ℜ(s_j) = V^dj

-B_jkV^q

+V^q

B_jkV^dk + G_jkV^q

Gjk

k=1

∑(

)

∑(

)

(22)

ℑ(s_j) = V^dj

-B_jkV^dk - G_jkV^q

+V^q

-B_jkV^q

Gjk

k=1

Из (21) и (22) легко получить формулы для активной и реактивной генераций

на узлах

∑(

)

P^gj = f_Pg(Vd, Vq) = Vdj

-B_jkV^q

Gjk

k=1

(23)

∑(

)

+V^qj

B_jkV^dk + G_jkV^q

+P^lj,

k=1

∑(

)

Q^gj = f_Qg(Vd, Vq) = Vdj

-B_jkV^dk - G_jkV^q

k=1

(24)

∑(

)

+V^qj

-B_jkV^q

+P^lj.

Gjk

k=1

Кроме того,

(25)

|V_j |² = fVj (V^d, V^q) = (V^dj)² + (V^qj)².

Сформулируем еще раз задачу OPF в описанных обозначениях. Ограни-

чимся частным случаем, в котором минимизируется генерация на первом уз-

ле при ограничениях на напряжение и удовлетворение спроса на остальных

узлах.

f_Pg

→ min,

f_Pg

≥P^lk,

∀k ∈ N,

f_Qg

≥Q^lk,

∀k ∈ N,

(Vmink)² ≤ f_V

(V^d, V^q) ≤ (Vmaxk)²,

∀k ∈ N,

V q₁ = 0.

Теперь рассмотрим, как из (21)-(25) получается релаксация по методу мо-

ментов. Введем вектор x, который овеществляет вектор напряжений:

x = [V d1 ,··· ,V dn ,V q1 ,··· ,V ^qn]^T ∈ R2n,

x^α - моном степени α = [α₁,··· ,α2n]^T,

∑

x^α = (Vd1)α1 ··· (V^qn)αn ,

α_j = α.

j=1

Тогда полином g(x) с коэффициентами g_α равен

∑

g(x) =

g_αx^α.

α∈N2n

Мономы x^α можно заменить на скаляры y_α и получить линейный функцио-

нал

∑

L_y{g} =

g_αy_α.

α∈N2n

Замена происходит на основе степеней мономов, т.е. для двух узлов моном

(Vd1)(Vd2)²(Vq1)(Vq2)² переходит в y₁₂₁₂. Аналогично будут записываться функ-

ционалы, например

g(x) = -1 + (Vd2)² + (Vq2)² → L_y{g} = -y₀₀₀ + y₀₂₀ + y₀₀₂.

Для релаксации методом моментов порядка γ вводится вектор мономов по-

рядка γ

[

x_γ =

1, Vd1, · · · , V^qn, (Vd1)², Vd1Vd2, · · · , (V^qn)², (Vd1)³, · · · , (V^qn)^γ

]^T .

Определим матрицу моментов M_γ(y) = L_y(x_γ xTγ). Для этого вначале пере-

множаются вектор-столбец x_γ на вектор-строку xTγ, в результате получается

матрица, элементами которой являются различные мономы, которые в даль-

нейшем заменяются на y_α по вышеописанному правилу. Например, пусть x =

= [1, x₁, x₂] и γ = 1, тогда

⎞

^⎛1

x₁

x₂

^⎛y00 y10

y₀₁

L_y(x₁xT1) = L_y ⎝x1 x¹ x1x2⎠= ⎝y10 y20 y11⎠=M1(y).

x₂

x₁x₂

x²

y₀₁

y₁₁

y₀₂

Последнее необходимое понятие - это локализационная матрица, которая

строится на основе матрицы моментов для заданного функционала. Если

заданный функционал f имеет степень 2β или 2β - 1, то сначала строит-

ся матрица момента γ - β, каждый элемент которой затем умножается на f,

т.е.

M_γ-β(f(y)y) = L_y(f(y)x_γ-βxTγ-β).

Для примера выше пусть f(x) = 1 + x²¹ + x²², тогда

⎛

⎞

1+x²¹ +x²²

x₁ + x³¹ + x₁x²²

x₂ + x²¹x₂ + x³²

⎜

⎟

M₁(f(y)y) = L_y

⎝x1 + x¹ + x1x² x¹ + x¹ + x¹x² x1x2 + x¹x2 +

x₁x³²

⎠=

x₂ + x²¹x₂ + x³² x₁x₂ + x³¹x₂ + x₁x³² x²² + x²¹x²² + x⁴

⎞

^⎛y₀₀ + y₂₀ + y₀₂ y₁₀ + y₃₀ + y₁₂ y₀₁ + y₂₁ + y₀₃

=^⎝y₁₀ + y₃₀ + y₁₂ y₂₀ + y₄₀ + y₂₂ y₁₁ + y₃₁ + y₁₃

⎠_.

y₀₁ + y₂₁ + y₀₃ y₁₁ + y₃₁ + y₁₃ y₀₂ + y₂₂ + y₀₄

Подробнее теория в основе метода моментов описана в [21, 22].

Используя описанный инструментарий можем сформулировать релакса-

цию по методу моментов для задачи OPF:

(

)

minLy fPg

((

) )

Mγ-1

f_Pg

-P^l

≽ 0,

∀k ∈ N,

((

) )

Mγ-1

f_Qg

-P^l

≽ 0,

∀k ∈ N,

((

)

Mγ-1

fVk - Vmink

≽ 0,

∀k ∈ N,

Mγ-1 ((Vmaxk - f_V

)y) ≽ 0,

∀k ∈ N,

M_γ (y) ≽ 0,

y00···0 = 1,

y_·p··· = 0,

∀p ≥ 1.

Условие y_·p··· = 0 — эквивалент условия Vq1 = 0, можно сказать, что этим

условием “задается точка отсчета” для напряжений (точка означает любое

число из интервала [0, γ]), т. е. любой моном, в который входит Vq1, равен

нулю.

С увеличением γ растет сложность задачи, но при этом увеличивается ка-

чество решения. На практике метод оказывается достаточно сложным из-за

того, что сильно разрастается количество переменных с ростом γ. Уже для

задачи из двух узлов, матрица второго момента M₂ будет размера 10 × 10, а

для задачи из 10 узлов — 210 × 210 (без учета симметричных элементов).

Реальные сети могут состоять из тысячи узлов, что делают данную релакса-

цию ресурсоемкой и затрудняют ее применение на практике.

Пример конструирования данной релаксации хорошо описан в [19].

3.4. QC-релаксация

В основе метода лежат ранее рассмотренные формулировки, а невыпуклые

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

об условии W_jk = V_j VHk, которое ранее превращалось в два новых условия

rank(W ) = 1 и W ≽ 0. В [23] авторы метода предлагают использовать три-

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

оболочки.

Воспользовавшись тригонометрическим представлением комплексных на-

пряжений V = v(cos(θ) + i sin(θ)), перепишем матрицу W = V V^H следующим

образом:

W_jk = V_jVHk = v_jv_k(cos(θ_j) + isin(θ_j))(cos(θ_k) + isin(θ_k)),

∀(j, k) ∈ E,

ℜ(W_jk) = v_jv_k cos(θ_j - θ_k),

∀(j, k) ∈ E,

ℑ(W_jk) = v_jv_k sin(θ_j - θ_k),

∀(j, k) ∈ E,

W_jj = v2j,

∀i ∈ E.

Введем выпуклые оболочки для функций x², xy, cos(x), sin(x) на интер-

валах [x^l, x^u] и [y^l, y^u] (подробнее в [24]).

{

x≥x

conv(x²) =

x ≤ (x^l + x^u)x - x^lx^u,

⎧

⎪x

y≥x^ly+y^lx-x^ly^l

⎨

y≥x^uy+y^ux-x^uy^u

conv(xy) =

⎪x

y≤x^ly+y^ux-x^ly^u

⎩

y≤x^uy+y^lx-x^uy^l,

⎧

)

⎪

⁽θ^u)(

θ^u

⁽θ^u)

⎨sθ ≤ cos

θ-

+ sin

conv(sin(θ)) =

)

⎪

⁽θ^u)(

θ^u

⁽θ^u)

sθ ≥ cos

θ+

- sin

⎧

⎨

1 - cos(θ^u)

cθ ≤ 1 -

θ²

conv(cos(θ)) =

(θ^u)²

⎩

cθ ≥ cos(θ^u).

С использованием полученных формул переписывается условие W = V_jV Hk .

W_jj = v2j → conv(v2j)ℜ(W_jk) = v_jv_k cos(θ_j - θ_k) →

→ conv(conv(v_j v_k)conv(cos(θ_j - θ_k)))ℑ(W_jk) =

= v_jvk sin(θ_j - θ_k) → conv(conv(v_jv_k)conv(sin(θ_j - θ_k))).

Авторы утверждают, что метод не доминируется SDP-релаксацией и до-

минирует SOCP-релаксацию.

4. Реализация на тестовом примере

В качестве тестового примера была выбрана простая сеть из четырех уз-

лов (см. рис. 4), представленная в библиотеке MATPOWER [25]. Для решения

оптимизационных задач используется MatLab и библиотека CVX [26] с сол-

вером Mosek [27].

5,1696 + i25,8478

3,8156 + i19,078

3,0237 + i15,1185

5,1696 + i25,8478

Рис. 4. Граф сети из четырех узлов со значениями проводимости для линий.

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

третий узлы являются чистыми потребителями. Граф неориентированный,

поэтому если имеется ребро (j, k), то также имеется и ребро (k, j). Спрос на

узлах представлен в табл. 1.

Таблица 1. Потребление в сети

Номер узла

Потребление P^lj + iQ^lj

0,5 + i0,31

1,7 + i1,05

2 + i1,23

0,8 + i0,5

Суммарное потребление

5 + i3,09

N = {1,2,3,4} - узлы,

E = {(1,2),(1,3),(2,4),(3,4)} - ребра (линии электропередач),

G = {1,4} - множество генераторов.

При этом генерация активной мощности на узле 4 не более чем 2.0 p.u.⁴

(Pg4 ≤ 2.0). Значения для V_j и V_j были установлены 0, 9 и 1, 1 соответственно.

В самой простой формулировке задача заключается в нахождении объемов

генерации для удовлетворения заданного спроса на каждом из доступных

генераторов при ограничении на напряжение и мощности генераторов.

∑

(26)

min

ℜ(s_j) + P^lj,

j∈G

(27)

V_j ≤ |V_j| ≤ V_j

∀j = 1,n,

(28)

ℜ(s_j ) + P^lj

= 0,

∀j ∈ G,

ℑ(s_j) + Q^lj = 0,

∀j ∈ G,

ℜ(s₄) + Pl4 ≤ Pg4.

В задаче (26) целевая функция заключается в минимизации генерации

суммарной активной мощности на всех генераторах при ограничении (27)

на напряжение на каждом узле и отсутствии генерации (28) на узлах-

потребителях.

4.1. Полуопределенная релаксация

Делаем замену переменных вида W = V V^H, перепишем исходную задачу

в новых переменных, которыми являются элементы эрмитовой матрицы W :

∑

min

ℜ(s_j) + P^lj,

j∈G

Vj2 ≤ W_jj ≤ Vj2,

∀j = 1,n,

ℜ(s_j ) + P^lj = 0,

∀j ∈ G,

ℑ(s_j) + Q^lj = 0,

∀j ∈ G,

ℜ(s₄) + Pl4 ≤ Pg4,

W ≽ 0.

Для данного примера SDP-релаксация является точной. Матрица W име-

ет одно ненулевое собственное значение (rank(W ) = 1), и оно положитель-

ное (W ≽ 0), значит, можно восстановить исходный вектор V по формуле

⁴ per unit - относительные единицы. Все величины (комплексные напряжения, мощно-

сти) нормируются делением на базовую величину. Здесь базовое значение для мощности -

100, напряжения сразу вычисляются в относительных единицах.

Таблица 2. Оптимальные режимы релаксаций

Напряжение (|V |∡V )

Номер узла

SDP

Chordal

SOCP

1,0488∡1,3843^◦

1,0488∡1,3839^◦

1,0488∡1,378^◦

1,0183∡ - 1,1234^◦

1,0183∡ - 1,1236^◦

1,0183∡ - 1,121^◦

1,0094∡ - 1,3536^◦

1,0094∡ - 1,3539^◦

1,0094∡ - 1,3575

1,0476∡0^◦

Таблица 3. Генерация в оптимальном режиме

Генерация P^gj + iQ^gj

Номер узла

SDP

Chordal

SOCP

3,0447 + i1,6009

3,0447 + i1,6016

3,0447 + i1,6007

2 + i1,721

2 + i1,7203

2 + i1,7212

Суммарная генерация

5,0447 + i3,3219

5,0447 + 3,3219i

√

V =

λh, где λ — ненулевое собственное значение, а h — соответствующий

собственный вектор матрицы W . Оптимальный режим и генерация в опти-

мальном режиме представлены в табл. 2 и 3 соответственно.

Потери активной мощности в сети составляют 0,0447 p.u.

4.2. Хордальная релаксация

Граф сети не является хордальным, поэтому сначала необходимо найти

его хордальное расширение. На рис. 5 представлено одно из трех возможных

расширений.

Рис. 5. Хордальное расширение графа сети из четырех узлов.

В этом графе имеются две максимальные клики

— C₁ = {1,2,4} и

C₂ = {1,3,4}. И условие W ≽ 0 упрощается до WC1 ≽ 0 и WC2 ≽ 0.

∑

min

ℜ(s_j) + P^lj,

j∈G

Vj2 ≤ W_jj ≤ Vj2,

∀j = 1,n,

ℜ(s_j ) + P^lj = 0,

∀j ∈ G,

ℑ(s_j) + Q^lj = 0,

∀j ∈ G,

ℜ(s₄) + Pl4 ≤ Pg4,

WC1 ≽ 0,

WC2 ≽ 0.

Решая задачу, получаем некоторую частичную матрицу W , ее подматри-

цы, соответствующие кликам C₁ и C₂, являются неотрицательно определен-

ными с рангом, равным одному. Следовательно, релаксация является точной

и можно дополнить частично определенную матрицу W до полной неотрица-

тельно определенной матрицы с единичным рангом. Восстанавливая режим,

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

луопределенной релаксации, но со слегка отличными углами. Генерация от-

личается только реактивной составляющей. Данные приведены в табл. 3.

4.3. Коническая релаксация

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

графа. Условие W ≽ 0 заменяется на W (e) ≽ 0, ∀(j, k) ∈ E. Т.е. для каждого

ребра графа строится матрица (2 × 2) вида

]

^[W_jj W_jk

W (e) =

W_kj W_kk

Напомним, что матрица W является эрмитовой, поэтому W_jk = WHkj.

В остальном запись задачи остается похожей на случай хордальной релак-

сации.

∑

min

ℜ(s_j) + P^lj,

j∈G

Vj2 ≤ W_jj ≤ Vj2,

∀j = 1,n,

ℜ(s_j ) + P^lj = 0,

∀j ∈ G,

ℑ(s_j) + Q^lj = 0,

∀j ∈ G,

ℜ(s₄) + Pl4 ≤ Pg4,

W (e) ≽ 0, ∀e = (j, k) ∈ E.

Все подматрицы, соответствующие ребрам графа, являются неотрицатель-

но определенными с единичным рангом. Также необходимо проверить усло-

вие на цикл.

В графе есть один цикл (без учета направления движения)

—

((1, 3), (3, 4), (4, 2), (2, 1)). Оптимальное решении релаксированной задачи

⎛

⎞

1,1000 + 0i

1,0670 + 0,0468i

1,0574 + 0,0505i

⎜

⎟

⎜1,0670 - 0,0468i

1,0369 + 0,0000i

1,0665 - 0,0209i⎟

⎜

⎟

⎝1,0574 - 0,0505i

1,0188 + 0,0000i

1,0571 - 0,0251i⎠

−

1,0665 + 0,0209i

1,0571 + 0,0251i

1,0975 + 0i

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

условие, получаем

ℑ(W (1, 3)) + ℑ(W (3, 4)) + ℑ(W (4, 2)) + ℑ(W (2, 1)) ≈ 0 mod 2π.

Следовательно, релаксация точная, можно восстановить оптимальный ре-

жим.

Значения |V_j | для всех узлов восстанавливаются по формуле

√

|V_j | =

W_jj.

Значения углов восстанавливаются из исходной матрицы W^∗ с использо-

ванием подматрицы для ребер W (e). Пусть генератор на узле 4 будет “сла-

ком”⁵, т.е. зафиксируем ∡V₄ = 0. Восстановить угол для узла k, зная угол на

смежном узле j, можно следующим образом:

W_kj = V_kVHj,

|W_kj| = |V_k||V_j |,

∡W_kj = ei(∡Vk-∡Vj),

∡V_k = ∡W_kj + ∡V_j.

Восстанавливая напряжения описанным способом, получаем режим, ана-

логичный полуопределенной и хордальной релаксациям (табл. 2 и 3).

В этой главе были подробно разобраны три эквивалентные релаксации

для AC-формулировки задачи OPF. На простом примере было показано, как

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

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

И было показано, как восстановить оптимальный режим из однорангового

решения релаксированной задачи. Если для SDP-релаксации процедура до-

вольно проста и очевидна, то в случае конической релаксации все не так

тривиально.

⁵ slack bus - специальный узел сети, используемый при решении задач о потоках в

энерегетических сетях, для балансировки активной и реактивной мощностей в сети.

Для данного простого примера, хотя сеть не является древовидной, все

три релаксации оказались точными, полученные решения и восстановленные

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

реактивной генерации, точнее в распределении некоторой оптимальной вели-

чины реактивной генерации между двумя генераторами, что ведет к отличи-

ям в углах напряжения в оптимальном режиме.

В [10] приводятся численные эксперименты, из которых видно, что с ро-

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

времени. Для сети из почти 2400 узлов время работы в 6,5 раз меньше, чем

у хордальной. А SDP-релаксацию для 2400 узлов авторы даже не запускали.

5. Заключение

Для определения оптимального режима работы энергетической сети ис-

пользуются различные подходы, но самым точным режимом является ре-

шение задачи AC-OPF. Это достигается за счет включения в формулировку

различных инженерных ограничений, которые позволяют очень точно учесть

все особенности конкретной электроэнергетической сети. По этой причине за-

дача очень важна для индустрии.

Главной сложностью AC-формулировки является невыпуклость задачи,

что создает трудности для быстрого и точного решения. Справиться с этой

проблемой позволяют выпуклые релаксации - исходное множество допусти-

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

задача. При этом сохраняется исходная физическая структура задачи. К со-

жалению, релаксации не всегда оказываются точными. На данный момент

сформулированы условия точной релаксации только для древовидных сетей,

а в реальных сетях не всегда отсутствуют циклы.

В данной работе были описаны пять различных релаксаций: полуопре-

деленная (SDP), хордальная, коническая (SOCP), релаксация моментов и

QC-релаксация. Использование первых трех релаксаций было по шагам разо-

брано на простом примере. Каждая из них обладает своими преимущества-

ми и недостатками. Например, полуопределенная релаксация очень проста

для понимания и использования. Хордальная требует дополнительного по-

строения хордального расширения графа сети и нахождения максимальных

клик, что также является нетривиальной задачей, но это необходимо сделать

один раз для конкретной сети. За счет перехода от полной матрицы сети к

подматрицам клик удается воспользоваться разреженностью сети, не сильно

проигрывая полуопределенной релаксации по точности. Коническая релак-

сация также использует разреженность сети и не требует дополнительных

преобразований графа, но является менее точной по сравнению с полуопре-

денной и хордальной. Релаксация моментов является тем точнее, чем выше

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

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

увеличения времени получения решения или вовсе сделать задачу неразре-

шимой. QC-релаксация достигает точности полуопределенной релаксации, но

не требует рангового условия, т.е. всегда можно восстановить напряжения.

Кроме того, QC обладает схожей с SDP точностью.

В работе была рассмотрена простая постановка задачи Optimal Power

Flow, с классическими генераторами и заданным спросом. Вообще говоря, ре-

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

инженерных ограничений. Во-первых, за последние годы существенно уве-

личилась доля альтернативных генераторов, которые предоставляют очень

дешевую энергию, но обладают высокой нестабильностью. Поэтому добавле-

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

рода неопределенностей. Помимо возобновляемой генерации, другим суще-

ственным источником неопределенностей является спрос, который также яв-

ляется случайной величиной. Добавление неопределенностей в классическую

формулировку ведет к задаче Stochastic Optimal Power Flow, решая которую,

не хотелось бы оставаться слишком консервативным (что часто бывает при

решении стохастических оптимизационных задач), так как незначительные

улучшения в решении ведут к значительной экономии денег. Во-вторых, на

практике необходимо учитывать большое число различных критериев без-

опасности или наличия резервов генерации, например (N - 1)-критерий.⁶

Тем не менее, главным вопросом остается набор условий, при которых

релаксации остаются точными для смешанных сетей. Пока не удается от-

ветить на этот вопрос даже в случае простой AC-формулировки без сто-

хастики и дополнительных инженерных ограничений. Случается так, что

небольшие изменения данных приводят к тому, что конкретная задача ста-

новится неразрешимой или полученное решение имеет ранг больше 1, что

не позволят восстановить оптимальный режим. Помимо сложностей из-за

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

из-за слишком большой размерности, например, Российская сеть включает

примерно 9000 узлов, следовательно, в SDP-релаксации будет симметричная

(9000 × 9000)-матрица переменных. SDP такой размерности практически не

решаемы или время нахождения решения превысит доступный лимит вре-

мени. Конечно, хордальная и коническая релаксация позволяют снизить раз-

мерность за счет разреженности сети, но этого может оказаться недостаточно

или они могут оказаться неточными. Для этого необходима разработка чис-

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

СПИСОК ЛИТЕРАТУРЫ

1. Cain M., O’Neill R., Castillo A. History of optimal power flow and formulations //

Federal Energy Regulatory Commission. 2012. V. 1. P. 1-36.

2. Stott B., Alsac O. Optimal Power Flow-Basic Requirements for Real-Life Problems

and Their Solutions // SEPOPE XII Sympos., Rio de Janeiro, Brazil, 2012. V. 1.

P. 1866-76.

3. Веников В.А., Суханов Р.П. Кибернетические модели электрических систем: М.:

Энергоиздат, 1982.

4. Stott B., Jardim J., Alsac O. DC Power Flow Revisited // IEEE Transact. Power

Syst. 2009. V. 24. No. 3. P. 1290-1300.

5. Momoh J. Electric Power System Applications of Optimization. Boca Raton: CRC

Press, 2009.

⁶ Оптимальный режим должен оставаться достижимым при выходе из строя одного

генератора или линии.

Zhifeng Q., Deconinck G., Belmans R. A Literature Survey of Optimal Power Flow

Problems in the Electricity Market Context // IEEE/PES Power Syst. Conf. Expos.

2009. V. 1. P. 1-6.

Gan L., Li N., Topcu U., Low S. Exact Convex Relaxation of Optimal Power Flow

in Radial Networks // IEEE Transact. Autom. Control. 2015. V. 60. No. 1. P. 72-87.

Zorin I., Vasilyev S., Gryazina E. Fragility of the semidefinite relaxation for the

optimal power flow problem // IEEE Int. Conf. Sci. Electr. Engineer. (ICSEE).

2016. P. 1-5.

Boyd L., Vandenberghe S. Semidefinite Programming // SIAM Rev. 1996. V. 38.

No. 1. P. 49-95.

10.

Bose S., Low S., Teeraratkul T., Hassibi B. Equivalent Relaxations of Optimal Power

Flow // IEEE Transact. Autom. Control. 2015. V. 60. No. 3. P. 729-742.

11.

Lavaei J., Low S. Zero Duality Gap in Optimal Power Flow Problem // IEEE

Transact. Power Syst. 2011. V. 27. P. 92-107.

12.

Capitanescu F. Critical review of recent advances and further developments needed

in AC optimal power flow // Electr. Power Syst. Res. 2016. V. 136. P. 57-68.

13.

Lesieutre B., Molzahn D., Borden A., DeMarco C. Examining the limits of the

application of semidefinite programming to power flow problems // Proc. Allerton

Conf. 2011. V. 1. P. 1492-1499.

14.

Robert G., Johnson C., Sa E., Wolkowicz H. Positive Definite Completions of Partial

Hermitian Matrices // Linear Algebra Its Appl. 1984. V. 58. P. 109-24.

15.

Woerdeman H. Minimal Rank Completions for Block Matrices // Linear Algebra Its

Appl. 1989. V. 121. P. 105-22.

16.

Mituhiro F., Kojima M., Murota K., Nakata K. Exploiting Sparsity in Semidefinite

Programming via Matrix Completion I: General Framework // SIAM J. Optim. 2001.

V. 11. P. 647-74.

17.

Low S. Convex Relaxation of Optimal Power Flow-Part I: Formulations and

Equivalence // IEEE Transact. Control Net. Syst. 2014. V. 1 No. 1. P. 15-27.

18.

Low S. Convex Relaxation of Optimal Power Flow-Part II: Exactness // IEEE

Transact. Control Net. Syst. 2014. V. 1. No. 2. P. 177-189.

19.

Molzahn D., Hiskens I. Moment-Based Relaxation of the Optimal Power Flow

Problem // Power Syst. Comput. Conf. (PSCC). 2014. V. 1. P. 1-7.

20.

Josz C., Maeght J., Panciatici P., Gilbert J. Application of the Moment-SOS

Approach to Global Optimization of the OPF Problem // IEEE Transact. Power

Syst. 2015. V. 30. No. 1. P. 463-470.

21.

Lasserre J. Global Optimization with Polynomials and the Problem of Moments //

SIAM J. Optim. 2006. V. 11 No. 3. P. 796-817.

22.

Lasserre J. Moments, Positive Polynomials and Their Applications. London: Imperial

College Press, 2010.

23.

Coffrin C., Hijazi H., Van Hentenryck P. The QC Relaxation: A Theoretical and

Computational Study on Optimal Power Flow // IEEE Transact. Power Syst. 2016.

V. 31. No. 4. P. 3008-3018.

24.

Hijazi H., Coffrin C., Van Hentenryck P. Convex Quadratic Relaxations for Mixed-

Integer Nonlinear Programs in Power Systems // Math. Program. Comput. 2017.

V. 9. No. 3. P. 321-367.

25.

Zimmerman R., Murillo-Sanchez C., Thomas R. MATPOWER: Steady-State

Operations, Planning and Analysis Tools for Power Systems Research and Education

// IEEE Transact. Power Syst. 2011. V. 26. No. 1. P. 12-19.