convolution of variable

[adityam]

Hi,

I am trying to optimize the difference between two entropy expressions (which, we can prove is convex). The code is as follows:

using Distributions
using Convex

mx = 2
ms = 2

px  = Binomial(mx, 0.5)
pxd = pdf(px) 

function objective(ps)
    pw = conv(ps,pxd)
    return Convex.entropy(pw) - Convex.entropy(ps)
end

theta = Variable(ms + 1)

problem = minimize(objective(theta))
problem.constraints += theta >= 0
problem.constraints += sum(theta) <= 1.0

solve!(problem)
println(problem.optval)
println(theta.value)

When I run it, I get the error:

ERROR: LoadError: MethodError: `conv` has no method matching conv(::Convex.Variable, ::Array{Float64,1})
Closest candidates are:
  conv{T<:Union{Complex{Float32},Complex{Float64},Float32,Float64}}(::Union{DenseArray{T<:Union{Complex{Float32},Complex{Float64},Float32,Float64},1},SubArray{T<:Union{Complex{Float32},Complex{Float64},Float32,Float64},1,A<:DenseArray{T,N},I<:Tuple{Vararg{Union{Colon,Int64,Range{Int64}}}},LD}}, ::Union{DenseArray{T<:Union{Complex{Float32},Complex{Float64},Float32,Float64},1},SubArray{T<:Union{Complex{Float32},Complex{Float64},Float32,Float64},1,A<:DenseArray{T,N},I<:Tuple{Vararg{Union{Colon,Int64,Range{Int64}}}},LD}})
  conv{T<:Integer,S<:Union{Complex{Float32},Complex{Float64},Float32,Float64}}(::Union{DenseArray{T<:Integer,1},SubArray{T<:Integer,1,A<:DenseArray{T,N},I<:Tuple{Vararg{Union{Colon,Int64,Range{Int64}}}},LD}}, ::Union{DenseArray{S<:Union{Complex{Float32},Complex{Float64},Float32,Float64},1},SubArray{S<:Union{Complex{Float32},Complex{Float64},Float32,Float64},1,A<:DenseArray{T,N},I<:Tuple{Vararg{Union{Colon,Int64,Range{Int64}}}},LD}})
 in objective at /home/adityam/Dropbox/privacy/code/iid.jl:13
while loading /home/adityam/Dropbox/privacy/code/iid.jl, in expression starting on line 19

Any ideas on how to circumvent that?

[Ayush-iitkgp]

@adityam can you try conv(pxd,ps)? I think conv expects first argument to be a value and the second one to be a variable.

[adityam]

Thanks. That works! (in that I don't get an error). But now I get

WARNING: Expression not DCP compliant. Trying to solve non-DCP compliant problems can lead to unexpected behavior.
WARNING: Problem not DCP compliant: objective is not DCP

and then

WARNING: Problem status Unbounded; solution may be inaccurate.
1.0
[5.969074075048959e-7
 -1.8826116855053157e-7
 5.969074075030421e-7]

which violates the constraint.

So, I guess that I cannot use Convex.jl to solve this problem :-(

[Ayush-iitkgp]

@adityam Convex.jl uses DCP rules to determine the convexity and if the expressions are not DCP compliant, it is not advisable to use Convex.jl for convex optimization. DCP compliance implies convexity but the converse is not true. For example sqrt(square(x)) is convex but non-DCP.

[madeleineudell]

@adityam, thanks for posting this issue. There are two problems you're having:

1) conv is not defined when the second argument is a variable (and the first is constant). That's a bug and should (and will) be fixed. 2) the difference of two entropy is not DCP compliant: entropy is concave, -entropy is convex, and so the vexity of their sum cannot be determined from the parts. However! If you know the expression is convex, you may be able to reexpress that function in a different way that is DCP compliant. For example, can you express it as a single entropy, or as a KL divergence?

[adityam]

@Ayush-iitkgp @madeleineudell , Thanks!

The expression can be expressed as mutual information (and hence KL divergence) expression. I'll try that and see if it works (convexity is not obvious from the mutual information expression either; our proof uses Cauchy-Schwartz inequality at some stage). I'll also read up on DCP rules and see if I can figure out a way to express way that satisfies those rules.