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

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$$

• No. The $\max$ function is convex, so the inequality "goes the wrong way" – David M. Jun 15 '18 at 14:47
• Thanks a lot. Do you have any idea to handle this kind problem? – Dave Jun 15 '18 at 14:49
• Thanks. Could you please explain in detail? – Dave Jun 15 '18 at 15:01
• Simplest way is probably solving $n$ instances of $\min f(x)$, where you use the constraint $1-x_i \geq 0$ in instance $i$. – LinAlg Jun 15 '18 at 21:29

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$.

• Thanks for your answer. I shall think about it. – Dave Jun 15 '18 at 15:26
• These big-$M$ constraints (as they're called) are pretty standard in the world of operations research, mixed-integer programming, etc. They definitely take a little thought and getting used to. – David M. Jun 15 '18 at 15:27
• You mentioned in the above that CVX can be used here. I notice that the transformed problem by introducing binary variables is a discrete problem, so are you sure that CVX can solve the problem? – Dave Jun 15 '18 at 15:32
• The CVXPY docs indicate that you can (as long as you pair with a solver that can handle integer variables) – David M. Jun 15 '18 at 15:34
• CVX can handle this, using the big M formulation, providing that you have the CVX professional (including academic) version , not the free version, and have an integer-capable solver installed, and providing that f(x() is representable in CVX - not all convex functions are. Nor will CVXPY accept all convex functions. – Mark L. Stone Jun 15 '18 at 16:06