В первой части я подробно рассмотрел обычную задачу наименьших квадратов. В этой части (часть 2) я рассмотрю многоцелевые задачи наименьших квадратов. Если вы еще не прочитали первую часть, обратитесь к следующей статье для получения дополнительной информации:
Для получения дополнительной информации и более подробных объяснений, пожалуйста, обратитесь к моему каналу YouTube.
Многоцелевой метод наименьших квадратов
Предположим, мы ищем решение, которое уменьшает более чем одну функцию цели / стоимости. Эта проблема называется многокритериальной задачей оптимизации. Если все целевые функции имеют форму задачи наименьших квадратов, то проблема называется многокритериальной задачей наименьших квадратов.
Постановка проблемы
Предположим, у нас есть K целевая функция наименьших квадратов, и наша цель - найти единственный x, который сделает все из них маленькими.
Где каждый Aᵢ представляет собой матрицу mᵢ xn, а каждый bᵢ представляет собой вектор mᵢ x 1.
Есть много способов решить и сформулировать многокритериальную задачу LS, но, возможно, наиболее распространенный метод - минимизировать взвешенную сумму всех целевых функций , где веса определяют влияние или важность каждой целевой функции.
где λ’s - веса для каждой целевой функции. Здесь я представляю два метода решения многоцелевых задач LS.
Метод 1. Прямое дифференцирование
В этом методе мы берем производную Jₜₒₜ по x и устанавливаем ее равной нулю.
Хотя этот метод кажется достаточно простым, но второй метод более распространен и обеспечивает лучшую интуицию.
Метод 1: составная матрица
Это лучший подход для решения многоцелевой Проблемы LS, поскольку они используют решение проблемы OLS и непосредственно моделируют проблему как проблему OLS.
Сначала мы строим новую матрицу A и B, а затем формулируем задачу как простую задачу OLS, используя то, что мы вывели на рисунке 2.
Этот метод работает только в том случае, если в стеке A есть линейно независимые столбцы, аналогичные OLS, где требуется, чтобы матрица A имела линейно независимые столбцы (высокая и обратимая слева матрица).
Когда составная матрица имеет линейно независимые столбцы
Как уже упоминалось ранее, чтобы использовать подход с накоплением матриц, нам нужно убедиться, что матрица с накоплением обратима слева или имеет линейно независимые столбцы, это означает:
- Если хотя бы одна из матриц A₁, A₂,. . ., Aₖ имеет линейно независимые столбцы, то сложенная матрица будет иметь линейно независимые столбцы.
- Однако матрица с накоплением может иметь линейно независимые столбцы, даже если все матрицы A₁, A₂,. . ., Aₖ имеют линейно зависимые столбцы, и это происходит, когда выполняется следующее условие:
Предположим, что A₁ равно m₁x n, A₂ равно m₂ xn и Aₖ равно mₖ на n, тогда если каждый m_i меньше или равен n, но их sum больше или равно n, тогда сложенная матрица все еще остается высокой и может быть левой обратимой матрицей (линейно независимые столбцы). Математически это означает следующее:
Тихоновская регуляризация
Предположим, вы пытаетесь решить задачу наименьших квадратов с учетом:
- Матрица A не имеет линейно независимых столбцов.
- Или мы хотели бы минимизировать || Ax - b || ² так, чтобы || x || мала (мала норма x).
Один из способов сформулировать эту проблему так:
На рисунке 7 λ является положительным весом и определяет важность второй целевой функции по сравнению с первой. Если λ равно нулю, мы возвращаемся к OLS. если λ мало, мы увеличиваем вес первой целевой функции. Это обычный способ формулирования многокритериальной задачи путем нормализации веса первичной целевой функции на 1, и пусть λ обозначает относительные веса.
Чтобы решить вышеприведенное уравнение, мы можем использовать либо метод 1, либо метод 2, но для демонстрации подхода с накоплением матриц мы будем использовать второй метод.
Прежде чем решать проблему на рисунке 8, важно доказать, что составная матрица A имеет линейно независимые столбцы. Доказать это можно двумя способами:
- Единичная матрица имеет линейно независимые столбцы, поэтому составная матрица имеет линейно независимые столбцы независимо от того, есть ли у A зависимые столбцы или нет.
- Следуйте стандартной процедуре, чтобы доказать линейную независимость столбцов:
Теперь, когда составная матрица имеет линейно независимые столбцы, решение можно легко найти следующим образом:
Чтобы узнать больше о многоцелевом методе наименьших квадратов, посетите мой канал на YouTube.
Что дальше:
Обязательно ознакомьтесь с частью 3 статьи о наименьших квадратах с ограничениями.
Вывод
В этой статье я обсуждаю многоцелевые задачи наименьших квадратов, в следующей части (часть 3) я буду обсуждать задачи наименьших квадратов с ограничениями.
Если вы найдете какую-либо часть этой или предыдущей статьи сложной, обратитесь к моему каналу на YouTube, где у меня есть серия видеороликов по числовой линейной алгебре и оптимизации, которые не требуют предварительных знаний в матричной алгебре или оптимизации.