7 votos

Encontrar el minimizer de $w_1 \|x - a\|_1 + w_2 \|x - b\|_2$

Encontrar $$\arg\min_{x \in \mathbb{R}^n} w_1\|x - a\|_1 + w_2\|x - b\|_2$$

Estoy tratando de evaluar

$$\hat{x} := \arg\min_{x \in \mathbb{R}^n} w_1\|x - a\|_1 + w_2\|x - b\|_2 \tag{1}$$

para encontrar una forma cerrada, o al menos de una forma más simple expresión, en términos de $w_1 > 0, w_2 > 0, a \in \mathbb{R}^n$, e $b \in \mathbb{R}^n$. Mientras que esto es vago, estoy esperando a tener una expresión que es razonablemente interpretables.

Solución intento yo

En mi primer intento de encontrar una forma cerrada, tomé el subgradiente, que puede encontrar un candidato minimizer. Desde el primer fin de condición, sabemos que $\hat{x}$ cumple que el subgradiente de el objetivo en (1) es igual a cero; es decir, $$0 = w_1 \hat{z} + w_2 \frac{\hat{x}-b}{\|\hat{x}-b\|_2},$$ donde

$$\hat{z} \in \begin{cases} \{\mathrm{sgn}(\hat{x} - a)\} & \mathrm{ if } \hat{x} \ne a \\ [-1,1] & \mathrm{ if } \hat{x} = a \end{cases}$$

Si bien esta es una caracterización de $\hat{x}$, lo que no está claro para mí cómo proceder a encontrar una forma cerrada.

Solución intente II

Como un segundo intento, he intentado utilizar la dualidad para encontrar una expresión más sencilla.

Mediante la introducción de $y = x-a$, podemos ver que este problema es equivalente a $$\hat{y} = \arg\min_{y \in \mathbb{R}^n} w \|y\|_1 + \|y - (b-a)\|_2,$$ where $w = \frac{w_1}{w_2}$. By the Lagrangian duality, we know that there exists some $C \in \mathbb{R}$, de modo que \begin{align} \hat{y} & = \arg\min_{\|y\|_1 \le C} \|y - (b-a)\|_2 \\ & = \arg\min_{\|y\|_1 \le C} \|y - (b-a)\|_2^2 \\ & = \arg\min_{y} \|y - (b-a)\|_2^2 + \lambda \|y\|_1 \\ & = \mathrm{sgn}(b-a) \left( |b-a| - \lambda \right)_+, \end{align} es sólo suave umbral, para algunos variable dual de $\lambda$ que depende del $C$ $b-a$ de alguna manera que no entiendo. Esta parece ser una forma cerrada, pero, puesto que el $\lambda$ no es una forma cerrada de la función de $w_1, w_2, a$$b$, esto no satisfacer lo que estoy buscando.

0voto

Eric Fisher Puntos 306

Voy a resolver primero para el caso de $\mathbb{R}^1$. A continuación, voy a usar esa intuición para resolver general.

Escriba su función objetivo como $f(x)$. Es real valorados, y es suave todo el mundo, sino $a=x$$x=b$. Voy a utilizar la notación que $\hat{x}$ es un minimizer.

Si $a=b$, entonces la solución es trivial $\hat{x}=a=b$. Así que supongamos $a \ne b$. También voy a suponer que $w_1 >0$$w_2 > 0$; de lo contrario, la solución es nuevo trivial.

En este sencillo caso, la función objetivo es simplemente $$ f(x)=w_1|x-a|+ w_2\sqrt{(b-x)^2} $$ Esta función es minimizado mediante el establecimiento $\hat{x}=a$ si $w_1 \ge w_2$ $\hat{x}=b$ lo contrario. (Si $w_2=w_1$, ninguna de las $x$ $a$ $b$ es un minimizer.)

Ahora voy a tratar de extender esta solución a $\mathbb{R}^n$.

