2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 минимизация квадратичной функции на множестве как в ЛП
Сообщение13.08.2015, 16:19 


13/08/15
3
Задача, казалось бы проста, учебное пособие Шведова есть, но вот беда - там не врубиться.

1. Множество неотрицательных $ x _{i} $ (типа $  x_{1} + x_{2} + x_{3} = 1 $) задается как в ЛП. Матрицей В или иногда просто одним уравнением.
То есть при $ m=1 $ у В одна строка.

2. Функция минимизации - квадратична и положительно определена
$ -\lambda$ \sum x_{i} E_{i}  + \sum_{i} \sum_{j} x_{i} x_{j}  cov_{ij}$

3. Причем - уже знаю, как найти решение для минимальной дисперсии, когда $\lambda = 0 $.

4. И я уже понял, как найти решение $ x _{i} $ при максимальной $\lambda $.
Но её найти не знаю как.

5. Учебник Кузнецова пишет про приведение к задаче ЛП (через Теорему Куна-такера), но там - тоже непонятно, как найти
эту $\lambda  $.

 Профиль  
                  
 
 Re: минимизация квадратичной функции на множестве как в ЛП
Сообщение13.08.2015, 18:49 
Заслуженный участник
Аватара пользователя


30/01/09
6591
mathemnikiforov в сообщении #1045032 писал(а):
Задача, казалось бы проста,

Понятие простоты у каждого разное. Вы по какому критерию тут оцениваете?
mathemnikiforov в сообщении #1045032 писал(а):
учебное пособие Шведова есть, но вот беда - там не врубиться.

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

 Профиль  
                  
 
 Re: минимизация квадратичной функции на множестве как в ЛП
Сообщение13.08.2015, 21:21 


13/08/15
3
Дело в том, что сам Шведов пишет БУКВАЛЬНО - "решается очень просто". А потом дает 6 таблиц и ни одного пояснения. Всего одна страница и конец книги.
Я нашел два граничных решения, но не понимаю, как посчитать $ \lambda$.
всё остальное - понимаю.

-- 13.08.2015, 21:23 --

КУЧИ алгоритмов совершенно НЕ НУЖНО. Просто нужен хоть один, кто действительно умеет решать.

А не рассказывать давно известные преобразования через Теорему Куна-Таккера.

 Профиль  
                  
 
 Re: минимизация квадратичной функции на множестве как в ЛП
Сообщение14.08.2015, 19:27 
Заслуженный участник
Аватара пользователя


30/01/09
6591
mathemnikiforov в сообщении #1045107 писал(а):
Дело в том, что сам Шведов пишет БУКВАЛЬНО - "решается очень просто".

Нет у меня учебного пособия Шведова. Но существует совершенно элементарный метод. Этод метод перебора всех граней, рёбер (всех размерностей) допустимого множества. Но он работоспособен только для малых размерностей. Посмотрите учебник Васильева по методам оптимизации (параграф по задаче квадратичного программирования). Или воспользуйтесь стандртной программой из какого-нибудь матпакета (допустим, матлаба).

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

Модераторы: zhoraster, Супермодераторы



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

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


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group