## Degenerate case of linear programming duality?

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

Let's say we have a maximization linear program that looks like this: maximize $\vec{c}\vec{x}$, subject to $\matrix{A}\vec{x} \leq 0$, $\vec{x} \geq 0$. If we take the dual, we have "minimize $0\vec{y}$, subject to $\vec{y}\matrix{A}\geq\vec{c}, \vec{y}\geq 0$". I'm particularly bothered by the "minimize $0$" part of the dual program - but does the duality theorem still hold - that is: is it true that if there is a $\vec{y}$ that is feasible for the dual program, then for all $\vec{x}$ that is feasible for the primal program, $\vec{c}\vec{x} \leq 0$?

Thanks!

-

## 2 Answers

Yes, the duality theorem holds. "Minimize 0" makes your life much easier, because you know exactly what the optimal value of the dual program is...

-

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

Igor is correct, and more can be said about this primal-dual pair of linear programs: because the primal maximization problem is homogeneous (i.e. zero constant terms in the constraints), the common optimal objecive value for both problems is either zero or $+\infty$:

1. If there exists a feasible solution $\vec{x}$ with a positive objective value, i.e. with $A \vec{x} \le 0$ and $\vec{c}\vec{x} > 0$, then this solution can be scaled by any positive constant $\lambda > 0$ (because $A (\lambda \vec{x}) \le 0$), which shows that the problem is unbounded ($\vec{c}(\lambda \vec{x})$ tends to $+\infty$ as $\lambda \to +\infty$).
2. If no feasible solution with negative objective value exists, then $\vec{x}=0$ is an optimal solution, and the optimal objective value is zero.

Using duality theory, one can check that the first case corresponds to an infeasible dual problem (no $\vec{y}\ge 0$ such that $\vec{y} A \ge \vec{c}$), while the second situation happens as soon as the dual problem admits a feasible solution.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 21, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9235310554504395, "perplexity_flag": "head"}