Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 4 ] 
Автор Сообщение
 Заголовок сообщения: Квадратичная или линейная оптимизация
СообщениеДобавлено: 09 апр 2018, 00:15 
Не в сети
Начинающий
Зарегистрирован:
08 апр 2018, 23:24
Сообщений: 3
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Здравствуйте!
Возникла такая задача:
[math]\min_{w_1, \dots, w_k}
\{
x_1 + \dots + x_n\},[/math]
(1)

[math]\sum_{i=1}^{n}
{\boldsymbol{w}}{\boldsymbol{a_{i,j}}^T}x_i=b_j,[/math]
(2)

[math]{\boldsymbol{D}}\boldsymbol{w}>\boldsymbol{d}.[/math]
(3)


Здесь жирными символами обозначены вектора и матрицы.
При этом группа условий (2) однозначно задаёт [math]x[/math], то есть существует единственное решение СЛАУ
[math]\boldsymbol{Q}\boldsymbol{x}=\boldsymbol{b},[/math]

где каждый элемент матрицы [math]q_{i,j}[/math] есть некоторая линейная комбинация элементов [math]\{w_1, \dots, w_k\}[/math]:

[math]q_{i,j}={\boldsymbol{w}}{\boldsymbol{a_{i,j}}^T}.[/math]


Очевидно, что
[math]\boldsymbol{x}=\boldsymbol{Q}^{-1}\boldsymbol{b}[/math]
и можно задавать целевую функцию в виде
[math]\boldsymbol{Q}^{-1}\boldsymbol{b}\boldsymbol{1},[/math]

где [math]\boldsymbol{1}[/math] есть единичный столбец. Но как оптимизировать это дальше точными методами не знаю.

С другой стороны можно рассмотреть [math]{x_1, \dots, x_n,}[/math] в качестве переменных и величин и производить минимизацию и по ним, но тогда условия (2) уже не будет линейным. Получается уже квадратичное программирование (в общем случае это NP задачи), а хотелось свести эту задачу к чему-то более простому с точки зрения вычислений.

Буду благодарен за любую информацию и идеи.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Квадратичная или линейная оптимизация
СообщениеДобавлено: 09 апр 2018, 00:16 
Не в сети
Начинающий
Зарегистрирован:
08 апр 2018, 23:24
Сообщений: 3
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Здравствуйте.
Возникла такая задача:
[math]\min_{w_1, \dots, w_k}
\{
x_1 + \dots + x_n\},[/math]
(1)

[math]\sum_{i=1}^{n}
{\boldsymbol{w}}{\boldsymbol{a_{i,j}}^T}x_i=b_j,[/math]
(2)

[math]{\boldsymbol{D}}\boldsymbol{w}>\boldsymbol{d}.[/math]
(3)


Здесь жирными символами обозначены вектора и матрицы.
При этом группа условий (2) однозначно задаёт [math]x[/math], то есть существует единственное решение СЛАУ
[math]\boldsymbol{Q}\boldsymbol{x}=\boldsymbol{b},[/math]

где каждый элемент матрицы [math]q_{i,j}[/math] есть некоторая линейная комбинация элементов [math]\{w_1, \dots, w_k\}[/math]:

[math]q_{i,j}={\boldsymbol{w}}{\boldsymbol{a_{i,j}}^T}.[/math]


Очевидно, что
[math]\boldsymbol{x}=\boldsymbol{Q}^{-1}\boldsymbol{b}[/math]
и можно задавать целевую функцию в виде
[math]\boldsymbol{Q}^{-1}\boldsymbol{b}\boldsymbol{1},[/math]

где [math]\boldsymbol{1}[/math] есть единичный столбец. Но как оптимизировать это дальше точными методами не знаю.

С другой стороны можно рассмотреть [math]{x_1, \dots, x_n,}[/math] в качестве переменных и величин и производить минимизацию и по ним, но тогда условия (2) уже не будет линейным. Получается уже квадратичное программирование (в общем случае это NP задачи), а хотелось свести эту задачу к чему-то более простому с точки зрения вычислений.

Буду благодарен за любую информацию и идеи.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Квадратичная или линейная оптимизация
СообщениеДобавлено: 09 апр 2018, 10:12 
Не в сети
Последняя инстанция
Аватара пользователя
Зарегистрирован:
15 мар 2016, 15:08
Сообщений: 9390
Cпасибо сказано: 122
Спасибо получено:
1726 раз в 1634 сообщениях
Очков репутации: 235

Добавить очки репутацииУменьшить очки репутации
Somebody писал(а):
С другой стороны можно рассмотреть x1,…,xn, в качестве переменных и величин и производить минимизацию и по ним, но тогда условия (2) уже не будет линейным.

Правильно.
Somebody писал(а):
Получается уже квадратичное программирование

Неправильно. Получается задача нелинейного программирования.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Квадратичная или линейная оптимизация
СообщениеДобавлено: 09 апр 2018, 13:41 
Не в сети
Начинающий
Зарегистрирован:
08 апр 2018, 23:24
Сообщений: 3
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
searcher писал(а):
Somebody писал(а):
Получается уже квадратичное программирование

Неправильно. Получается задача нелинейного программирования.


Задача с квадратичными ограничениями и линейной целевой функцией (QCLP).

Да, можно рассмотреть и в общем случае в виде задачи нелинейной оптимизации, но хотелось свести её во что-то более красивое.
Возможно, что метод множителей Лагранжа что-то тогда и даст, но пока не пытался его использовать.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 4 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Квадратичная форма

в форуме Линейная и Абстрактная алгебра

Nurzha18

21

588

03 дек 2017, 17:45

Квадратичная форма

в форуме Линейная и Абстрактная алгебра

BUtton

0

255

15 май 2017, 21:35

Квадратичная форма

в форуме Линейная и Абстрактная алгебра

BabyRooJr

3

261

07 май 2019, 19:24

Квадратичная форма

в форуме Линейная и Абстрактная алгебра

Maxmax87

11

884

14 июн 2015, 14:24

Квадратичная форма

в форуме Функциональный анализ, Топология и Дифференциальная геометрия

lion1995

0

474

12 дек 2014, 00:16

Квадратичная форма 4 степени

в форуме Линейная и Абстрактная алгебра

constantin01

4

312

15 ноя 2020, 08:31

Граф и квадратичная форма

в форуме Линейная и Абстрактная алгебра

nickspa

3

419

10 фев 2017, 13:39

Первая квадратичная форма

в форуме Функциональный анализ, Топология и Дифференциальная геометрия

lion1995

0

420

12 дек 2014, 00:12

Квадратичная формула Эйлера

в форуме Размышления по поводу и без

Galina Alexandrovna

19

1481

29 июн 2017, 20:05

Первая квадратичная форма

в форуме Функциональный анализ, Топология и Дифференциальная геометрия

lion1995

1

1312

27 дек 2014, 12:46


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 9


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved