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

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

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

Как уже отмечалась ранее, исследования предполагается проводить по двум направлениям:
Стохастическая оптимизация (в приложении к задаче классического регрессионного анализа) и планирование оптимального эксперимента. В этой связи представляется целесообразным дать обзор по обеим исследуемым областям.
I. Стохастическая оптимизация.
Алгоритмы оптимизации, в целом, можно разделить на два основных класса: детерминированные и вероятностные.
Детерминированные алгоритмы чаще всего применяются в тех случаях, когда существует четкая связь между
характеристиками возможных решений и их «полезностью» для исследуемой проблемы. При этом пространство поиска решений может быть эффективно исследовано, с помощью, например, схемы "разделяй и властвуй" (divide and
conquer). Если связь между кандидатом в решение и его “пригодностью” не столь очевидна или слишком сложна, или размерность пространства поиска решений высока, решить проблему детерминировано становится существенно труднее. Попытка сделать это, скорее всего сведется к исчерпывающему перечислению всевозможных решений (из пространства поиска решений), что невозможно даже для задач сравнительно небольшой размерности.
Альтернативным подходом являются вероятностные алгоритмы. Первоначально работа в этой области, которая сейчас стала одной из важнейших областей исследований в области оптимизации, была начата около 70 лет назад (см. [1, 2, 3, 4]). Особенно перспективным семейством вероятностных алгоритмов являются подходы, основанные на методе
Монте-Карло. Они позволяют выбрать компромисс между заданной точностью решения и временем необходимым для его поиска.
Как правило, ключевая проблема, связанная с использованием вероятностных оптимизационных алгоритмов, заключается в отсутствии гарантии того, что найденное решение является действительно глобальным максимумом (минимумом). Одним из возможных путей минимизации рисков застревания в локальном максимуме (минимуме) является использование эвристик (т.е. правил, определяющих критерии отбора будущих кандидатов из пространства поиска решений) [5, 6, 7] и метаэвристик (стратегий выбора эвристик) [8, 9, 10]. Последние часто реализуются с помощью различных стохастических методов с использованием статистик, полученных из выборок из пространства поиска решений, или на основе моделей каких-либо природных явлений или физических процессов. Имитация отжига, например, определяет, какое решение-кандидат будет оценено следующим в соответствии с коэффициентом вероятности Больцмана для конфигураций атомов твердеющих металлических сплавов. Эволюционные алгоритмы моделируют поведение естественной эволюции и рассматривают кандидатов на решение как индивидуумов, которые конкурируют в виртуальной среде. Некоторые объединенные модели процедур метаэвристической оптимизации были предложены в работах Vaessens et al. [11, 12], Rayward-Smith [13], Osman [14] и Taillard et al. [15].

