Solución analítica de problemas lineales de mínimos cuadrados restringidos con límites x ≤ ub

Question

Considerando el siguiente problema lineal de mínimos cuadrados con restricciones: problemas lineales de mínimos cuadrados restringidos con límites x 0

min (1/2) *||(C.x-d)||2 , x<=0

donde d es un escalar( 1*1); C y x son vectores (por ejemplo, C puede ser 1*m y x puede ser m*1). ¿Existe alguna solución analítica para ello? ¿Podemos encontrar el punto óptimo (x) sin utilizar ninguna caja de herramientas de optimización?

Answer 1

Suponiendo que $C$ es una matriz, no hay una solución de forma cerrada para este problema. Con un simple cambio de variable se pueden obtener las restricciones $x \geq 0$ y luego puede utilizar uno de los muchos algoritmos para el problema de los mínimos cuadrados no negativos (NNLS).

Si $C$ es simplemente un vector de filas (notación impar), entonces vea la respuesta de @Michael.

Answer 2

Quieres encontrar $x \in \mathbb{R}^n$ para minimizar $|c^Tx-d|$ con sujeción a $x \leq 0$ , donde $c$ es un vector dado en $\mathbb{R}^n$ y $d$ un número real dado. Esto no es difícil. Una solución óptima $x^*=(x_1^*, ..., x_n^*)$ que tenga como máximo una componente no nula.

Caso 1: Supongamos que $d\geq 0$ :

-Si hay un $i \in\{1, ... ,n\}$ tal que $c_i<0$ Entonces, defina $x_i^*=\frac{d}{c_i}$ y $x_j^*=0$ para todos $j \neq i$ . Entonces $|c^Tx^*-d|=0$ y $x^*\leq 0$ .

-Else, $c_i \geq 0$ para todos $i \in \{1, ..., n\}$ . Así, $c^Tx \leq 0$ para cualquier vector $x$ que satisface $x \leq 0$ . De ello se desprende que $x^*=0$ es óptima.

Caso 2: Supongamos que $d<0$ :

-Si hay un $i \in \{1, ..., n\}$ tal que $c_i>0$ Entonces, defina $x_i^*=\frac{d}{c_i}$ y $x_j^*=0$ para todos $j \neq i$ . Entonces $|c^Tx^*-d|=0$ y $x^*\leq 0$ .

-Else, $c_i \leq 0$ para todos $i \in \{1, ..., n\}$ . Así, $c^Tx \geq 0$ para cualquier vector $x$ que satisface $x \leq 0$ . De ello se desprende que $x^*=0$ es óptima.