2
$\begingroup$

I have a problem which simplifies to: $$ \begin{align} \max w &\\ w&\le xy \\ x,y&\le10 \\ x,y&\ge0 \end{align} $$ Recognizing that $xy$ form a hyperbolic constraint, I can solve by introducing a second-order cone: $$ \begin{align} \max w & \\ \left\lVert\begin{bmatrix} 2w \\ x - y \end{bmatrix}\right\rVert &\le x+y \\ x,y&\le10 \\ x,y&\ge0 \end{align} $$ And all is well with the world, except that $w=\sqrt{xy}$. What I would like in reality is $w=xy$.

Is there an SOCP way of achieving this?

$\endgroup$
3
$\begingroup$

No, the product is indefinite so it can neither be bounded from above using an tight convex epigraph representation, nor from below using a convex hypograph representation.

If you cannot accept a general nonlinear form (and thus a general nonlinear solver), you might use a geometric programming form (and thus solve as a convex problem) if all your other constraints satisfy the requirements for a posynomial representation. In GP language, you are minimizing the posynomial $w^{-1}$ under the posynomial constraint $wx^{-1}y^{-1}\leq 1$.

$\endgroup$
3
  • $\begingroup$ It's unclear to me what you mean by your first paragraph. The current SOC is a lower bound, albeit a loose one, and isn't the point of Mccormick envelopes to provide lower and upper bounds? $\endgroup$
    – Richard
    Mar 27 at 13:38
  • $\begingroup$ Why are you talking about linear Mccormick outer approximations now?The question was if it is possible to represent $w\leq xy$ using convex programming, i.e. writing a hypograph representation of $xy$, and the answer is no since the function $xy$ is not concave. An epigraph $w \geq xy$ is not possible either since $xy$ is not convex either. $\endgroup$ Mar 27 at 13:47
  • $\begingroup$ ...and with bounds I mean tight graph bounds, not approximations (updated answer) $\endgroup$ Mar 27 at 13:52

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.