Важным классом вероятностных метаэвристик Монте-Карло являются эволюционное моделирование. Данный класс охватывает все алгоритмы, основанные на наборе нескольких кандидатов на решение (называемых совокупностью), которые итеративно уточняются. Эта область оптимизации также относится к классу мягких вычислений (Soft Computing), а также является частью области искусственного интеллекта. Хороший обзор эволюционных алгоритмов, основанных на моделировании биологических и физических процессов приводится в работах [16, 17]. Несмотря на большое разнообразие существующих на настоящий момент эволюционных алгоритмов данное направление интенсивно развивается (см., например, [18, 19, 20]) и является весьма актуальным.
Литература к разделу I:
[1] Herbert Robbins and Sutton Monro. A stochastic approximation method. Annals of Mathematical Statistics, 22(3):400–407, September 1951.
[2] Richard M. Friedberg. A learning machine: Part i. IBM Journal of Research and Development, 2:2–13, November 1958
[3] Woodrow “Woody” Wilson Bledsoe and I. Browning. Pattern recognition and reading by machine. In Proceedings of the Eastern Joint Computer Conference (EJCC)– Papers and Discussions Presented at the Joint IRE - AIEE - ACM Computer Conference, pages 225–232. The 1959 Eastern Joint Computer Conference for The National Joint Computer Committee, December 1–3, Boston,
Massachusetts, USA, 1959.
[4] A. Brindle. Genetic algorithms for function optimization. PhD thesis, University of Alberta, Department of Computer Science, Edmonton. Technical Report TR81-2, 1981
[5] Zbigniew Michalewicz and David B. Fogel. How to Solve It: Modern Heuristics. Springer, second, revised and extended edition, December 2004.
[6] Victor J. Rayward-Smith, Ibrahim H. Osman, Colin R. Reeves, and George D. Smith, editors. Modern Heuristic Search Methods. Wiley, December 1996.
[7] Judea Pearl. Heuristics: Intelligent Search Strategies for Computer Problem Solving. The Addison-Wesley series in artificial intelligence. Addison-Wesley Pub (Sd), April 1984
[8] Fred Glover and Gary A. Kochenberger, editors. Handbook of Metaheuristics, volume 57 of International Series in Operations Research & Management Science. Kluwer Academic Publishers / Springer, New York, USA, 2003
[9] Teofilo F. Gonzalez, editor. Handbook of Approximation Algorithms and Metaheuristics. Chapmann & Hall/CRC Computer and Information Science Series. Chapmann & Hall/CRC Press (Tailor & Francis Group), 2007.
[10] Christian Blum and Andrea Roli. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, 35(3):268–308, 2003
[11] Rob J. M. Vaessens, Emile H. L. Aarts, and Jan Karel Lenstra. A local search template. In Parallel Problem Solving from Nature, PPSN II, pages 67–76, 1992.
[12] Rob J. M. Vaessens, Emile H. L. Aarts, and Jan Karel Lenstra. A local search template. Computers and Operations Research, 25(11):969–979, November 1998.
[13] Victor J. Rayward-Smith. A unified approach to tabu search, simulated annealing and genetic algorithms. In Victor J. Rayward-Smith, editor, Applications of Modern Heuristic Methods – Proceedings of the UNICOM Seminar on Adaptive Computing and Information Processing, volume I, pages 55–78, January 25–27, 1994, Brunel University Conference Centre, London, UK.
[14] Ibrahim H. Osman. An introduction to metaheuristics. In M. Lawrence and C. Wilsdon, editors, Operational Research Tutorial Papers, pages 92–122. Stockton Press, Hampshire, UK, 1995
[15] Eric D. Taillard, Luca Maria Gambardella, Michael Gendrau, and Jean-Yves Potvin. Adaptive memory programming: A unified view of metaheuristics. European Journal of Operational Research, 135(1):1–16, November 6, 2001
[16] А. П. Карпенко. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой: учебное пособие. - 2-е изд. - Москва : Издательство МГГУ им. Н. Э. Баумана, 2017
[17] Thomas Weise. Global Optimization Algorithms – Theory and Application. e-book: http://www.it-weise.de, 2009
[18] Ermakov S. M., Semenchikov D. N. Genetic global optimization algorithms //Communications in Statistics - Simulation and Computation. — P. 1–10. — 2019.
[19] Vladimirova, L.V., Zhdanova, A.Y., Rubtsova, I.D. and Edamenko, N.S. Genetic stochastic algorithm application in beam dynamics optimization problem. Stability and Control Processes. In Proc. of the 4th International Conference Dedicated to the Memory of Professor Vladimir Zubov,
Springer International Publishing (Lecture Notes in Control and Information Sciences-Proceedings)-2020.
[20] Sergej Ermakov, Liudmila Vladimirova, Irina Rubtsova, Alexey Rubanik. Genetic Stochastic Method of Global Extremum Search for Multivariable Function, CYBERNETICS AND PHYSICS, VOL. 11, NO. 1, 11–15, 2022.

