Como lidar com restrições de desigualdade de normas

Quero resolver a tarefa de otimização (convexa):

$max_{r,z}\quad r$
sujeito às duas restrições a seguir \ | z \ | \ leq 1 r \ geq0
‖ z ‖ ≤ 1 r ≥ $r\|x_i\| - x_i^Tz \leq 0 \qquad \forall i=1,\dots, N$
$\|z\| \leq 1$
$r\geq0$

$r$ é um escalar, $z$ é um vetor, os $x_i$ são vetores da mesma dimensão e $\|\cdot\|$é o eucl simples. norma. Pode-se supor que a região viável não esteja vazia.

Existe uma maneira fácil de resolver isso? Eu acho que isso deve ser fácil, porque sem a restrição $\|z\|\leq 1$ , este é apenas um programa linear. Antes de consultar meus pacotes de software, você pode dar uma dica sobre a abordagem geral que é útil para esse tipo de tarefa?
Graças DG

Você tem algumas opções, dependendo de como é crucial que você adote a norma euclidiana de .$z$

1. Use sua formulação como está, com um pequeno ajuste:

   r ″ x i ″ - x T i z ≤ $max_{r,z}\quad r$
   sujeito às duas restrições a seguir
   z T z ≤ 1 r ≥ $r\|x_i\| - x_i^Tz \leq 0 \qquad \forall i=1,\dots, N$
   $z^{T}z \leq 1$
   $r\geq0$

   Esse problema é um programa quadraticamente restrito, para o qual existem muitos solucionadores rápidos por aí, como o CPLEX e o Gurobi. Esse programa específico também é um programa de cone de segunda ordem, programa semidefinido e programa não linear convexo, para que você também possa usar qualquer um desses solucionadores. A razão pela qual substituí a restrição da norma euclidiana por um produto escalar é que as duas restrições são equivalentes, mas a segunda é diferenciável, enquanto a primeira não é. Funções não diferenciáveis ​​requerem algoritmos mais caros e esse problema não exige esse tipo de maquinário, portanto é melhor evitá-lo.

2. Mude a norma de . A norma 1 e a norma infinito são funções lineares dos elementos de , e a substituição da norma euclidiana em sua formulação por uma dessas normas resulta em um programa linear, para o qual os melhores solucionadores tendem a ser comerciais (Gurobi, CPLEX ), mas existem resolvedores livres mais lentos (GLPK, solucionadores no conjunto COIN-OR). Usar a norma 1 significa que qualquer solução para essa formulação também seria uma solução viável da sua formulação atual (ou seja, o uso da norma 1 traria uma restrição à sua formulação atual). Usar a norma infinito significa que qualquer solução para sua formulação atual também seria viável na formulação padrão infinito (ou seja, o uso da norma infinito produziria um relaxamento da sua formulação atual).$z$$z$

Embora seja verdade que os solucionadores de programação linear sejam muito eficientes, eu selecionaria a opção 1, porque os solucionadores de programação com restrições quadráticas também são muito eficientes (em relação aos solucionadores de programação convexos e outros tipos de solucionadores de programação não lineares) e podem resolver formulações grandes (em centenas de milhares de variáveis ​​de decisão, última vez que olhei a literatura). A menos que sua formulação seja surpreendentemente grande, você deve usar um solucionador de programação quadraticamente restrito em série e não precisa alterar a norma em sua formulação, a menos que seja absolutamente necessário.

Uma observação final: eu os vetores antes de construir sua formulação para que todos tenham uma norma de unidade, o que provavelmente ajudará no condicionamento de sua formulação quando você a resolver numericamente. É outro truque que praticamente não custa nada, mas protege contra dificuldades numéricas.$x_{i}$

Como vemos na resposta de Geoffs, esse é um problema quadraticamente restrito muito simples, ou mais geralmente um programa de cone de segunda ordem. Se você não possui requisitos extremos de desempenho ou dimensões enormes, resolvê-lo usando um solucionador não-linear padrão na forma quadrática ou usando um solucionador SOCP na formulação de normas funcionará perfeitamente bem.″ z ″ ≤ $z^Tz \leq 1$$\|z\|\leq 1$

Se você precisar melhorar o desempenho, existem métodos para explorar o recurso de cone único. Aqui está um exemplo

SIAM J. Optim., 17 (2), 459-484. (26 páginas) Um método ativo definido para programas de cone de segunda ordem de cone único E. Erdougan e G. Iyengar

Gostaria de salientar que a substituição da norma por uma norma 1 provavelmente não funcionará bem. A norma quadrática tem sua origem no fundo geométrico desse problema (que eu interpreto como encontrar um vetor que tenha o menor ângulo para um determinado conjunto de vetores).

Curiosamente, uma aproximação de QP do problema parece funcionar extremamente bem. Remova a restrição quadrática e adicione uma penalidade ao objetivo. Eu não ficaria surpreso se for possível provar algo sobre isso.$\alpha z^Tz$

No código abaixo, implementado usando o YALMIP (Disclaimer, desenvolvido por mim) no MATLAB, usando o CPLEX como solucionador, a distância média do verdadeiro e calculado usando as heurísticas do QP é da ordem de , enquanto a distância para a solução da formulação LP (1 norma) está na ordem .z 10 - 6 10 - $z$$z$$10^{-6}$$10^{-1}$

z = sdpvar(5,1);
r = sdpvar(1);

err1 = [];
err2 = [];
for i = 1:1000
    X = randn(5,10);
    Con = [r*sqrt(sum(X.^2,1)) <= z'*X,norm(z,2) <= 1]
    sol = solvesdp(Con,-r)
    if sol.problem == 0 & double(r)>1e-3
        zSOCP = double(z);
        Con = [r*sqrt(sum(X.^2,1)) <= z'*X];
        sol = solvesdp(Con,-r+0.001*z'*z);
        zQP = double(z/norm(double(z)));
        err1 = [err1 norm(zQP-zSOCP)];
        Con = [r*sqrt(sum(X.^2,1)) <= z'*X, norm(z,1)<=1];
        sol = solvesdp(Con,-r);
        zLP = double(z/norm(double(z)));
        err2 = [err2 norm(zLP-zSOCP)];
    end
end

Por fim, o uso de insight geométrico pode levar a uma abordagem muito melhor para resolver esse problema. Você está procurando essencialmente um centro particularmente definido de um conjunto de pontos na esfera unitária.