минимизация квадратичной функции на множестве как в ЛП

[mathemnikiforov]

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

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 $.

[мат-ламер]

mathemnikiforov в сообщении #1045032 писал(а):

Задача, казалось бы проста,

Понятие простоты у каждого разное. Вы по какому критерию тут оцениваете?

mathemnikiforov в сообщении #1045032 писал(а):

учебное пособие Шведова есть, но вот беда - там не врубиться.

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

[mathemnikiforov]

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

-- 13.08.2015, 21:23 --

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

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

[мат-ламер]

mathemnikiforov в сообщении #1045107 писал(а):

Дело в том, что сам Шведов пишет БУКВАЛЬНО - "решается очень просто".

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