Equivalent optimization problem

76 Views Asked by At

I have the following optimization problem: $$ \min_{x} c^Tx \,\text{s.t.}\sum_i|x_i|\leq 1 $$ We can convert the problem equivalently as the Linear Program: $$\min_{x,u} c^Tx \,\text{s.t.}\sum_iu_i\leq 1,\,|x_i|\leq u_i\forall i$$ So we can conclude that the sets $L_1=\{x;\sum_i|x_i|\leq 1\}$ and $L_2=\{(x,u);\sum_iu_i\leq 1,\,|x_i|\leq u_i\forall i\}$ are equivalent, that is, from a feasible point of one set, we can find the feasible point of the other.

My doubt is (maybe too simple), why are we considering $|x_i|\leq u_i$ instead of $|x_i|= u_i$ in the set $L_2$. Won't equality be more appropriate? Or is it for the sole purpose of making the set convex?

1

There are 1 best solutions below

0
On

You are right, the optimization problems are equivalent.

Expressing them in terms of $|x_i |\le u_1$ gives us convexity.