Relativt enkel optimering

Är en relativt enkel optimeringsuppgift som jag inte riktigt lyckas få till.

max x' * a - k/2 * x' * A * x = f(x)
s.t. x' * 1 = c

1 är en nx1 vektor med 1or. x är nx1. B är nxn. ' betecknar transponat.

Deriverar f(x) ger

a - k*A*x = 0

Deriverar igen ger -k*A är negativ eftersom A är positivt definit. så funktionen är konkav

löser ut x ger x=1/k*A^(-1)a. Men jag fattar inte hur jag ska göra med
x' * 1 = c, får ju inte ut något av det genom att ersätta.

En Lagrangemultiplikator kanske kan fungera?

Sätt g(x; λ) = f(x) + λ (x * 1 - c) och sätt derivatorna m.a.p. x och λ lika med 0.

Derivatan m.a.p. λ blir bivillkoret du hade. Derivatan m.a.p. x kommer att innehålla λ. Det låter som det blir ett värre system att lösa, men ofta kan det hjälpa.

Problemet blir ju att att deriverar jag m.a.p. x får jag:

a - k*A*x + λ * 1

sen m.a.p. λ

x' * 1 - c = 0

Men har ju inget jag kan lösa ut lambda ifrån. Så jag kommer ju inte så mycket längre med detta. Eller tänker jag helt fel?

Du har n st reella ekvationer som alla innehåller λ:
a - k*A*x + λ * 1 = 0

Det räcker med 2 av dessa ekvationer för att eliminera λ.

Hmm jo, svaret blir lite väl krångligt då dock. Ska gå att uttrycka m.h.a. av dessa konstanter, vektorer och matriser.

Har inte hunnit kolla så mycket på uppgiften, men funderar över om diagonalisering av A skulle kunna hjälpa.

Hur då tänker du?

Om A är diagonal, A = diag(d1, ..., dn), blir de n raderna som a - k A x ger upphov till väldigt enkla:
a1 - k d1 x1
...
an - k dn xn

Om A inte är diagonal får du i stället
a1 - k (a11 x1 + ... + a1n xn)
...
a1 - k (an1 x1 + ... + ann xn)

Kom på hur jag kunde lösa den. Tack för din input =)

Det skulle vara intressant att se hur du gjorde.

Sure, ser det som inequality constraints först och skriver om det till en minimizing problem:

max x' * a - k/2 * x' * A * x = f(x) -> min k/2 * x' * A * x - x' * a
s.t. x' * 1 =< c

Så m.h.a. lagrangemultipliers får jag:

k/2 * x' * A * x - x' * a + y*(x'*1 - c) = L(x,y)

d/dx(L(x,y)) = k*A*x - a + y*1 = 0 -> k*A*x + y*1 = a

Så vi lägger vi till villkoret att x'*1 = c alt: 1'*x = c, så kan vi sätta vi lösa följande system:

[k*A 1; 1' 0]*[x; y] = [a; c]

Det vill säga
[x; y] = [k*A 1; 1' 0]^(-1) * [a; c]

Det blev alltså Lagrangemultiplikatorn till slut.