Constrainted optimization for general (blackbox) convex objective function

[Mike_Wong]

Hello,

This is Mike. I'm rather new to Yalmip and still learning the art of SDP, and recently I ran into the following problem in research:

We'd like to optimize a function f(X) where X is a symmetric matrix, and X is subject to linear constraints of <Ci,X>=ci.

Now, if f(X) is also linear, i.e. <A,X>, then this becomes a standard SDP problem. However, I wonder what would happen if f(X) is a general non-linear (but convex) function - which can be e.g. just a function handle in MATLAB - that cannot be described by analytical operators in Yalmip, and can only be numerically evaluated? 

(We're actually currently using some linear approximation of f and taking the approach of multiple iterations, but this is rather slow.) I'm wondering if there's a solver that can directly solve this problem without the linear approximation, i.e. similar to MATLAB's fmincon which takes in a general function handle? I guess this would be categorized as nonlinear convex optimization, although looks like fmincon doesn't take in matrices as variable & constraints, and from https://yalmip.github.io/command/sdpfun/ , it seems one can simply say f_sdp=sdpfun(X,f) to include numerical function in Yalmip, but e.g. Mosek doesn't support this, and the webpage says it only works for BMIBNB and it's not that fast for larger problem (as this is a general global solver - while here f is actually a convex function for local searching so the extra information is not used). 

I wonder if there might be any kind suggestions on whether there's any solver that can help with this? Thanks!

Mike

[Mike_Wong]

(P.S. Sorry I forgot to add - but X also satisfies X>=0 in addition to symmetric, i.e. semidefinite-programming).

[Johan Löfberg]

I don't know of any SDP solver which supports black-box objectives (and thus no such support in YALMIP)

Is it really black-box, or simply a function with standard operations?

Your best best is probably to implement your current iterative scheme using an efficient optimizer parameterizing the linear objective a'*x in a

[Mark L. Stone]

Can you provide more information on the blackbox? Is is actually a deterministic simulation (such as numerically solving differential equations), or stochastic (Monte Carlo) simulation, in which the number of replications can be controlled? Is it actually a graybox for which you have access to source code and which might allow automatic differentiation to be applied to it?

I have an experimental solver which might be able to handle that, and am interested in getting test problems for it. It is better if derivatives can be obtained, but if not, my solver can employ numerical differentiation..Hopefully your variables are continuous and the objective function is (mostly) smooth.Some error or noise in objective function evaluation might be o.k. Se habla SDP.

[Mike_Wong]

Dear Prof. Löfberg,

Many thanks for the reply!

I see. Yes, our (or actually previous students in our group's) current implementation is calculating the gradient of the function f which is now a constant, and optimizing <f',x> given the same constraints on x, and implementing an iterative (Frank-Wolfe) algorithm to approach the optimal x. (The problem is actually in a Quantum Information context so x is a Hermitian matrix and inner product is defined as trace. Our group's previous method was in https://arxiv.org/pdf/1710.05511.pdf ) and here I was actually thinking of whether there might be a more efficient way than linearizing f with its gradient and iteratively obtain results (since this solves SDP multiple times), to instead solve one single nonlinear optimization problem on f, but as you have kindly suggested, perhaps using a blackbox function would be even less efficient than just calculating a linear objective and iterate multiple times. 

Thanks again!

Mike

[Mike_Wong]

Dear Dr. Stone,

Many thanks for the reply!

Yes, the problem is actually in a Quantum Information context so x is a Hermitian matrix and inner product is defined as trace. The blackbox is actually source code known to us (but contains multiple operations which is difficult to define with only Yalmip/CVX operators, for instance a quantum relative entropy operation. I see that you have kindly mentioned in http://ask.cvxr.com/t/adding-quantum-relative-entropy-to-cvx/3424/2 that another solver CVXQUAD in cvx supports it internally - I think another student in our group was actually studying that solver). 

In fact, just as you and Prof. Löfberg have both kindly suggested, our group's current method is taking numerical gradient, and computing the linear function f'*x, and doing iterative searches with Frank-Wolfe algorithm (as in https://arxiv.org/pdf/1710.05511.pdf) although here I was actually thinking of whether there might be some way to solve one single nonlinear optimization problem on an unknown blackbox function f in Yalmip, but as Prof. Löfberg have suggested, perhaps using a blackbox function would be even less efficient than just calculating a linear objective and iterating multiple times. 

Also, may I ask if the solver you have kindly mentioned could be found somewhere on Github?

Thanks again!

Mike

Your reply has been posted

[Johan Löfberg]

if it is something you can represent using some combination of the exp-cone representable operators

https://yalmip.github.io/tags/#exponential-cone-programming-representable

acting on the eigenvalues of a symmetric matrix, you can use the undocumented operator eigv to obtain an epigraph-representation of the eigenvalues to be used in the exp-cone operations

[v,Epimodel] = eigv(X);
Model =[Epimodel, other constraints]
objective = entropy(v)...

eigv is not efficiently implemented, it was just a quick hack for a similar quantum problem, but it might do the trick

[Mark L. Stone]

CVXQUAD is not a solver. it is an add-on to CVX which formulates SDP (LMI) constraints to include in a CVX model, and employ a semidefinite representable apprcximation to the matrix logarithm in order to handle quantum entropy, quantum relative entropy, trace of matrix logarithm, and some other functions listed at https://github.com/hfawzi/cvxquad .

My answers at http://ask.cvxr.com/t/perspective-of-log-det-function-and-cvx-formulations-of-related-log-det-problems-using-quantum-relative-entropy-from-cvxquad/4033 contain formulation of log det related problems using CVXQUAD's quantum relative entropy function.  I had no applications in mind. I just extended scalar formulations to their matrix counterparts.

A "YALMIPQUAD" could be developed to implement similar capability in YALMIP as CVXQUAD does in CVX. The CVXQUAD developer has considered, but not yet completed, such an undertaking. I think that could be designed for YALMIP to even allow incorporation of SDP (LMI) constraints to model those functions, even in the context of an overall non-convex problem(that would be impossible to do in CVX).

Per table 1 of https://arxiv.org/pdf/1705.00812.pdf , the implementation by CVXQUAD of quantum relative entropy involves 2n^2 by 2n^2 SDPs, when the underlying problem has n variables (the other functions are no worse than 2n by 2n SDPs). So it doesn't scale well to even medium size problems. If someone could find a barrier function for the quantum relative entropy cone, a much better solution method could be developed, and probably implemented in a solver such as Mosek.

My solver is not available anywhere except on my PC, and is not user friendly right now, even for me. Unless it is lucky and the problem is very easy, it is going to formulate and solve a large number of SDPs (if there are SDP constraints) in the course of solving a single SDP-constrained blackbox optimization problem.

My solver can even handle nonlinear SDPs, although it is limited now by how good the nonlinear SDP solvers (e.g., PENLAB, or better yet, PENBMI and PENNON) are.  Id the SDPs are linear, and there are no non-Mosek-representable constraints, my solver can call Mosek or other linear SDP solver as subproblem solver (and do so via YALMIP). Whether linear or nonlinear SDP, my solver terminates based on the first order optimality criteria for whatever combination of SDP and non-SDP constraints there are, It can also evaluate 2nd order optimalitty criteria for non-SDP problems. And this is all true, even if the objective function is evaluated by stochastic (Monte Carlo) simulation, and therefore the objective function and gradient are noisy.

You can contact me per http://marklstone.com .

[Mark L. Stone]

BTW, whether for linear or nonlinear SDP, my solver formulates and solves a linear SDP to evaluate the first order optimality criteria at a candidate solution (similar to how you would formulate and solve a nonnegative linear least squares problem to evaluate KKT optimality score for non-SDP nonlinear optimization problems).

[Mark L. Stone]

Of course, if you can use Johan's method to allow formulation of the problem you really want to solve, without resorting to blackbox evaluation, you will be better off than using my blackbox solver. Or perhaps, Johan's method can be used to create an improved blackbox formulation, which could then be solved by my blackbox solver.

[Mark L. Stone]

Using http://www.matrixcalculus.org/matrixCalculus , it should be "easy" to find the gradient of quantum relative entropy relative to its arguments. Therefore, perhaps also the gradient of the actual objective function (call it a blackbox, a graybox, or a callback, as suits your fancy.). My solver can utilize this.