Связанные понятия
Метод Стронгина — метод решения одномерных задач условной липшицевой оптимизации. Позволяет находить глобально оптимальное решение в задачах с ограничениями неравенствами при условии, что целевая функция задачи и левые части неравенств удовлетворяют условию Липшица в области поиска.
Не путать с «симплекс-методом» — методом оптимизации произвольной функции. См. Метод Нелдера — МидаСимплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.
Подробнее: Симплекс-метод
Целочисленное программирование является NP-трудной задачей. Специальный случай, 0-1 целочисленное линейное программирование, в которой переменные принимают значения 0 или 1, является одной из 21 NP-полных задач Карпа.
Полуопределённое программирование (en: Semidefinite programming, SDP) — это подраздел выпуклого программирования, которое занимается оптимизацией линейной целевой функции (целевая функция — это заданная пользователем функция, значение которой пользователь хочет минимизировать или максимизировать) на пересечении конусов положительно полуопределённых матриц с аффинным пространством.
Предобуславливание (также предобусловливание) — процесс преобразования условий задачи для её более корректного численного решения. Предобуславливание обычно связано с уменьшением числа обусловленности задачи. Предобуславливаемая задача обычно затем решается итерационным методом.
Метод внутренней точки — это метод позволяющий решать задачи выпуклой оптимизации с условиями, заданными в виде неравенств, сводя исходную задачу к задаче выпуклой оптимизации.
Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно (BFGS) (англ. Broyden — Fletcher — Goldfarb — Shanno algorithm) — итерационный метод численной оптимизации, предназначенный для нахождения локального максимума/минимума нелинейного функционала без ограничений.
Алгоритм Левенберга — Марквардта — метод оптимизации, направленный на решение задач о наименьших квадратах. Является альтернативой методу Ньютона. Может рассматриваться как комбинация последнего с методом градиентного спуска или как метод доверительных областей. Алгоритм был сформулирован независимо Левенбергом (1944) и Марквардтом (1963).
Ме́тоды Ру́нге — Ку́тты (в литературе встречаются названия: ме́тоды Ру́нге — Ку́тта или же ме́тоды Ру́нге — Кутта́) — большой класс численных методов решения задачи Коши для обыкновенных дифференциальных уравнений и их систем. Первые методы данного класса были предложены около 1900 года немецкими математиками К. Рунге и М. В. Куттой.
Вариацио́нное исчисле́ние — раздел анализа, в котором изучаются вариации функционалов. Наиболее типичная задача — найти функцию, на которой заданный функционал достигает экстремального значения.
Метод наименьших квадратов (МНК) — математический метод, применяемый для решения различных задач, основанный на минимизации суммы квадратов отклонений некоторых функций от искомых переменных. Он может использоваться для «решения» переопределенных систем уравнений (когда количество уравнений превышает количество неизвестных), для поиска решения в случае обычных (не переопределенных) нелинейных систем уравнений, для аппроксимации точечных значений некоторой функции. МНК является одним из базовых методов...
Вероятностное округление — это широко используемый подход для разработки и анализа таких аппроксимационных алгоритмов. Базовая идея — использование вероятностного метода для преобразования соответствующей оптимального решения задачи линейного программирования (ЛП) в приближённое к оптимальному решению исходной задачи.
Метод обратного распространения ошибки (англ. backpropagation) — метод вычисления градиента, который используется при обновлении весов многослойного перцептрона. Впервые метод был описан в 1974 г. А. И. Галушкиным, а также независимо и одновременно Полом Дж. Вербосом. Далее существенно развит в 1986 г. Дэвидом И. Румельхартом, Дж. Е. Хинтоном и Рональдом Дж. Вильямсом и независимо и одновременно С.И. Барцевым и В.А. Охониным (Красноярская группа). Это итеративный градиентный алгоритм, который используется...
Гауссовский процесс назван так в честь Карла Фридриха Гаусса, поскольку в его основе лежит понятие гауссовского распределения (нормального распределения). Гауссовский процесс может рассматриваться как бесконечномерное обобщение многомерных нормальных распределений. Эти процессы применяются в статистическом моделировании; в частности используются свойства нормальности. Например, если случайный процесс моделируется как гауссовский, то распределения различных производных величин, такие как среднее значение...
Метод Ньютона , алгоритм Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Модификацией метода является метод хорд и касательных. Также метод Ньютона может быть использован...
Приближение с помощью кривых — это процесс построения кривой или математической функции, которая наилучшим образом приближается к заданным точкам с возможными ограничениями на кривую . Для построения такого приближения может использоваться либо интерполяция , где требуется точное прохождение кривой через точки, либо сглаживание, когда «сглаживающая» функция проходит через точки приближённо. Связанный раздел — регрессионный анализ, который фокусируется, главным образом, на вопросах статистического...
Метод перебора (метод равномерного поиска, перебор по сетке) — простейший из методов поиска значений действительно-значных функций по какому-либо из критериев сравнения (на максимум, на минимум, на определённую константу). Применительно к экстремальным задачам является примером прямого метода условной одномерной пассивной оптимизации.
Алгоритм Гельфонда — Шенкса (англ. Baby-step giant-step; также называемый алгоритмом больших и малых шагов) — в теории групп детерминированный алгоритм дискретного логарифмирования в мульпликативной группе кольца вычетов по модулю простого числа. Был предложен советским математиком Александром Гельфондом в 1962 году и Дэниэлем Шенксом в 1972 году.
В прикладной статистике метод наименьших полных квадратов (МНПК, TLS — англ. Total Least Squares) — это вид регрессии с ошибками в переменных, техника моделирования данных с помощью метода наименьших квадратов, в которой принимаются во внимание ошибки как в зависимых, так и в независимых переменных. Метод является обобщением регрессии Деминга и ортогональной регрессии и может быть применён как к линейным, так и нелинейным моделям.
Множество больших тригонометрических сумм — понятие теории чисел — множество индексов, в которых преобразование Фурье характеристической функции заданного подмножества группы принимает достаточно большие значения.
Вариационный метод — метод решения математических задач с помощью минимизации определённого функционала, используя пробную функцию, которая зависит от небольшого количества параметров.
Ме́тод моме́нтов — метод оценки неизвестных параметров распределений в математической статистике и эконометрике, основанный на предполагаемых свойствах моментов (Пирсон, 1894 г.). Идея метода заключается в замене истинных соотношений выборочными аналогами.
Квазиньютоновские методы — методы оптимизации, основанные на накоплении информации о кривизне целевой функции по наблюдениям за изменением градиента, чем принципиально отличаются от ньютоновских методов. Класс квазиньютоновских методов исключает явное формирование матрицы Гессе, заменяя её некоторым приближением.
В математике методы проверки на простоту с помощью эллиптических кривых (англ. - Elliptic Curve Primality Proving, сокр. ЕСРР) являются одними из самых быстрых и наиболее широко используемых методов проверки на простоту . Эту идею выдвинули Шафи Гольдвассер и Джо Килиан в 1986 году; она была превращена в алгоритм А.О.Л. Аткином в том же году. Впоследствии алгоритм был несколько раз изменён и улучшен, в особенности Аткином и François Morain в 1993. Концепция использования факторизации с помощью эллиптических...
Подробнее: Тест простоты с использованием эллиптических кривых
Условия Вольфе — в теории оптимизации набор условий, которые используются в алгоритме приближенного поиска вдоль направления, в алгоритме Бройдена — Флетчера — Гольдфарба — Шанно (BFGS). Впервые опубликованы Филипом Вольфе в 1969 году.
Метод конечных элементов (МКЭ) — это численный метод решения дифференциальных уравнений с частными производными, а также интегральных уравнений, возникающих при решении задач прикладной физики. Метод широко используется для решения задач механики деформируемого твёрдого тела, теплообмена, гидродинамики и электродинамики.
Постепенная оптимизация — это техника глобальной оптимизации, которая пытается решить трудную задачу оптимизации путём решения сначала сильно упрощённой задачи с последовательным преобразованием этой задачи, пока она не станет эквивалентна исходной трудной оптимизационной задаче.
Метод главных компонент (англ. principal component analysis, PCA) — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретён Карлом Пирсоном в 1901 году. Применяется во многих областях, в том числе, в эконометрике, биоинформатике, обработке изображений, для сжатия данных, в общественных науках.
Винеровская теория нелинейных систем — подход к решению задач анализа и синтеза нелинейных систем с постоянными параметрами, при котором в качестве математической модели нелинейной системы рассматривается функционал, который ставит в соответствие каждой функции (входному сигналу системы за рассматриваемое время) число (мгновенный выходной сигнал системы).
Неотрицательное матричное разложение (НМР), а также неотрицательное приближение матрицы, это группа алгоритмов в мультивариантном анализе и линейной алгебре, в которых матрица V разлагается на (обычно) две матрицы W и H, со свойством, что все три матрицы имеют неотрицательные элементы. Эта неотрицательность делает получившиеся матрицы более простыми для исследования. В приложениях, таких как обработка спектрограмм аудиосигнала или данных мускульной активности, неотрицательность свойственна рассматриваемым...
Вычислительные (численные) методы — методы решения математических задач в численном видеПредставление как исходных данных в задаче, так и её решения — в виде числа или набора чисел.
Обобщённый ме́тод моме́нтов (ОММ; англ. GMM — Generalized Method of Moments) — метод, применяемый в математической статистике и эконометрике для оценки неизвестных параметров распределений и эконометрических моделей, являющийся обобщением классического метода моментов. Метод был предложен Хансеном в 1982 году. В отличие от классического метода моментов количество ограничений может быть больше количества оцениваемых параметров.
Табулирование функции — это вычисление значений функции при изменении аргумента от некоторого начального значения до некоторого конечного значения с определённым шагом. Именно так составляются таблицы значений функций, отсюда и название — табулирование. Необходимость в табулировании возникает при решении достаточно широкого круга задач. Например, при численном решении нелинейных уравнений f(x) = 0, путём табулирования можно отделить (локализовать) корни уравнения, то есть найти такие отрезки, на...
Односторонняя функция — математическая функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции. Здесь «легко» и «трудно» должны пониматься с точки зрения теории сложности вычислений. Разрыв между сложностью прямого и обратного преобразований определяет криптографическую эффективность односторонней функции. Неинъективность функции не является достаточным условием для того, чтобы называть её односторонней. Односторонние функции могут называться...
Ядерные методы в машинном обучении — это класс алгоритмов распознавания образов, наиболее известным представителем которого является метод опорных векторов (МОВ, англ. SVM). Общая задача распознавания образов — найти и изучить общие типы связей (например, кластеров, ранжирования, главных компонент, корреляций, классификаций) в наборах данных. Для многих алгоритмов, решающих эти задачи, данные, представленные в сыром виде, явным образом преобразуются в представление в виде вектора признаков посредством...
Подробнее: Ядерный метод
Математи́ческий ана́лиз (классический математический анализ) — совокупность разделов математики, соответствующих историческому разделу под наименованием «анализ бесконечно малых», объединяет дифференциальное и интегральное исчисления.
Принцип максимума энтропии утверждает, что наиболее характерными распределениями вероятностей состояний неопределенной среды являются такие распределения, которые максимизируют выбранную меру неопределенности при заданной информации о «поведении» среды. Впервые подобный подход использовал Д.Гиббс для нахождения экстремальных функций распределений физических ансамблей частиц. Впоследствии Э.Джейнсом был предложен формализм восстановления неизвестных законов распределения случайных величин при наличии...
Модель бинарного выбора — применяемая в эконометрике модель зависимости бинарной переменной (принимающей всего два значения — 0 и 1) от совокупности факторов. Построение обычной линейной регрессии для таких переменных теоретически некорректно, так как условное математическое ожидание таких переменных равно вероятности того, что зависимая переменная примет значение 1, а линейная регрессия допускает и отрицательные значения и значения выше 1. Поэтому обычно используются некоторые интегральные функции...
Метод опорных векторов (англ. SVM, support vector machine) — набор схожих алгоритмов обучения с учителем, использующихся для задач классификации и регрессионного анализа. Принадлежит семейству линейных классификаторов и может также рассматриваться как специальный случай регуляризации по Тихонову. Особым свойством метода опорных векторов является непрерывное уменьшение эмпирической ошибки классификации и увеличение зазора, поэтому метод также известен как метод классификатора с максимальным зазором...
Векторная авторегрессия (VAR, Vector AutoRegression) — модель динамики нескольких временных рядов, в которой текущие значения этих рядов зависят от прошлых значений этих же временных рядов. Модель предложена Кристофером Симсом как альтернатива системам одновременных уравнений, которые предполагают существенные теоретические ограничения. VAR-модели свободны от ограничений структурных моделей. Тем не менее, проблема VAR-моделей заключается в резком росте количества параметров с увеличением количества...
В комбинаторной оптимизации под линейной задачей о назначениях на узкие места (linear bottleneck assignment problem, LBAP) понимается задача, похожая на задачу о назначениях.
Подробнее: Линейная задача о назначениях в узких местах
Квадратичное программирование (англ. quadratic programming, QP) — это процесс решения задачи оптимизации специального типа, а именно — задачи оптимизации (минимизации или максимизации) квадратичной функции нескольких переменных при линейных ограничениях на эти переменные. Квадратичное программирование является частным случаем нелинейного программирования.
Двойственность , или принцип двойственности, — принцип, по которому задачи оптимизации можно рассматривать с двух точек зрения, как прямую задачу или двойственную задачу. Решение двойственной задачи даёт нижнюю границу прямой задачи (при минимизации). Однако, в общем случае, значения целевых функций оптимальных решений прямой и двойственной задач не обязательно совпадают. Разница этих значений, если она наблюдается, называется разрывом двойственности. Для задач выпуклого программирования разрыв двойственности...
Спектральные методы — это класс техник, используемых в прикладной математике для численного решения некоторых дифференциальных уравнений, возможно, вовлекая Быстрое преобразование Фурье. Идея заключается в переписи решения дифференциальных уравнений как суммы некоторых «базисных функций» (например, как ряды Фурье являются суммой синусоид), а затем выбрать коэффициенты в сумме, чтобы удовлетворить дифференциальному уравнению, насколько это возможно.
Подробнее: Спектральный метод
Алгоритм Гаусса — Ньютона используется для решения задач нелинейным методом наименьших квадратов. Алгоритм является модификацией метода Ньютона для нахождения минимума функции. В отличие от метода Ньютона, алгоритм Гаусса — Ньютона может быть использован только для минимизации суммы квадратов, но его преимущество в том, что метод не требует вычисления вторых производных, что может оказаться существенной трудностью.
Вероятностно приблизительно корректное обучение (ВПК обучение, англ. Probably Approximately Correct learning, (PAC learning) в теории вычислительного обучения — это схема математического анализа машинного обучения. Схему предложил в 1984 Лесли Вэлиант.
Многокритериальная оптимизация , или программирование (англ. Multi-objective optimization) — это процесс одновременной оптимизации двух или более конфликтующих целевых функций в заданной области определения.