II. Планирование оптимального эксперимента.
Проблема нахождения зависимости между некоторым набором величин является одной из наиболее часто встречающихся проблем, встающих перед учеными различных специальностей. Во многих случаях искомую зависимость удается описать с помощью функции, определенной с точностью до некоторого набора неизвестных параметров, и, задача, тем самым, сводится к нахождению их оценок. Существенную роль при этом играет определение оптимальных, по некоторому критерию, условий проведения экспериментов. Известно, что создание таких условий может привести к значительной экономии средств. В случае дорогостоящих экспериментов экономия может быть колоссальной. Исследования в области планирования эксперимента актуальны в сельском хозяйстве (агрономии),
фармацевтике (испытания лекарств), при испытаниях промышленных изделий (в том числе военного назначения) и др. Правильная постановка эксперимента позволяет сократить число испытаний необходимое для получения корректных выводов.
Теория оптимального планирования регрессионных экспериментов была инициирована работами Elfving (1952), Chernoff (1953), Ehrenfeld (1955) и Kiefer, Wolfowitz (1960). Эта теория быстро развивается с конца 60-х годов и в ее развитие значительный вклад внесли российские ученые И.П. Клепиков, С.Н. Соколов, В.В. Налимов, В.В. Федоров, М.Б. Малютов, Г.К. Круг, С.М. Ермаков, В.П. Козлов и многие другие. Монография В.В. Федорова (1971) была переведена на английский язык (см. Fedorov (1972)) и оказалась первой
монографией по этой теории. Работы В.П. Козлова по планированию регрессионных экспериментов, собранные в посмертно изданной книге Козлов (2000), остаются непревзойденными до сих пор. Текущее состояние в этих исследованиях хорошо отражено в монографиях Ермаков и др. (1983), Бримкулов и др. (1986), Pukelsheim (2006), Melas (2006). Теоретическая часть исследований в области планирования эксперимента включает статистическую часть, где средствами математической статистики формируется критерий оптимальности эксперимента и разработку специальных вычислительных методов, направленных на определение оптимальных условий его проведения. Последняя задача есть задача определения экстремума функции очень большого числа переменных. Как правило, она решается также статистическими методами. Под оптимальными планами понимаются дискретные вероятностные меры, доставляющие экстремальное значение заданному функционалу от информационной матрицы Фишера. Большинство исследований относятся к линейным по
параметрам одномерным регрессионным моделям в предположении некоррелированности наблюдений. Для таких моделей получено значительное число аналитических результатов. В литературе по планированию эксперимента наиболее изученными являются оптимальные планы для линейных по параметрам регрессионных моделей (см. Pukelsheim, 2006; Fedorov, Hackl, 1997; Atkinson et al., 2007). Данные модели достаточно универсальны и получили широкое распространение на практике, однако они не всегда позволяют описать исследуемую зависимость с требуемой точностью, поэтому во многих случаях используются многомерные и
нелинейные (по параметрам) модели. Вместе с тем, такие модели изучены относительно мало. Общие результаты для многомерных моделей получены лишь для случая, когда регрессионная функция представлена в виде прямого
произведения функций одной переменной (см. монографию Schwabe (1996)). Из других случаев аналитически построены лишь D-оптимальные планы для многочленов второго порядка на гиперкубе, гипершаре и симплексе (см.
Ермаков и др. (1983, гл. 3)), планы для оценивания экстремума таких многочленов (Melas et al. (2003)) и D-оптимальные планы для сферических гармонических функций (Dette, Melas, Pepelyshev (2005)). Недавно были аналитически построены насыщенные D-оптимальные планы для двумерных моделей Эйена-Петерса, Кобба-Дугласа и Лейбла (Grigoriev, Melas and Shpilev (2017,2018,2021)).
В случае нелинейных по параметрам моделей информационная матрица зависит от истинных значений параметров модели. Для преодоления этой трудности Чернов (см. Chernoff (1953)) предложил рассматривать локально оптимальные планы, т.е. планы оптимальные для фиксированных значений неизвестных параметров. К сожалению, такие планы могут оказаться малоэффективными, так как зависят от начального приближения. Минимаксный подход к построению оптимальных планов для нелинейных моделей был развит в работах Melas (1978), Мелас (1981). Этот подход
разрабатывался многими авторами, причем в работе Muller (1995) было развито понятие максиминно эффективных планов. Такие планы максимизируют отношение эффективности рассматриваемого плана к эффективности локально-оптимального плана.

