ИСПОЛЬЗОВАНИЕ  СИМВОЛЬНЫХ  ВЫЧИСЛЕНИЙ  В  ЗАДАЧАХ  КОНЕЧНОМЕРНОЙ  ОПТИМИЗАЦИИ

Новиков  Максим  Юрьевич

ассистент  кафедры  анализа  систем  и  принятия  решений  Уральского  Федерального  Университета;  Аспирант  Института  Математики  и  Механики  Уральского  отделения  Российской  Академии  Наук,  РФ,  г.  Екатеринбург

E-mail: 

THE  USE  OF  SYMBOLIC  COMPUTATIONS  IN  PROBLEMS  OF  FINITE‑DIMENSIONAL  OPTIMIZATION

Novikov  Maxim

assistant  of  the  department  of  systems  analysis  and  decision-making  of  the  Ural  Federal  University;  post-graduate  student  of  the  Institute  of  Mathematics  and  Mechanics,  Ural  Branch  of  the  Russian  Academy  of  Sciences,  Russia,  Yekaterinburg

АННОТАЦИЯ

Работа  посвящена  вопросам  использования  символьных  вычислений  для  реализации  алгоритмов  решения  задач  конечномерной  оптимизации  на  ЭВМ.  Представлены  некоторые  особенности  и  сравнение  результатов  вычислений  частных  задач  численными  методами  и  символьными  вычислениями  на  языках  С/С++  и  Python  соответственно.  На  основе  проведенного  исследования  автором  сформулированы  рекомендации  по  использованию  символьных  вычислений  для  решения  задач  конечномерной  оптимизации,  используя  библиотеку  SymPy.

ABSTRACT

The  work  is  devoted  to  the  use  of  symbolic  computations  to  implement  algorithms  of  solving  tasks  of  finite-dimensional  optimization  on  the  computer.  There  are  some  features  and  comparing  of  the  results  of  calculations  of  particular  problems  by  using  numerical  methods  and  symbolic  computations  on  programming  languages  C/C++  and  Python  respectively.  On  the  basis  of  the  research,  the  author  has  formulated  the  recommendations  how  to  use  symbolic  computations  for  solving  problems  of  finite-dimensional  optimization  by  using  the  library  of  SymPy. 

Ключевые  слова:  оптимизация;  метод;  алгоритм;  градиент;  функция.

Keywords:  optimization;  method;  algorithm;  gradient;  function.

Современное  развитие  вычислительной  техники  и  интенсивное  проникновение  математических  моделей  в  различные  области  науки  является  хорошим  двигателем  прогресса  в  различных  областях  человеческой  деятельности.  Многие  отрасли  производства,  науки  и  экономики  используют  математику  не  только  как  орудие  для  вычислений,  но  и  как  метод  исследования  процессов  и  закономерностей.  В  процессе  исследования  и  проектирования  моделей  обычно  ставится  задача  определения  наилучших  параметров  объектов.  Задача  поиска  минимума  или  максимума  целевой  функции  на  заданной  области  конечномерного  пространства,  ограниченной  набором  равенств  и/или  неравенств  называется  задачей  оптимизации.  Математическое  программирование  –  область  математики,  которая  изучает  методы  решения  задач  на  оптимизацию  с  ограничениями.  Несмотря  на  развитие  теории  оптимизации,  по  сей  день  остаются  актуальными  вопросы  практической  реализации  методов  и  алгоритмов  решения  задач  математического  программирования.

При  решении  задач  оптимизации  численными  методами.  Возникает  ряд  трудностей  и  вопросов.  Каким  образом  выбрать  подходящее  начальное  приближение?  Ведь  если  задача  содержит  нелинейные  функции,  значит,  возможно,  существует  несколько  экстремумов.  Таким  образом,  если  выбрать  начальное  приближение,  которое  слишком  далеко  от  искомого  решения,  оптимизация  может  остановиться  в  точке  локального  экстремума.  С  целью  устранения  данного  эффекта  необходимо  тщательно  выбирать  начальные  значения  переменных.  Часто  приблизительные  значения  получают,  используя  ранее  проведенные  исследования  или  исходя  из  логических  соображений.  Альтернативный  вариант  заключается  в  использовании  нескольких  начальных  данных  из  допустимой  области.  При  таком  подходе  проверяют,  является  ли  результатом  вычислений  критерия  одно  и  то  же  значение.

