Ideally, the feasible region of a linear program (henceforth "LP") is a convex polytope, a geometric object that is convex, closed, bounded, and has a finite number of flat sides (intersecting at vertices or extreme points). Figure 1 shows a two dimensional example. The shaded area is the feasible region; the dots are the vertices.

Figure 1: Polytope |

Being closed and bounded (and therefore, in finite dimensions, compact) ensures, via the extreme value theorem, that any continuous objective function attains its maximum and minimum over the feasible region at one or more points. Of course, the objective function of a linear or quadratic program is continuous. For a linear objective function, we can be more specific: the optimum will be attained at one or more extreme points. So we only need to check the vertices, and this in essence is what the famed simplex algorithm does.

To see why that is important, consider the following candidate for world's most trivial LP:\[ \begin{array}{lrcl} \textrm{minimize} & x\\ \textrm{subject to} & x & \ge & 0. \end{array} \] Its solution is, shockingly, $x=0$. Now suppose we try to use a strict inequality in the lone constraint:\[ \begin{array}{lrcl} \textrm{minimize} & x\\ \textrm{subject to} & x & \gt & 0. \end{array} \]The lower bound of the objective function is again 0, but it is never attained, since $x=0$ is not a feasible solution. This is a consequence of the feasible region not being closed. Technically, while the objective function ($f(x)=x$) has an infimum over the feasible region, it

*does not have a minimum*. While trivial, this is a useful example of why

*we never use strict inequalities (>, <) in a mathematical program*.

One step more general than a polytope is a polyhedron, which retains all the characteristics of a polytope except boundedness. Figure 2 illustrates a polyhedron.

Figure 2: Polyhedron |

- if the objective function degrades (gets bigger if minimizing, smaller if maximizing) along
*every*recession direction, the optimal value of the objective function will be attained at one or more extreme points; - if the objective function improves (gets smaller if minimizing, bigger if maximizing) along
*any*recession direction, the problem is unbounded (the objective function does not have a maximum or minimum, whichever one you were hunting), which likely means you omitted or screwed up a constraint; and - if the objective function is constant along at least one recession direction

and does not improve along any of them, the objective function achieves its optimum at one or more extreme points and along every ray starting from one of those extreme points and pointing in a recession direction where the objective stays constant.

Figure 3: Nonconvex polytope |

I think you may be having an issue with your LaTeX renderer (MathJax?). I'm seeing things like $x$ in the post.

ReplyDeleteRyan: Thanks for letting me know. You're the second person to report that, and it seems to be a recent thing. You're right that I'm using MathJax, and the site looks okay to me, in both Firefox and Chrome, on every device I've tested. So far, the only ideas I've had (both pure speculation) are either intermittent issues with the MathJax CDN or security settings at the viewer's end blocking cross-site scripting. AFAIK Blogger does not have its own MathJax installation, so (short of moving my blog to another server) I'm stuck using the CDN.

DeleteIt would help to know if you have anything blocking cross-site scripting.