Метод наименьших квадратов с условиями

в общем случае можно доказать, что µ₁k₁+µ₂k₂=0 и заюзать это. Ща попробую свпомнить подробности.

короче, рассматриваешь варианты, когда µ₁, µ₂ равны нулю (четыре варианта получается). В зависимости от этого ты знаешь, равны ли k₁,k₂ нулю. Так как есть условие комплементарности µ_i k_i = 0.

А вообще заюзай в octave quadratic solver и все. qp называется там. Как раз под тебя заточено.

А так путь такой:

приводишь целевую функцию к виду f(k)=k^t Q k + c^t k, где k=(k_1, k_2)^t.

Система KKT получается такая:

Qk + c-µ₁-µ₂=0

µ₁,µ₂ ≥ 0

µ₁k₁=µ₂k₂=0.

Теперь первый вариант: ни один из множителей µ_i не равен нулю, значит k₁=k₂=0. Посчитал функцию f(k) и запомнил.

второй вариант: µ₁=0,µ₂>0. Значит k₂=0. Получаем задачу оптимизации с одним переменным. и двумя вариантами k₁=0 и k₁>0. Первый вариант уже известен, считаем второй просто вычислив k₁ из уравнения Qk+c=0 при k₂=0.

Аналогично считаем третий вариант с µ₁>0, µ₂=0.

Четвертый вариант с µ₁ и µ₂ >0 получаем опять же из простого уравнения Qk+c=0.


Единственная проблема, которая может возникнуть, это если Q не строго положительно определена. Но этого не будет, ибо целевая функция строго выпуклой выходит.

k1 * x - k2*x^2

Не совсем понятно зачем тебе ККТ, может просто сделать замену: k1 = a1^2, k2 = a2^2, а дальше использовать любой метод оптимизации...

Или у тебя лабораторка?

кстати, у тебя там множество точек или уже известные функции?

Не совсем понятно зачем тебе ККТ, может просто сделать замену: k1 = a1^2, k2 = a2^2, а дальше использовать любой метод оптимизации...

не получиццо. Ибо тогда целевая функция будет полиномом четвертой степени, которая не есть квадратичной формой. А значит и градиент от функции Лагранжа не будет линейной системой уравнений. А это значит - только численные методы решения, если не будет чудесного совпадения и можно будет как-то понизить степень этой системы удачно.

Так я и имел в виду использование ЧМ.

Так я и имел в виду использование ЧМ.

так нафиг тогда ухудшать сходимость и точность, если те же ЧМЫ отлично работают на исходной задаче? Тем более, что для квадратичных систем есть целый выводок отличных быстро сходящихся алгоритмов.

В той же функции qp из octave. Достаточно задать матрицу Q и вектор c + нижнюю границу для k₁ и k₂ и усе готово.

Не совсем понял, что от этого изменится.

Множество точек

Про оптимальность такого варианта я не говорил, ну и про использование octave тоже ничего не было известно...

Множество точек

ок. Можно даже не заморачиваться с формальными KKT уравнениями. А просто посчитать минимизацию на краю допустимой области для k (то есть два варианта: k_1=0, а потом k_2=0). А потом внутри этой облати. И то и другое без всяких множителей делается.

Кстати, если бы были готовые функции и не было бы условий на положительность коэффеициентов, то можно было бы изящно обойтись без МНК. А просто выбрать ортонормальный базис из полиномов {x,x^2} и спроецировать на него данную функцию (то есть тупо взять два интеграла)

Про оптимальность такого варианта я не говорил, ну и про использование octave тоже ничего не было известно...

Ничего страшного. Мы просто сделаем вид, что ничего не было :D

Квадрат вещественных чисел всегда больше нуля, соответственно при нахождении глобального минимума условия насчет выпуклости выполнятся автоматом.

Но есть подводные грабли: придется использовать численные методы, возможны локальные минимумы...

Точно, туплю же. Спасибо.

если бы были готовые функции и не было бы условий на положительность коэффеициентов

К сожалению, задача здесь сугубо технологическая, связанная с аппроксимацией результатов эксплуатации аппарата :)

К сожалению, задача здесь сугубо технологическая, связанная с аппроксимацией результатов эксплуатации аппарата :)

тогда забей болт на эти KKT и юзай октаву.

Квадрат вещественных чисел всегда больше нуля, соответственно при нахождении глобального минимума условия насчет выпуклости выполнятся автоматом.

насчет выпуклости: нихера подобного.

Ну да, погорячился я насчёт положительности квадратов, они неотрицательны, соответственно, в

k1 * x - k2*x^2

k2 может обнулиться и тогда...

насчет выпуклости: нихера подобного.

А какие еще могут быть случаи, кроме k2==0?

насчет выпуклости: нихера подобного.

А какие еще могут быть случаи, кроме k2==0?

да даже если там плюс k2 был бы - не спасет. Полином четвертой степени не выпуклый в общем случае, построй например x^4-x^2.

Мне казалось, что ТС интересует выпуклость относительно х...

Мне казалось, что ТС интересует выпуклость относительно х...

дык он делает МНК оптимизацию. То есть ищет оптимальные k_1 и k_2, чтобы функция наилучшим образом приближала _данное_ множество точек (x_i,y_i).

По иксу там вообще любые функции могут быть, нам по-барабану.

ааа...

Ну извините...

МНК подразумевает минимизацию суммы кдваратов разностей

\sum (y_i-f(x_i;k_1,k_2))^2.

и вот эту сумму надо минимизировать по k_1 и k_2. то есть по факту эта сумма при любой заданной f будет квадартичной формой от k.