linear programmingvector-spaces
In linear programming problems, the usual form is
minimize $ \sum c_j x_j$
subject to $\sum_{j=1}^n {\bf a_j} x_j = {\bf b}$
and $x_j \geq 0$.
where ${\bf a_j }$ are column vectors. Now, here my professor said:
The collection of vectors of the form $\sum_{j=1}^n {\bf a_j} x_j $ where $x_1, x_2, …, x_n \geq0$ is the ${\bf cone}$ generated by the vectors ${\bf a_1}, {\bf a_2}, …, {\bf a_n}$.
Im really not understanding how is this true. Perhaps am I getting this concept wrong?
Let's try to breakdown understanding in several steps for clarification.
With this in mind, let's determine if $$W_1 = \{ p \in P_3 \, : \, p(x) = a_0+a_1x + a_2x^2 +a_3x^3, \quad a_0 = 0 \}$$ is a subspace of $P_3$. Since $a_0=0$ then really all polynomials in $W_1$ are of the form $$p_1(x) = a_1x + a_2x^2 +a_3x^3.$$ Now we need to check the conditions. If we sum another polynomial $p_2 (x) = b_1 x +b_2x^2 +b_3x^3$ to $p_1(x)$, is the sum still a polynomial with null independent coefficient? If we multiply either of those by a number, will the independent coefficient still be zero? We have $$p_1(x) + p_2(x) = (a_1+b_1)x + (a_2+b_2)x^2 +(a_3+b_3)x^3 = c_1x +c_2 x^2 +c_3x^3,$$ therefore the sum is still a polynomial with zero independent coefficient. Multiplying by a number gives $$k p_1(x) = (ka_1) x + (ka_2)x^2 +(ka_3)x^3 = d_1 x + d_2x^2 +d_3x^3,$$ and it's still of the form given. Since the conditions are satisfied, we've proved $W_1$ is a subspace of $P_3$. Check the others.
The requirement space is the set of all nonnegative vectors ${\bf x} = (x_1,x_2,x_3,x_4,x_5,x_6)$ that satisfy the linear combination $\sum_{i=1}^6 {\bf a}_i x_i$ where ${\bf a}_i$ is the ith column of matrix $A$. Graphically, you can depict a combination of vectors as a cone. For example, the cone generated by $a_1$ and $a_2$ is:
Since the cone contains $b$, this combination of vectors has a feasible $x$ ($x_1=8/3$, $x_2=2/3$). The other combinations of vectors that contain $b$ are $(a_1,a_4)$, $(a_1,a_5)$, $(a_1,a_6)$, $(a_2,a_3)$, $(a_3,a_4)$ and $(a_3,a_6)$. If you find the $x$ for each of these combinations and compute the objective value for each of those $x$, the one with the largest objective value is optimal.
However, the question is flawed. There is no optimal solution, since $x=[0; 0; c; 0]$ is feasible to the original problem for any $c\geq 6$. The objective value is $2c$, which can grow arbitrarily large.
Best Answer
Given vectors $\mathbf{a}_1,\dotsc,\mathbf{a}_n$, you can refer to the sum $\sum_{i=1}^n \mathbf{a}_ix_i$, with $x_i \ge 0$ for $i = 1,\dotsc,n$ as their conical combination. As explained here, such a combination generates a cone, which is the collection of all the terms $\sum_{i=1}^n \mathbf{a}_ix_i$ with non-negative $x_i$'s.
If you take any two constraints $\sum_{i=1}^n \mathbf{a}_ix_i = \mathbf{b}$ and $\sum_{i=1}^n \mathbf{a}_iy_i = \mathbf{c}$, their sum $\sum_{i=1}^n \mathbf{a}_i(x_i+y_i) = \mathbf{b} + \mathbf{c}$ is still a constraint (it happens to be less informative though). In this sense, the space of your constraints is a cone.