If I am minimizing a quadratic function (not necessarily convex) over a linearly constrained feasible region, what are the necessary and sufficient conditions that the objective value is unbounded?
|
1
|
My guess would be that there are no such (polynomial checkable) conditions. Solving over this is NP-hard, so it seems likely that determining whether it is bounded is NP-hard. You'd have to look at the proof in Sahni, S. "Computationally related problems," in SIAM Journal on Computing, 3, 262--279, 1974 (reference from Wikipedia) to determine if the same reduction goes through. |
||
|
|
OR-Exchange! Your site for questions and answers about operations research.
|
1
|
This answer may be too basic, but just in case ... The obvious necessary condition is that the feasible region is unbounded. (I assume you're in finite dimensions, so a bounded region has a compact closure.) Directions in which the feasible region is unbounded are called "recession directions". The obvious sufficient condition is that a recession direction exists along which the objective function is strictly decreasing (negative directional gradient). |
||
|
|
|
1
|
This condition is not sufficient for say Min (x-1)^2 s.t. x>=0, x \in R. At point x=0.5, the direction of descent is along a recession direction but the solution is still bounded. Probably you meant to say that "objective function is decreasing along a recession direction at all feasible points". Such a condition would be difficult to check. |
|||
|
