Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have the following semi-infinite programming problem: I need to minimize a strictly convex real-valued 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?

share|improve this question
    
How about the other simple approach: start with some feasible $x_0$. At each step thereafter ensure that $x_k$ lies in the sublevel set defined by $f(x_0)$. So at least no $x_k$ will run off to infinity (though I guess the initial sublevel set must be closed)... –  Suvrit Mar 24 '13 at 1:17
    
You can try for each iteration to find a most-violated inequality (this could work e.g. if $g_i$ are strictly convex), and adding that inequality to your constraints. I don't know whether this is theoretically efficient, but at least avoids the problem pointed out by Brian below. –  Cristóbal Guzmán Apr 16 at 18:13
add comment

1 Answer

up vote 1 down vote accepted

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 -1-1/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 -1-1/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.

share|improve this answer
    
You are right, I haven't given all details. My problem is [ \min_{x\in\mathbb R^n}f(x) ] subject to [ g(x,t)=x_1g_1(t)+\cdots+x_ng_n(t)\geq 0,\quad t∈T ] where $f$ is a strictly convex function with a unique (unconstrained) minimum and all $g_j$ are continuously differentiable and strictly positive on a noncompact set $T\subseteq \mathbb R^p$. Moreover, it is always possible after minimization with respect to a finite number of constraints to locate a new $t$ for which the corresponding constraint is violated and hence it is added to the next finite set of constraints. –  George Mar 26 '13 at 7:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.