Given that $f(\cdot)$ is a convex function of $(x_1,\cdots,x_n)\in\mathbb{R}^n_+$, is Problem $\mathbf{P}$ convex?

Question

Given that $f(\cdot)$ is a convex function of $(x_1,\cdots,x_n)\in\mathbb{R}^n_+$, is Problem $\mathbf{P}$ convex? $$(\mathbf{P})\min_{x_1,\cdots,x_n}f(x_1,\cdots,x_n)\\ s.t. \quad\max\{1-x_1,\cdots,1-x_n\}\ge 0$$

Answer 1

The proposed problem is not convex, since the inequality "goes the wrong way".

One way to model/solve such a problem is to formulate the $\max$ function using binary variables. As an example, suppose we want to enforce the constraint

$$ \max\{x_1,x_2,x_3\}\geqslant0. $$

This approach requires us to know a positive constant (typically called $M$) such that $-M$ is a lower bound on the values of $x_1,x_2,x_3$ that we care about.

Note: Arbitrarily choosing some huge $M$ value can have bad computational side effects--it's best to think about the problem you're solving and come up with the best lower bounds possible.

Suppose that we have $M>0$ such that $-M\leqslant{x_i}$ is a valid lower bound for $i=1,2,3$ (in practice we could choose three constants $M_i$ for each $x_i$, but I'm keeping things simple).

Then introduce a binary variable $z_i\in\{0,1\}$ for each $i=1,2,3$, and add the constraints

$$ x_i+Mz_i\geqslant0\text{ for }i=1,2,3 $$ and $$ z_1+z_2+z_3\leqslant2. $$ The constraint $z_1+z_2+z_3\leqslant2$ means that there will be at least one $z_i=0$. For this $i$, the first constraint becomes $x_i\geqslant0$. Hence there exists an $i$ such that $x_i\geqslant0\Rightarrow\max\{x_1,x_2,x_3\}\geqslant0$.