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$

1 Answer 1

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$
5
  • $\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
    Commented Mar 27, 2021 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$ Commented Mar 27, 2021 at 13:47
  • $\begingroup$ ...and with bounds I mean tight graph bounds, not approximations (updated answer) $\endgroup$ Commented Mar 27, 2021 at 13:52
  • $\begingroup$ @JohanLöfberg between a hyperbolic constraint of the OP Richard (transformation into an SOCP constraint) and a geometric constraint $w{x^{ - 1}}{y^{ - 1}} \le 1$, which one is better in term of complexity for a convex optimization problem ? $\endgroup$ Commented May 23, 2023 at 23:06
  • 1
    $\begingroup$ Depends. SOCP solvers are much more developed than dedicated GP solvers, but good general purpose nonlinear solvers would probably solve the GP formulation very efficiently too. Also, to be able to use a GP formulation, everything else has to be GP-representable too (and to use an SOCP solver, everything else has to be SOCP-representable) $\endgroup$ Commented May 24, 2023 at 5:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.