I understand that this question may not have a corresponding answer.

We are developing a control algorithm using dynamic programming. Effectively we are change one input variable and then plot the results to generate a system operating curve (SOC). Because of the complicated nature of the system and DP, the DP part is a "black box" and we can not analytically predicate the results of the DP solution. The DP solution has over a possible 54 million states and is used in a large fast-time Monte-Carlo simulation of millions of simulations. These two factors make it impossible to know the analytic form of the function.

Right now we are just trying a couple of reasonable points and seeing what happens. I like to take this a step further and introduce a level of optimization. However we don't know the form of the function and its subsequent derivative.

We do have a specific result we are striving for however. Suppose the DP solution is defined q|x where x is the tunable DP input. q|x is used as an input into function, f, where we want f(q|x) = y

f(q|x) = y

I have written up a simple 1D bisection in Matlab. Note for testing, I just picked an arbitrary function, f(x) = x, it can be whatever you want. Just remember that when I run this for real, I will not know the function form. Can I do something better than this simple implementation?

clc; clear all;
% Initial costs
costLow = 1e-9;
costHigh = .5;
costGuess = .1;

% Result goal
resultGoal = 0.001;

% Search conditions
maxIterations = 20;
tol = 0.0001;

f = @(x)(x);

isConverge = false;
numIterations = 0;

% Calculate initial points
resultLow = f(costLow);
resultHigh = f(costHigh);

while numIterations < maxIterations && ~isConverge
    resultGuess = f(costGuess);

    % Test if result converged
    if abs(resultGuess - resultGoal) < tol
        isConverge = true;

    % If not converged, set new guess
    if resultGuess > resultGoal
        costHigh = costGuess;
        costLow = costGuess;
    %costGuess =  mean([costHigh costLow]);
    costGuess = exp(mean(log([costHigh costLow])));

    % Loop housekeeping
    numIterations = numIterations + 1;
  • 1
    $\begingroup$ Why can't you just use fzero? $\endgroup$ – Xodarap Jun 21 '11 at 17:37
  • $\begingroup$ @Xodarap, A builtin Matlab function is a possibility but due to the complexity of the problem and simulation framework, I would prefer to avoid it. I also like like to fully understand the optimization problem, hence another reason why I asked this question. $\endgroup$ – Elpezmuerto Jun 21 '11 at 18:11

The algorithm you've implemented is not Newton-Raphson, it's the bisection method. Newton-Raphson requires knowledge of the derivative, so is not directly applicable for your problem. However, the secant method is very similar and does not require derivatives, so it should work for you. In general, you can look up numerical root-finding methods which solve exactly this kind of problem.

  • $\begingroup$ you are correct. I was accidentally stated it was newton-raphson because I was thinking I didn't know the derivative. I have corrected it above. $\endgroup$ – Elpezmuerto Jun 21 '11 at 16:15

You could use the Nelder-Mead algorithm for optimization. It only requires function values, not derivatives. The algorithm is also called the "simplex" method, though it has nothing to do with the famous simplex method for linear programming.

See also Richard Brent's book "Algorithms for Minimization Without Derivatives."


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.