Loading [MathJax]/jax/element/mml/optable/GeneralPunctuation.js

7 votos

¿Cómo minimizar sin usar programación lineal?

Hay una forma cerrada de la solución para el problema de minimización \min_{c \in \mathbb{R}}\left\lVert c \mathbf{x} - \mathbf{y}\right\rVert_1 donde \mathbf{x} = \begin{bmatrix}0 & 1 & \dots & n \end{bmatrix}^T e \mathbf{y} \in \mathbb{R}^{n+1} fijo es un vector, y la norma es el 1-norma?

Sé que esto puede ser expresado como la programación lineal \begin{alignat*}{2} & \text{minimize } & & \boldsymbol{1}^T\mathbf{t} \\ & \text{subject to } & &\begin{aligned}[t] -\mathbf{t} \leq c\mathbf{x} - \mathbf{y} \leq \mathbf{t} \\ \end{aligned} \end{alignat*} pero me pregunto si hay otras maneras de solucionar esto? O ¿existen algunas aproximaciones que no requieren la solución de un problema de programación lineal? Gracias.

6voto

SiongthyeGoh Puntos 61

\begin{align}\|cx-y\|_1&= |y_0|+\sum_{i=1}^n|ci-y_i|\\ &=|y_0|+ \sum_{i=1}^n i|c-\frac{y_i}i|\end{align}

Tenga en cuenta que |y_0| no tiene una influencia en la elección de c.

Deje v ser ordenado de vectores que consisten i copias de \frac{y_i}{i} (posiblemente con duplicity), donde 1 \le i \le n. A continuación, c puede ser elegido para ser la mediana del vector v.

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