Другой,  не  менее  важный  вопрос,  касается  уменьшения  ошибок  вычислительной  процедуры.  Нередко  в  процессе  вычисления  возникают  большие  погрешности,  что  снижает  эффективность  большого  числа  алгоритмов  оптимизации.  Наиболее  часто  доставляют  неприятность  ошибки  при  округлении,  а  также  при  аппроксимации  производных  разностными  выражениями.  При  программировании  компьютерных  алгоритмов  для  минимизации  ошибок  можно  использовать  символьные  вычисления  вместо  численных  методов.

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

f  =(x₁,x_2,  …, х_n)  →  min  (max).                                      (1)

При  этом  функция  f  выпукла  вниз  (вверх)  и  непрерывно  дифференцируема  на  множестве  X  (выпуклое  замкнутое  множество).

Для  подобных  задач  нет  единого  метода  решения.  В  зависимости  от  вида  целевой  функции  и  системы  ограничений  разработаны  специальные  методы  решения.  Рассмотрим  алгоритм  метода  проекции  градиента  в  общем  виде  [1,  с.  269].  На  основе  анализа  алгоритма  можно  сформулировать  рекомендации  для  его  реализации  на  одном  из  современных  языков  программирования.  Ниже  представлен  наиболее  оптимальный  по  мнению  автора  алгоритм  метода  проекции  градиента.

Задача.   Найти    для  заданной  функции    и  заданного  множества  .  Функция    выпукла  вниз  и  непрерывно  дифференцируема  на  множестве  X  (выпуклое  замкнутое  множество)

Алгоритм

Н  а  ч  а  л  о.

           I. Выбрать  начальное  приближение 

        II. Присвоить  k=0.

О  с  н  о  в  н  о  й  ц  и  к  л.

     III. Вычислить 

    IV. Выбрать  множитель  ,  удовлетворяющий  условию:

                           (2)

       V. Вычислить  точку  по  формуле:

                       (3)

    VI. Вычислить  точку    —  проекцию  точки    на  выпуклое  замкнутое  множество  X.

 VII. Вычислить  множитель    по  формуле:

        (4)

VIII. Присвоить:

                          (5)

                                          (6)

и  перейти  к  шагу  III.

К  о  н  е  ц.

Наибольшую  трудность  при  практической  реализации  алгоритма  может  доставить  вычисление  проекции  точки  на  множество.  Дело  даже  не  в  том,  что  далеко  не  для  всех  множеств  можно  найти  точную  проекцию.  Исходя  из  определения,  проекцией  точки    на  множество    называется  вектор  ,  удовлетворяющий  условию:

                                (7)

Рисунок  1.  Геометрическая  иллюстрация  проекции  точки  на  множество

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

                             (8)

Очевидно,  что  задача  отыскания  проекции  точки  на  выпуклое  множество  –  это  задача  минимизации  выпуклой  функции  на  выпуклом  множестве.  Необходимо  заметить,  что,  как  правило,  отыскать  точно  проекцию  точки  невозможно.  Поэтому  приходится  пользоваться  процедурами  для  нахождения  приближенных  значений  проекции.  Однако,  при  достаточно  «простых»  множествах  X  проекцию  можно  вычислить,  пользуясь  достаточно  простыми  «явными»  формулами.  Приведем  несколько  примеров  таких  множеств  [3].

Пусть  произвольная  точка.

·     Шар:  ,  то 

                                               (9)

·     Координатный  параллелепипед:  ,  то

                                  (10)

·     Неотрицательный  ортант:  ,  то 

                              (11)

·     Гиперплоскость:  ,  ()  то 

                                   (12)

·     Полупространство:  ,  (),  то 

                 (13)

Среди  множества  современных  языков  программирования,  одним  из  наиболее  удобных  для  научных  вычислений,  является  интерпретируемый  язык  Python  [4].  Язык  близок  с  MATLAB  и  хорош  для  программирования  математических  вычислений.  К  тому  же  Python  умеет  работать  с  такими  языками  как  Fortran,  C  и  С++,  которые  уже  широко  используются  в  научных  расчетах.  Имеется  большое  количество  модулей,  написанных  на  Python,  которые  упрощают  процесс  вычисления  (NumPy,  SymPy  и  другие).

Процесс  вычисления  минимума  функции  методом  проекции  градиента  будет  зависеть  от  выпуклого  замкнутого  множества  X.  Его  тип  будет  определять,  какая  формула  должна  быть  использована  с  целью  вычисления  координат  проекции  точки  на  множество  X.

