I have the following semiinfinite programming problem: I need to minimize a strictly convex realvalued function $f:\mathbb R^n\to\mathbb R$ subject to infinite linear constraints. I know in advance that the problem has a unique solution. The feasible set defined by these constraints forms an unbounded convex closed cone (and hence noncompact). My question is the following: Is it valid to apply the standard discretization method, that is, start by a finite number of constraints, minimize $f$ subject to them, then find a constraint that is violated by the minimizer, augment the number of constraints by adding this particular one, minimize again and so on? That is, is it guaranteed that the sequence of partial minimizers will converge to the minimizer of the original problem?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

No. The problem with this simple minded approach is that the sequence of constraints that you add might go on forever without adding a critical constraint. Consider the following example problem. $\min x$ subject to $ x \ge 0$ $ x \ge 11/n, \;\;\; n=1, 2, ...$ Now, suppose that you start with the inequality $x \ge 2$, and that in each successive iteration you find that the next inequality of the form $x \ge 11/n$ is violated and add it to the problem. Your sequence of solutions will have $x$ converging to 1, which clearly isn't optimal. You'll need to specify additional structure in the problem and/or use a more sophisticated algorithm. 