Максиминно эффективные планы более робастны, чем локально оптимальные, однако экстремум достигается на границе допустимого множества параметров. Поэтому вполне вероятным является потенциальное преимущество планов, оптимальных в смысле байесовского подхода. Байесовские оптимальные планы рассматривались многими авторами (Lauter (1974), Lauter (1976), Pronzato, Walter (1988), Chaloner and Larntz (1989), Dette, Neugebauer (1996), Han, Chaloner (2004), Dette, Neugebauer (1997)). Такой подход значительно шире локально-оптимального. Вместо задания приближений к значениям параметров этот подход предполагает задание априорной меры. Соответствующий план будет обладать высокой эффективностью для
различных значений параметров. Задание априорной меры в виде дискретной меры позволяет свести задачу построения байесовского плана к задаче построения локального плана для расширенного списка моделей. Однако построение таких планов в явном виде оказывается возможным лишь для самых простых моделей с одним неизвестным параметром. Поэтому большинство авторов исследуют байесовские планы, главным образом, численными методами. Функциональный подход, вкратце описанный выше, позволяет строить и исследовать байесовские планы с помощью степенных рядов. Что, в свою очередь, позволяет исследовать поведение функций эффективности локально-оптимальных планов по отношению к байесовским. Развитие функционального подхода позволит создать значительно более общие методы построения оптимальных планов и исследования их эффективности и робастности.

В серии работ (Yang, Stufken(2009, 2012), Yang(2010), Dette, Melas(2011)) рассмотрен вопрос о переносе на нелинейный случай знаменитого результата де ла Гарза (de la Garza(1954)) об условиях, при которых число n опорных точек в оптимальных планах для одномерных линейных моделей регрессии минимально, т. е. совпадает с числом p неизвестных параметров модели (условие насыщенности). В частности, в работе де ла Гарза (de la Garza(1954)) показано, что для полиномиальных моделей регрессии D-оптимальные планы всегда являются насыщенными. С другой стороны, для нелинейных по параметрам моделей нередки случаи, в которых появляются локально-оптимальные планы с числом опорных точек n >p (избыточные планы).
Феномен избыточности оптимальных планов хорошо известен в байесовском и максимин-оптимальном подходах к планированию. В данном случае, этот феномен связан, как со свойствами пространства параметров модели, так и с
заданным на нем априорном распределении параметров. Вместе с тем, до последнего времени, данный феномен оставался малоизученным. В основном были получены лишь численные результаты. Например, феномен избыточности для байесовских планов на эмпирическом уровне был исследован в (Chaloner, Larntz(1989)), где на примере логистической модели и равномерного относительно опорных точек априорного распределения pi было показано увеличение числа точек плана при возрастании дисперсии D(pi) априорного распределения. Там же приводятся ссылки и на более ранние работы, в которых равномерное распределение рассматривалось в более простом варианте: равномерными предполагались не только спектр плана, но и веса опорных точек.

