3
$\begingroup$

Is it even possible to model an optimization problem with mutual exclusivity of two variables, without introducing integer variables?

I am trying to formulate and solve an optimization problem in trading using CVXPY. The goal is to maximize returns by either buying (long) or selling (short) the asset at each time point, but not both simultaneously. Here's a summary of the problem:

  1. Objective Function: Minimize the negative returns from long and short positions: $$ \text{Minimize } -\sum_{t=1}^T (r_{L,t} \cdot L_t + r_{S,t} \cdot S_t) $$ where $ r_{L,t} $ and $ r_{S,t} $ are the expected returns for long and short positions at time $ t $.

I was thinking about something like this:

  1. Variables:

    • $ L_t $: amount bought (long) at time $ t $.
    • $ S_t $: amount sold (short) at time $ t $.
    • $ z_t $: auxiliary variable to enforce mutual exclusivity.
  2. Constraints:

    • At each time point $ t $, you can either buy or sell power up to a maximum amount $ \beta_t $:

      $ L_t \leq \beta_t \cdot (1 - z_t) $

      $ S_t \leq \beta_t \cdot z_t $

    • $ 0 \leq z_t \leq 1 $

I can see that $z=1/2$ is feasible, but then they aren't exclusive.. How can I work around this without introducing binary variables?

$\endgroup$

1 Answer 1

5
$\begingroup$

You want to enforce $L_t=0 \lor S_t=0$, where both variables are nonnegative. Here are three ways:

  1. The approach in your question, but with $z_t$ binary.
  2. Nonlinear “complementarity” constraint $L_t S_t = 0$.
  3. $\operatorname{SOS1}(L_t, S_t)$ constraint that allows at most one nonzero variable among its arguments.
$\endgroup$
3
  • $\begingroup$ Okay, so it is not possible to derive such constraint, but linear and continuous? My problem is that I have semidefinite constraints, and I can't seem to solve the program with binary variables AND sdp constraints in CVXPY... $\endgroup$
    – Lyft
    Commented Jun 28 at 13:10
  • 1
    $\begingroup$ Your desired constraint is nonconvex so cannot modeled as LP. To convince yourself of the nonconvexity, consider the (L-shaped) feasible region, which consists of two orthogonal rays from the origin. $\endgroup$
    – RobPratt
    Commented Jun 28 at 13:17
  • $\begingroup$ I see - thank you :) $\endgroup$
    – Lyft
    Commented Jun 28 at 13:20

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.