Quiero minimizar una función objetivo complicada, y no estoy seguro de si es convexa. ¿Existe un buen algoritmo que intente demostrar que no es convexo? Por supuesto, el algoritmo podría fallar en probar esto, en cuyo caso no sabría si es convexo o no, y esto está bien; Solo quiero tratar de descartar la convexidad antes de pasar mucho tiempo tratando de determinar analíticamente si la función objetivo es convexa, por ejemplo, tratando de reescribir el problema en una forma estándar conocida como convexa. Una prueba rápida sería tratar de minimizar desde varios puntos de partida y si se encuentran múltiples mínimos locales de esta manera, entonces no es convexo. Pero me preguntaba si hay un mejor algoritmo diseñado con este objetivo en mente.
9
Respuestas:
fuente
Para ver una serie de pruebas de verificación de convexidad / no convexidad prácticamente útiles, consulte (autodescargo de responsabilidad, soy el tercer autor en este documento):
R. Fourer, C. Maheshwari, A. Neumaier, D. Orban y H. Schichl, Convexity and Concavity Detection in Computational Graphs. Tree Walks for Convexity Assessment, INFORMS J. Computing 22 (2010), 26-43.
Tenga en cuenta que hay muchas funciones que son convexas en el dominio de interés pero que no pueden ser fácilmente "disciplinadas", es decir, escritas en una de las formas requeridas por los solucionadores convexos estructurados como CVX .
fuente
Una función puede ser no convexa sin tener múltiples mínimos. Hay una variedad de métodos de optimización que aplican iteraciones de gradiente conjugado (lineal o no lineal), truncadas cuando se calcula una norma de operador negativa. El valor negativo indica una dirección de curvatura negativa (que no puede suceder para funciones convexas). Si rara vez se encuentra una curvatura negativa, estos métodos convergen en un pequeño número de iteraciones de optimización. (Si hay un preacondicionador de calidad disponible, los pasos internos también deberían converger rápidamente).
fuente