0
$\begingroup$

Suppose we have a linear objective function that we want to maximize. All variables are from the set of reals. We have a constraint of the form:

$$\max(x_1,x_2) + \max(x_3,x_4)\leq c\,, \text{ with } c\in\mathbb{R}$$

Can we transform this such that we obtain a linear program? I have read that constraints of the form

$$\max(x_1,x_2)\geq x_3$$

are problematic because this transforms into

$x_1\geq x_3$ OR $x_2\geq x_3$

Back to my constraint, I would do the following transformation:

$m_1 + m_2\leq c$

$\max(x_1,x_2)\leq m_1$

$\max(x_3,x_4)\leq m_2$

which is transformed into

$m_1 + m_2\leq c$

$x_1\leq m_1$

$x_2\leq m_1$

$x_3\leq m_2$

$x_4\leq m_2$

which looks plausible to me as there is no OR introduced and both have equivalent meanings to me. The blowup is just polynomial in the original size of the input.

Could you please say if this transformation is correct or not with a proof? I am very interested in understanding how such proofs work. I know that linear constraints split the convex feasible set into a convex feasible and unfeasible set. The constraints that I introduced are linear which should make the feasible set convex. But how does this relate to my original problem which had a maximization? Will the solution of the obtained linear program be the optimal solution of the original optimization problem?

$\endgroup$
  • $\begingroup$ That first constraint is convex, so while I believe you should be able to transform it into a set of linear constraints, you can definitely use convex optimization software like CVX for your overall problem if you don’t want to bother with the transformation. $\endgroup$ – cdipaolo Feb 8 at 3:03
  • $\begingroup$ Also, yes, I believe your transformation is correct. $\endgroup$ – cdipaolo Feb 8 at 3:15
  • 1
    $\begingroup$ @cdipaolo okay nice so my proof will be using the fact that all constraints are convex and successively adding each convex constraint will keep the feasible set convex. This was most likely proven already so i will just look up the literature for some reference. $\endgroup$ – Domdom Feb 8 at 12:14
  • $\begingroup$ adding a convex constraint is equivalent to intersecting the previously feasible set with a convex set. If the previously feasible set is convex, this means the new constraint set is convex, since the intersection of convex sets remains convex. (See early in Boyd's book for a reference to this, for example. I'm sure it exists in the first couple chapters.) $\endgroup$ – cdipaolo Feb 9 at 1:04
  • $\begingroup$ If you're curious to learn more about transformations that preserve convexity, this paper is a good reference: web.stanford.edu/~boyd/papers/pdf/cvxpy_rewriting.pdf $\endgroup$ – Akshay Agrawal Apr 24 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.