"Задача оптимизации"

[Евгений Машеров]

Насколько я понимаю, трудность здесь в наличии ограничений-неравенств. Что означает, что некоторые из них обращаются в равенства, а некоторые выполняются "сами собой", и априори неизвестно, какие какие. Ограничения-равенства легко учитываются введением множителей Лагранжа. а перебор всех $2^n$ наборов ограничений для даже скромных n непрактичен. Тут, насколько я понимаю, существует либо стратегии направленного перебора вершин множества ограничений, сходные с симплекс-методом, либо используется техника нелинейной оптимизации "общего вида", стартуя от внутренней точки множества ограничений и идя по градиенту.
Возможный вариант - заметить, что решением задачи без ограничений является $x=A^+b$, где $A^+$ - псевдообратная к А матрица, ввести новые переменные $y=x-A^+b$, и искать ближайшую к нулю точку множества ограничений.

[artempalkin]

Евгений Машеров в сообщении #1527091 писал(а):

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

Трудность тут в том, что это целая отдельная задача линала (и каких-то смежных дисциплин), в общем виде не решаемая (если только нельзя назвать решением задачи в общем виде решение типа: "Найдем решение. Запишем его в ответ.").
Короче, какой-то развод на вступительных экзаменах :) Предполагаю, что положительную оценку ставили за какие-то хотя бы мысли в направлении решения задачи.

[Евгений Машеров]

Как мне представляется, если это экзамен, то это может быть либо вопрос, либо задача к билету. Ответ на вопрос должен состоять в объявлении этого задачей квадратичного программирования с квадратичными ограничениями (может даже, одного этого на троечку хватит...) и описания метода её решения "в общем". При этом метод должен быть описан в ранее пройденных курсах. Или в "литературе к экзамену". Если задача к билету - то она за пределами решения вручную, значит, есть какой-то софт (и с ним знакомили ранее) и надо его использовать.

[Евгений Машеров]

И нетактичный вопрос к топикстартеру. Вы студент, собирающийся сдавать этот экзамен (и есть так - ранее учились в том же ВУЗе, получив степень бакалавра, или перешли в другой?), или же репетитор, помогающий студенту, готовящемуся к экзамену (или ещё какого-то рода помощник)?

[vpb]

artempalkin в сообщении #1527177 писал(а):

это целая отдельная задача линала (и каких-то смежных дисциплин), в общем виде не решаемая

Угу.

[Евгений Машеров]

artempalkin в сообщении #1527177 писал(а):

в общем виде не решаемая

Как-то очень сильно сказано. Вполне себе решаемая "в общем виде" (в том смысле, что для решения не требуется какой-то особый вид условий, как, скажем, для решения в радикалах уравнений выше 4 степени). Нет простой и явной формулы, дающей ответ - да, так оно и есть. Для ограничений-равенств такую можно написать, а для неравенств непонятно, какие действительно ограничения, превратившиеся в равенства, а какие выполняются, как неравенства и нас не стесняют. Нужен итеративный алгоритм, и такие есть. Разные. Перебирающие ограничения и выясняющие, какие обращаются в равенства и дают слагаемые в функции Лагранжа (и можно для них искать множители Лагранжа), а какие ни на что не влияют. Или другие алгоритмы, внутренней точки, с барьерной функцией. А вот что требуется на экзамене - собственно, для этого я и спрашивал, в каком качестве ТС имеет к экзамену отношение.
Да, и это не "линал", хотя и использует линейную алгебру. Это "Методы оптимизации".

[vpb]

Евгений Машеров в сообщении #1527219 писал(а):

Для ограничений-равенств такую можно написать, а для неравенств непонятно, какие действительно ограничения, превратившиеся в равенства, а какие выполняются, как неравенства и нас не стесняют. Нужен итеративный алгоритм, и такие есть. Разные. Перебирающие ограничения и выясняющие, какие обращаются в равенства и дают слагаемые в функции Лагранжа (и можно для них искать множители Лагранжа), а какие ни на что не влияют.

Коллега, вы что-то путаете. В этой задаче ограничение только одно, в виде эллипсоида. Общая задача квадратичного программирования --- это другое дело (в котором я не разбираюсь). Может, вам показалось, что там неравенство покомпонентное ? так отнюдь, просто одна квадратичная функция.

[artempalkin]

Евгений Машеров в сообщении #1527206 писал(а):

И нетактичный вопрос к топикстартеру. Вы студент, собирающийся сдавать этот экзамен (и есть так - ранее учились в том же ВУЗе, получив степень бакалавра, или перешли в другой?), или же репетитор, помогающий студенту, готовящемуся к экзамену (или ещё какого-то рода помощник)?

Репетитор, помогающий готовиться.

vpb в сообщении #1527227 писал(а):

Может, вам показалось, что там неравенство покомпонентное ?

Да, вот мне тоже так показалось, что вам так показалось :)
Я бы прислал вам вариант экзамена (это 2018 года), просто думаю, как это сделать.
Но вот ради интереса соседняя задача (следующая по номеру, то есть в принципе как бы более сложная по логике):
Дана матрица такая, что $P^2=P$. Докажите, что сумма всех ее собственных значение меньше $n$ (это порядок матрицы).

[Евгений Машеров]