В недавних работах (Grigoriev, Melas and Shpilev (2017,2018,2021)) феномен избыточности исследовался для моделей Эйена-Петерса, Кобба-Дугласа и Лейбла, и D-критерия оптимальности. Для этих моделей были получены
аналитические результаты. В частности, найдены в явном виде функции, определяющие границы областей планирования на которых оптимальный план сохраняет свою структуру. Было показано, что при изменении области
планирования насыщенный оптимальный план становится избыточным и наоборот.
Литература к разделу II:
[1]. Бримкулов У.Н., Круг Г.К., Саванов В.Л. (1986). Планирование экспериментов при исследовании случайных полей и процессов. М., Наука.
[2]. Ермаков С.М. и др. (1983). Математическая теория планирования эксперимента. М., Наука.
[3]. Козлов В.П. (2000). Избранные труды по теории планирования эксперимента и обратным задачам оптического зондирования. Изд-во С.-Петербург. ун-та, СПб.
[4]. Мелас В.Б. (1981). Оптимальное планирование эксперимента для экспоненциальной регрессии. В сб. Математические методы планирования эксперимента. Наука, Новосибирск, 174--198.
[5]. Федоров В.В. (1971). Теория оптимального эксперимента. М., Наука.
[6]. Atkinson, A. C., Donev, A. N., and Tobias, R. D. (2007). Optimum Experimental Designs, with SAS. Oxford University Press, Oxford.
[7]. Chaloner K. and Larntz K. (1989). Optimal Bayesian design applied to logistic regression experiments, J. Statistical Plannning and Inference 21: 191--208.
[8]. Chernoff, H. (1953). Locally optimal design for estimator parameters. Ann. Math. Stat. 24: 586--602.
[9]. de la Garza A (1954) Spacing of information in polynomial regression. Ann. Math. Stat. 25:123--130.
[10]. Dette, Holger, Melas, Viatcheslav B., Pepelyshev, Andrey. (2005). Optimal designs for three-dimensional shape analysis with spherical harmonic descriptors. Ann. Statist. 33(6): 2758--2788.
[11]. Dette H, Melas B (2011) A note on the de la Garza phenomenon for locally optimal designs. Ann. Stat. 39(2):1266--1281.
[12]. Dette H., Neugebauer H.-M. (1996). Bayesian optimal one point designs for one parameter nonlinear models. Journal of Statistical Planning and Inference 52(1): 17--31.
[13]. Dette H., Neugebauer H.-M. (1997). Bayesian optimal designs for exponential regression models. Journal of Statistical Planning and Inference 60(2), 331--349.
[14]. Ehrenfeld, E. (1955). On the efficiency of experimental design. Annals of Mathematical Statistic 26(2): 247--255.
[15]. Elfving, G. (1952). Optimum allocation in linear regression theory. Annals of Mathematical Statistics 23(2): 255--262.
[16]. Fedorov, V.V. (1972). Theory of Optimal Experiments. Academic Press, New York.
[17]. Fedorov, V.V. and Hackl, P. (1997). Model-Oriented Design of Experiments. Springer, New York.
[18]. Grigoriev, Y. D., Melas, V. B., and Shpilev, P. V. (2017). Excess of locally D-optimal designs and homothetic transformations. Vestnik St. Petersburg University: Mathematics, 50(4):329--336.
[19]. Grigoriev, Y. D., Melas, V. B., and Shpilev, P. V. (2018). Excess of locally D-optimal designs for Cobb-Douglas model. Statistical Papers, 59(4):1425--1439.
[20]. Grigoriev, Y.D., Melas, V.B., Shpilev, P.V. (2021). Excess and saturated D-optimal designs for the rational model. Statistical Papers, 62 (3), pp. 1387-1405.
[21]. Han C., Chaloner K. (2004). Bayesian experimental design for non-linear mixed-effect models with applications to HIV dynamics. Biometrics 60, 25--33.
[22]. Kiefer, J., Wolfowitz, J. (1960). The equivalence of two extremum problems. //Can. J. Math., 14: 363—366.
[23]. Lauter E. (1974). Experimental designs in a class of models. Math. Operationsforsch. Statist. 5, 379--396.
[24]. Lauter, E. (1976). Optimal multipurpose designs for regression models. Ann. Math. Statist. 7, 51--68.
[25]. Melas, V.B. (1978). Optimal designs for exponential regression. Math. Operationsforsh. Statist. 9, 45--59.
[26]. Melas V.B. (2006). Functional approach to optimal experimental design. Lecture Notes in Statistics, vol. 184, Heidelberg: Springer.
[27]. Melas, V., Pepelyshev, A., and Cheng, R. (2003). Designs for estimating an extremal point of quadratic regression models in a hyperball. Metrika, 58:193--208.
[28]. Muller, C. (1995). Maximin efficient designs for estimating nonlinear aspects in linear models. J. Statist. Plann. Inf. 44, 117--132.
[29]. Pronzato, L. and Walter, E. (1993). Experimental design for estimating the optimum point in a response surface. Acta Applicandae Mathematicae, 33:45--68.
[30]. Pukelsheim, F. (2006). Optimal Design of Experiments. Philadelphia: SIAM.
[31]. Schwabe, R. (1996). Optimum designs for multi-factor models. Springer-Verlag New York, Inc.
[32]. Yang M, Stufken J (2009) Support points of locally optimal designs for nonlinear models with two parameters. Ann. Stat. 37:518--541.
[33]. Yang M (2010) On the de la Garza phenomenon. Ann Stat 38:2499–2524
[34]. Yang M, Stufken J (2012) Identifying locally optimal designs for nonlinear models: a simple extension with profound consequences. Ann. Stat. 40(3):1665--1681.

Срок реализации проекта – 2 года: 2023,2024.
I. Предлагаемые методы и общий план работы по реализации теоретической части проекта

