Cómo resolver un programa lineal por el método de subgradiente

Answer 1

¡Creo que encontré la respuesta! 🙂
1. En el método de subgrado, el TAMAÑO DE PASO debe ser positivo:
(Crédito de la diapositiva: Stefanie J. (por Suvrit Sra), UC Berkeley)
2. el código utiliza el tamaño de pasos de polyak para implementar el método de subgradiente:

pero, aquí el f * no se conoce de antemano. Una solución es usar una versión modificada del tamaño de pasos de Polyak:

(crédito de la diapositiva: Boyd)
En el código anterior, simplemente ignora f * (o f_best) o cualquier aproximación de este. El método que se muestra en la figura anterior converge más rápido. (tenga en cuenta que no puedo imaginar f * = 0 en este caso, porque cuando lo deslizo por programación lineal veo unos (n, 1) ‘* x_min = -1.4083 -> para ver ver esta línea de código “x_min = linprog (unos (n, 1), A, b); “)

El último punto que quiero mencionar para completar mi respuesta es el siguiente:
3. a pesar del vector gradiente, el subgradiente no es único. cualquier hiperplano de soporte puede usarse como un subgradiente. En el código anterior, utiliza la columna de A que hace que Ax-b sea máximo en la x actual. Se puede considerar como la dirección más ascendente / descendente. (porque no tenemos un gradiente real y debemos elegir entre subgraduados).

Realmente lo agradezco, si me notifica mis errores / conceptos erróneos en esta respuesta.