I' trying to solve the following problem:
Consider the problem
$$min_{x \in \mathbb{R}^2} c^Tx$$ $$\text{such that: }$$ $$Ax \ge b$$ for $$A = \begin{bmatrix}1 & 1\\1 & -1\\-4 & 1\end{bmatrix}, b=\begin{bmatrix}2\\-2\\-4\end{bmatrix}, c=\begin{bmatrix}-1\\-1\end{bmatrix} $$
Let $x^*$ be the solution of the problem and let $a_i^T$ be the $i$-th rowof $A$. Show that the vector $c$ can be expressed as
$$c = \sum_{i \in \mathbb{I}} \alpha_i*a_i$$
where $\alpha_i \ge 0$ and $\mathbb{I}$ characterizes the in $x^*$ active restrictions (meaning it applies equality). It was hinted that a good way to solve this would be to consider the dual problem and using the complementarity of $(x^*,z^*)$, which is given due to the optimality criteria.
After rewriting the above problem into the standard form I have written down the dual problem as follows:
$$max_{y,z} \ b*y$$ $$\text{such that: }$$ $$A^Ty+z=c, z \ge 0$$
where $$A = \begin{bmatrix}1 & -1 & 1 & -1 & -1 & 0 & 0 \\1 & -1 & -1 & 1 & 0 & -1 & 0 \\-4 & 4 & 1 & -1 & 0 & 0 & -1\end{bmatrix}$$
But how could I use the complementarity of $(x^*,z^*)$ on that?
Primal:
$$\min c^Tx$$
subject to
$$Ax \ge b$$
The corresponding dual is $$\max b^Ty$$
subject to $$A^Ty=c$$$$y \ge 0$$
First, prove that the solution is finite (exercise).
Suppose for the primal contraint, it is not active, then the correponding dual variable $y_i=0$ by complementary slackness condition.
That is if $i \notin I, y_i=0$
Hence $$c=\sum_{i \in I} y_i a_i$$ and by the dual nonnegtive constraint, $y_i \ge 0$.