# Tag Info

0

You can get a more complete description of all the cases by arguing along the following lines: The feasible regions in both cases are the intersection of two half-spaces in the plane. (I am ignoring the nonnegative constraints on the coordinates). For such a region to be empty the lines defining the boundary should be parallel. We can multiply each ...

1

Take $(c,d,f,g)=(1,-1,-1,1)$ and $(a,b,e,h)=(1,0,0,-1)$. This way the primal constraints are $x_1-x_2\le 0$ and $-x_1+x_2\le -1$, which is equivalent to $x_1-x_2\ge 1$. Together we get $1 \le x_1 - x_2 \le 0$, which is impossible to satisfy. Similarly, the dual constraints are $0\ge y_1-y_2\ge 1$.

0

There is no duality gap in linear programming. In the primal world, the original problem and the version where it is in canonical form share the same solution (as in objective function). Since there is no duality gap, the corresponding dual will achieve the same objective function as well.

1

Well, $$Ax \le b$$ Now pre-multiply $y^T$ on both sides. Also, $$c^T \le y^T A$$ Now post-multiply $x$ on both sides.

1

Let $\mu^d$ be the restriction of a measure $\mu\in\mathcal{P}(\Omega)$ to its atoms ($\mu^d(A)$ is the maximum of $\mu(A\cap S)$ over countable $S\subseteq\Omega$). Then a counterexample is given by $$\phi(\mu)=\mu^d(\Omega)=\max\left\{\mu(S)\colon S\subseteq\Omega\textrm{ is countable}\right\}.$$

1

In all four cases, your $A^{-1}$ should be $A^T$. (Make sure you understand the difference!) Apart from that, $(D1)$ and $(D2)$ are fine. For $(D3)$, since the primal is a minimization problem with the restriction $A \mathbf x \leq \mathbf b$ (as opposed to $A \mathbf x \geq \mathbf b$), then the dual should have its variables constrained by $\mathbf x \leq ... 0 I haven't worked out the details - also I suspect we still haven't been given all the relevant definitions. But in case it helps, here's how the argument "must" go in outline, if it's by R-N: Somehow we reduce to the case$\mu(\Omega)<\infty$. Define a complex measure$\nu$by $$\nu(E)=x^*(\chi_E).$$Detail: Something shows somehow that$\nu$is in fact ... 0 (a) Both$x^*$and$\tilde{x}$are feasible solutions to$Ax=b, x \geq 0$, by definition of$\tilde{x}$, we have $$\tilde{c}'\tilde{x}\leq \tilde{c} x^*$$ Similarly, by definition of$x^*\$, we have $$c'x^*\leq c'\tilde{x}.$$ Adding the two terms up, we have $$\tilde{c}'\tilde{x}+c'x^*\leq \tilde{c} x^*+c'\tilde{x}$$ which is equivalent to ...

Top 50 recent answers are included