Convex.jl: Trouble with partially specified function inside another problem?

I’m trying to use a partially defined function as in DCP documentation. I have a minimization problem including convex function that isn’t a disciplined convex function. It’s fenchel conjugate is, however, so I was hoping to represent the original function as its biconjugate, so that I could use Convex.jl.

To test drive this, I wrote a little script for finding the conjugate and biconjugate of 1/2 x^2. This is a neat function that equals its conjugate, so its a good test. I thought would work, but doesn’t.

function conjugate(z)
     x = Variable()
     y = 1/2*x^2
     problem = maximize(z*x-y)
     solve!(problem, SCSSolver(verbose=false))
     return problem.optval
end

function biconjugate(x)
     z = Variable()
     problem = maximize(x*z-conjugate(z))
     solve!(problem, SCSSolver(verbose=false))
     return problem.optval
end

conjugate(z) behaves correctly, approximately returning 1/2 z^2
biconjugate(x) gives

ERROR: multiplication of two non-constant expressions is not DCP compliant

It gives the same error even if the biconjugate problem is written

     problem = maximize(Constant(x)*z-conjugate(z))

What’s going on here? I could understand if Convex.jl didn’t recognize conjugate(z) as convex, but the multiplication error indicates a problem with Constant(x)*z.

(Using Julia v0.6)

I think it should be fix!(x) to make x::Variable constant. I’m not sure what Constant(::Variable) does; in the latest version of Convex it is not defined, at least, and you will get a method error. Beware bugs with fix! in old versions of Convex.jl though: I fixed some in https://github.com/JuliaOpt/Convex.jl/pull/294 and https://github.com/JuliaOpt/Convex.jl/pull/299, but those are only in the latest version, 12.2, which requires Julia 1.0.

edit: I just noticed this post was from July 2018? But it also says created 28m ago. So I’m not really sure what’s going on but sorry if I brought back up an old post!

Haha I guess I went back in time, then.

I think I was a bit unclear with my variables. I used x and z in both functions, knowing that they were safely in separate scopes, for mathematical clarity, not programmatic clarity. z is in the dual space of x in both cases. However,

x = Variable()

occurs in the function definition of conjugate(z), and

problem = maximize(Constant(x)*z-conjugate(z))

occurs in the function definition of biconjugate(x). I can rewrite biconjugate(x) as:

function biconjugate(w)
     v = Variable()
     problem = maximize(w*v-conjugate(v))
     solve!(problem, SCSSolver(verbose=false))
     return problem.optval
end

or even more clearly,

function biconjugate(w)
     v = Variable()
     u = Constant(w)
     problem = maximize(u*v-conjugate(v))
     solve!(problem, SCSSolver(verbose=false))
     return problem.optval
end

still gives the same error. Since the Convex.jl documentation does not describe partially defined functions, but the Matlab cvx documentation does, maybe they’re not implemented in the Julia package?

I’m trying to test it out on Julia 1.0.

Ah, I see, thanks for explaining. Yes, I don’t think they are implemented; however maybe someone else knows how. As far as I understand, they are used internally in some sense: correct me if I’m mistaken, but I think the definition of sum_largest here is essentially such a thing: https://github.com/JuliaOpt/Convex.jl/blob/c6155a11850b410f4e395c5ca4dff885ae7858e4/src/atoms/lp_cone/sumlargest.jl#L53-L60. But I don’t think it’s explicit. Actually, I was thinking it would be interesting to somewhat reimplement Convex (in particular to allow variables with more than 2 dimensions and use more type information internally), and I was thinking that defining the Problem type to be explicitly compositional in this way would be helpful to reimplement the atoms faster.

I’m not sure I know enough about the implementation of Convex.jl to see if that’s what’s going on there, but I’ll look a bit harder, later.

I also realized that the MATLAB cvx example of a partially specified function uses an infimal projection (i.e. min f(u,w), which is always convex as long as f(u,w) is jointly convex). They note that it is jointly convex in both variables, u and w. They don’t note that in this case, cvx treats the partial minimum of a convex function as convex, despite failing the DCP analyzer. Convex conjugate, (i.e. sup(<x,z>-f(x)), also fails the DCP analyzer, but is likewise always convex.

I guess, good next steps:

  1. Test out the MATLAB cvx example on Convex.jl with Julia 1.0
  2. If it fails, add it as an issue to the GitHub (feature request or bug)
  3. Do a bit of reading to see if its possible to implement convex conjugate of convex function as an atom in a DCP.
  4. If it is possible, it would allow Convex.jl to implement all convex piecewise-linear-quadratic functions. Probably worth a feature request in that case.

For completeness, the function that I wanted to represent in CVX was a quadratic penalty on x for laying outside of some box defined by the origin and vector b:

f(x) = 1/2 * norm(x.-min.(max.(x, zeros(length(x))), b))^2

It’s definitely convex, but it doesn’t follow the DCP composition rules as explicitly written (If someone can think of a way to write it, explicitly, according to DCP composition, that would be awesome, but I’m not sure its possible). However, it’s fenchel conjugate is

f*(z) = 1/2 norm(z)^2 + max(0, dot(b,z))

which is the sum of convex functions and thus DCP compliant. I can define

f**(x) = f(x) = maximize(dot(x,z)-f(z))

which I hope to include the actual problem I’m trying to solve.

Thanks for the information-- I’ve made an issue on Convex.jl for partially specified functions, with some preliminary thoughts about implementation: https://github.com/JuliaOpt/Convex.jl/issues/310.