Restrições envolvendo

16

Suponha

minAvec(U)subject to Ui,jmax{Ui,k,Uk,j},i,j,k=1,,n

onde U é uma matriz n × simétrica n×ne vec(U) remodela U em um vetor unidimensional com n2 entradas.

A parte do programa acima que me causa problemas é o max{,} . (A restrição de soluções para matrizes simétricas não-negativas parece ser direta.)

Agradecemos antecipadamente por qualquer ajuda ou referências!

N21
fonte
alguma razão para você não poder adicionar as duas restrições?
Aron Ahmadia
11
@AronAhmadia: Ele não pode adicionar ambas as restrições, porque isso seria equivalente a Ui,jmin{Ui,k,Uk,j} para todos os i,j,k . Eu não acho que exista uma reformulação do LP desse problema, mas poderia haver uma reformulação do MILP, embora isso provavelmente torne mais caro a solução.
21812 Geoff Oxberry
@ N21: Qual o tamanho que você espera n ser para os problemas que você quer resolver?
21812 Geoff Oxberry
@ Geoff: Obrigado! I última análise, esperamos ter grande n , mas agora eu estou mais preocupado em obter uma solução preliminar com n menos do que, digamos, 100, ou mesmo 10.
N21
Obrigado por esclarecer @GeoffOxberry, não pensei nisso antes de postar.
Aron Ahmadia

Respostas:

14

Edit: Vamos tentar esta explicação novamente, desta vez quando estou mais acordado.

Há três grandes problemas com a formulação (em ordem de gravidade):

  1. Não há reformulação óbvia do problema que seja obviamente suave, convexa ou linear.
  2. Não é bom.
  3. Não é necessariamente convexo.

Nenhuma reformulação suave / convexa / linear óbvia

Primeiro, não existe uma reformulação padrão e óbvia de cada restrição . A sugestão de Aron se aplica à restrição min mais comum , na qual uma restrição como U i jmin k { U i k , U k j } é substituída pelas duas desigualdades equivalentes a seguir: U i jU i k ,maxmin

Uijmink{Uik,Ukj}
L i jL k j ,
UijUik,k
A reformulação não é ideal, cadarestrição mínima foi substituída por 2 n restrições lineares, mas converte um programa não-linear não suave em um programa linear, cuja ordem de magnitude é mais rápida de resolver.
UijUkj,k.
min2n

Wolfgang ressalta que pode ser possível (ele não inclui uma prova) reformular as restrições para que elas sejam lineares e suaves, adicionando variáveis ​​de folga. Uma variável de folga precisa ser adicionada para cada restrição máxima na formulação original, o que significa que estamos adicionando n 2 restrições nessa reformulação. Além disso, toda restrição máxima é substituída por 2 n (mais ou menos) restrições lineares. O verdadeiro assassino é que a não suavidade é movida das restrições para o objetivo, de modo que a formulação de Wolfgang ainda produz um programa não linear não suave.maxmaxn2max2n

Não há uma reformulação padrão das restrições em um problema de minimização que eu conheço, depois de verificar meu livro de programação linear e fazer uma pesquisa na literatura. Isso não significa que essa reformulação não exista; isso apenas significa que não me deparei com isso. Se eu tivesse que adivinhar, diria que não existe uma formulação de LP.max

Não suavidade

Nesse contexto, não suavidade significa que pelo menos uma das funções da formulação (o objetivo ou as restrições) não é duas vezes continuamente diferenciável. As funções não suaves nesta formulação são as funções .max

A não lisura é um grande problema porque:

  • imediatamente torna seu problema não linear
  • a maioria dos solucionadores de programação não-linear assume duas funções continuamente diferenciáveis

Como as funções não são nem uma vez continuamente diferenciáveis, você não pode nem usar os métodos tradicionais de descida de gradiente sem dificuldade. Os algoritmos de programação não linear não suaves são mais lentos do que seus equivalentes suaves.max

Possível não convexidade

