Welcome
TwitterFacebookGoogle

Convergence detection for optimization algorithms: Approximate-KKT stopping criterion when Lagrange multipliers are not available

In this paper we investigate how to efficiently apply Approximate-Karush–Kuhn–Tucker proximity measures as stopping criteria for optimization algorithms that do not generate approximations to Lagrange multipliers. We prove that the KKT error measurement tends to zero when approaching a solution and we develop a simple model to compute the KKT error measure requiring only the solution of a non-negative linear least squares problem. Our numerical experiments on a Genetic Algorithm show the efficiency of the strategy.

 

Highlights:

  • We use AKKT as stopping criteria for GA.
  • AKKT is used for optimality condition.
  • Our approach showed to be very efficient.

Gabriel Haeser, Vinicius Veloso de Melo:
Convergence detection for optimization algorithms: Approximate-KKT stopping criterion when Lagrange multipliers are not available. Oper. Res. Lett. 43(5): 484-488 (2015). http://dx.doi.org/10.1016/j.orl.2015.06.009

 

@article{DBLP:journals/orl/HaeserM15,
author = {Gabriel Haeser and
Vinicius Veloso de Melo},
title = {Convergence detection for optimization algorithms: Approximate-KKT
stopping criterion when Lagrange multipliers are not available},
journal = {Oper. Res. Lett.},
volume = {43},
number = {5},
pages = {484–488},
year = {2015},
url = {http://dx.doi.org/10.1016/j.orl.2015.06.009},
doi = {10.1016/j.orl.2015.06.009},
timestamp = {Sat, 21 Nov 2015 19:36:36 +0100},
biburl = {http://dblp.uni-trier.de/rec/bib/journals/orl/HaeserM15},
bibsource = {dblp computer science bibliography, http://dblp.org}
}

 
Keywords:
Condizioni di ottimo; Algoritmi di ottimizzazione; Arresto criteri; Gli algoritmi genetici
Conditions d’optimalité; Les algorithmes d’optimisation; Critères d’arrêt; Les algorithmes génétiques
Optimalitätsbedingungen; Optimierungsalgorithmen; Abbruchkriterien; genetische Algorithmen
Condiciones de optimalidad; Algoritmos de optimización; Detener criterios; Algoritmos genéticos
Optimality शर्तों; अनुकूलन एल्गोरिदम; मानदंड रोकना; आनुवंशिक एल्गोरिदम
最適条件。最適化アルゴリズム。基準を停止。遺伝的アルゴリズム
最优性条件;优化算法;停止准则;遗传算法
最優性條件;優化算法;停止準則;遺傳算法
최적 조건; 최적화 알고리즘; 기준을 중지; 유전자 알고리즘