Ia. Стохастическая оптимизация.

Для решения задач регрессионного анализа высокой размерности существует ряд подходов, хорошо зарекомендовавших себя на практике. Классический подход заключается в использовании модели, представляющей из себя линейную комбинацию признаков (контролируемых переменных). Задача нахождения функции регрессии сводится к оценке неизвестных коэффициентов (параметров) рассматриваемой линейной комбинации, которые подбираются таким образом, чтобы минимизировать ошибку прогноза. Наиболее распространённым на практике методом построения оценок является метод наименьших квадратов (МНК), согласно которому в качестве оценок параметров выбираются значения, доставляющие минимум сумме квадратов отклонений истинных значений целевой переменной (полученных в результате экспериментов) от прогнозируемых. Согласно теореме Гаусса-Маркова оценки, полученные по методу наименьших квадратов (МНК-оценки), являются наилучшими несмещенными оценками в классе линейных оценок, при этом, задача нахождения таких оценок сводится к задаче решения нормального уравнения (линейной системы уравнений относительно неизвестных коэффициентов), что, в свою очередь, сводится к нахождению обратной матрицы к X’X, где X- матрица признаков.

Основные сложности такого подхода заключаются в том, что, во-первых, матрица X’X может быть вырожденной или плохо обусловленной, и, во-вторых, линейная модель может оказаться недостаточно адекватной (мощной) для описания искомой зависимости. Кроме того, при увеличении размерности матрицы X’X существенно увеличивается вычислительная сложность решения исходной задачи. Также стоит отметить и то обстоятельство, что при изменении матрицы X (т.е. появлении новых данных) задачу оценки параметров приходится решать повторно. Однако, все эти ограничения можно обойти. Так, например, мощность модели можно увеличить, используя подходы квадратичного программирования, результаты теоремы Мерсера и подходящую ядерную функцию. С другой стороны, для решения нормального уравнения можно использовать различные оптимизационные алгоритмы, например, метод стохастического градиентного спуска, поддерживающий возможность динамического обучения модели (т.е. обучения на мини-пакетах данных), что позволяет, в частности, решить проблему с обновляющимися данными. Альтернативным подходом, является использование других стохастических методов, в частности, эволюционных алгоритмов. Так, перспективным представляется подход, основанный на модификации метода CMA-ES (см., например, [1]) суть которой заключается в том, что переход к новым решениям на каждой итерации осуществляется на основе многомерного нормального распределения, без использования преобразований его математического ожидания, стандартного отклонения и ковариационной матрицы (см., например, [2]). Другим вариантом является (mu,lambda)-ES алгоритм ([3]), суть которого заключается в том, что для генерации новых решений используется не общая совокупность всех наилучших решений на предыдущей итерации, как в вышеупомянутых методах, а каждое найденное наилучшее решение по-отдельности. В процессе работы над проектом планируется рассмотреть ряд эволюционных алгоритмов и разработать новые модификации, наилучшим образом подходящие к исследуемой задаче.
В 2023 году планируется рассмотреть и выбрать набор (с учетом реальных данных) эволюционных алгоритмов, являющимися наиболее перспективными для данной задачи.
В 2024 на основе выбранных алгоритмов планируется предложить модификацию(и) и исследовать ее(их) эффективность и универсальность в приложении к задачам решения систем линейных уравнений большой размерности с плохо обусловленной матрицей коэффициентов.

[1] Hansen N. The CMA Evolution Strategy: A Comparing Review // Towards a New Evolutionary Computation - Advances in the Estimation of Distribution Algorithms. — Springer, 2006. — Vol. 192. — P. 75–102.
[2] Rubtsova I. Genetic Stochastic Algorithm Application in Beam Dynamics Optimization Problem. — SCP 2020: Stability and Control Processes pp 265–272, 2020.
[3] Sean Luke, 2009, Essentials of Metaheuristics, available at http://cs.gmu.edu/ ~ sean/book/metaheuristics/

Ib. Планирование экспериментов.

