Classificando como um programa linear

Um número surpreendente de problemas tem reduções bastante naturais na programação linear (LP). Veja o Capítulo 7 de [1] para exemplos como fluxos de rede, correspondência bipartida, jogos de soma zero, caminhos mais curtos, uma forma de regressão linear e até avaliação de circuitos!

Como a avaliação do circuito se reduz à programação linear, qualquer problema em deve ter uma formulação de programação linear. Portanto, temos um "novo" algoritmo de classificação, via redução para um programa linear. Então, minhas perguntas são$P$

1. Qual é o programa linear que classificará uma matriz de números reais?$n$
2. Qual é o tempo de execução do algoritmo de classificação reduzir para LP e resolver?

1. Algoritmos de S. Dasgupta, C. Papadimitriou e U. Vazirani (2006)

A resposta a seguir é basicamente equivalente à que você já conhece, mas pode parecer um pouco menos "mágica". Por outro lado, é mais técnico, mas acredito que a técnica geral "escreva seu problema como uma otimização em matrizes de permutação e invoque Birkhoff-von Neumann" é excelente.

Para uma permutação de { 1 , … , n } defina a matriz de permutação P σ como a matriz 0-1, de modo que P i j = 1 se j = σ ( i ) e P i j = 0 caso contrário. Esta é simplesmente a matriz que permite as coordenadas de um vetor x de acordo com σ : se y = P σ x então y i = x $\sigma$$\{1, \ldots, n\}$$P_\sigma$$P_{ij} = 1$$j = \sigma(i)$$P_{ij}=0$$x$$\sigma$$y = P_\sigma x$ . Denotareiy= P σ xcomoσ(x) apartir de agora.$y_i = x_{\sigma(i)}$$y=P_{\sigma}x$$\sigma(x)$

Mais uma definição: um não negativo matriz H é duplamente estocástica se cada uma das suas linhas e cada uma das suas colunas montantes para um.$n\times n$$M$

E um fato que é muito importante na otimização combinatória - o teorema de Birkhoff-von Neumann:

Uma matriz é duplamente estocástica se, e somente se, for uma combinação convexa de matrizes de permutação, isto é, se e somente se existirem permutações σ 1 , … , σ k e reais positivos α 1 , … , α k tais que M = ∑ k i = 1 α i P σ i e $M$$\sigma_1, \ldots, \sigma_k$$\alpha_1 , \ldots, \alpha_k$$M = \sum_{i = 1}^k{\alpha_i P_{\sigma_i}}$.$\sum{\alpha_i} = 1$

Observe que uma matriz duplamente estocástica é definida pelas desigualdades

∀ j : n ∑ i = 1 M i j = 1 ∀ i , j : M i j ≥

$P$

Portanto, dada uma entrada a ser classificada, precisamos apenas apresentar um objetivo linear f a ( $a = (a_1, \ldots, a_n)$$f_a(M)$

• $f_a(P_\tau) < f_a(P_\sigma)$$\sigma(a)$$\tau(a)$

$f_a(M)$$P_\sigma$$\sigma$$\sigma(a)$$\sigma$$P_\sigma$

$f_a(M)$$v^T M a$$v = (1, \ldots, n)$

• $M$
• $P_\sigma$$f_a(P_\sigma) = \sum_{i = 1}^n{i a_{\sigma(i)}}$
• $\sigma$$\sigma(a)$$\sigma(a)$

E pronto, você tem um programa linear para classificação. Parece bobagem para classificação, mas esse é, de fato, um método poderoso de otimização.