Otimização multicritério

Otimização multicritério (também chamada de programação multicritério, em inglês multi-objective optimization, multi-criteria optimization) é a área da otimização matemática que estuda problemas de otimização simultânea de duas ou mais funções objetivo (critérios), que geralmente entram em conflito entre si. Formalmente, o problema é expresso como a minimização de uma função objetivo vetorial sobre um conjunto de soluções viáveis.

Definição e terminologia

O problema de otimização multicritério em sua forma geral é escrito da seguinte maneira: $\underset{x\in S}{\min }\{f_1(x),f_2(x),\dots ,f_k(x)\}$ onde $S\subseteq {\mathbb{ℝ}}^n$ é um conjunto não vazio de soluções viáveis, e $f_i:S\to \mathbb{ℝ}$ são as funções objetivo ($k\ge 2$). O vetor $f(x)=(f_1(x),\dots ,f_k(x))$ é chamado de vetor objetivo.

Diferentemente da otimização escalar, na formulação multicritério, geralmente não existe uma única solução que melhore os valores de todos os critérios simultaneamente. Portanto, o conceito clássico de ótimo é generalizado usando o conceito de otimalidade de Pareto.

• Solução de Pareto (solução Pareto-ótima ou eficiente): uma solução viável $x^{*}\in S$ para a qual não existe outra solução $x\in S$ tal que $f_i(x)\le f_i(x^{*})$ para todo $i=1,\dots ,k$, e $f_j(x)<f_j(x^{*})$ para pelo menos um índice $j$. Em outras palavras, uma solução é Pareto-ótima se nenhum valor de critério pode ser melhorado sem piorar pelo menos um outro critério.
• Fronte de Pareto (ou conjunto de Pareto): o conjunto de todos os vetores objetivo correspondentes às soluções Pareto-ótimas.
• Solução fracamente Pareto-ótima: uma solução $x^{*}\in S$ para a qual não existe outra solução $x\in S$ tal que $f_i(x)<f_i(x^{*})$ para todo $i$.

Propriedades e teoremas chave

• Teorema da soma ponderada: Em problemas convexos (onde todas as funções $f_i(x)$ e o conjunto $S$ são convexos), qualquer solução Pareto-ótima $x^{*}$ é uma solução para o problema escalar de minimização da soma ponderada dos critérios $\underset{x\in S}{\min }\sum _{i=1}^k{w}_i{f}_i(x)$ para algum conjunto de pesos não negativos $w_i\ge 0$. No entanto, em problemas não convexos, este método pode não encontrar algumas partes da fronteira de Pareto.

• Condições de otimalidade de Karush-Kuhn-Tucker (KKT): As condições necessárias de otimalidade para problemas suaves são generalizadas para o caso multicritério. Em um ponto Pareto-ótimo, existe um conjunto não nulo de multiplicadores não negativos (pesos) para os quais os gradientes das funções objetivo e das restrições ativas são linearmente dependentes.

• Propriedades do conjunto de soluções: A fronteira de Pareto possui várias características qualitativas importantes. Seus limites são definidos pelo ponto ideal (composto pelos mínimos de cada critério individualmente) e pelo ponto nadir (composto pelos máximos de cada critério na fronteira).

Exemplos

• Problema linear: Minimizar $f_1(x)=-x_1$ e $f_2(x)=-x_2$ sujeito às restrições $x_1+x_2\le 1$, $x_1,x_2\ge 0$. Neste caso, a melhoria de um critério (por exemplo, aumentar $x_1$) leva inevitavelmente à piora do outro (diminuir $x_2$). O conjunto de soluções Pareto-ótimas é o segmento de reta $x_1+x_2=1$.
• Problema não convexo: Minimizar $f_1(x)=x^2$ e $f_2(x)=(x-2{)}^2$ no intervalo $[0,2]$. A fronteira de Pareto é não convexa. O método da soma ponderada com pesos positivos não conseguirá encontrar soluções no interior desse intervalo (por exemplo, no ponto $x=1$), pois a combinação linear dos critérios atingirá seu mínimo apenas nos pontos extremos $x=0$ ou $x=2$.

Conceitos relacionados e aplicações

A otimização multicritério está intimamente relacionada à tomada de decisão multicritério (MCDM), que estuda a escolha da melhor alternativa levando em conta as preferências do tomador de decisão. Os principais métodos para transformar um problema multicritério em um escalar (escalarização) incluem:

• Método da soma ponderada.
• Método das $\epsilon$-restrições: Um critério é otimizado, enquanto os outros são convertidos em restrições da forma $f_i(x)\le {\epsilon }_i$. Este método é capaz de encontrar soluções em partes não convexas da fronteira.

A otimização multicritério tem ampla aplicação em projeto de engenharia, economia (por exemplo, otimização de portfólio), gestão e ecologia.

Ver também

• Otimalidade de Pareto
• Otimização vetorial
• Teoria da decisão
• Sistemas de apoio à decisão
• Pesquisa operacional