В работе [1] была сформулирована теорема эквивалентности, в соответствии с которой D-оптимальность плана эквивалентна тому, что некоторая функция для этого плана удовлетворяет определенным условиям. Существует множество разновидностей теоремы эквивалентности для разных критериев оптимальности (см., напр., [2]). Как правило, данные теоремы используются для построения оптимального плана. Вместе с тем, во многих случаях число и вид точек оптимального плана зависит от выбора области планирования (см. Atkinson (2010), Dette, Melas, Shpilev
(2012), Dette, Melas, Shpilev (2013), Dette, Melas, Shpilev (2017)).
Идея предлагаемого нами подхода заключается в использовании теорем эквивалентности не только для построения оптимальных планов но и для определения областей планирования, на которых оптимальный план сохраняет свою структуру. Данный подход был применен ранее при решении подобных задач для нелинейных моделей Эйена-Петерса и Кобба-Дугласа (Grigoriev, Melas and Shpilev (2017,2018,2021)) и D-критерия оптимальности. В некоторых случаях функции границ соответствующих областей удалось найти явно, в аналитическом виде, в остальных случаях были построены разложения этих функций в ряд Тейлора с помощью функционального подхода. Основы общей теории этого подхода к оптимальному планированию эксперимента развиты в монографии (Melas, 2006). В данном проекте мы планируем обобщить полученные ранее результаты на случай многомерных полиномиальных моделей.

[1] Kiefer, J., Wolfowitz, J. (1960). The equivalence of two extremum problems. Can. J. Math., 14, 363--366.
[2] Pukelsheim, F. (2006). Optimal Design of Experiments. Philadelphia: SIAM.
[3] Atkinson, A. C. (2010). The non-uniqueness of some designs for discriminating between two polynomial models in one variablel. MODA 9, Advances in Model-Oriented Design and Analysis, pages 9-16.
[4] Dette H., Melas V. B., Shpilev P. (2012). T-optimal designs for discrimination between two polynomial models, Annals of Statistics, 40, 188-205.
[5] Dette H., Melas V. B., Shpilev P. (2013). Robust T-optimal discriminating designs. Annals of Statistics, 41, 1693-1715.
[6] Dette H., Melas V. B., Shpilev P. (2017). T-optimal discriminating designs for Fourier regression models. Computational Statistics and Data Analysis, Volume 113, pp. 196-206.
[7] Grigoriev, Y. D., Melas, V. B., and Shpilev, P. V. (2017). Excess of locally D-optimal designs and homothetic transformations. Vestnik St. Petersburg University: Mathematics, 50(4):329--336.
[8] Grigoriev, Y. D., Melas, V. B., and Shpilev, P. V. (2018). Excess of locally D-optimal designs for Cobb-Douglas model. Statistical Papers, 59(4):1425--1439.
[9] Grigoriev, Y.D., Melas, V.B., Shpilev, P.V. (2021). Excess and saturated D-optimal designs for the rational model. Statistical Papers, 62 (3), pp. 1387-1405.
[10] Melas V.B. (2006). Functional approach to optimal experimental design. Lecture Notes in Statistics, vol. 184, Heidelberg: Springer.

2023: Построение в аналитическом виде D-оптимального плана для двумерной полиномиальной модели определенного порядка. Исследование эффективности построенного плана. Определение областей планирования, на которых D- оптимальный план сохраняет свою структуру.
2024: Обобщение полученных результатов на случай многомерной (> 2) полиномиальной модели. Исследование эффективности построенных планов. Исследование областей планирования, на которых D-оптимальный план сохраняет свою структуру.

II. Предлагаемые методы и общий план работы по реализации практической части проекта.
Альтернативным подходом к решению классической задачи регрессии является использование моделей машинного
обучения. Согласно известной теореме об отсутствии бесплатных обедов ([1]) невозможно предложить наилучшую
модель априори. Поэтому в ходе реализации проекта планируется рассмотреть наиболее популярные модели,
используемые на практике (метод опорных векторов, ансамблевые методы, анализ главных компонент, различные
архитектуры нейронных сетей) и выбрать из них несколько наиболее перспективных. Можно ответить следующие
основные этапы реализации практической части проекта, для которых потребуется наладить взаимодействие с
региональным партнером конкурса (правительством Санкт-Петербурга):
1. Выяснение общей картины.
2. Получение данных.
3. Исследование данных для понимания их сущности.
4. Подготовка данных для алгоритмов машинного обучения.
5. Исследование различных моделей и составление окончательного списка лучших из них.
6. Точная настройка моделей и их объединение в наилучшее решение.
7. Представление своего решения.
8. Запуск, наблюдение и сопровождение системы.
В 2023 году планируется рассмотреть и определить набор (с учетом реальных данных) наиболее перспективных моделей для рассматриваемой задачи. Разработать рабочий вариант программы на языке Python для осуществления прогноза целевых значений (срока службы дорожного покрытия). Код проект разместить в открытом доступе на GitHub.

