0
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ Thanks for your answer. I shall think about it. $\endgroup$ – Dave Jun 15 '18 at 15:26
  • $\begingroup$ 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. $\endgroup$ – David M. Jun 15 '18 at 15:27
  • $\begingroup$ 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? $\endgroup$ – Dave Jun 15 '18 at 15:32
  • $\begingroup$ The CVXPY docs indicate that you can (as long as you pair with a solver that can handle integer variables) $\endgroup$ – David M. Jun 15 '18 at 15:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Mark L. Stone Jun 15 '18 at 16:06

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.