Máximo de uma combinação convexa sobre um casco convexo de variáveis ​​reais

x∈R

Estou procurando uma maneira rápida de resolver o problema acima sem usar um solucionador de LP. Existe um procedimento rápido a seguir? (além do Simplex).

Obrigado!

A solução ideal é a seguinte: Defina todas as variáveis ​​iguais aos seus mínimos. Em seguida, começando do maior para o menor, iterativamente, defina o correspondente o maior possível, até que você pressione . Se ou , o problema é inviável. Eu acredito que esta é a mesma solução que o algoritmo de Geoffrey Irving produz.x i Σ i x i = 1 Σ i x i , m i n > 1 Σ i x i , m um x < $a_i$$x_i$$\sum_i x_i = 1$$\sum_i x_{i,min} > 1$$\sum_i x_{i,max} < 1$

A razão pela qual isso funciona é que você pode transformar seu problema no relaxamento de LP do problema da mochila 0-1 via

No espaço variável em , o problema se torna Maximizar Σ i c i y i Sujeito a 0 ≤ y i ≤ 1 ,  para cada  $y$

onde , , e . Se o problema original for possível, . Os e 'não são negativos, então temos o relaxamento de LP de 0-1 mochila. (A expressão aparece tecnicamente no objetivo, mas como é uma constante, podemos eliminá-lo.)b i = ( x i , m a x - x i , m i n ) d = 1 - ∑ i x i , m i n d ≥ 0 c i b i ∑ i a $c_i = a_i (x_{i,max} - x_{i,min})$$b_i = (x_{i,max} - x_{i,min})$$d = 1 - \sum_i x_{i,min}$$d \geq 0$$c_i$$b_i$$\sum_i a_i x_{i,min}$

Supondo que as variáveis ​​sejam classificadas pela razão do maior para o menor, a solução ótima conhecida é a ambiciosa: Defina para o maior possível , defina e defina . Transformar essa solução novamente no espaço do problema com variável fornece a solução que acabei de descrever.y1=y2=⋯=yk=1kyk+1=d-∑ k i = 1 biyk+2=⋯=yn=0$\frac{c_i}{b_i} = a_i$$y_1 = y_2 = \cdots = y_k = 1$$k$$y_{k+1} = d - \sum_{i=1}^k b_i$$y_{k+2} = \cdots = y_n = 0$$x$

Além disso, a mochila 0-1 possui uma restrição vez de uma restrição . Se você puder ajustar todos os itens da mochila com espaço sobrando, o problema original da variável é inviável porque .= x ∑ i x i , m a x < $\leq$$=$$x$$\sum_i x_{i,max} < 1$

O algoritmo ganancioso funciona: comece com uma solução que atenda às suas restrições e aumente iterativamente o com o maior que não esteja em e o com o menor que não esteja em o mais longe possível. Pare quando nenhum movimento de par adicional for possível. Isso leva para classificar e tempo para o resto.a i x max x j a j x min O ( n log n ) a O ( n $x_i$$a_i$$x_{\max}$$x_j$$a_j$$x_{\min}$$O(n \log n)$$a$$O(n)$

Quando o algoritmo for concluído, haverá um conjunto de preso em (aqueles com grande ), um conjunto de preso em (aqueles com pequeno ) e em mais um com e . Uma mudança diferencial em iniciada a partir dessa posição não pode aumentar o objetivo, pois quaisquer ganhos devido ao aumento de ou seriam mais do que compensados ​​por perdas devido à diminuição de ou .x max a i x j x min a j x k x min < x k < x max a i > a k > a j x x j x k x i x $x_i$$x_{\max}$$a_i$$x_j$$x_{\min}$$a_j$$x_k$$x_{\min} < x_k < x_{\max}$$a_i > a_k > a_j$$x$$x_j$$x_k$$x_i$$x_k$