В 2024 году планируется осуществить окончательную настройку моделей и предложить наилучшее решение. Подготовить финальный вариант программы на языке Python для осуществления прогноза целевых значений (срока службы дорожного покрытия). Код проект разместить в открытом доступе на GitHub.
[1] Wolpert, D.H., Macready, W.G. (1997), "No Free Lunch Theorems for Optimization", IEEE Transactions on Evolutionary
Computation 1, 67

Руководитель проекта в течение ряда лет занимается изучением проблем, близких к данной тематике. В плане опыта практической реализации, можно отметить следующее. Руководителем проекта (Шпилевым П.В.) был
разработан ряд учебных курсов по анализу данных и методам машинного обучения, читаемых в настоящее время на математико-механическом факультете СПбГУ. За последние несколько лет по данной тематике под его руководством студентами были написаны (и успешно прошли защиту) ВКР, включающие реализацию соответствующих программ. Так, например, в 2022 году были подготовлены работы на следующие темы: «Методы матричной факторизации и их применение в рекомендательных системах» и «Исследование проблемы адаптации языковых моделей к человеческим
предпочтениям» обе темы являются весьма актуальными и связаны с непосредственным использованием наиболее передовых моделей машинного обучения.

Что касается задачи стохастической оптимизации, соответствующий подход был исследован в недавних работах ([1], [2]) руководителя проекта применительно к задачам многокритериальной оптимизации планирования эксперимента в рамках работы по гранту РФФИ (проект 17-01-00267 «Теория и приложения рандомизованных методов квази Монте-
Карло»). Идея исследуемого подхода заключалась в том, что наряду с использованием квазислучайных последовательностей на каждом этапе генетического алгоритма было предложено использовать технику оценки
матрицы ковариаций пробных векторов. Эта техника была впервые предложена Сергеем Михайловичем Ермаковым в 1976 году, показала надёжные результаты, но мало использовалась ввиду её большой трудоёмкости. В работе ([18] раздел заявки 4.5) была доказана лемма, позволяющая уменьшить эту трудоёмкость на порядок. Полученные результаты легли в основу системы программ, позволивших решить несколько сложных задач планирования эксперимента [1], [2]. В процессе эксплуатации программы продемонстрировали высокую эффективность разработанных алгоритмов.

Заделом по задаче оптимального планирования эксперимента является ряд работ ([1-4]), посвященных исследованию влияния гомотетии области планирования эксперимента на число точек носителя оптимального плана для многомерных и нелинейных по параметрам регрессионных моделей. Полученные результаты позволяют сделать вывод, что не только разумный выбор условий проведения эксперимента (т.е. точек оптимального плана), но и выбор походящей области планирования, может снизить расходы на проведение эксперимента.
[1] Григорьев, Ю.Д., Мелас, В.Б., Шпилев, П.В. Избыточность локально D-оптимальных планов и гомотетии (2017)
Вестник СПбГУ. Математика. Механика. Астрономия, Том 4(4), стр. 552-562.
[2] Grigoriev, Y.D., Melas, V.B., Shpilev, P.V. Excess of locally D-optimal designs for Cobb–Douglas model (2018) Statistical
Papers, 59 (4), pp. 1425-1439.
[3] Grigoriev, Y.D., Melas, V.B., Shpilev, P.V. Excess and saturated D-optimal designs for the rational model (2021) Statistical
Papers, 62 (3), pp. 1387-1405.
[4] Мелас, В.Б., Шпилев, П.В. Исследование свойства избыточности L-оптимального плана для модели Лэйбла (2022)
Вестник СПбГУ. Математика. Механика. Астрономия, Том 9(3), стр. 495–505.