# Removing constraints in convex optimization

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.

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

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.

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.

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