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?
2
-
$\begingroup$ 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)... $\endgroup$– SuvritCommented Mar 24, 2013 at 1:17
-
$\begingroup$ 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. $\endgroup$– Cristóbal GuzmánCommented Apr 16, 2014 at 18:13
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
answered Mar 24, 2013 at 4:16
-
$\begingroup$ 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. $\endgroup$– GeorgeCommented Mar 26, 2013 at 7:38