13
$\begingroup$

The theory surrounding Linear Programming is based on variables, bounds and coefficients that take on values in $\mathbb R$, the set of real numbers.

I have long wondered whether there might be serious application possibilities by applying LP theory within the realm of $\mathbb C$, the set of complex numbers, but I have not come across much in the way of useful application myself.

Have others come across any good OR applications of complex valued variables/bounds/coefficients within a LP or MILP modelling framework?

$\endgroup$
  • 2
    $\begingroup$ For a complex-valued objective function, how do you want to define $\min$ or $\max$? $\endgroup$ – Marcus Ritt Jun 18 '19 at 0:46
  • 1
    $\begingroup$ The most likely possibility I suspect, is that from an objective point of view we would only be interested in minimizing or maximizing the real component of some complex-linear function. But there might be other possibilities involving a metric on the size of the objective function, such as a (potentially weighted) sum of the real and imaginary components, or the maximum of the real and imaginary components. $\endgroup$ – Mark H Jun 18 '19 at 1:04
  • 1
    $\begingroup$ Note that the same applies to inequalities: you need to define "$\leq$" means. If you want to have an objective or constraint on real or imaginary parts, then since everything is linear the simplest way is to separate real from imaginary parts, and formulate all as a real-valued LP. The same would work for weighted sums of real and imaginary parts. However, if want to minimize or compare absolute values, the problem gets quadratic. $\endgroup$ – Marcus Ritt Jun 18 '19 at 1:18
  • $\begingroup$ I agree that it is likely that some applications would involve simply separating real from imaginary and formulating as a real-valued LP. I wonder though whether there is more depth to be had. Taking the maximum of the real and imaginary parts can be a useful measurement of size. This can be minimized in an LP objective and can also be compared. $\endgroup$ – Mark H Jun 18 '19 at 1:31
  • $\begingroup$ It's very funny -- I was literally about to post almost the same question, today. Great minds. :) (I was going to give AC OPF as an example and ask whether there are other examples out there, and how they are modeled.) $\endgroup$ – LarrySnyder610 Jun 18 '19 at 2:15
11
$\begingroup$

Complex numbers are commonly used in power systems optimization problems, in particular, AC optimal power flow (OPF) problems. We have constraints of the form $$p_{ij} + iq_{ij} = f(v_i,v_j),$$ where $p_{ij}$ and $q_{ij}$ are real-valued decision variables, $i=\sqrt{-1}$, $v_i$ and $v_j$ are complex-valued decision variables, and $f(\cdot)$ is a complex-valued function. Writing each $v_i$ as $$v_i = |v_i|(\cos \theta_i + i\sin \theta_i),$$ where $|v_i|,\theta_i\in \mathbb{R}$, and doing a lot of simplifying, we get a constraint of the form $$p_{ij} + iq_{ij} = f_1(|v_i|,|v_j|,\theta_i,\theta_j) + if_2(|v_i|,|v_j|,\theta_i,\theta_j),$$ where $f_1(\cdot)$ and $f_2(\cdot)$ are real-valued functions.

The typical approach is then to decompose the complex constraints into two real-valued constraints: $$\begin{align} p_{ij} & = f_1(|v_i|,|v_j|,\theta_i,\theta_j) \\ q_{ij} & = f_2(|v_i|,|v_j|,\theta_i,\theta_j). \end{align}$$ The functions $f_1$ and $f_2$ are nonconvex, so a lot of the research in OPF problems is on convexifying or approximating these constraints.

But the main point here is just that each complex constraint gets rewritten as a pair of constraints that have only real-valued parameters and decision variables. I'm curious as to whether the same approach is used in other optimization problems that involve complex numbers.

Also, the objective function is real-valued, although it can be a function of complex decision variables.

| improve this answer | |
$\endgroup$
  • $\begingroup$ "convexifying" (+1) $\endgroup$ – SecretAgentMan Jun 18 '19 at 4:00
7
$\begingroup$

Not quite Linear Programming, but if you are willing to generalize to Convex Programming, I have stumbled over some modeling systems (for disciplined convex programming) that support optimization with complex variables and expressions, e.g.,:

  • CVXPY: Complex-valued expressions
  • Convex.jl: Optimization with Complex Variables.
| improve this answer | |
$\endgroup$
  • $\begingroup$ About implementation details, Complex.jl has this to say: > Internally, Convex.jl transforms the complex-domain problem to a larger > real-domain problem using a bijective mapping. It then solves the real-domain > problem and transforms the solution back to the complex domain. $\endgroup$ – Robert Schwarz Jun 19 '19 at 8:37

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.