Seu problema pode ser não-convexo, porque na "forma padrão" para programas não lineares (ou seja, expressando todas as restrições na forma ), as restrições problemáticas em sua formulação sãog(x)0

Uijmaxk{Uik,Ukj}0,i,j,k.

Essas funções são côncavas.

Prova: Nesse caso, as funções e max k { U i k , U k j } são ambas convexas. A soma das funções convexas é convexa, e multiplicar uma função convexa por -1 resulta em uma função côncava. (QED.)Uijmaxk{vocêEuk,vocêkj}

Como Tim ressalta, apenas porque é não-convexo não significa que seu problema seja realmente não-convexo, mas se você estiver tentando resolver um problema de otimização para otimizar globalmente, poderá garantir apenas que um solucionador de otimização convexo retornará um ótimo global se o seu problema for convexo. Se você realmente deseja um ótimo global, caberia a você determinar se seu conjunto viável é convexo (ou não). Na ausência de tais informações, você deve assumir que seu problema pode não ser convexo e usar algoritmos que não dependem de informações de convexidade. Mesmo assim, a não suavidade e a falta de uma boa reformulação são questões muito maiores.g

Opções para resolver o problema

  • Aceite possivelmente encontrar uma solução viável. Nesse caso, faça o que Aron disse e substitua com U i jmin k { U i k , U k j } ,

    Uijmaxk{Uik,Ukj},i,j,k
    que podem ser reexpressos como duas desigualdades separadas usando uma reformulação padrão do LP. O problema resultante será uma restrição de LP do problema que você deseja resolver; ela deve ser resolvida rapidamente em relação ao seu problema original e, se houver uma solução, essa solução será viável para o seu problema original e seu valor de função objetivo será um limite inferior ao valor ideal de função objetivo de seu problema original.
    Uijmink{Uik,Ukj},i,j,k,
  • Tente sua sorte em sua formulação, como é o caso de um solucionador de pacotes para programas não suaves. Não tenho muita experiência com esses tipos de solucionadores. (Um colega meu os usa em sua pesquisa.) Provavelmente são lentos, pois não podem usar informações derivadas. (Eu acho que eles usam informações de gradiente generalizadas do subgradiente ou de Clarke.) Também é improvável que você consiga resolver grandes instâncias de problemas com um solucionador de pacotes.

Geoff Oxberry
fonte
11
Geoff, coisas boas; isso atinge os pontos principais e oferece muitas idéias e sugestões construtivas. Eu votei. Mas você parece estar tratando a não-convexidade como algo separado do fato de que, como você diz, "não há reformulação padrão das restrições máximas em um problema de minimização que eu conheço". Mas, de fato, o primeiro é precisamente o motivo pelo qual o último não é possível. Restrições não convexas não podem ser expressas em programação linear --- ponto final! Este é um problema não convexo e precisará ser reformulado como um problema de número inteiro misto ou alguma outra heurística aplicada.
Michael Grant
@ MichaelGrant: Eu argumentei esse argumento nas revisões 1 e 2 há mais de um ano e, em seguida, entrei em um longo tópico de comentários sobre minha afirmação de que o problema não é convexo. (Veja a resposta de Tim abaixo.) Como me lembro, na época, Tim argumentou que uma desigualdade com g côncava não torna um conjunto viável não-convexo. Não sei por que, porque, por definição, um programa convexo deve ser capaz de ser expresso de modo que g ( x ) 0 para g convexo. Eu cansei de discutir com Tim sobre isso; Eu deveria reverter algumas das minhas edições anteriores. g(x)0gg(x)0g
Geoff Oxberry
11
É verdade que funções de restrição não convexas podem descrever conjuntos convexos (de fato, a noção de quaseiconvexidade cobre a maioria desses casos). Mas o fato é que descreve um conjunto não convexo em ( x , y , z ) . Portanto, a alegação de Tim é irrelevante para esse problema específico. Também é concebível que a interseção de conjuntos não convexos acabe sendo convexa, mas é uma ocorrência improvável. xmax{y,z}(x,y,z)
Michael Grant
11
Sim, você pode provar essa afirmação em particular porque esse conjunto é o hipógrafo de , e o conjunto definido pelo hipógrafo de uma função é convexo se a função for côncava. max{y,z}
Geoff Oxberry 23/03
3

