I have problems to make proof for below two statements.
Let Γ be the LP max cᵀx s.t. Ax ≤ b.
- prove that set of all optimal solutions to Γ is a convex set
- Let x' be a basic feasible solution of Γ. Let J denote the set of n linearly independent rows a_j x ≤ b satisfied with equality. Suppose c = ∑ {a_j | j∈J}. Show that for all feasible y ≠ x', cᵀy < cᵀx' .
For the first one, if Set S={all optimal solutions to Γ} is a convex set, then any two x,y from S, there should be a vector
p: tx+(1-t)y
is still in S, t is in [0,1]. But for the constraints
A(tx+(1-t)y) = tAx+Ay-tAy<= b + t(Ax-Ay) (Could not guarteen it is <=b)
I could not get that p is still in S. So where is wrong?
For the 2nd one, J={row_1, row_2, ...row_n}, while these rows are linear indepedent, and C=(∑a_i_1, ∑a_i_2, .. ∑a_i_n) i=1,..n
Then
C^t * y = ∑ (a_i_1 *y1+....a_i_n * yn ) C^t *x' = ∑ (a_i_1 *x1+....a_i_n * xn ), and non basic variables x_k are all 0.
At the same time, the original problme can be extended to Γ' be the LP max cᵀx* s.t. Ax* = b, by introducing some slack variables x.
But how to do next, still have not reach the target..
By linearity, $A(tx) = t Ax \preceq t b$ and $A((1-t)y) = (1-t)(Ay) \preceq (1-t)b$. Adding them together gives the desired result.