The problem is given as \begin{equation*} \text{minimize} \hspace{.8em} -x_1-3x_2\\ \text{subject to} \hspace{.8em} x_1-2x_2 \le 4\\ \hspace{2 cm} -x_1+x_2 \le 3 \\ \hspace{2 cm} x_1,x_2\geq 0. \end{equation*} Graphically it's clear that the solution is unbounded but how do i show this analytically? i have converted it into the form \begin{equation*} \text{minimize} \hspace{.8em} C^{\top}x\\ \text{subject to} \hspace{.8em} Ax=b\\ \hspace{2 cm} x_1,x_2 \ge 0 \end{equation*} Where $C^{\top}=[-1~-3~~ 0~ ~0~ ~0], b=[4~~3]^{\top}$ and $A=\begin{pmatrix}1&-2&1&0\\-1&1&0&1\end{pmatrix}$ , Now i think i have to find a vector $d$ s.t cost is unbounded for $x_{*}+\alpha d$, so how do i choose $d$ and $x_{*}$ ? or there's any other way ?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Try $d=(1,1)^T$ for the upper version and multiply it with a positive scalar $\endgroup$– sqlmanCommented Mar 21, 2020 at 10:03
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
If your plot out the diagram,
you can pick $x_*=(4,0)^T$ and pick $d=(2,1)^T$. Note that $(2,1)$ is orthogonal to $(1,-2)$ which is the normal direction of the first inequality.
$$\lim_{\alpha \to \infty}-(4+2\alpha)-3\alpha \to -\infty$$
$$(4+2\alpha)-2(\alpha)\le 4$$ $$-(4+2\alpha)+\alpha=-4-\alpha\le -4\le -3$$ $$4+2\alpha \ge 0, \alpha \ge 0$$
answered Mar 21, 2020 at 10:06
-
$\begingroup$ so $d, x_{*}$ has to be picked inside the feasible region right ? $\endgroup$ Commented Mar 21, 2020 at 10:09
-
1$\begingroup$ Just find a point and a feasible direction that decreases the objective value. You can also pick other line segments which lies in the feasible set. Alternatively, if you have the concept of duality, you might like to take dual and see that it is not feasible but the primal is feasible. $\endgroup$ Commented Mar 21, 2020 at 10:14
-
$\begingroup$ yes thanks, one doubt : we are doing this for the first system right? not the one where i have introduced slack variables $\endgroup$ Commented Mar 21, 2020 at 10:51
-
1$\begingroup$ visualizing $2$ dimensions should be easier =) so yup, the version without slack variable $\endgroup$ Commented Mar 21, 2020 at 10:57