Первый  шаг  основного  цикла  заключается  в  поиске  значения  градиента  функции  в  точке  x_0.  Данная  точка  является  точкой  начального  приближения  для  первой  итерации,  а  в  последствии  —  меняется  на  вычисленные  в  ходе  текущей  итерации  новые  значения. 

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

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

  , 

где

vars_func   —  список,  содержит  имена  аргументов,  например,  [«x1»,  «x2»];

grad_func   —  список,  содержит  частные  производные  в  явном  виде;

funct  —  функция,  заданная  в  явном  виде  с  переменными  из  vars_func.

Численное  значение  градиента  функции  в  точке    вычисляется  на  каждой  итерации:

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

Функция  eval  служит  для  обработки  строк  «на  лету»  при  обрабатывании  математических  формул,  а  exec  позволяет  выполнить  любой  код  на  Python  [2].  В  качестве  примера  использования  данных  функций  можно  привести  следующий:

При  перечислении  элементов  из  списка  x0,  формируется  строчка  на  языке  Python,  которая  присваивает  переменной  соответствующее  значение.  Функция  exec  выполняет  код. 

Алгоритм,  написанный  на  языке  C++,  будет  лишен  той  гибкости,  которую  предоставляет  интерпретируемый  язык  Python.  Ввод  функций  в  процессе  работы  программы  и  ее  последующая  обработка,  с  первого  взгляда,  не  представляется  возможной.  Возникает  мысль  о  необходимости  создания  мини‑интерпретатора  для  математических  выражений,  однако,  такой  подход  очень  трудоемок. 

Алгоритм  метода  проекции  градиента  предполагает  получение  в  качестве  входных  данных  функцию  нескольких  переменных.  При  этом  программа  должна  воспринимать  ее  именно  как  математическое  выражение,  а  не  как  массив  символов.  Допуская  некоторые  ограничения  по  вводу  пользователем  функций,  можно  избавиться  от  проблемы  получения  начальных  данных.  Например,  используя  в  качестве  допустимых  переменных  только  вида    и,  применив  обратную  польскую  нотацию,  можно  получать  численное  значение  заданной  функции  в  точке  начального  приближения.  В  ходе  выполнения  основного  цикла  подсчет  значений  )  можно  производить  по  этой  же  схеме.

Метод  проекции  градиента  использует  значения  частных  производных  заданной  функции  в  точке  .  Поэтому  неприятным  моментом  при  реализации  алгоритма  на  языке  C++  может  стать  отсутствие  хороших  библиотек  символьных  вычислений.  Если  на  языке  Python  можно  было  вычислить  частные  производные  функции  и  затем  подставить  в  их  формулы  конкретные  значения,  то  на  языке  C++  это  не  представляется  возможным.  В  этом  случае  приходится  применять  численное  решение  задачи  нахождения  производной  исходя  из  того,  что  разностное  отношение:

                                                 (14)

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

  ,             (15)

мы  можем  приближенно  заменить    этим  разностным  отношением  с  достаточно  малым  h. 

При  реализация  алгоритма  на  языке  Python  выявлено,  что  использование  символьных  вычислений  и  интерпретируемого  языка  очень  удобно  при  решении  задач  математического  программирования.  Пользователь  может  самостоятельно  вводить  любые  допустимые  функции,  определять  количество  переменных  функции,  таким  образом,  ему  предоставляется  возможность  управлять  работой  программы  в  процессе  ее  исполнения.  К  недостаткам  интерпретируемой  программы  можно  отнести  невозможность  ее  выполнения  без  программы-интерпретатора.  Вторым  неприятным  качеством  программы  на  языке  Python  стала  довольно  низкая  общая  производительность  собранного  приложения.

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

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

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

Список  литературы:

1.Бейко  И.В.  Методы  и  алгоритмы  решения  задач  оптимизации.  Бейко  И.В.,  Бублик  Б.Н.,  Зинько  П.Н.  К.:  Вища  школа.  Головное  издательство,  1983  —  512  с.

2.Документация  SymPy  /  [Электронный  ресурс].  —  Режим  доступа.  —  URL:  http://sympy.org/en/index.html  (дата  обращения:  04.02.2015).

3.Интернет-учебник  по  курсу  «Методы  оптимизации»  /  [Электронный  ресурс].  —  Режим  доступа.  —  URL:  http://kek.ksu.ru/EOS/MO/uchebnik.asp  (дата  обращения:  16.01.2015).

4.Статья  «Программирование  и  научные  вычисления  на  языке  Python».  /  [Электронный  ресурс].  —  Режим  доступа.  —  URL:  http://ru.wikiversity.org/wiki/  (дата  обращения:  01.02.2015).