Конвекс-оптимизация: Линейное программирование

Convex Optimization

Linear Programming (LP)

• Definition: A linear programming problem is a type of convex optimization problem where the objective function and constraints are linear.
• Standard Form: Maximize or minimize a linear objective function, subject to a set of linear equality and inequality constraints.
• Characteristics:
  • Linear objective function
  • Linear constraints
  • Non-negativity constraints (x ≥ 0)
• Methods:
  • Simplex Method
  • Dual Simplex Method
  • Interior-Point Methods

Quadratic Programming (QP)

• Definition: A quadratic programming problem is a type of convex optimization problem where the objective function is quadratic and the constraints are linear.
• Standard Form: Minimize a quadratic objective function, subject to a set of linear equality and inequality constraints.
• Characteristics:
  • Quadratic objective function
  • Linear constraints
  • Non-negativity constraints (x ≥ 0)
• Methods:
  • Interior-Point Methods
  • Active Set Methods
  • Semidefinite Programming (SDP) Relaxation

Convex Relaxations

• Definition: A convex relaxation is a method to approximate a non-convex optimization problem by a convex one, making it solvable using convex optimization algorithms.
• Types:
  • Semidefinite Relaxation (SDR): Relax a non-convex quadratic constraint to a semidefinite constraint.
  • Second-Order Cone Relaxation (SOCR): Relax a non-convex quadratic constraint to a second-order cone constraint.
  • Linear Relaxation: Relax a non-convex constraint to a linear constraint.
• Applications:
  • Non-convex quadratic programming
  • Mixed-integer programming
  • Global optimization

Оптимизация по выпуклости

Линейное Программирование (ЛП)

• Определение: Линейное программирование - это тип выпуклой оптимизации, где целевая функция и ограничения линейны.
• Стандартная Форма: Максимизация или минимизация линейной целевой функции, с условием линейных равенств и неравенств ограничений.
• Характеристики:
  • Линейная целевая функция
  • Линейные ограничения
  • Ограничения неотрицательности (x ≥ 0)
• Методы:
  • Метод Симплекса
  • Метод Двойного Симплекса
  • Методы Внутренней Точки

Квадратичное Программирование (КП)

• Определение: Квадратичное программирование - это тип выпуклой оптимизации, где целевая функция квадратична, а ограничения линейны.
• Стандартная Форма: Минимизация квадратичной целевой функции, с условием линейных равенств и неравенств ограничений.
• Характеристики:
  • Квадратичная целевая функция
  • Линейные ограничения
  • Ограничения неотрицательности (x ≥ 0)
• Методы:
  • Методы Внутренней Точки
  • Методы Активного Набора
  • Расслабление Семидефинитного Программирования (SDP)

Выпуклые Релаксации

• Определение: Выпуклая релаксация - это метод аппроксимации не выпуклой оптимизационной задачи выпуклой,，使 ее решаемой с помощью алгоритмов выпуклой оптимизации.
• Типы:
  • Расслабление Семидефинитного Программирования (SDR): Релаксация не выпуклого квадратичного ограничения до семидефинитного ограничения.
  • Расслабление Второго Порядка Конуса (SOCR): Релаксация не выпуклого квадратичного ограничения до ограничения второго порядка конуса.
  • Линейное Расслабление: Релаксация не выпуклого ограничения до линейного ограничения.
• Применения:
  • Не выпуклое квадратичное программирование
  • Смешанное целочисленное программирование
  • Глобальная оптимизация

Операции с Матрицами

• Сложение и Умножение на Скаляр:
  • Сложение матриц: элемент за элементом
  • Умножение на скаляр: умножение каждого элемента на скаляр
  • Свойства:
    • Коммутативность: A + B = B + A
    • Ассоциированность: (A + B) + C = A + (B + C)
    • Дистрибутивность: a(A + B) = aA + aB
• Умножение Матриц:
  • Произведение матриц: A × B = [a_ij] × [b_ij] = [c_ij], где c_ij = Σa_ik * b_kj
  • Свойства:
    • Некоммутативность: A × B ≠ B × A (в общем случае)
    • Ассоциированность: (A × B) × C = A × (B × C)
    • Дистрибутивность: A × (B + C) = A × B + A × C
• Обратная и Транспозиция:
  • Обратная матрица: A^(-1) удовлетворяет A × A^(-1) = A^(-1) × A = I (единичная матрица)
  • Транспозиция: A^T - матрица, полученная путём транспозиции строк и столбцов A
  • Свойства:
    • (A × B)^T = B^T × A^T
    • (A^T)^(-1) = (A^(-1))^T

Линейные Преобразования

• Определение:
  • Линейное преобразование T: ℝ^n → ℝ^m - функция, удовлетворяющая:
    • T(u + v) = T(u) + T(v)
    • T(av) = aT(v)
  • Может быть представлено матрицей A, такая что T(v) = Av
• Свойства:
  • Линейность: сохраняет линейные комбинации
  • Инъективность: взаимно-однозначное соответствие между входами и выходами
  • Сюръективность: каждый выход имеет соответствующий вход
• Типы Линейных Преобразований:
  • Изоморфизм: биективное линейное преобразование (инъективное и сюръективное)
  • Эндоморфизм: линейное преобразование из векторного пространства в само себя
  • Автоморфизм: изоморфизм из векторного пространства в само себя

Определитель

• Определение:
  • Определитель квадратной матрицы A, обозначается det(A) или |A|
  • Может быть 计算ан с помощью формулы Лейбница или расширения Лапласа
• Свойства:
  • Мультипликативность: det(A × B) = det(A) × det(B)
  • Аддитивность: det(A + B) = det(A) + det(B) (только для матриц 2x2)
  • Возвратимость: det(A) ≠ 0 если и только если A является обратимой
• Применения:
  • Решение систем линейных уравнений
  • Поиск обратной матрицы
  • Вычисление объёма параллелепипеда