Так с.з. такой матрицы могут быть только 0 или 1. Далее очевидно.

[Евгений Машеров]

Виноват. Mea culpa.
Но у меня не та ошибка, я что ограничение скалярное, понял. А чего сослепу не заметил - что оно одно, воспринял, как
$x^TP_ix-q_i^Tx+w_i\leqslant 0$, $i=1,k$ примерно как по ссылке задача квадратичного программирования с k квадратичными ограничениями.
Но если оно одно - задача драматически упрощается.

(Оффтоп)

Пациент либо жив, либо мёртв

Либо ограничение в оптимальном решении выполняется, как равенство, либо как строгое неравенство. В последнем случае оно ни на что не влияет.
Решаем задачу без ограничений.
$x_u=(A^TA)^{-1}A^Tb$
И проверяем, удовлетворяет ли $x_u$ ограничению. Если удовлетворяет - ответ готов. Если нет - ограничение становится
$x^TPx-q^Tx+w=0$ и оно учитывается через множитель Лагранжа.

[artempalkin]

Евгений Машеров в сообщении #1527237 писал(а):

Так с.з. такой матрицы могут быть только 0 или 1. Далее очевидно.

Ну вот и сравните уровень сложности задач 6 и 7 из одного и того же варианта. Все остальные задачи по сложности уровня 7.

-- 26.07.2021, 22:30 --

Евгений Машеров в сообщении #1527245 писал(а):

Либо ограничение в оптимальном решении выполняется, как равенство, либо как строгое неравенство. В последнем случае оно ни на что не влияет.
Решаем задачу без ограничений.
$x_u=(A^TA)^{-1}A^Tb$
И проверяем, удовлетворяет ли $x_u$ ограничению. Если удовлетворяет - ответ готов. Если нет - ограничение становится
$x^TPx-q^Tx+w=0$ и оно учитывается через множитель Лагранжа.

Так на каком этапе решение заканчивается? То есть что тут оценивается в 10 баллов (скажем, что это максимальная оценка за задачу, я точно не знаю)?

[Евгений Машеров]

Честно сказать - не знаю. Возможно, действительно "на 10 баллов" надо дать полное решение в три притопа:
1. Решение задачи без ограничений (которое должно на автомате выскакивать, это алгоритм регрессионного анализа)
2. Проверка, удовлетворяет ли полученное решение ограничению.
3. Решение задачи при ограничениях (вот тут надо выписать минимизируемую функцию с учётом множителей Лагранжа и использовать матричное дифференцирование).
Да, и вопрос относительно Вашей роли был ещё и к тому, не была ли такая задача рассмотрена в предшествующих курсах (бакалавриата), а репетируемый студент либо прогулял, либо забыл, либо поступает в магистратуру другого ВУЗа, где немного отличная программа. То есть хорошо бы посмотреть конспекты бакалавров данного ВУЗа.

-- 27 июл 2021, 09:05 --

artempalkin в сообщении #1527260 писал(а):

Ну вот и сравните уровень сложности задач 6 и 7 из одного и того же варианта. Все остальные задачи по сложности уровня 7.

Ну и нет обязанности давать все задачи одной сложности. Вовсе нет трудных - ничего не проверяем у студента, кроме бойкости и памяти. Все трудные - и студенту плохо, и проверяющему преподавателю. Так что может быть одна действительно требующая и знаний, и работы, а прочие вопросы на "быстроту соображения" и знание некоторых простых фактов, как задача с идемпотентной матрицей.

[vpb]

Евгений Машеров в сообщении #1527245 писал(а):

А чего сослепу не заметил - что оно одно,

Понятно.

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

[Евгений Машеров]

У меня подозрение, что это не "неразрешимая задача", а "разобранная на занятиях задача", просто г-н студент это либо забыл, либо прогулял, ну, может, учился в другом ВУЗе, где такого не было.

[Евгений Машеров]

В общем, мне представляется задача так.
Сперва решаем задачу без учёта ограничения. Что представляет собой задачу регрессионного анализа, по сути. И гг. студентам её и вывод давали (тут вопрос, отчего Ваш студент не знает - плохо ходил на занятия, или же в другом ВУЗе немного отличалась программа?)
Подставляем ответ в ограничение. Либо оно удовлетворяется (ура! всё готово!), либо не удовлетворяется этим решением, а тут надо понимать, что ограничение может быть только равенством. Тогда через множитель Лагранжа. Получаем выражение, зависящее от неизвестной лямбды.

artempalkin в сообщении #1526720 писал(а):

$$(2A^TA+2\lambda P)x=2A^Tb+q$$

(вывод не проверял, но выглядит правдоподобно).
Задачу рассматриваем, как решение нелинейного уравнения от лямбды. Бисекция, regula falsi... Ищем лямбду такую, чтобы ограничение, в которое подставлены значения вектора x при заданной $\lambda$, выполнялось, как равенство. При этом обращаемая матрица вырожденной быть не может, поскольку сумма неотрицательно определённой (матрица Грама $A^TA$) и положительно определённой P.
Иначе говоря, никакой "суперсложности" нет, есть комбинация из двух изученных методов оптимизации, и немного на понимание того, что ограничение существенно, когда равенство, строгое неравенство означает, что ограничение не "играет".