Optimización sin saber la función de la forma o de sus derivados

Question

Entiendo que esta pregunta no tiene una respuesta correspondiente.

Estamos desarrollando un algoritmo de control mediante programación dinámica. Efectivamente estamos de cambio de una variable de entrada y, a continuación, trazar los resultados para generar un sistema operativo de la curva (SOC). Debido a la complicada naturaleza del sistema y DP, DP parte es una "caja negra" y no podemos analíticamente predicado de los resultados de la DP solución. El DP solución tiene más de un posible 54 millones de miembros y es utilizado en una gran rápido tiempo de simulación Monte-Carlo de millones de simulaciones. Estos dos factores hacen que sea imposible conocer la forma analítica de la función.

Ahora estamos tratando de un par de razonable puntos y ver qué pasa. Me gusta llevar esto un paso más allá y la introducción de un nivel de optimización. Sin embargo, no sabemos la forma de la función y su posterior derivado.

Tenemos un resultado específico que estamos tratando de lograr, sin embargo. Supongamos que el DP solución se define q|x donde x es el sintonizables de entradas DP. q|x se utiliza como una entrada en función, f, donde queremos f(q|x) = y

f(q|x) = y

He escrito un simple 1D interseccion en Matlab. Nota para la prueba, que acaba de recoger una función arbitraria, f(x) = x, puede ser lo que usted desea. Sólo recuerde que cuando ejecuto esto de verdad, yo no sé la forma de la función. Puedo hacer algo mejor que esta simple aplicación?

%% 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

Answer 1

Usted podría utilizar la Nelder-Mead algoritmo de optimización. Sólo se requiere que los valores de la función, no de los derivados. El algoritmo también es llamado el "simplex" método, a pesar de que no tiene nada que ver con el famoso método del simplex para programación lineal.

Véase también Richard Brent del libro "los Algoritmos de Minimización Sin Derivados."

Answer 2

El algoritmo que se ha implementado no es el de Newton-Raphson, es la interseccion método. Newton-Raphson requiere el conocimiento de la derivada, por lo que no es directamente aplicable a su problema. Sin embargo, el método de la secante es muy similar y no requiere de derivados, por lo que se debe trabajar para usted. En general, usted puede buscar numérico de la raíz-búsqueda de métodos que resuelven exactamente este tipo de problema.