A solução para sua pergunta é .

Seja ComoAv(U)e suas restrições são lineares emU, qualquer múltiplo positivotde±Usatisfaz as restrições. Portanto,minV(Avec(V))mint(Avec(tU))=-.

U=(1111).
Avec(U)Ut±UminV(Avec(V))mint(Avec(tU))=
Último folego
fonte
Definitivamente, uma solução para a questão apresentada. Meu palpite é que o OP apresentará alguma restrição de não-negatividade em ; nesse caso, o valor ótimo da função objetiva pode não ser - . U
Geoff Oxberry
@GeoffOxberry: Verdadeiro. Mesmo com restrições de positividade em a resposta é 0 . A forma como posou implica que ele é realmente uma questão de otimização da matriz a la 2 tr ( A * L ) = A - L 2 - A2 - U 2 . U02tr(A^U)=A^U2A^2U2
Deathbreath
2

A fim de formular as restrições , criamos n variáveis binárias , b i{ 0 , 1 } , 1 i n . Seja M o limite da variável f , basta adicionar as seguintes restrições:fmax{f1,f2,...,fn}n bi{0,1}1inMf

1) ffi+(1bi)M,i

2) ibi=1

Normalmente, defina se pudermos estimar o valor de f i .M:=maxifiminififi

Kevin
fonte
1

xi<=max(ai1,ai2,...,ain)
xi<=si
si>=ai1
si>=ai2
...
si>=ain
cmax(simax(ai),0)
simax(ai)c

si>=max(ai)xi=sisimax(ai) para problemas que entram na região inviável.)

Wolfgang Bangerth
fonte
É uma boa ideia. Supondo que sua prova seja aprovada, o problema passa a mover a não linearidade e a não suavidade das restrições para o objetivo, as quais ainda são qualidades indesejáveis ​​em uma formulação.
22812 Geoff Oxberry
aij(xi,ai1,ai2,...,ain)(xi,si,ai1,ai2,...,ain)
1

Não consigo encontrar o botão de comentário ...

euog(x)<5

Se for um conjunto convexo, você poderá realizar uma descida gradiente em sua função objetivo, usando algo como o_projection_algorithm de Dykstra para projetar de volta no espaço de restrições.

Tim
fonte
Votado para o comentário sobre funções côncavas; Eu deveria ter pensado mais sobre a minha explicação. Projetar no conjunto viável é uma possibilidade, embora não tenha certeza se você pode aplicar esses algoritmos com restrições não suaves.
precisa
x2+y2<5
"Problemas não-convexos só são difíceis de NP se tiverem um número NP de possíveis soluções." NP significa "polinomial não determinístico". Estou completamente perdido sobre o que você está falando. Em segundo lugar, mencionei concavidade porque funções lineares são côncavas e convexas; a função não é convexa. Só porque a função é não suave e linear por partes não exclui imediatamente a possibilidade de uma reformulação de LP existir.
22612 Geoff Oxberry
vocêEujmink{vocêEuk,vocêkj}
Desculpe, tive que abreviar o comentário, então usei NP para não-polinomial e P para polinonomial. O ponto era que a otimização não convexa nem sempre é difícil para o NP. É difícil para NP se o número de soluções possíveis for pior que o polinomial. Desculpe a confusão :) Você está certo sobre a reformulação como linear. Você parecia dizer "Consequentemente, não há como reformular seu programa como um programa linear", devido à não-convexidade, eu estava apenas observando que não está relacionado à convexidade, mas à linearidade.
Tim
0

0

U0An0

abccmax(a,b)b=ci,j,k

  1. Uij<Ujk=Uik
  2. Uik<Ujk=Uij
  3. Ujk<Uik=Uij
  4. Uij=Ujk=Uik

tG(t)Uij=tUij=Ujk=tUj=tUi=Uk=tG(t)

ps
fonte