State a system as a canonical minimum problem

371 Views Asked by At

Suppose we have a linear system $$Ax=b,\,\,x\ge0,$$ where $A$ is a $m\times n$ matrix and $b$ is a given $n\times 1$ column vector.

Def: We say a problem is a canonical minimum problem if the problem requires us to find a $x\in\mathbb R^n $ s.t. $$Ax=b,\,\,x\ge0\text{ , minimize }c\cdot x \text{ for some given }c\in\mathbb R^n.$$

My problem: Consider the linear system $Ax=b,\,\,x\ge0$ with nothing to be optimized. Show how to state this system as a canonical minimum problem by the right choice for the vector $c$.

In fact, I am confused with what the problem says. And I am not sure what it wants me to do. Can someone help me understand it?

Thanks in advance.

1

There are 1 best solutions below

1
On

LinAlg has almost answered this question. I am posting this answer so as to clear this question from the unanswered question queue.

Can someone help me understand it?

\begin{align} S_1 &= \{ x \in \Bbb{R}^n \mid Ax=b, x \ge 0 \} \\ S_2 &= \arg\min_{x \in \Bbb{R}^n \\ Ax=b \\ x \ge 0} c^Tx \end{align}

Determine $c \in \Bbb{R}^n$ such that $S_1 = S_2$.

The solution is trivial: take $c = 0 \in \Bbb{R}^n$, so that $c^Tx \equiv 0$. In this case, any element in $S_1$ is a minimiser to the trivial "canonical LP", so $S_1 \subseteq S_2$. The other inclusion should be clear, and I left the detailed explanation as an exercise.