Applications of Convex.jl in Optimization Involving Complex Numbers¶

Ayush Pandey | JuliaCon 2017¶

https://github.com/Ayush-iitkgp/JuliaCon2017Presentation

About Me¶

  • BS and MS in Mathematics and Computing Sciences (July'12-June'17) at Indian Institute of Technology Kharagpur

  • Google Summer of Code 2016 and 2017 student under the Julia Language

  • GitHub: Ayush-iitkgp

  • Website: https://ayush-iitkgp.github.io

Outline¶

  • Power Flow Optimization
  • Fidelity in Quantum Information

Optimal Power Flow - Introduction¶

  • Power flow study is an analysis of a connected electrical power system’s capability to adequately supply the connected load.

An example of a power network

  • Unknowns: - Voltages angle and magnitude information for each bus
  • Knowns: - Load( such as appliances and lights.) and generator real power and voltage condition.

Optimal Power Flow - Mathematical Formulation¶

Constraints¶

Each transmission line has four flows

  • $p_{ij}$: Active power entering the line from node i
  • $q_{ij}$: Reactive power entering the line from node i
  • Let $x_{i}$ denote the complex voltage for node i of the network.

We have the following power balance equations which are non-linear in unknown $x_{i}$ and $x_{j}$.

Power balance equations

Objective¶

Depends upon the business needs such as:

  • Minimize power losses in an electrical network
  • Minimize cost of generation

Optimal Power Flow - SDP Relaxation¶

  • The original optimal power flow problem is non-convex in nature.
  • Thanks to the lifting technique which converts the above optimization problem to a SemiDefinite Programming Problem.
  • The relaxed SDP problem finds the near global solution of the original non-convex problem.

Example¶

  • The data is taken from the IEEE 14 Bus test case which represents a portion of the American Electric Power System (in the Midwestern US) as of February, 1962.
In [1]:
using Convex  # Read the input data
using FactCheck
using MAT   #Pkg.add("MAT")
TOL = 1e-2;
input = matopen("Data.mat")
varnames = names(input)
Data = read(input, "inj","Y");
n=size(Data[2],1); # Create some intermediate variables
Y=Data[2];
inj=Data[1];
In [2]:
W = ComplexVariable(n,n); # W is the matrix of pairwise products of the voltages

