Not sure about the second legend (I guess in matplotlib this operates directly with legend objects?), but you could simply add two invisible lines to the plot to have the legend entries:
plot(rand(10), color=1, label = "random")
plot!(rand(10), color=2, label = "optimized")
plot!(rand(10), color=1, linestyle=:dot, label = "")
plot!(rand(10), color=2, linestyle=:dot, label = "")
plot!([1], [0], label = "validation", color = "black")
plot!([1], [0], linestyle = :dot, label = "cost", color = "black")