By: Julia Developers
Re-posted from: http://feedproxy.google.com/~r/JuliaLang/~3/MY_pv6X_SOQ/announcing-support-for-complex-domain-linear-programs-in-Convex.jl
I am pleased to announce the support for complex-domain linear programs (LPs) in Convex.jl. As one of the Google Summer of Code students under The Julia Language, I had proposed to implement the support for complex semidefinite programming. In the first phase of project, I started by tackling the problem of complex-domain LPs where in first subphase, I had announced the support for complex coefficients during JuliaCon’16 and now I take this opportunity to announce the support for complex variables in LPs.
Complex-domain LPs consist of a real linear objective function, real linear inequality constraints, and real and complex linear equality constraints.
In order to enable complex-domain LPs, we came up with these ideas:
- We redefined the conic_form! of every affine atom to accept complex arguments.
- Every complex variable z was internally represented as
z = z1 + i*z2
, where z1 and z2 are real. - We introduced two new affine atoms real and imag which return the real and the imaginary parts of the complex variable respectively.
- transpose and ctranspose perform differently on complex variables so a new atom CTransposeAtom was created.
- A complex-equality constraint RHS = LHS can be decomposed into two corresponding real equalities constraint real(RHS) = real(LHS) and imag(RHS) = imag(LHS)
After above changes were made to the codebase, we wrote two use cases to demonstrate the usability and the correctness of our idea which I am presenting below:
# Importing Packages
Pkg.clone("https://github.com/Ayush-iitkgp/Convex.jl/tree/gsoc2")
using Convex
# Complex LP with real variable
n = 10 # variable dimension (parameter)
m = 5 # number of constraints (parameter)
xo = rand(n)
A = randn(m,n) + im*randn(m,n)
b = A * xo
# Declare a real variable
x = Variable(n)
p1 = minimize(sum(x), A*x == b, x>=0)
# Notice A*x==b is complex equality constraint
solve!(p1)
x1 = x.value
# Let's now solve by decomposing complex equality constraint into the corresponding real and imaginary part.
p2 = minimize(sum(x), real(A)*x == real(b), imag(A)*x==imag(b), x>=0)
solve!(p2)
x2 = x.value
x1==x2 # should return true
# Let's now consider an example using a complex variable
# Complex LP with complex variable
n = 10 # variable dimension (parameter)
m = 5 # number of constraints (parameter)
xo = rand(n)+im*rand(n)
A = randn(m,n) + im*randn(m,n)
b = A * xo
# Declare a complex variable
x = ComplexVariable(n)
p1 = minimize(real(sum(x)), A*x == b, real(x)>=0, imag(x)>=0)
solve!(p1)
x1 = x.value
xr = Variable(n)
xi = Variable(n)
p2 = minimize(sum(xr), real(A)*xr-imag(A)*xi == real(b), imag(A)*xr+real(A)*xi == imag(b), xr>=0, xi>=0)
solve!(p2)
x1== xr.value + im*xi.value # should return true
List of all the affine atoms are as follows:
- addition, substraction, multiplication, division
- indexing and slicing
- k-th diagonal of a matrix
- construct diagonal matrix
- transpose and ctranspose
- stacking
- sum
- trace
- conv
- real and imag
Now, I am working towards implementing complex-domain second order conic programming. Meanwhile, I invite the Julia community to play around with the complex-domain LPs. The link to the development branch is here.
Looking forward to your suggestions!
Special thanks to my mentors Madeleine Udell and Dvijotham Krishnamurthy!