I'm faced with the problem
$\min x \in R^2: (1/2) x' M x$
subject to $a'x = b, c'x = 1, x \ge 0$
where $c = [1, 1, ..., 1]$ and $a = [a_1, a_2, ..., a_n]'$, where $a_j$ are in $R$, $b$ is in $R$ as well, and $M$ is a positive definite real symmetric matrix.
My first idea was setting up the Lagrangian
$L(x, y) = (1/2) x' M x + y_1 \times (a'x - b) + y_2 \times (c'x - 1)$
where $y_1$ and $y_2$ are lagrangian multipliers on the constraints, and $y = [y_1, y_2]'$. This led me to
$dL/dx = M x + y_1 \times a' + y_2 \times c'$
$dL/dy_1 = a'x - b$
$dL/dy_2 = c'x - 1$
And if I understand the global optimality conditions correctly, since we have a convex function $(1/2) x' M x$ to work with since $M$ is positive definite,
for the gradient of the lagrangian to be zero
$dL/dx = M x + y_1 \times a' + y_2 \times c' = 0$
$dL/dy_1 = a'x - b = 0$
$dL/dy_2 = c'x - 1 = 0$
for feasibility
$x \ge 0$
However, my book gave me the following facit:
$M x - a u + c v - y = 0$
$b - a'x = 0$
$c'x - 1 = 0$
$x_i * y_i = 0, j = 1, ..., n$
where $u$ and $v$ are in $r$, and $x$, $y$ are in $R^n$.
Now the last two lines are equal to what I had, and I had forgotten the complimentary slackness condition on the fourth, but the first I don't understand at all. Is $y$ the $([a; c] x - b)$ vector? Why is it there? and what are $u$ and $v$? It doesn't look like my $dL/dx$ condition. Am I grossly misunderstanding the optimality conditions for this program?
Regards, Nomi-
PS:
Is this just the Karush-Kuhn Tucker conditions in this case?
PSS:
Maybe their $u$ and $v$ are my lagrange multipliers $y_1$, $y_2$. Still that doesn't explain where their $y$ came from, why is it included in the derivative of the Lagrangian with respect to $x$, ...
PSSS:
Is it possible to solve this without using the Lagrangian?
TLDR: Do you have to include $a -y'x$ term in the Lagrangian? What does it mean? What does the $y$ vector mean if it's not a lagrangian multiplier? Why is there a minus sign? Gpt says something about it being a "penalty for violating the non-negativity constraints", so solutions of the lagrangian are allowed to violate $x \ge 0$? But not the optimal solution as it has to be optimal to the original problem as well? And if I change some equality constraints to $\ge$ inequality constraints, does that mean that the gradient of the lagrangian only needs to be $\le 0$, and do I then have complimentary slackness conditions on that gradient with respect to the lagrange variables?
Cheers to anyone able to clear up my confusion,
regards, Nomi.
Edit: Ok I'm sorry this thread is becoming long but are the lagrange multipliers associated with dual feasibility? Shouldn't they be nonnegative then for the optimal solution according to the theorem of strong duality? Oh maybe that's just when I change out equality constraints with inequality constraints. When I have inequality constraints then, the lagrange multipliers need be non-negative and complimentary slackness must hold?