El objetivo de la función de $f(x)$ es continuo, y en cualquier delimitada $X \subset \mathbb{R}^n$ que contiene $a$ $b$ es compacto. Por lo $f(x)$ alcanza un mínimo en $X$. Sabemos que el minimizer $\hat{x}$ va a satisfacer $$ f(\hat{x}) \le min\{f(a),f(b) \}= min \{w_1 \paralelo a - b \parallel_1,w_2\paralelo a - b \parallel_2 \} $$ Escribir $I_i=[min\{a_i,b_i\} , max\{a_i,b_i\}]$. Observe que $\hat{x}_i \in I_i$ porque de lo contrario la función objetivo podría ser hecho menor moviendo $\hat{x}_i$ en ese intervalo cerrado. Ahora pon $X=I_1 \times \cdots \times I_n$. A partir de ahora, vamos a restringir $f(.)$ a de este pacto de dominio. Deje $U \subset \mathbb{R}^n$ ser un conjunto abierto que contiene a $X$. Observe además que la $f(x)$ es suave todo el mundo en $U$, excepto en $x_i = a_i$ o $x = b$. Por lo $f(.)$ es suave, incluso en el límite de $X$, excepto en aquellos valores.

La condición necesaria de primer orden con respecto a a $x_i$ es $$ \begin{array}{c} \partial f / \partial x_i = \pm w_1 - w_2 \dfrac{b_i - \hat{x}_i}{\parallel b-\hat{x} \parallel_2}= 0 \\ \pm w_1 = w_2 \dfrac{b_i - \hat{x}_i}{\parallel b- \hat{x} \parallel_2}. \end{array} $$ desde $w_1 > 0$$w_2 > 0$, ninguno de los $\hat{x}_i=b_i$ si $\hat{x}=b$. Sumando los cuadrados, obtenemos: $$ n w_1^2 = w_2^2 \sum_i \dfrac{(b_i - \hat{x}_i)^2}{\paralelo b-\hat{x} \parallel_2^2} \\ n w_1^2=w_2^2 $$ que no puede ser cierto en general, ya que $w_1$ $w_2$ son arbitrarias. Si esto fuera cierto, entonces cualquier $\hat{x}$ en el interior de $X$ sería un minimizer.

Hemos demostrado que $\hat{x_i}=a_i$ algunos $i$ o $\hat{x}=b$, excepto para el caso especial cuando $nw_1^2=w_2^2$.

Si $\hat{x}_i=a_i$, luego alejarse de $a_i$ no debe disminuir la función objetivo. Por lo tanto: $$ w_1^2 \ge w_2^2 \dfrac{(b_i-a_i)^2}{\paralelo b-\hat{x} \paralelo^2_2}, $$ con la igualdad de los índices para que $\hat{x}_j \ne a_j$. El cuadrado y sumando de nuevo, obtenemos: $$ nw_1^2 \ge w_2^2 $$ Por lo tanto, si $w_1$ es lo suficientemente grande, entonces hay algo de $x_i=a_i$. Esta es la generalización de la condición de $w_1 \ge w_2$ para el caso de que $n=1$.

Podemos decir más. Vamos $$ \begin{array}{c} m_i=\dfrac{(b_i-a_i)^2}{\parallel b- a \parallel_2^2} \\ \end{array} $$ y aviso que $$ \begin{array}{c} m_i < \dfrac{(b_i-a_i)^2}{\parallel b - \hat{x} \parallel_2^2} \\ \end{array} $$ para cualquier $\hat{x} \ne a$. A continuación, escriba $m = min \{m_1, ..., m_n\}$$M=max \{m_1, ..., m_n\}$. Si $m_i \le m_k$$\hat{x}_k =a_k$, entonces sabemos que $\hat{x}_i=a_i$. Así que si $w_1 \ge M w_2$$\hat{x}=a$. Y si $w_1 < m w_2$, $\hat{x}_i \ne a_i$ cualquier $i$.

Si $w_1 < m w_2$, entonces la fórmula de los mínimos cuadrados da $\hat{x}$. Deje $y=sign(a_i-b_i)w_1/w_2$. Entonces $$ \hat{x} = b(b^Tb)^{-1}b^Ty $$

Por último, si $\hat{x}=b$, alejándose de cualquier $b_i$ no debe disminuir la función objetivo. Sólo necesitamos considerar $x_i=a_i$. Ahora no podemos utilizar el primer orden de condición. Por lo tanto $$ w_1^2 \le w_2^2 (b_i-a_i)^2 $$ para cada $i$. Sumar de nuevo, podemos ver: $$ nw_1^2 \le w_2^2 \paralelo b-a \parallel_2^2 $$ Así que para los de bajo pena de $w_1$, ponemos a $\hat{x} = b$

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X