El subgradiente de la diferencia mínima absoluta unidimensional (LAD)

Question

Intento resolver el siguiente problema de optimización unidimensional de diferencia mínima absoluta (DMA)

y estoy utilizando el método de bisección para encontrar la mejor beta (un escalar). Tengo el siguiente código:

import numpy as np
x = np.random.randn(10)
y = np.sign(np.random.randn(10))  + np.random.randn(10)

def find_best(x, y):
    best_obj = 1000000
    for beta in np.linspace(-100,100,1000000):
        if np.abs(beta*x - y).sum() < best_obj:
            best_obj = np.abs(beta*x - y).sum()
            best_beta = beta
    return best_obj, best_beta

def solve_bisect(x, y):
    it = 0
    u = 100
    l = -100
    while True:
        it +=1

        if it > 40:
            # maxIter reached
            return obj, beta, subgrad

        # select the mid-point
        beta = (l + u)/2

        # subgrad calculation. \partial |x*beta - y| = sign(x*beta - y) * x. np.abs(x * beta -y) > 1e-5 is to avoid numerical issue
        subgrad = (np.sign(x * beta - y) * (np.abs(x * beta - y) > 1e-5) * x).sum()
        obj = np.sum(np.abs(x * beta - y))
        print 'obj = %f, subgrad = %f, current beta = %f' % (obj, subgrad, beta)

        # bisect. check subgrad to decide which part of the space to cut out
        if np.abs(subgrad) <1e-3:
            return obj, beta, subgrad
        elif subgrad > 0:
            u = beta + 1e-3
        else:
            l = beta - 1e-3
brute_sol = find_best(x,y)
bisect_sol = solve_bisect(x,y)
print 'brute_sol: obj = %f, beta = %f' % (brute_sol[0], brute_sol[1])                                                                                                                                         
print 'bisect_sol: obj = %f, beta = %f, subgrad = %f' % (bisect_sol[0], bisect_sol[1], bisect_sol[2])

Como puedes ver también tengo una implementación de fuerza bruta que busca sobre el espacio para obtener la respuesta del oráculo (hasta cierto error numérico). Cada ejecución puede encontrar el mejor óptimo y el valor objetivo mínimo. Sin embargo, el subgrad no es 0 (ni siquiera cerca). Por ejemplo, en una de mis ejecuciones obtuve lo siguiente:

brute_sol: obj = 10.974381, beta = -0.440700
bisect_sol: obj = 10.974374, beta = -0.440709, subgrad = 0.840753

Valor objetivo y mejor son correctos, pero subgrad no se acerca a 0 en absoluto. Así que la pregunta:

1. ¿por qué el subgrado no se acerca a 0? ¿La condición óptima no es que 0 esté en el subdiferencial si y sólo si es óptimo?
2. ¿Qué criterio de detención deberíamos utilizar en su lugar?

Answer 1

1. Creo que puede ser porque el subdiferencial del valor absoluto $f(x)=|x|$ es un ligero desplazamiento Función de Heaviside $\partial_p f(x) = 2H_0(x)-1$ . Así que podría ser numéricamente difícil obtener exactamente cero. (Véase también aquí ).

2. En su lugar, creo que deberías buscar un salto grande y un cambio de signo en el subgradiente.