¿Cuál es la ventaja de añadir $\log$ ¿Barrera para resolver un programa lineal?

Question

Dejemos que $A \in \mathbb{R}^{n \times m}$ , $b \in \mathbb{R}^{n}$ y $x \in \mathbb{R}^{m}$ . Sea $Ax \leq b$ sea el conjunto de inecuaciones lineales que pueden escribirse como $a_i^Tx-b_i \leq 0 \,\,\,\,\forall i= 1, \ldots , m$ . Consideremos el siguiente programa lineal

$$ \min_{Ax\ \leq\ b} c^Tx \tag{1} $$ donde $c \in \mathbb{R}^{m}$ es un vector arbitrario. Si este problema tiene solución, entonces según el teorema de la representación (o de Weyl-Minkowski) la solución ocurre en los vértices del conjunto de restricciones. Optimización convexa en la página 499 dice $f(x)=-\sum_{i=1}^m \log (b_i -a_i^Tx)$ es una autoconcordancia $\log$ función de barrera para desigualdades lineales. Por lo tanto, el problema de restricción anterior puede ser un problema sin restricciones como $$ \min_{x \in \mathbb{R}^{m}} c^Tx -\sum_{i=1}^m \log (b_i -a_i^Tx) \tag{2} $$

Sean las soluciones de (1) y (2) $x_1^\ast$ y $x_2^\ast$ respectivamente.

1- ¿Las soluciones son las mismas ( $x_1^\ast=x_2^\ast$ )? (Es decir, la barrera prohíbe al algoritmo acercarse a la frontera del conjunto de restricciones porque va al infinito. Sin embargo, la solución está en la frontera. ¿Cómo puede (2) atrapar la solución?)
2- En términos de iteraciones y complejidad del algoritmo ¿cuál es superior? Sé que para (2) podemos utilizar el método de Newton para encontrar la respuesta, pero ¿cómo acelerar el algoritmo utilizando el método de Newton?

3- ¿Podemos demostrar analíticamente que los dos problemas son iguales o que uno tiene superioridad sobre el otro?

Por favor, aborden mis preguntas cuidadosamente aportando pruebas rigurosas.

Answer 1

1. No, las soluciones no son las mismas. En la página 499, el libro se limita a presentar un ejemplo de función autoconcordante.

2. Cuando pregunta por la complejidad del algoritmo para el problema (1), ¿en qué algoritmo está pensando? En este punto del desarrollo del libro, no está claro cómo resolver el problema (1) de forma eficiente. El libro presentará una estrategia que utiliza funciones log-barrera en el capítulo 11.

3. No, los problemas no son equivalentes.

Debe leer el capítulo 11 (Métodos de punto interior), y específicamente la sección 11.2, que presenta una estrategia para minimizar $f_0(x)$ con sujeción a las restricciones $f_i(x) \leq 0, Ax = b$ resolviendo un secuencia de subproblemas de la forma \begin{align} \text{minimize} & \quad f_0(x) + \sum_{i=1}^m - (1/t) \log(-f_i(x)) \\ \text{subject to} &\quad Ax = b \end{align} con valores crecientes de $t$ . Se utiliza el método de Newton para resolver cada subproblema. Como $t$ aumenta, la solución del subproblema se convierte en una mejor aproximación a la solución del problema original. Así es como se utilizan las funciones de barrera logarítmica para resolver problemas con restricciones de desigualdad.