objective = real(sum(diag(W))); # The objective is to minimize cost of generation
In [3]:
c1 = Constraint[]; # The constraints are power balance equations
for i=2:n
    push!(c1,sum(W[i,:].*(Y[i,:]'))==inj[i]);
end
c2 = W in :SDP;
c3 = real(W[1,1])==1.06^2;
push!(c1, c2);
push!(c1, c3);
In [4]:
p = maximize(objective,c1); # Create the problem
solve!(p); # Solve the problem
p.optval #15.125857662600703
evaluate(objective) #15.1258578588357
----------------------------------------------------------------------------
	SCS v1.2.6 - Splitting Conic Solver
	(c) Brendan O'Donoghue, Stanford University, 2012-2016
----------------------------------------------------------------------------
Lin-sys: sparse-direct, nnz in A = 1344
eps = 1.00e-04, alpha = 1.80, max_iters = 20000, normalize = 1, scale = 5.00
Variables n = 393, constraints m = 812
Cones:	primal zero / dual free vars: 406
	sd vars: 406, sd blks: 1
Setup time: 7.29e-02s
----------------------------------------------------------------------------
 Iter | pri res | dua res | rel gap | pri obj | dua obj | kap/tau | time (s)
----------------------------------------------------------------------------
     0|      inf       inf      -nan      -inf       inf       inf  1.20e-01 
   100| 3.92e-02  8.28e-02  6.88e-05 -1.43e+01 -1.43e+01  1.23e-16  2.08e-01 
   200| 7.31e-03  1.97e-02  1.66e-05 -1.48e+01 -1.48e+01  0.00e+00  2.75e-01 
   300| 2.71e-03  5.88e-03  5.13e-06 -1.50e+01 -1.50e+01  1.27e-16  3.21e-01 
   400| 8.98e-04  1.92e-03  1.68e-06 -1.51e+01 -1.51e+01  1.27e-16  3.67e-01 
   500| 2.88e-04  6.27e-04  5.46e-07 -1.51e+01 -1.51e+01  1.27e-16  4.14e-01 
   600| 9.25e-05  2.02e-04  1.75e-07 -1.51e+01 -1.51e+01  1.27e-16  4.60e-01 
   680| 3.73e-05  8.15e-05  7.03e-08 -1.51e+01 -1.51e+01  1.27e-16  4.96e-01 
----------------------------------------------------------------------------
Status: Solved
Timing: Solve time: 4.96e-01s
	Lin-sys: nnz in L factor: 2906, avg solve time: 1.97e-05s
	Cones: avg projection time: 6.98e-04s
----------------------------------------------------------------------------
Error metrics:
dist(s, K) = 2.1500e-09, dist(y, K*) = 2.0328e-09, s'y/|s||y| = 3.5844e-13
|Ax + s - b|_2 / (1 + |b|_2) = 3.7310e-05
|A'y + c|_2 / (1 + |c|_2) = 8.1457e-05
|c'x + b'y| / (1 + |c'x| + |b'y|) = 7.0266e-08
----------------------------------------------------------------------------
c'x = -15.1259, -b'y = -15.1259
============================================================================
In [5]:
output = matopen("Res.mat"); # Verify the results
names(output);
outputData = read(output, "Wres");
Wres = outputData;
real_diff = real(W.value) - real(Wres);
imag_diff = imag(W.value) - imag(Wres);
@fact real_diff => roughly(zeros(n,n), TOL);
@fact imag_diff => roughly(zeros(n,n), TOL)
WARNING: The `=>` syntax is deprecated, use `-->` instead
Out[5]:
Success :: (line:441) :: fact was true
  Expression: imag_diff --> roughly(zeros(n,n),TOL)
    Expected: [0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0]
    Occurred: [7.21891e-9 1.09908e-5 2.03142e-5 2.4322e-5 2.20655e-5 4.88765e-5 4.56099e-5 4.65576e-5 5.22527e-5 5.33708e-5 5.16477e-5 5.00836e-5 5.00343e-5 5.11381e-5; -1.09704e-5 -2.9351e-8 8.63911e-6 1.36025e-5 1.14299e-5 3.7428e-5 3.48544e-5 3.57447e-5 4.15345e-5 4.28357e-5 4.07829e-5 3.88891e-5 3.89983e-5 4.04856e-5; -2.03103e-5 -8.60839e-6 -7.09979e-8 6.05066e-6 3.72136e-6 2.97453e-5 2.77659e-5 2.8529e-5 3.47725e-5 3.63289e-5 3.3859e-5 3.15844e-5 3.18855e-5 3.38928e-5; -2.43209e-5 -1.35708e-5 -6.00392e-6 -3.13606e-7 -1.88926e-6 2.24612e-5 2.07537e-5 2.16031e-5 2.73258e-5 2.88318e-5 2.64326e-5 2.41747e-5 2.44664e-5 2.63617e-5; -2.20443e-5 -1.14021e-5 -3.72034e-6 2.07534e-6 -1.84344e-7 2.45569e-5 2.2733e-5 2.35753e-5 2.92654e-5 3.07001e-5 2.83942e-5 2.62314e-5 2.64812e-5 2.82721e-5; -4.88785e-5 -3.74309e-5 -2.97522e-5 -2.24708e-5 -2.44784e-5 -3.87313e-7 -9.82969e-7 -3.40895e-7 6.05173e-6 7.85915e-6 4.97049e-6 2.29021e-6 2.84209e-6 5.35518e-6; -4.56128e-5 -3.48578e-5 -2.77738e-5 -2.0657e-5 -2.2739e-5 9.68386e-7 -4.80534e-7 8.06184e-7 6.77224e-6 8.3796e-6 5.60517e-6 3.03697e-6 3.50253e-6 5.87174e-6; -4.65526e-5 -3.57413e-5 -2.85295e-5 -2.16068e-5 -2.35738e-5 3.33978e-7 -6.39029e-7 -1.27845e-7 6.01353e-6 7.704e-6 4.94367e-6 2.40328e-6 2.85565e-6 5.2099e-6; -5.22657e-5 -4.1548e-5 -3.47903e-5 -2.72942e-5 -2.92814e-5 -6.07701e-6 -6.44929e-6 -6.03233e-6 -7.73445e-7 1.95546e-6 -1.16352e-6 -3.87795e-6 -3.33431e-6 -7.19737e-7; -5.33756e-5 -4.28413e-5 -3.63384e-5 -2.88447e-5 -3.07081e-5 -7.87585e-6 -8.39717e-6 -7.71444e-6 -1.56187e-6 -4.75029e-7 -2.84532e-6 -5.68387e-6 -5.12984e-6 -2.56324e-6; -5.16454e-5 -4.07821e-5 -3.38616e-5 -2.64385e-5 -2.83949e-5 -4.84957e-6 -5.61542e-6 -4.94684e-6 1.14314e-6 3.00238e-6 -2.2845e-7 -2.71874e-6 -2.17579e-6 3.97771e-7; -5.00789e-5 -3.88847e-5 -3.15841e-5 -2.41781e-5 -2.62298e-5 -2.20113e-6 -3.04454e-6 -2.40263e-6 3.86015e-6 5.6745e-6 2.71626e-6 -1.22655e-7 5.7586e-7 3.1552e-6; -5.00336e-5 -3.89984e-5 -3.18895e-5 -2.44736e-5 -2.64833e-5 -2.66205e-6 -3.51414e-6 -2.85949e-6 3.31239e-6 5.11613e-6 2.16904e-6 -5.15582e-7 -2.69548e-7 2.61995e-6; -5.11346e-5 -4.04833e-5 -3.38943e-5 -2.6366e-5 -2.82716e-5 -5.36328e-6 -5.88052e-6 -5.21155e-6 8.19018e-7 2.5525e-6 -4.01939e-7 -3.15624e-6 -2.53924e-6 -1.62076e-7]

Fidelity in Quantum Information Theory - Introduction¶

  • This example is inspired from a lecture of John Watrous in the course on Theory of Quantum Information.

  • Fidelity is a measure of the closeness of two quantum states.

  • The ability to distinguish between the quantum states is equivalent to the ability to distinguish between the classical probability distributions.

  • If fidelity between two states is 1, they are the same quantum state.

  • Application

Quantum Cryptography

  • The Fidelity between two Hermitian semidefinite matrices P and Q is defined as:
$$F(P,Q) = {||{P}^{1/2}{Q}^{1/2} ||}_{tr} = \max\; |trace({P}^{1/2}U{Q}^{1/2})|$$

where the trace norm $||.||_{tr}$ is the sum of the singular values, and the maximization goes over the set of all unitary matrices U.

Fidelity in Quantum Information Theory - Mathematical Formulation¶

Fidelity can be expressed as the optimal value of the following complex-valued SDP:

$$ \textbf{maximize} \frac{1}{2} trace(Z+Z^*)$$$$\text{subject to } \left[\begin{array}{cc}P&Z\\{Z}^{*}&Q\end{array}\right] \succeq 0$$$$\text{where } Z \in \mathbf {C}^{n \times n}$$

Example¶

In [7]:
n = 20 # Create the data
P = randn(n,n) + im*randn(n,n);
P = P*P';
Q = randn(n,n) + im*randn(n,n);
Q = Q*Q';
In [8]:
Z = ComplexVariable(n,n); # Declare convex variable

objective = 0.5*real(trace(Z+Z'));  # Specify the objective
In [9]:
constraint = [P Z;Z' Q]  0;
problem = maximize(objective,constraint);
 
solve!(problem) # Solve the problem
----------------------------------------------------------------------------
	SCS v1.2.6 - Splitting Conic Solver
	(c) Brendan O'Donoghue, Stanford University, 2012-2016
----------------------------------------------------------------------------
Lin-sys: sparse-direct, nnz in A = 1621
eps = 1.00e-04, alpha = 1.80, max_iters = 20000, normalize = 1, scale = 5.00
Variables n = 801, constraints m = 6401
Cones:	primal zero / dual free vars: 3161
	sd vars: 3240, sd blks: 1
Setup time: 9.62e-04s
----------------------------------------------------------------------------
 Iter | pri res | dua res | rel gap | pri obj | dua obj | kap/tau | time (s)
----------------------------------------------------------------------------
     0|      inf       inf      -nan      -inf      -inf       inf  3.30e-02 
   100| 9.40e-04  2.11e-01  1.71e-02 -6.10e+02 -5.90e+02  0.00e+00  1.89e-01 
   200| 2.15e-04  4.93e-02  3.08e-03 -6.18e+02 -6.14e+02  0.00e+00  3.62e-01 
   300| 7.74e-05  1.72e-02  7.98e-04 -6.18e+02 -6.17e+02  0.00e+00  5.49e-01 
   400| 3.23e-05  7.04e-03  2.58e-04 -6.18e+02 -6.18e+02  0.00e+00  7.24e-01 
   500| 1.40e-05  3.12e-03  9.69e-05 -6.18e+02 -6.18e+02  0.00e+00  8.96e-01 
   600| 6.35e-06  1.44e-03  3.98e-05 -6.18e+02 -6.18e+02  0.00e+00  1.07e+00 
   700| 2.97e-06  6.86e-04  1.72e-05 -6.18e+02 -6.18e+02  0.00e+00  1.24e+00 
   800| 1.43e-06  3.31e-04  7.72e-06 -6.18e+02 -6.18e+02  0.00e+00  1.41e+00 
   900| 6.95e-07  1.62e-04  3.54e-06 -6.18e+02 -6.18e+02  0.00e+00  1.58e+00 
   980| 3.94e-07  9.16e-05  1.92e-06 -6.18e+02 -6.18e+02  0.00e+00  1.72e+00 
----------------------------------------------------------------------------
Status: Solved
Timing: Solve time: 1.72e+00s
	Lin-sys: nnz in L factor: 8823, avg solve time: 5.46e-05s
	Cones: avg projection time: 1.63e-03s
----------------------------------------------------------------------------
Error metrics:
dist(s, K) = 3.8219e-09, dist(y, K*) = 1.0983e-09, s'y/|s||y| = -7.2118e-12
|Ax + s - b|_2 / (1 + |b|_2) = 3.9389e-07
|A'y + c|_2 / (1 + |c|_2) = 9.1596e-05
|c'x + b'y| / (1 + |c'x| + |b'y|) = 1.9185e-06
----------------------------------------------------------------------------
c'x = -618.1931, -b'y = -618.1908
============================================================================
In [10]:
# Verify that computer fidelity is equal to actual fidelity
computed_fidelity = evaluate(objective)
P1,P2 = eig(P);
sqP = P2 * diagm([p1^0.5 for p1 in P1]) * P2'
Q1,Q2 = eig(Q)
sqQ = Q2 * diagm([q1^0.5 for q1 in Q1]) * Q2'
actual_fidelity = sum(svd(sqP * sqQ)[2])
diff = computed_fidelity - actual_fidelity
@fact diff => roughly(0, TOL)
Out[10]:
Success :: (line:441) :: fact was true
  Expression: diff --> roughly(0,TOL)
    Expected: 0
    Occurred: -2.0267065679036023e-5

Thank You!¶