9
$\begingroup$

Say I have a convex optimization problem of the form $$\min_x f(x) ~~ s.t.\\ g_1(x)\leq0,\\\vdots \\g_n(x)\leq 0$$ with all functions convex. Suppose that $x^*$ is a unique optimizer to my problem and that we have $g_i(x^*)=0$ for some index $i$ and that $g_j(x^*)<0$ for all other indices. Then, it is well-understood that $x^*$ is also a solution to the problem $$\min_x f(x) ~~ s.t.\\ g_i(x)\leq0~.$$ in other words, the $(n-1)$ inactive constraints did not contribute anything to the problem. My question is: does anything change if, instead of having $n$ constraint functions, I have a continuum of functions? That is, say that I now have the problem $$\min_x f(x) ~~ s.t.\\ g_t(x)\leq0 ~ \forall t\in[0,1] ~ $$ for some parameterized family of functions $g_t$, and I can again show that there is a unique minimizer $x^*$ where there is a single value of $t^*$ such that $g_{t^*}(x^*)=0$ and $g_{t}(x^*)<0$ otherwise. Are there any extra precautions I need to take before claiming that it will suffice to consider the simpler problem $$\min_x f(x) ~~ s.t.\\ g_{t^*}(x)\leq0 ~ $$? My gut tells me no, but strange things are known to happen at infinity.

$\endgroup$
  • $\begingroup$ Should "$g_t(x^*)=0$ otherwise" be "$g_t(x^*)<0$ for $t\neq t^*$"? $\endgroup$ – Joonas Ilmavirta Nov 16 '14 at 20:58
4
$\begingroup$

Part of the reason this works for a finite set of constraints, and in particular the reason that the simplified problem still has a unique minimizer, is that $x^*$ is an interior point of each of the regions $g_j(x) \lt 0,\; j \ne i$ and therefore is an interior point of their intersection. This does not work if there are infinitely many constraints, and you cannot rely on uniqueness.

For a simple example consider minimizing $x_2$ under the constraint $x_1^2 - x_2 \le 0$. Clearly the unique minimizer is $(0, 0)$. We can however replace the single strictly convex constraint by an equivalent family of linear constraints $g_t(x) = 2tx_1 - x_2 - t^2 \le 0,\; t \in \mathbb{R}$. The only active constraint is then $g_0(x) \le 0$, but if we remove all the other constraints, the (over)simplified problem has every $(x_1, 0),\; x_1 \in \mathbb{R}$ as a minimizer.

$\endgroup$
1
$\begingroup$

I think the claim is true under some additional assumption: Let $\bar x$ be another solution of $$\min_x f(x) ~~ s.t.\\ g_{t^*}(x)\leq0 ~ $$ for which some constraints are not fulfilled, i.e. $g_{\bar t}(\bar x) >0$ for $\bar t\in T$ with some set $T$.

Let's try this additional assumption:

Now assume that $\sup_{t\in T} g_t(\bar x)$ is finite, i.e. the constraint violation is bounded.

But since the set of solutions of a convex problem is convex, you can take a convex combination $x_\epsilon = \epsilon \bar x + (1-\epsilon) x^*$ which is also a solution of the "reduced problem". Now check, if $x_\epsilon$ fulfills all constraints of the original problem, i.e. $g_t(x_\epsilon)\leq 0$: By convexity of $g_t$ this follows if $\epsilon g_t(\bar x) + (1-\epsilon)g_t(x^*)\leq 0$ which is equivalent to $g_t(x^*) \leq -\tfrac{\epsilon}{1-\epsilon} g_t(\bar x)$.

Oh, but here one sees that the additional assumption still does not guarantee that $x_\epsilon$ fulfills the constraints for $\epsilon$ small enough but that one needs a stronger assumption on how fast $g_t(x^*)$ and $g_t(\bar x)$ depart from zero if $t\neq t^*$. You may be able to build and prove an additional assumption that can be helpful for your case by exploiting additional structure of $g_t$…

This feels related to the concept of a Slater point

I think that there could be a counterexample without the additional assumption but I could not construct one yet.

$\endgroup$
  • $\begingroup$ I do not understand how $x_\epsilon$ can be proven to exist -- how can one construct an appropriately small $\epsilon$? $\endgroup$ – Jeff Kenney Nov 17 '14 at 18:26
  • $\begingroup$ Well, ehm, actually I don't see it either… Adapted my answer which is only a "partial answer" now… $\endgroup$ – Dirk Nov 19 '14 at 12:49

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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