Vectorized gradient based optimizers

Is there any vectorized gradient based optimizer available ? Even outside matlab ?

Answer 1

[Matt J]

As long as you are willing to supply the gradient, you can vectorize the minimization of N objectives,

by applying fminunc to the consolidated objective,

or analogously with fmincon if each problem has constraints.

[Matt J]

mahmoud's answer relocated to comment:

Can you please elaborate more on how to do that? I have 11 variables that define my constraints and one of those variables is the one to be minimized using fmincon. Each of these variables can be a vector and i want to use fmincon on all elements of the vectors at the same time (vectorized)

Thank you for your help

[Matt J]

I have 11 variables that define my constraints and one of those variables is the one to be minimized using fmincon.

Your objective and constraints must be written as functions that take a single vector containing all of your unknowns as an input argument. That way, all functions have access to all variables, whether they need them all or not.

[Matt J]

mahmoud's answer relocated to comment:

In my objective and nonlincon functions i passed a matrix x where x contains a vector for each variable of my 11 variables but the runtime did not change.

Is that what you meant?

[Matt J]

Is that what you meant?

I think so. It's hard to be sure what' you're doing without seeing code or equations.

However, I wouldn't really expect a decrease in runtime unless you are supplying your own derivative calculations for the objective and constraints.

Incidentally, please use the Comment boxes (not the Answer boxes) for replies in connection with another answer.

[mahmoud tarek]

This is the objective and nonlincon code

function OBJ = Obj(X)
OBJ = X(:,11);
end

and my NonLinCon function is

function [C, CEQ] = NonLinCon(X, NCHV, PCHV, IN_SPEC)
DOF.M(1).L = X(:,1);
 DOF.M(2).L = X(:,2);
 DOF.M(3).L = X(:,3);
 DOF.M(4).L = X(:,4);
 DOF.M(5).L = X(:,5);
 DOF.M(1).RHO = X(:,6);
 DOF.M(2).RHO = X(:,7);
 DOF.M(3).RHO = X(:,8);
 DOF.M(4).RHO = X(:,9);
 DOF.M(5).RHO = X(:,10);
 DOF.IB = X(:,11)*1e-3;
[~, OUT_SPEC] = aaSynFoldedPmosOL(NCHV,PCHV,DOF);
C(:,1) = IN_SPEC.UGF ./ double(OUT_SPEC.UGF) - 1;
C(:,2) = IN_SPEC.PM ./ double(OUT_SPEC.PM) - 1;
C(:,3) = log10(IN_SPEC.AVDC) ./ log10(double(OUT_SPEC.AVDC)) - 1;
C(:,4) = IN_SPEC.FO ./ double(OUT_SPEC.FO) - 1;
C(:,5) = IN_SPEC.FP1 ./ double(OUT_SPEC.FP1) - 1;
C(:,6) = IN_SPEC.VO_SWING ./ double(OUT_SPEC.VO_SWING) - 1;
CEQ =[]     

where in_spec are given by user and aaSynFoldedPmosOL is a function that calculates the constraints i have not yet given a grradient function for either nonlincon or obj functions i was using finite difference step size options to control the gradient.

my function is highly nonlinear so what kind of gradient should i provide ?

Thank you.

[Matt J]

Now that we have a clearer view of your problem, it is not clear what you were hoping to "vectorize". Vectorization means that you try to process N separate tasks as a single task. But you do not appear to have N separate optimization jobs - your constraints depend on all X(i,j) simultaneously.

[mahmoud tarek]

By vectorized i mean i want fmjncon to make use of my vectorized aaSynFolded function and my X matrix which has a number of design points row and 11 variables column. I want to run fmincon on each point of my matrix simultaneously. I tried to pass my X matrix as a starting point for fmincon but it give me error: supplied objective function must return scalar value

[Matt J]

function OBJ = Obj(X)
 OBJ = sum(X(:,11),1);
end

[mahmoud tarek]

First of all thank you for your help. I tried your solution and what it did is it made function evaluations of the size of my input matrix every iterations which took a lot of time and memory. I was thinking about your first suggestion to provide my own derivative calculation for obj and nonlincon but i do not know how. Do i need to provide the derivative of my obj function which is just a vector of my input matrix with respect to every other variable in my matrix? And if that's correct does it mean i need to get x11 as a function of all other variables from my synfolded function?

[Matt J]

This documentation page talks about supplying your own derivatives,

https://www.mathworks.com/help/optim/ug/nonlinear-constraints-with-gradients.html

You may want to consider first, though, whether this "vectorization" you are pursuing is worthwhile. You haven't told us how many sub-problems you are trying to simultaneously solve. I think you would have to have at least several hundred, each of them fairly simple to solve individually, before you would see a benefit.

And if that's correct does it mean i need to get x11 as a function of all other variables from my synfolded function?

No, all of your x(i,j) are to be viewed as independent variables.

[mahmoud tarek]

Thank you for the documentation you provided. I am still facing a problem unlike the documentation my obj and nonlincon constraints are not a direct function of my 11 variables so i do not know how to provide the gradient. As for the reason i am pursuing vectorization is that my input is many points and i wanted to run an optimization function on each of my input points simultaneously but fmincon can not do that so instead i tried to provide the gradients. All of that is just to try and get the least run time possible. Thank you again for your patience.

[Matt J]

How many is "many"?

If you cannot supply your own gradient calculation, then it will probably not be worthwhile to try to vectorize.

[mahmoud tarek]

My input points can be up to million each of 11 design variables so it is a large space. My function is not an explicit one it is a simulation function so i do not know how to provide gradient for it.

[Matt J]

Can you even be sure it has a derivative?

[mahmoud tarek]

I'm not sure, i think my variables and constraints are related in a non linear fashion, as i said it is based on simulations. Does that mean i can not provide my own gradients to the function?

[Matt J]

If the function is not differentiable, then it does not make sense to use a gradient-based optimizer.

[mahmoud tarek]

But how did matlab solve it with finite differences?

[Matt J]

How do you know it solved it? How do you know the correct solution was found?

[mahmoud tarek]

It gave me good results. I know it is not gonna exactly solve it but it gave me good results within the tolerances i provided.

[Matt J]

Then maybe the function is differentiable (even if you cannot prove it). Or, you got lucky and the iterations never landed near a point of non-differentiability.

It is still an open question, though, whether vectorization is a worthwhile option for you. Can you even run the simulation in a vectorized fashion? I.e., can you run a batch of simulations for multiple parameter sets more efficiently than just doing a loop over the parameter sets?

[mahmoud tarek]

yes, i can and i am trying now to provide the gradients (if possible) of my simulations function.

Do you have any documents or ideas on how to do that ?

[Matt J]

The chain rule,

https://en.wikipedia.org/wiki/Chain_rule#General_rule

If an analytical calculation is too difficult, you can also try your own vectorized finite difference method to find the Jacobian of your simulation function. From that, it should be easier to find the total derivative of your objective using the chain rule.

delta = small_number;
Y0=simulation(X); %

Jacobian=nan(size(X)); %to hold the result
for i=1:11
    
    Xp=X;
    Xp(:,i)=Xp(:,i)+delta;
    
    Yp=simulation(Xp);
    
    Jacobian(:,i)=(Yp(:,i)-Y0(:,i))/delta;
    
end