Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

%% INPUTS
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);

%% CALCULATE
isConverge = false;
numIterations = 0;

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

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

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

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

    % Loop housekeeping
    numIterations = numIterations + 1;
end
share|improve this question
1  
Why can't you just use fzero? –  Xodarap Jun 21 '11 at 17:37
    
@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. –  Elpezmuerto Jun 21 '11 at 18:11
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
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. –  Elpezmuerto Jun 21 '11 at 16:15
add comment

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."

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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