Mínimos cuadrados no lineales unilaterales con restricciones lineales

Estoy tratando de resolver un problema de mínimos cuadrados no lineales unilateral con restricciones lineales, es decir, el problema:

$\min_{\mathbf{x}} \quad \sum^m_{i=1} \mathbf{r}_i(\mathbf{x}) \qquad \text{ s.t } \quad A\mathbf{x} \leq \mathbf{b}$

dónde

$r_i(\mathbf{x})=f_i(\mathbf{x})^2$ if $f_i(\mathbf{x})>0$ , y $r_i(\mathbf{x})=0$ más.

En palabras, esto puede considerarse un problema de mínimos cuadrados donde solo se incluyen los residuos positivos (las $f$ 's). No puedo enfatizar lo suficiente que este no es un caso de ajuste de datos. Soy consciente de lo que sucedería si se usara para la mayoría de los casos de ajuste de datos, donde el resultado sería simplemente una función que está "por encima" de todas las observaciones. La aplicación es para resolver un problema de optimización muy específico que normalmente se resuelve en la norma minmax ( $\min_{\mathbf{x}} ||\mathbf{f}(\mathbf{x})||_\infty$ ). En todos los casos prácticos, la solución no llega a cero, es decir, $||\mathbf{f}(\mathbf{x})||_\infty \neq 0$ debido al comportamiento de las funciones $f$ .

Las funciones $f$ no son lineales y tenemos acceso a sus derivados, de modo que podemos calcular analíticamente el jacobiano sin muchos problemas adicionales.

Con cierto éxito, hemos aplicado un algoritmo de Levenberg-Marquardt donde la función objetivo se formula como anteriormente, es decir, las $f$ 's por debajo de 0 se eliminan de la suma y las filas correspondientes de la J jacobiana se $J$ponen a cero (es decir, J_ {i ,: } = 0$J_{i,:}=0$ if $f_i(\mathbf{x})<=0$ Esto es bastante crudo pero funciona bien, desafortunadamente no hemos podido incorporar las restricciones lineales.

Somos conscientes de una serie de métodos que resuelven el problema NLLSQ con solo restricciones limitadas, pero esos métodos obviamente no resuelven nuestro problema. Hemos encontrado solo un NLLSQ con restricciones lineales, llamado DQED, y lo hemos usado con éxito limitado (no estamos contentos con el número de iteraciones / evaluaciones de funciones) modificando nuestra función objetivo como lo hicimos con Levenberg Marquardt.

Lo que estoy buscando

Cualquier sugerencia de métodos que resuelvan el problema de los mínimos cuadrados no lineales con restricciones lineales. Además, las sugerencias sobre cómo modificar algoritmos para incorporar el hecho de que solo incluimos los residuos positivos son más que bienvenidas. Finalmente, cualquier sugerencia o pensamiento es bienvenido, aunque debo enfatizar nuevamente que la formulación del problema no es incorrecta, aunque me doy cuenta de que no es la más adecuada para la optimización debido a la falta de diferenciabilidad de cuando .r i ( x ) = $r_i(\mathbf{x})$$r_i(\mathbf{x})=0$

Gran parte de mi respuesta a esta pregunta también se aplica aquí; simplemente ignore la parte PDE y finja que estoy hablando de un problema de optimización no lineal común y corriente.

En general, dado que tiene funciones continuas, puede usar métodos de búsqueda directa, aunque la convergencia de esos métodos puede ser más lenta que los métodos correspondientes que usan información derivada de orden superior (que, en este caso, no tiene). También puede intentar buscar solucionadores de optimización no suaves, como los que usan métodos de paquete. El nombre principal en el campo es Frank Clarke, quien desarrolló gran parte de la teoría detrás de la optimización no lisa; De lo contrario, no sé mucho sobre ese cuerpo de literatura.

Supongo que debido a las capacidades no diferenciadas en su objetivo, el uso de métodos que asumen información derivada de primer o segundo orden está causando problemas con la convergencia.

(Años después), como saben, los optimizadores de Levenberg-Marquardt toman un vector completo de funciones y hacen la suma y la cuadratura en su interior. Por lo tanto, verá solo , que es lo que desea, ¿es así?$[f_i]$
f i > $\qquad levmar(\ max(\ [f_i ...],\ 0\ )]$
$f_i > 0$

Las restricciones lineales tienen la misma propiedad que su , que solo importan los términos positivos. Por lo tanto, puede simplemente levmar el lote: (con multiplicado por 1000 o 1000000.) Por supuesto, los tengo que mirar los signos de y , pero eso es fácil. También agregaría un término para evitar que desvíe hasta el infinito.$lin_i(x) \equiv A_i \cdot x - b_i \leq 0$$f_i$
$\qquad levmar(\ max(\ [f_i ...\ lin_i ...],\ 0\ )]$
$lin_i$$Jacobians_i(x)$$f_i$$lin_i$$\|x\|$$x$

(Tanto Scipy least_squares como ceres hacen restricciones de cuadro, pero no veo ninguna forma de mapear regiones a cuadros).$Ax\leq b$