1) Sí. Ambas formas admiten siempre a solución, pero no es necesariamente única.
La forma restringida (su segunda formulación) es un poco más fácil de analizar.
Como se observa, el conjunto de restricciones $\mathcal{C} = \{x : \|x\|_0 \leq K\}$ no está acotado, por lo que no es del todo obvio que haya un mínimo. (Más concretamente, no es compacto, por lo que no tenemos las habituales garantías "fáciles" de que existe y se obtiene un mínimo).
Sin embargo, en este caso, podemos garantizar que existe una solución con sólo considerar el problema directamente. El "truco" está en la estructura del conjunto de restricciones. Obsérvese que puede escribirse como la unión de conjuntos más sencillos; por ejemplo, si $K = 4$ entonces
$\begin{aligned}\{x: \|x\|_0 \leq K\} =&\phantom{\cup+}\{x: (x_1, x_2, x_3, x_4) \in \mathbb{R}, (x_5, \dots, x_n) = 0 \} \\ &\cup \{x: (x_1, x_2, x_3, x_5) \in \mathbb{R}, (x_4, x_6, \dots, x_n) = 0 \} \\ &\cup \{x: (x_1, x_2, x_3, x_6) \in \mathbb{R}, (x_4, x_5, x_7, \dots, x_n) = 0 \} \\ &\cup \dots\ \\ =&\bigcup_{S \text{ is a set of 4 integers $\leq N$}} \underbrace{\{x: x_i = 0 \quad \forall i \notin S\}}_{\mathcal{C}_S}\end{aligned} $
Se trata de una unión sobre un conjunto finito de conjuntos convexos, por lo que podemos resolver el problema original simplemente resolviendo $\min_{x \in \mathcal{C}_i} \|Ax - b\|_2^2$ y luego tomar el mínimo sobre todas las soluciones y utilizarlo como nuestra solución global.
En símbolos:
$\begin{aligned} \min_{x \in \mathcal{C}} \|Ax-b\|_2^2 = \min_{S \in \mathcal{S}} \min_{x \in S} \|Ax-b\|_2^2\end{aligned}$ donde $\mathcal{S}$ es el conjunto de (distintos) $K$ -tuplas.
Un poco menos formal, siempre podemos resolver el $K$ -problema disperso, encontrando la mejor solución posible para cada conjunto de a lo sumo $K$ columnas de $A$ y luego simplemente tomar lo "mejor de lo mejor" como nuestra solución global.
Este enfoque de "fuerza bruta" es lento cuando $K$ es mayor que 2 o 3 (ya que tenemos que resolver $\sum_{i=0}^K \binom{n}{i}$ OLS), pero si eres inteligente y tienes un gran ordenador y algo de tiempo para quemar, es factible hasta $n \approx 1000$ . En [1] se dan los detalles escabrosos y en [2] se ofrece un paquete de R que implementa el enfoque de [1].
Si $K$ es grande o si hay redundancia entre las columnas de $A$ (la condición formal es $\text{rank}(A) < K$ ), dos de estos subproblemas pueden dar el mismo valor, por lo que no se garantiza un único $\text{arg min}$ solución, pero siempre tiene una única $\text{min}$ porque es sólo el mínimo sobre un conjunto finito.
2) No. No son del todo equivalentes, pero es cierto que si se tiene una solución a (1) para un determinado $\lambda$ puede elegir un $K$ tal que sea una solución de (2). No siempre se puede encontrar $K$ tal que una solución de (1) que coincide con una solución dada de (2) sin embargo. Este fenómeno se observa en la sección 1.3 de [3], pero no se discute en profundidad.
[1] D. Bertsimas, A. King, R. Mazumder. "Selección del mejor subconjunto a través de una lente de optimización moderna". Annals of Statistics 44(2), p.813-852, 2016. https://projecteuclid.org/euclid.aos/1458245736
[2] https://github.com/ryantibs/best-subset
[3] R.J. Tibshirani. "Grados de libertad y búsqueda de modelos". Statistica Sinica 25, p.1265-1296, 2015.
