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

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

Рассматривается разрешимость специальной задачи вогнутого программирования на пересечении конечного числа шаров и строится эффективный способ вычисления значения выпуклой функции. Доказывается единственность решения задачи шаров. В общем случае приводится верхняя оценка для этой задачи....

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2014
1. Verfasser: Ненахов, Э.И.
Format: Artikel
Sprache:Russian
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2014
Schriftenreihe:Теорія оптимальних рішень
Online Zugang:http://dspace.nbuv.gov.ua/handle/123456789/111516
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:О решении экстремальных задач при квадратичных условиях / Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 98-105. — Бібліогр.: 4 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-111516
record_format dspace
spelling irk-123456789-1115162017-01-11T03:03:19Z О решении экстремальных задач при квадратичных условиях Ненахов, Э.И. Рассматривается разрешимость специальной задачи вогнутого программирования на пересечении конечного числа шаров и строится эффективный способ вычисления значения выпуклой функции. Доказывается единственность решения задачи шаров. В общем случае приводится верхняя оценка для этой задачи. Розглядається розв’язність спеціальної задачі увігнутого програмування на перетині скінченого числа куль та будується ефективний спосіб обчислення значення опуклої функції. Доводиться єдність розв’язку задачі куль. В загальному випадку приводиться верхня оцінка для цієї задачі. A solvability of special case of the concave programming problem in a set determined by the intersection of a finite collection of balls is considered and construct an effective way for calculating mean of convex function. We proved a unique solution of the ball problem. For the general case upper bound of this problem is obtained. 2014 Article О решении экстремальных задач при квадратичных условиях / Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 98-105. — Бібліогр.: 4 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/111516 519.8 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
description Рассматривается разрешимость специальной задачи вогнутого программирования на пересечении конечного числа шаров и строится эффективный способ вычисления значения выпуклой функции. Доказывается единственность решения задачи шаров. В общем случае приводится верхняя оценка для этой задачи.
format Article
author Ненахов, Э.И.
spellingShingle Ненахов, Э.И.
О решении экстремальных задач при квадратичных условиях
Теорія оптимальних рішень
author_facet Ненахов, Э.И.
author_sort Ненахов, Э.И.
title О решении экстремальных задач при квадратичных условиях
title_short О решении экстремальных задач при квадратичных условиях
title_full О решении экстремальных задач при квадратичных условиях
title_fullStr О решении экстремальных задач при квадратичных условиях
title_full_unstemmed О решении экстремальных задач при квадратичных условиях
title_sort о решении экстремальных задач при квадратичных условиях
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate 2014
url http://dspace.nbuv.gov.ua/handle/123456789/111516
citation_txt О решении экстремальных задач при квадратичных условиях / Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 98-105. — Бібліогр.: 4 назв. — рос.
series Теорія оптимальних рішень
work_keys_str_mv AT nenahovéi orešeniiékstremalʹnyhzadačprikvadratičnyhusloviâh
first_indexed 2025-07-08T02:16:34Z
last_indexed 2025-07-08T02:16:34Z
_version_ 1837043281380245504
fulltext 98 Теорія оптимальних рішень. 2014 ТЕОРІЯ ОПТИМАЛЬНИХ РІШЕНЬ Рассматривается разрешимость специальной задачи вогнутого программирования на пересечении конечного числа шаров и стро- ится эффективный способ вычи- сления значения выпуклой функ- ции. Доказывается единствен- ность решения задачи шаров. В общем случае приводится верхняя оценка для этой задачи.   Э.И. Ненахов, 2014 УДК 519.8 Э.И. НЕНАХОВ О РЕШЕНИИ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ ПРИ КВАДРАТИЧНЫХ УСЛОВИЯХ Предметом исследования являются экстремальные задачи на пересечении конечного числа шаров. Такого типа задачи возникают, например, в максминной проблеме лока-лизации [1]. Общая задача вогнутого программирования может иметь локальные экстремумы и сложно найти ее глобальный экстремум. Укажем вначале возможность сведения задачи вогнутого программирования к задаче строго вогнутого квадратичного програм-мирования. Для решения последней задачи существуют различные эффективные алгоритмы [2]. Рассмотрим в пространстве nR задачу вогнутого программирования в следующем виде:       max , 0, , , 1,...,i ic x x a x b i m       max ,c x x D  , (1) где  x – вогнутая функция, множество   mibxaRxM ii n ,...,1,,:  ограниченное. Пусть выполняется условие Слейтера и обозначим множество решений задачи (1) D Ø. Определение. Задача вогнутого программирования (1) удовлетворяет условию ,U если существует 0  такое, что для всех , 0  ,    справедливо следующее равенство     arg max , ,x c x x x x D        argmax ,x x x D   . (2) О РЕШЕНИИ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ … Теорія оптимальних рішень. 2014 99 Теорема 1. Для того, чтобы задача вогнутого программирования (1) удовлетворяла условию ,U необходимо и достаточно, чтобы функция Лагранжа задачи строго вогнутого программирования            max , , , , 0, max ,x x c x c x x x M x x x D         (3) обладала седловой точкой на множестве 2.M R Доказательство. Необходимость. Пусть справедливо условие .U При 0     для задачи     max , ,c x x x x D   выполнены условия теоремы Куна – Таккера [3]. Тогда существует число 0  такое, что          , , , , ,с x x x c x x x x x M          или            1 , , , , , .x x x x c x c x x x M               Это означает, что существует седловая точка функции Лагранжа задачи (3). Достаточность. В силу условия Слейтера существует седловая точка функции Лагранжа задачи (1)  , :x       , , , , 0.c x c x x x M       (4) Но по условию теоремы существует седловая точка функции Лагранжа задачи (3)  0 1 0 1, , , 0, 0 :x                 0 1, , , , , .x x x x c x c x x x M           (5) В случае 0 0  из (5) следует   argmax ,x x x x D    и для любого 0  выполняется условие    , , , .x x x x x D      (6) Складывая неравенства (4), (6) и учитывая (3), получаем выполнение (2) для всех 0.  В случае 0 0  из (5) следует          2, , , , , ,c x x x c x x x x x M             (7) Э.И. НЕНАХОВ 100 Теорія оптимальних рішень. 2014 где 0 2 1 00 1/ , / .        Пусть 0 1,p  умножим (4) на  1 ,p а (7) – на ,p сложим полученные неравенства. Тогда для любого p    выполняется неравенство             2, , , , 1 , ,c x x x c x x x p p x x M               из которого вновь следует (2). Теорема доказана. Итак, выполнение условия U обеспечивает сведение задачи вогнутого программирования к параметрической задаче строго вогнутого программирования. В качестве целевой функции задачи вогнутого программирования всегда можно брать линейную функцию. Заметим также, что общая задача линейного программирования удовлетворяет условию U [4]. Далее, определим множества       : , , , 1,..., ,i iD b x x x a x i m     : ,Y y Cy d  где , ,n k ia R d R  матрица C порядка .k n Рассмотрим задачу выпуклого программирования     2 min min max . y Y y Y x D b f y y x      (8) Для нахождения значения выпуклой функции  yf в данной точке Yy необходимо решить задачу вогнутого программирования на пересечении шаров, которая может иметь локальные экстремумы. Однако, как будет показано далее, существует условие, при котором решение единственно. Это дает возможность легко минимизировать выпуклую функцию при линейных ограничениях. Пусть     1,..., , : Ш,mb B b D b              1 , , 2 , min , ,i i i m f x y y y y x a x              , argmax , .x y b f x y x D b  (9) О РЕШЕНИИ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ … Теорія оптимальних рішень. 2014 101 Определим множество 1 1 : , 0, 1 / 2 . m m i i i i i i V v v a                  Если вектор  byx , принадлежит границе множества  D b , то  f y    2 , .y x y b  Действительно, предположим противное, т. е. существует точка  bDx такая, что   22 ,byxyxy  и пусть индекс i такой, что      2 , , , .i ix y b a x y b   Учитывая эти соотношения, получаем             22 , , 2 , , , ,if x y y y y x x x y x y x y b y y               2 , , , , .ia y x y b f x y b y   То есть, получено строгое неравенство     ybyxfyxf ,,,  , которое противоречит определению вектора  , .x y b Теорема 2. Для того, чтобы вектор  byx , из равенства (9) при любых BbYy  , удовлетворял     2 , argmax ,x y b y x x D b   необходимо и достаточно, чтобы выполнялось условие VY  Ø. Несложно доказать, что условие VY  Ø обеспечивает единственность взятия максимума в задаче (8) в точке  byx , . Поэтому функция  yf имеет градиент в точке     byxyyfy ,2  . Итак, данное условие обеспечивает эффективное решение задачи вогнутого программирования, а также дает простой способ вычисления субградиента выпуклой функции. Последнее существенно при решении задачи (8), например, методом описанных эллипсоидов. Для этого находим исходный эллипсоид YE 0 с центром в точке 0y . Если Yy 0 , то строим множество    0 0 0 0: , , 0 .E y y E f y y y     Э.И. НЕНАХОВ 102 Теорія оптимальних рішень. 2014 Если же 0y Y, т. е. существует неравенство   0 00, ,k kс y d то   00 0 0: , , 0 .kE y y E c y y    Здесь  0yf и 0kc – нормальные векторы отсекающих плоскостей. Далее, находится новый эллипсоид 01 EE  с наименьшим объемом и вычисления продолжаются. Число операций, требуемых для вычисления вектора-нормали, не превосходит числа операций, необходимых для максимизации кусочно- линейной вогнутой функции на пересечении конечного числа шаров. Исследуем еще одну оптимизационную задачу на пересечении шаров:       max , , , , 1,..., .i ix x x x a x b i m   (10) Отметим, что эта задача тесно связана с задачей вогнутого квадратичного программирования:     argmax , , , 1,..., .i iv x x a x b i m   (11) Действительно, рассмотрим задачу (10) в более общем виде:         argmax , , , , 1,..., .i iu p x x x x a x b p i m     (12) Пусть 2 ,p v поскольку v – допустимый вектор задачи (12), то     2 2 2 , .u v u v v (13) Так как  2 vu – допустимый вектор для задачи (11), то несложно получить противоположное неравенство для (13). Значит,   2 2 2 ,v u v т. е. оптимальные значения целевых функций задач (11) и (12) совпадают. Итак, задача вогнутого квадратичного программирования тесно связана с оптимизационной задачей на пересечении шаров. О РЕШЕНИИ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ … Теорія оптимальних рішень. 2014 103 Определим вогнутую функцию      1 min ,i i i m x b a x      и рассмотрим задачу выпуклого программирования для :b B       argmax .x b x x D b   (14) Нетрудно доказать, что вектор  bx – решение задачи (10) тогда и только тогда, когда  bx лежит на границе множества  bD . Пусть множество  , 1,..., ,iC co a i m  тогда связь между задачами (10) и (14) устанавливает Теорема 3. Для того, чтобы вектор  bx для всех Bb был решением задачи (10), необходимо и достаточно, чтобы C0 . Покажем, что задача (10) имеет единственное решение при условии C0 . Действительно, любое решение задачи (14) лежит на границе  bD . Если это не правильно, то сопряженный конус к конусу возможных направлений в точке  bx на множестве  bD содержит единственный нулевой вектор. Это означает, что   0 x b C  [3], что противоречит исходному условию. Но, в силу строгой выпуклости  bD  bx – единственное решение задачи (14), а по теореме 3 – оно также решение задачи (10). Пусть x – произвольное решение задачи (10), то выполняются равенства            , , .x x x x b x b x b     Следовательно, любое решение исходной задачи – это решение задачи (14), которое единственно. Тогда задача (10) имеет также единственное решение. Замечание 1. Если в задаче (10) вместо функции  xx, рассматривать произвольную выпуклую функцию, то теорема 3 остается правильной. Замечание 2. Пусть 0 C и для некоторого Bb  bx – не решение за- дачи (10). Тогда для любого 0p  вектор       argmax ,x x p x x x D b    не будет решением исходной задачи. Действительно, так как Э.И. НЕНАХОВ 104 Теорія оптимальних рішень. 2014                 , , , ,x b p x b x b x p x x x x b        то выполняется неравенство       xxbxbx ,,  . То есть для такого вектора b уменьшение  x не увеличивает значение целевой функции исходной задачи u , кроме того,  bDx int . Существует непустое подмножество векторов Bb , для которых при условии 0 C  bx – также решение задачи (10). Для проверки этого, в частности, достаточно проверить равенство        , .x b x b x b  Наконец, для общего случая приведем верхнюю оценку  xx,max . Пусть   bDx int0 Ø, nix i ,...,1,  , принадлежит границе  bD и n -симплекс  nxxxcoS ,...,, 10 . Будем считать, что  0 10, ,..., nx l    и    1 1 1 ,... arg max 0, . n n n i i i i i i l x D b                     Учитывая сильную выпуклость  bD получаем 1 1 n j j    и полагаем 1 , 1,..., . n i j i j x x i n     Строим новый n -симплекс    nxxxcoSp ,...,, 10 . Пусть n -симплекс  110 ...,  nyycoS такой, что  0 00 int ,S S D b  . Строим граничные точки    maxi i i i ix y y D b       и n -сим- плексы:    0 1 1 1 1, ,..., , ,..., , , 1,..., 1.i i i n iS co x x x x x p S i n     Очевидно, что     1 1    n i iSpbD . Для нахождения верхней границы       iSpbDxxx ,max решаем задачу вогнутого программирования на симплексе     ii Spxxxt  ,max1 и задачу выпуклого программирования   2 max ,i it x x Z   где функция  x определена ранее, а множество   1 1 1 1 : , 0, 1 , 1,... 1. n n i k k k k k k k i k i Z x D b x x i n                            О РЕШЕНИИ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ … Теорія оптимальних рішень. 2014 105 Лемма. Величина  1 2min ,i i it t t – верхняя граница для  max , |x x x    , 1,..., 1.iD b p S i n   Доказательство. Поскольку      ii SpSpbD  , то величина 1 it – верхняя граница. Пусть   ii Sxxxt  ,max0 , то выполняется 2010 , iiii tttt  . Если 20 ii tt  , то        10 ,max iii tSpbDxxxt   . Так как     iii ZSSpbD   , то величина 2 it – вновь верхняя граница. Отсюда вытекает утверждение. Числа 1,...,1,  niti дают грубую оценку решения исходной задачи. Однако, данный подход позволяет строить последовательности симплексов, улучшающих эту оценку и, в частности, использовать представление       1 1 : , 0 . n i k k k k k i D b p S x D b x x                    Е.І. Ненахов ПРО РОЗВ'ЯЗУВАННЯ ЕКСТРЕМАЛЬНИХ ЗАДАЧ ПРИ КВАДРАТИЧНИХ УМОВАХ Розглядається розв’язність спеціальної задачі увігнутого програмування на перетині скін- ченого числа куль та будується ефективний спосіб обчислення значення опуклої функції. Доводиться єдність розв’язку задачі куль. В загальному випадку приводиться верхня оцінка для цієї задачі. E.I. Nenakhov ON SOLUTION OF EXTREME PROBLEMS UNDER QUADRATIC CONDITIONS A solvability of special case of the concave programming problem in a set determined by the intersection of a finite collection of balls is considered and construct an effective way for calculating mean of convex function. We proved a unique solution of the ball problem. For the general case upper bound of this problem is obtained. 1. Dasarthy B., White L. A maximin location problem // Oper. Res. – 1980. – 28, N 6. – P. 1385 – 1401. 2. Horst R., Tuy H. Global optimization (Deterministic approaches). – Berlin: Springer – Verlag, 1990. – 696 p. 3. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. – М.: Наука, 1980. – 319 с. 4. Эрроу К., Гурвиц Л., Удзава Х. Исследование по линейному и нелинейному программированию. – М.: Изд-во иностр. лит., 1962. – 333 с. Получено 19.03.2014

Ähnliche Einträge