Métodos de otimização da biblioteca ALGLIB (Parte I)
145
1
Conteúdo
- Introdução
- Métodos de otimização da biblioteca ALGLIB:
Introdução
A distribuição padrão do terminal MetaTrader 5 inclui a biblioteca ALGLIB, que é uma poderosa ferramenta de análise numérica, podendo ser útil para desenvolvedores de sistemas de trading. A biblioteca ALGLIB oferece ao usuário um extenso arsenal de métodos de análise numérica, incluindo:
- Álgebra linear — resolução de sistemas de equações lineares, cálculo de autovalores e autovetores, decomposição de matrizes.
- Otimização — métodos de otimização unidimensional e multidimensional.
- Interpolação e aproximação — interpolação polinomial e por splines, aproximação de funções usando métodos dos mínimos quadrados.
- Integração e diferenciação numéricas — métodos de integração (trapézios, Simpson, etc.), diferenciação numérica.
- Métodos numéricos para solução de equações diferenciais — equações diferenciais ordinárias e métodos numéricos.
- Métodos estatísticos — estimativa de parâmetros, análise de regressão, geração de números aleatórios.
- Análise de Fourier: Transformada Rápida de Fourier.
Os métodos determinísticos de otimização apresentados na ALGLIB são baseados em várias variações da descida do gradiente e permitem o uso de abordagens tanto analíticas quanto numéricas. Neste artigo, vamos nos concentrar nos métodos numéricos, pois eles são os mais adequados para tarefas práticas dos traders.
É importante observar que muitas tarefas no setor financeiro têm natureza discreta, pois os dados de preços são apresentados em pontos separados. Por isso, nos interessam especialmente os métodos que utilizam representação numérica dos gradientes. O usuário não precisa calcular o gradiente — essa tarefa é assumida pelos métodos de otimização.
O aprendizado dos métodos de otimização da ALGLIB geralmente apresenta dificuldades devido à falta de uniformidade na nomenclatura dos métodos e na forma de utilizá-los. O principal objetivo deste artigo é preencher as lacunas de informação sobre a biblioteca e fornecer exemplos simples de uso. Vamos definir os principais termos e conceitos para entender melhor para que servem esses métodos.
Otimização — o processo de busca pela melhor solução dentro de condições e restrições definidas. Buscar implica ter pelo menos duas alternativas para resolver um problema, das quais é necessário escolher a melhor.
Uma tarefa de otimização — aquela em que se deve encontrar a melhor solução (máximo ou mínimo) dentre várias possibilidades que satisfaçam determinadas condições. Os principais elementos de uma tarefa de otimização são:
- Função objetivo (Objective Function ou Fitness Function). É a função que deve ser maximizada ou minimizada. Por exemplo, maximizar o lucro ou minimizar os custos (lucro ou custos — critérios de otimização).
- Variáveis. São os parâmetros que podem ser ajustados para alcançar o melhor resultado.
- Restrições. São condições que precisam ser respeitadas durante a busca pela solução ótima.
A função objetivo pode ser qualquer função definida pelo usuário, que recebe como entrada os parâmetros a serem otimizados e gera um valor que serve como critério de otimização. Por exemplo, a função objetivo pode ser o teste de um sistema de trading em dados históricos, onde os parâmetros da função são as configurações do sistema de trading, e o valor de saída é a qualidade de seu desempenho.
Tipos de restrições:
- Restrições de limite (Boundary Constraints ou Box Constraints) — são restrições aplicadas aos valores das variáveis, por exemplo, a variável "x" pode estar apenas no intervalo de 1 a 3.
- Restrições lineares de igualdade (Linear Equality Constraints) — são condições em que uma expressão com variáveis deve ser exatamente igual a um determinado número. Por exemplo, (x + y = 5) é uma igualdade linear.
- Restrições lineares de desigualdade (Linear Inequality Constraints) — são condições em que uma expressão com variáveis deve ser menor ou igual (ou maior ou igual) a um determinado número. Por exemplo, (x - y >= 1).
Nos exemplos a seguir, consideraremos apenas as restrições de limite. Assim, o artigo apresentará técnicas eficazes e uma forma simples de usar os métodos de otimização da ALGLIB com exemplos práticos.
Como exemplo de tarefa de otimização, usaremos uma função objetivo simples que deve ser maximizada. Trata-se de uma função suave e monótona com um único ponto de máximo — um paraboloide invertido. Os valores dessa função estão no intervalo [0; 1], independentemente da quantidade de argumentos, que pertencem ao intervalo [-10; 10].
//—————————————————————————————————————————————————————————————————————————————— //Paraboloid, F(Xn) ∈ [0.0; 1.0], X ∈ [-10.0; 10.0], maximization double ObjectiveFunction (double &x []) { double sum = 0.0; for (int i = 0; i < ArraySize (x); i++) { if (x [i] < -10.0 || x [i] > 10.0) return 0.0; sum += (-x [i] * x [i] + 100.0) * 0.01; } return sum /= ArraySize (x); } //——————————————————————————————————————————————————————————————————————————————
BLEIC (Boundary, Linear Equality-Inequality Constraints)
BLEIC (Boundary, Linear Equality-Inequality Constraints), algoritmo de conjunto ativo, é o nome de uma família de métodos usados para resolver tarefas de otimização com igualdades e desigualdades. O nome do método vem da classificação das restrições, que as divide em ativas no ponto atual e inativas. O método transforma uma tarefa com restrições em forma de igualdades e desigualdades em uma sequência de subtarefas com apenas igualdades. As desigualdades ativas são tratadas como igualdades, enquanto as inativas são temporariamente ignoradas (embora continuemos monitorando-as). De forma informal, o ponto atual se move dentro do conjunto admissível, “grudando” ou “desgrudando” das bordas.
1. O que ele faz — busca o mínimo ou o máximo de uma função (por exemplo, busca o maior lucro ou o menor custo), levando em conta várias restrições:
- Limites nos valores das variáveis (por exemplo, o preço não pode ser negativo)
- Igualdades (por exemplo, a soma dos pesos de um portfólio deve ser igual a 100%)
- Desigualdades (por exemplo, o risco não deve ultrapassar um determinado nível)
2. Como ele funciona — utiliza “memória limitada” (Limited memory), ou seja, não armazena todos os cálculos intermediários, apenas os mais importantes. Move-se em direção à solução de forma gradual, passo a passo:
- Avalia a posição atual
- Determina a direção de movimento
- Dá um passo nessa direção
- Verifica se as restrições não foram violadas
- Se necessário, corrige o movimento
3. Características:
- Requer que a função seja “suave” (sem saltos bruscos)
- Pode encontrar um mínimo local em vez do global
- É sensível à aproximação inicial (ponto de partida)
Um exemplo simples — imagine que você está procurando um local para construir uma casa num terreno. Você tem restrições: a casa deve ter um tamanho definido (igualdade), deve ficar a uma certa distância das bordas do terreno (desigualdade), e deve estar dentro dos limites do terreno (restrições de fronteira). Você quer que a vista seja a melhor possível (função objetivo). BLEIC vai “mover” gradualmente a casa imaginária pelo terreno, respeitando todas as restrições, até encontrar o melhor local em termos de vista. Informações mais detalhadas sobre esse algoritmo, assim como sobre os próximos, podem ser encontradas na página do autor da biblioteca.
Para usar o método BLEIC e os demais da biblioteca ALGLIB, precisamos conectar o arquivo (a biblioteca já vem com o terminal MetaTrader 5, não é necessário instalar nada adicionalmente).
#include <Math\Alglib\alglib.mqh> Vamos escrever um script — um exemplo de uso eficiente dos métodos da ALGLIB. Precisamos destacar as etapas principais típicas do uso dos métodos ALGLIB, e marcaremos com cores apropriadas os blocos de código idênticos.
1. Definimos as condições de fronteira da tarefa, como o número de execuções da função de avaliação (função objetivo), os intervalos dos parâmetros a serem otimizados e seus respectivos passos. Para os métodos da ALGLIB, é necessário atribuir valores iniciais aos parâmetros "x" a serem otimizados (os métodos são determinísticos e os resultados dependem completamente dos valores iniciais, então vamos aplicar geração de números aleatórios dentro do intervalo dos parâmetros da tarefa), bem como o escalonamento "s" (os métodos são sensíveis à escala relativa entre os parâmetros, neste caso definimos a escala como "1").
2. Declaramos os objetos necessários para o funcionamento do algoritmo.
3. Definimos os parâmetros externos do algoritmo (as configurações).
4. Inicializamos o algoritmo, passando para o método os intervalos e passos dos parâmetros a serem otimizados, bem como os parâmetros externos do algoritmo.
5. Executamos a otimização.
6. Obtemos os resultados da otimização para uso posterior.
É importante considerar um aspecto essencial: o usuário não pode intervir no processo de otimização ou interrompê-lo a qualquer momento. O método executa todas as operações de forma autônoma, chamando a função de avaliação internamente durante seu próprio processo. O algoritmo pode chamar a função de avaliação quantas vezes quiser (no método BLEIC não é possível especificar esse parâmetro como critério de parada), e o usuário pode apenas controlar o número máximo permitido de chamadas, tentando forçar uma interrupção por meio de um comando passado ao método.
//—————————————————————————————————————————————————————————————————————————————— void OnStart () { // Initialization of optimization parameters--------------------------------------- int numbTestFuncRuns = 10000; int params = 1000; // Create and initialize arrays for range bounds--------------------- double rangeMin [], rangeMax [], rangeStep; ArrayResize (rangeMin, params); ArrayResize (rangeMax, params); for (int i = 0; i < params; i++) { rangeMin [i] = -10; rangeMax [i] = 10; } rangeStep = DBL_EPSILON; double x []; double s []; ArrayResize (x, params); ArrayResize (s, params); ArrayInitialize (s, 1); // Generate random initial parameter values in given ranges---- for (int i = 0; i < params; i++) { x [i] = rangeMin [i] + ((rangeMax [i] - rangeMin [i]) * rand () / 32767.0); } // Create objects for optimization------------------------------------------ C_OptimizedFunction fFunc; fFunc.Init (params, numbTestFuncRuns); CObject obj; CNDimensional_Rep frep; CMinBLEICReportShell rep; // Set the parameters of the BLEIC optimization algorithm--------------------------- double diffStep = 0.00001; double epsg = 1e-16; double epsf = 1e-16; double epsi = 0.00001; CAlglib::MinBLEICCreateF (x, diffStep, fFunc.state); CAlglib::MinBLEICSetBC (fFunc.state, rangeMin, rangeMax); CAlglib::MinBLEICSetInnerCond (fFunc.state, epsg, epsf, rangeStep); CAlglib::MinBLEICSetOuterCond (fFunc.state, rangeStep, epsi); CAlglib::MinBLEICOptimize (fFunc.state, fFunc, frep, 0, obj); CAlglib::MinBLEICResults (fFunc.state, x, rep); // Output of optimization results----------------------------------------------- Print ("BLEIC, best result: ", fFunc.fB, ", number of function launches: ", fFunc.numberLaunches); } //——————————————————————————————————————————————————————————————————————————————
Como o método chama a função de avaliação por conta própria (e não através do programa do usuário), será necessário encapsular a chamada da função de avaliação em uma classe que herda de uma classe base da ALGLIB (essas classes base variam conforme o método). Vamos declarar a classe encapsuladora como "C_OptimizedFunction" e incluir na classe os seguintes métodos:
1. Func() — este é um método virtual que deve ser sobrescrito nas classes derivadas.2. Init() — inicializa os parâmetros da classe. Dentro do método:
- São inicializadas variáveis relacionadas ao número de execuções e ao melhor valor encontrado da função.
- São reservados os arrays "c" e "cB" para armazenar as coordenadas.
Variáveis:
- state — objeto do tipo CMinBLEICStateShell, específico do método BLEIC, usado na chamada dos métodos estáticos do algoritmo e no comando de parada.
- numberLaunches — número atual de execuções (necessário para evitar execuções incontroláveis ou demoradas demais da função de avaliação).
- maxNumbLaunchesAllowed — número máximo permitido de execuções.
- fB — melhor valor encontrado da função de avaliação.
- c[] — array de coordenadas atuais.
- cB[] — array para armazenar as melhores coordenadas encontradas.
//—————————————————————————————————————————————————————————————————————————————— // Class for function optimization, inherits from CNDimensional_Func class C_OptimizedFunction : public CNDimensional_Func { public: C_OptimizedFunction (void) { } ~C_OptimizedFunction (void) { } // A virtual function to contain the function being optimized-------- virtual void Func (CRowDouble &x, double &func, CObject &obj); // Initialization of optimization parameters--------------------------------------- void Init (int coords, int maxNumberLaunchesAllowed) { numberLaunches = 0; maxNumbLaunchesAllowed = maxNumberLaunchesAllowed; fB = -DBL_MAX; ArrayResize (c, coords); ArrayResize (cB, coords); } //---------------------------------------------------------------------------- CMinBLEICStateShell state; // State int numberLaunches; // Launch counter double fB; // Best found value of the objective function (maximum) double cB []; // Coordinates of the point with the best function value private: //------------------------------------------------------------------- double c []; // Array for storing current coordinates int maxNumbLaunchesAllowed; // Maximum number of function calls allowed }; //——————————————————————————————————————————————————————————————————————————————
O método "Func" da classe "C_OptimizedFunction" serve para chamar a função de avaliação do usuário. Ele recebe como argumentos o vetor "x" (uma das possíveis combinações dos parâmetros otimizáveis propostas pelo método de otimização), o argumento "func", no qual deve ser retornado o valor calculado da função de avaliação, e o objeto "obj" (cujo propósito não está claro para mim, talvez reservado para permitir a passagem de informações adicionais de/para o método). As principais etapas de execução do método são:
1. O contador "numberLaunches" é incrementado, o qual rastreia o número de chamadas ao método "Func".
2. Se o número de execuções ultrapassar o valor permitido "maxNumbLaunchesAllowed", a função define "func" como "DBL_MAX" (valor máximo do tipo "double"; os métodos da ALGLIB são voltados à minimização de funções, esse valor representa a pior solução possível). Em seguida, é chamada a função "MinBLEICRequestTermination", que serve para sinalizar ao método BLEIC que é necessário interromper o processo de otimização.
3. Em seguida, dentro de um laço, os valores do vetor "x" são copiados para o array "c". Isso é necessário para utilizar esses valores ao chamar a função de avaliação do usuário.
4. A função "ObjectiveFunction" é chamada, calculando o valor da função objetivo para os valores atuais no array "c". O resultado é armazenado em "ffVal", e o valor de "func" é definido como o valor negativo de "ffVal" (estamos otimizando um paraboloide invertido, que deve ser maximizado, e o BLEIC minimiza funções, portanto invertemos o valor).
5. Se o valor atual "ffVal" for maior que o melhor valor anterior "fB", então "fB" é atualizado, e o array "cB" copia o estado atual de "c". Isso permite rastrear o melhor valor encontrado da função objetivo com os parâmetros correspondentes, podendo acessá-los mais tarde, se necessário.
A função "Func" implementa a chamada à função de avaliação do usuário e monitora quantas vezes ela foi executada, atualiza os melhores resultados. Ela também gerencia as condições de parada, caso o número de execuções ultrapasse o limite definido.
//—————————————————————————————————————————————————————————————————————————————— // Implementation of the function to be optimized void C_OptimizedFunction::Func (CRowDouble &x, double &func, CObject &obj) { // Increase the function launch counter and limitation control---------------- numberLaunches++; if (numberLaunches >= maxNumbLaunchesAllowed) { func = DBL_MAX; CAlglib::MinBLEICRequestTermination (state); return; } // Copy input coordinates to internal array------------------------- for (int i = 0; i < x.Size (); i++) c [i] = x [i]; // Calculate objective function value---------------------------------------- double ffVal = ObjectiveFunction (c); func = -ffVal; // Update the best solution found-------------------------------------- if (ffVal > fB) { fB = ffVal; ArrayCopy (cB, c); } } //——————————————————————————————————————————————————————————————————————————————
Após executar o script de teste com o algoritmo BLEIC para otimização da função do paraboloide, teremos no print o seguinte resultado:
BLEIC, melhor resultado: 0.6861786206145579, número de execuções da função: 84022
Vale destacar que, mesmo após os comandos de parada da otimização com o método "MinBLEICRequestTermination", o algoritmo continuou o processo e tentou chamar a função de avaliação mais 74.022 vezes, ultrapassando o limite de 10.000 execuções.
Agora vamos deixar o BLEIC agir livremente, sem impor restrições, permitindo que ele siga seu próprio curso. Resultados foram os seguintes:
BLEIC, melhor resultado: 1.0, número de execuções da função: 72017
Como podemos ver, o BLEIC consegue convergir completamente na função do paraboloide, no entanto, nesse caso, é impossível estimar antecipadamente o número de execuções da função objetivo necessárias. A testagem completa em larga escala e a análise dos resultados serão feitas posteriormente.
No algoritmo, o passo de diferenciação é um elemento crítico. Por exemplo, se utilizarmos um passo muito pequeno, como 1e-16 em vez de 0.00001, o algoritmo se interrompe precocemente, ou seja, "trava", apresentando o seguinte resultado:
BLEIC, melhor resultado: 0.6615878186651468, número de execuções da função: 4002
L-BFGS (Limited-memory Broyden–Fletcher–Goldfarb–Shanno)
O algoritmo L-BFGS (Limited-memory Broyden–Fletcher–Goldfarb–Shanno) é um método de otimização eficiente, especialmente desenvolvido para resolver tarefas de alta dimensionalidade, quando o número de variáveis ultrapassa 1.000. Ele pertence à classe dos métodos quasi-Newtonianos e utiliza memória limitada para armazenar informações sobre a curvatura da função, o que evita a necessidade de armazenar e calcular a matriz Hessiana completa.
O funcionamento do algoritmo baseia-se na construção e no refinamento de um modelo quadrático da função a ser otimizada, utilizando os últimos M pares de valores e gradientes. Normalmente, M é um número moderado, de 3 a 10, o que reduz significativamente o custo computacional para O(N·M) operações. Na cada iteração, o algoritmo calcula o gradiente no ponto atual, determina a direção de busca usando os vetores armazenados e realiza uma busca linear para definir o tamanho do passo. Se o passo do método quasi-Newtoniano não reduzir suficientemente o valor da função ou do gradiente, a direção é ajustada novamente.
A principal característica do L-BFGS é a definição positiva do Hessiano aproximado, o que garante que a direção do método quasi-Newtoniano sempre será de descida, independentemente da curvatura da função.
De forma simples, como funciona o LBFGS:
1. A ideia principal: o algoritmo tenta encontrar o mínimo da função, "descendo" gradualmente até ele, construindo um modelo simplificado (quadrático) da função, que é constantemente ajustado.
2. Como ele faz isso: memoriza os últimos M passos (geralmente 310) e, a cada passo, armazena duas informações:
- onde estávamos (valor)
- para onde podemos ir (gradiente)
Com base nesses dados, o algoritmo constrói uma aproximação da curvatura da função (a matriz Hessiana) e usa essa aproximação para determinar o próximo passo.
3. Características: sempre se move “para baixo” (na direção da redução do valor da função), usa memória de forma econômica (armazenando apenas os últimos M passos) e é rápido (o custo computacional é proporcional ao tamanho da tarefa × M).
4. Exemplo prático. Imagine que você está descendo uma montanha com neblina:
- você só consegue perceber a direção da descida no ponto atual
- lembra de alguns passos anteriores e como o declive mudou
- com base nessas informações, projeta o melhor passo seguinte
5. Limitações:
- em “terrenos” muito complexos pode funcionar mais devagar
- pode exigir ajustes adicionais para melhorar o desempenho
Diferentemente do método BLEIC, o L-BFGS permite especificar diretamente uma limitação no número de execuções da função objetivo, mas não é possível definir condições de fronteira para os parâmetros otimizáveis. O valor de M no exemplo abaixo foi definido como “1”; o uso de outros valores não gerou mudanças significativas nos resultados nem no comportamento do algoritmo.
//—————————————————————————————————————————————————————————————————————————————— void OnStart () { // Initialization of optimization parameters--------------------------------------- int numbTestFuncRuns = 10000; int params = 1000; // Create and initialize arrays for search range bounds-------------- double rangeMin [], rangeMax [], rangeStep; ArrayResize (rangeMin, params); ArrayResize (rangeMax, params); for (int i = 0; i < params; i++) { rangeMin [i] = -10; rangeMax [i] = 10; } rangeStep = DBL_EPSILON; double x []; double s []; ArrayResize (x, params); ArrayResize (s, params); ArrayInitialize (s, 1); // Generate random initial parameter values in given ranges----- for (int i = 0; i < params; i++) { x [i] = rangeMin [i] + ((rangeMax [i] - rangeMin [i]) * rand () / 32767.0); } // Create objects for optimization------------------------------------------- C_OptimizedFunction fFunc; fFunc.Init (params, numbTestFuncRuns); CObject obj; CNDimensional_Rep frep; CMinLBFGSReportShell rep; // Set the parameters of the L-BFGS optimization algorithm--------------------------- double diffStep = 0.00001; double epsg = 1e-16; double epsf = 1e-16; CAlglib::MinLBFGSCreateF (1, x, diffStep, fFunc.state); CAlglib::MinLBFGSSetCond (fFunc.state, epsg, epsf, rangeStep, numbTestFuncRuns); CAlglib::MinLBFGSSetScale (fFunc.state, s); CAlglib::MinLBFGSOptimize (fFunc.state, fFunc, frep, 0, obj); CAlglib::MinLBFGSResults (fFunc.state, x, rep); //---------------------------------------------------------------------------- Print ("L-BFGS, best result: ", fFunc.fB, ", number of function launches: ", fFunc.numberLaunches); } //——————————————————————————————————————————————————————————————————————————————
No L-BFGS, o tipo da variável "state" é definido como "CMinLBFGSStateShell".
//—————————————————————————————————————————————————————————————————————————————— // Class for function optimization, inherits from CNDimensional_Func class C_OptimizedFunction : public CNDimensional_Func { public: //-------------------------------------------------------------------- C_OptimizedFunction (void) { } ~C_OptimizedFunction (void) { } // A virtual function to contain the function being optimized--------- virtual void Func (CRowDouble &x, double &func, CObject &obj); // Initialization of optimization parameters---------------------------------------- void Init (int coords, int maxNumberLaunchesAllowed) { numberLaunches = 0; maxNumbLaunchesAllowed = maxNumberLaunchesAllowed; fB = -DBL_MAX; ArrayResize (c, coords); ArrayResize (cB, coords); } //---------------------------------------------------------------------------- CMinLBFGSStateShell state; // State int numberLaunches; // Launch counter double fB; // Best found value of the objective function (maximum) double cB []; // Coordinates of the point with the best function value private: //------------------------------------------------------------------- double c []; // Array for storing current coordinates int maxNumbLaunchesAllowed; // Maximum number of function calls allowed }; //——————————————————————————————————————————————————————————————————————————————
A parada do processo de otimização é solicitada com o comando "MinLBFGSRequestTermination".
//—————————————————————————————————————————————————————————————————————————————— // Implementation of the function to be optimized void C_OptimizedFunction::Func (CRowDouble &x, double &func, CObject &obj) { //Increase the function launch counter and limitation control------------------- numberLaunches++; if (numberLaunches >= maxNumbLaunchesAllowed) { func = DBL_MAX; CAlglib::MinLBFGSRequestTermination (state); return; } // Copy input coordinates to internal array------------------------- for (int i = 0; i < x.Size (); i++) c [i] = x [i]; // Calculate objective function value---------------------------------------- double ffVal = ObjectiveFunction (c); func = -ffVal; // Update the best solution found-------------------------------------- if (ffVal > fB) { fB = ffVal; ArrayCopy (cB, c); } } //——————————————————————————————————————————————————————————————————————————————
Após a execução do script de teste com o algoritmo L-BFGS para otimizar a função do paraboloide, obtemos no print o seguinte resultado:
L-BFGS, melhor resultado: 0.6743844728276278, número de execuções da função: 24006
É bem provável que o parâmetro do número máximo permitido de execuções da função objetivo não esteja funcionando corretamente, pois o algoritmo executou mais que o dobro do número estipulado.
Agora vamos tentar não limitar o L-BFGS e permitir que ele execute a otimização sem restrições no número de execuções:
L-BFGS, melhor resultado: 1.0, número de execuções da função: 52013
O L-BFGS, assim como o BLEIC, é capaz de convergir completamente na função do paraboloide, mas o número de execuções se torna incontrolável. Na análise do próximo algoritmo, mostraremos que isso pode ser realmente um grande problema, se esse detalhe não for levado em consideração.
Para o L-BFGS, o passo de diferenciação também é um fator crítico. Se utilizarmos um passo muito pequeno, como 1e-16, o algoritmo para prematuramente — ele trava, e o resultado é:
L-BFGS, melhor resultado: 0.6746423814003036, número de execuções da função: 4001
NS (Nonsmooth Nonconvex Optimization Subject to box / linear / nonlinear - Nonsmooth Constraints)
NS (Nonsmooth Nonconvex Optimization Subject to box/linear/nonlinear - Nonsmooth Constraints) — o algoritmo de otimização não suave e não convexa é projetado para resolver tarefas nas quais a função objetivo não é nem suave nem convexa. Isso significa que a função pode apresentar mudanças abruptas, cantos ou outras irregularidades. As principais características desse tipo de tarefa estão no fato de que a função objetivo pode conter pontos de descontinuidade ou alterações bruscas, o que dificulta a análise por meio de métodos que dependem do cálculo de gradientes.
Os princípios de funcionamento do algoritmo incluem a estimativa de gradientes, onde se aplica o método de amostragem de gradiente, que realiza estimativas em vários pontos aleatórios ao redor da solução atual. Isso ajuda a contornar os problemas relacionados às irregularidades da função. Com base nas estimativas obtidas, é formulado um problema de programação quadrática (QP) com restrições, cuja solução permite determinar a direção a seguir para melhorar a solução atual. O algoritmo opera de forma iterativa, atualizando a solução a cada iteração com base nos gradientes calculados e na solução do problema QP.
Explicando em linguagem simples o que significa essa descrição de otimização:
1. NONSMOOTH (Otimização não suave):
- A função pode ter descontinuidades ou "quebras"
- Não há exigência de diferenciabilidade contínua
- Pode haver transições bruscas e saltos
2. NONCONVEX (Não convexa):
- A função pode ter múltiplos mínimos e máximos locais
- O “terreno” da função pode ser complexo, com “morros” e “vales”
3. Tipos de restrições (CONSTRAINTS): BOX (caixa), LINEAR (lineares), NONLINEAR-NONSMOOTH (não lineares e não suaves), já foram descritos anteriormente.
Uma particularidade desse método é a necessidade de indicar e configurar os parâmetros do resolvedor AGS (método de amostragem adaptativa de gradiente). Esse resolvedor foi desenvolvido especificamente para tarefas não suaves com restrições de caixa, lineares e não lineares. O AGS possui algumas características importantes: tratamento especial das restrições, escalonamento das variáveis (para lidar com tarefas mal escaladas) e suporte embutido para diferenciação numérica.
A limitação mais importante do resolvedor AGS é que ele não é indicado para tarefas de alta dimensionalidade. Um único passo do AGS exige aproximadamente 2·N avaliações de gradientes em pontos aleatórios (em comparação, o L-BFGS exige O(1) avaliações por passo). Em geral, são necessárias O(N) iterações para convergência, o que resulta em O(N²) avaliações de gradiente durante a sessão de otimização.
Diferente dos métodos anteriores, o NS exige o uso do tipo "CRowDouble" para as variáveis de condições de fronteira e valores iniciais dos parâmetros otimizáveis, em vez do tipo "double". Além disso, é necessário definir os parâmetros para o resolvedor AGS.
//—————————————————————————————————————————————————————————————————————————————— void OnStart () { // Initialization of optimization parameters--------------------------------------- int numbTestFuncRuns = 10000; int params = 1000; // Create and initialize arrays for search range bounds-------------- CRowDouble rangeMin, rangeMax; rangeMin.Resize (params); rangeMax.Resize (params); double rangeStep; for (int i = 0; i < params; i++) { rangeMin.Set (i, -10); rangeMax.Set (i, 10); } rangeStep = DBL_EPSILON; CRowDouble x, s; x.Resize (params); s.Resize (params); s.Fill (1); // Generate random initial parameter values in given ranges---- for (int i = 0; i < params; i++) { x.Set (i, rangeMin [i] + ((rangeMax [i] - rangeMin [i]) * rand () / 32767.0)); } // Create objects for optimization------------------------------------------ C_OptimizedFunction fFunc; fFunc.Init (params, numbTestFuncRuns); CObject obj; CNDimensional_Rep frep; CMinNSReport rep; // Set the parameters of the NS optimization algorithm------------------------------ double diffStep = 0.00001; double radius = 0.8; double rho = 50.0; CAlglib::MinNSCreateF (x, diffStep, fFunc.state); CAlglib::MinNSSetBC (fFunc.state, rangeMin, rangeMax); CAlglib::MinNSSetScale (fFunc.state, s); CAlglib::MinNSSetCond (fFunc.state, rangeStep, numbTestFuncRuns); CAlglib::MinNSSetAlgoAGS (fFunc.state, radius, rho); CAlglib::MinNSOptimize (fFunc.state, fFunc, frep, obj); CAlglib::MinNSResults (fFunc.state, x, rep); // Output of optimization results----------------------------------------------- Print ("NS, best result: ", fFunc.fB, ", number of function launches: ", fFunc.numberLaunches); } //——————————————————————————————————————————————————————————————————————————————
Para o método NS é necessário criar uma classe encapsuladora, agora herdada de outra classe base — "CNDimensional_FVec". Também será preciso alterar o método virtual para "FVec". Uma característica específica deste método é o fato de que não se pode retornar o valor da função de avaliação como "DBL_MAX", pois isso faz com que o método termine com erro, diferentemente dos métodos de otimização anteriores. Por isso, adicionaremos um campo adicional na classe — "fW", para acompanhar a pior solução durante o processo de otimização.
//—————————————————————————————————————————————————————————————————————————————— // Class for function optimization, inherits from CNDimensional_FVec class C_OptimizedFunction : public CNDimensional_FVec { public: //-------------------------------------------------------------------- C_OptimizedFunction (void) { } ~C_OptimizedFunction (void) { } // A virtual function to contain the function being optimized-------- virtual void FVec (CRowDouble &x, CRowDouble &fi, CObject &obj); // Initialization of optimization parameters--------------------------------------- void Init (int coords, int maxNumberLaunchesAllowed) { numberLaunches = 0; maxNumbLaunchesAllowed = maxNumberLaunchesAllowed; fB = -DBL_MAX; fW = DBL_MAX; ArrayResize (c, coords); ArrayResize (cB, coords); } //---------------------------------------------------------------------------- CMinNSState state; // State int numberLaunches; // Launch counter double fB; // Best found value of the objective function (maximum) double fW; // Worst found value of the objective function (maximum) double cB []; // Coordinates of the point with the best function value private: //------------------------------------------------------------------- double c []; // Array for storing current coordinates int maxNumbLaunchesAllowed; // Maximum number of function calls allowed }; //——————————————————————————————————————————————————————————————————————————————
Vermelho está indicado o que não deve ser feito. Em vez disso, vamos retornar a pior solução que foi encontrada no processo de otimização (com sinal negativo, já que o método trabalha com minimização). E, claro, é necessário alterar o método de parada para "MinNSRequestTermination".
//—————————————————————————————————————————————————————————————————————————————— void C_OptimizedFunction::FVec (CRowDouble &x, CRowDouble &fi, CObject &obj) { // Increase the function launch counter and limitation control---------------- numberLaunches++; if (numberLaunches >= maxNumbLaunchesAllowed) { //fi.Set (0, DBL_MAX); //Cannot return DBL_MAX value fi.Set (0, -fW); CAlglib::MinNSRequestTermination (state); return; } // Copy input coordinates to internal array------------------------- for (int i = 0; i < x.Size (); i++) c [i] = x [i]; // Calculate objective function value---------------------------------------- double ffVal = ObjectiveFunction (c); fi.Set (0, -ffVal); // Update the best and worst solutions found----------------------------- if (ffVal < fW) fW = ffVal; if (ffVal > fB) { fB = ffVal; ArrayCopy (cB, c); } } //——————————————————————————————————————————————————————————————————————————————
Após executar o script de teste com o algoritmo NS para otimizar a função do paraboloide, obtemos no print o seguinte resultado:
NS, melhor resultado: 0.6605212238333136, número de execuções da função: 1006503
Parece que, também para o NS, o parâmetro que define o número máximo permitido de execuções da função objetivo não está funcionando, pois o algoritmo, na prática, executou mais de 1 milhão de chamadas.
Agora vamos tentar não limitar o NS e permitir que ele execute a otimização sem restrição no número de execuções. O experimento não foi concluído; infelizmente, não consegui esperar até o final da execução do script e precisei interrompê-lo manualmente fechando o gráfico:
Sem resultado
Para o NS, o passo de diferenciação também é um fator importante. Se um passo muito pequeno, como 1e-16, for utilizado, o algoritmo trava prematuramente, sem utilizar todo o número de execuções alocado para ele, e o resultado é:
NS, melhor resultado: 0.6784901840822722, número de execuções da função: 96378
Considerações finais
Neste artigo, conhecemos os métodos de otimização da biblioteca ALGLIB, nos quais os gradientes são calculados numericamente de forma automática pelos próprios métodos. Exploramos as características principais de cada um desses métodos, e esse conhecimento permite não apenas realizar a otimização em si, mas também ajuda a evitar situações problemáticas, como o número descontrolado de chamadas à função objetivo.
No próximo e último artigo sobre os métodos de otimização da ALGLIB, vamos analisar detalhadamente mais três métodos. Faremos uma bateria de testes com todos os métodos apresentados até aqui, o que permitirá identificar seus pontos fortes e fracos na prática, além de concluir nosso estudo. Também vamos, como de costume, visualizar o funcionamento dos algoritmos, para demonstrar claramente o comportamento típico deles em tarefas de teste complexas. Isso ajudará a entender melhor como cada método lida com diferentes desafios de otimização.
O texto do artigo apresenta códigos de scripts totalmente funcionais para execução dos métodos ALGLIB. Além disso, no arquivo compactado você encontrará tudo o que precisa para começar a usar os métodos apresentados na otimização de suas estratégias de trading e outras tarefas desde já. Assim, o objetivo do artigo, que é mostrar exemplos simples e claros do uso dos métodos, foi alcançado.
Agradeço especialmente a Evgeniy Chernish, que me ajudou a compreender as particularidades do uso dos métodos da biblioteca ALGLIB.
Programas utilizados no artigo
| # | Nome | Tipo | Descrição |
|---|---|---|---|
| 1 | Simple test ALGLIB BLEIC.mq5 | Script | Script de teste para uso com BLEIC |
| 2 | Simple test ALGLIB LBFGS.mq5 | Script | Script de teste para uso com L-BFGS |
| 3 | Simple test ALGLIB NS.mq5 | Script | Script de teste para uso com NS |
Traduzido do russo pela MetaQuotes Ltd.
Artigo original: https://www.mql5.com/ru/articles/16133
Aviso: Todos os direitos sobre esses materiais pertencem à MetaQuotes Ltd. É proibida a reimpressão total ou parcial.
Esse artigo foi escrito por um usuário do site e reflete seu ponto de vista pessoal. A MetaQuotes Ltd. não se responsabiliza pela precisão das informações apresentadas nem pelas possíveis consequências decorrentes do uso das soluções, estratégias ou recomendações descritas.
Desenvolvendo um EA multimoeda (Parte 19): Criando etapas implementadas em Python
Ganhe uma Vantagem Sobre Qualquer Mercado (Parte III): Índice de Gastos com Cartões Visa
Do básico ao intermediário: Estruturas (IV)
Construindo Expert Advisors Auto-otimizantes Com MQL5 E Python (Parte II): Ajustando Redes Neurais Profundas
- Aplicativos de negociação gratuitos
- 8 000+ sinais para cópia
- Notícias econômicas para análise dos mercados financeiros
Você concorda com a política do site e com os termos de uso