3
$\begingroup$

Consider a function $ f: \mathbb{R}^n \times \mathbb{R}^m \rightarrow \mathbb{R} $ such that $\forall x \in \mathbb{R}^n$ the map $f(x,\cdot)$ is convex, and $\forall y\in \mathbb{R}^m$ the map $f(\cdot,y)$ is convex as well. We assume that $m<n$.

Given $y^1, ..., y^N \in \mathbb{R}^m$, and $c \in \mathbb{R}^n$, consider the following convex optimization problem.

$$ \min_{ x \in \mathbb{R}^n } c^\top x \ \ \ \text{ sub. to: } \ f(x,y^i) \leq 0 \ \ \forall i \in [1,N] $$

Let $x^\star$ be its optimizer, supposed to be unique.

Notice that the above optimization problem is equivalent to the following one.

$$ \min_{ x \in \mathbb{R}^n } c^\top x \ \ \ \text{ sub. to: } \ f(x,y) \leq 0 \ \ \forall y \in \text{conv}( \{y^1, ..., y^N\} ) $$

We now say that $f(x,y^k) \leq 0$ is a "true" constraint if it "really matters", i.e. any optimizer of the problem

$$ \min_{ x \in \mathbb{R}^n } c^\top x \ \ \ \text{ sub. to: } \ f(x,y^i) \leq 0 \ \ \forall i \in ([1,N]\setminus\{k\}), $$

which we denote by $x_{ \neg k }^\star$, is such that $c^\top x_{ \neg k }^\star < c^\top x^\star$.

What is the number of true constraints?

$\endgroup$
1
$\begingroup$

In generality, the removal of $y^k$ alters the feasible region iff $\operatorname{conv}(\{y^i, i=1,\ldots,N\}) \ne \operatorname{conv}(\{y^i, i=1,\ldots,N, i \ne k\})$. It is easy to construct an example, where all $y_i$ are extremal points of their convex hull. Note that, however, this may not change the optimal solution.

$\endgroup$
  • $\begingroup$ Thanks. So let me update the question, saying that a true constraint is whenever the optimal value changes. Then it is not clear what happens if all $y^i$'s are extreme points of their convex hull, because, as you say, removing one of them may not change the optimal solution. So I guess the question is still open. $\endgroup$ – user693 May 7 '13 at 9:40
0
$\begingroup$

I guess that by "true" constraints you are meaning "active" or "blocking" constraints, that is constraints such that $f(x^*,y^i)=0$.

Because, by convexity, if a constraint does not block -- i.e., $f(x^*,y^i)<0$ -- then removing it from the set of constraints does not change the optimum.

To count the blocking constraints is quite easy a posteriori, that is once you know the optimum. In facts, most software provides you the "Lagrange multipier" $\frac {\partial x^*} {\partial y^i}$ which are null exactly when they do block.

To count the blocking constraints a priori, before to compute the optimum is a $NP$ problem. Even simplifying the convex hull of constraints $\{x|\forall i, f(x,y^i)\le0\}$ is $NP$.

Maybe you can find something starting there.

$\endgroup$
  • $\begingroup$ Thanks for the answer. The set of active constraints is only a superset of the set of "true" constraints. In other words, it is possible that removing one active constraint the optimal solution does not change. $\endgroup$ – user693 May 23 '13 at 15:59
  • $\begingroup$ Let me understand: you can remove a constraint : (a) "globally" because it is outside the feasible region (that is $\forall j \not= i f(x,y^j)\le0 \implies f(x,y^i)\le0$). This is mathematically useless (because it does not change the topology of the feasible region), and computationaly hard. (b) "locally" because near the optimum $f(x^*,y^i)\lt0$. In that case, reoptimizing without this constraint will lead to the same $x^*$. Such constraints are easy to find, but you need to know $x^*$. What are your "true" constraints? $\endgroup$ – AlainD May 23 '13 at 16:42
  • $\begingroup$ I do not understand why you argument about $x^\star$. I am interested in the cost. Can you see what is meant in the question? $\endgroup$ – user693 May 23 '13 at 20:55
  • $\begingroup$ Maybe I am misunderstanding the question. So I asked for precision in an other answer (to be able to use markdown) $\endgroup$ – AlainD May 24 '13 at 8:21
0
$\begingroup$

What are you calling a "true" constraint? Suppose you want to minimize $c(x)=x^2$ under some sets of constraints:

  1. $x\le1$ and $x\le2$, optimum $x^*=0$ [$f(x,y)=x-y, y_1=1, y_2=2$]. The second constraint is redundant, it can be eliminated because its a consequence of the first ($y_1 \lt y_2$).

  2. $x\le1$, optimum $x^*=0$. [$f(x,y)=x-y, y_1=1$]. This constraint is inactive, it in not eliminated because of other constraints but because it is true near the optimum ($x^*\lt y_1$).

  3. $x\lt-1$, optimum $x^*=-1$. [$f(x,y)=x-y, y_1=-1$]. This constraint is active, you cannot remove it without changing the optimum.

Type 3 is clearly a "true" constraint and type 1 clearly not. But what about type 2?

$\endgroup$

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.