Non-convex QP

[luc27]

Ciao ragazzi,

vi pongo la seguente domanda e spero che qualcuno sia in grado di aiutarmi.

In Linear programming (LP) utilizzando il principio del massimo e assumendo che i vincoli constituiscano una feasible region limitata, é possibile dimostrare che la soluzione del problema é sempre sul bordo della feasible region.

In convex quadratic programming (QP) questo non vale piú, l'ottimo puó essere trovato in qualsiasi regione della feasible region. Basta prendere $ f(x) = x^2 $ con $ x \in [-1,1] $.

Il problema che sto trattando ha una objective function del tipo $ f(x) = xy $ con vincoli lineari e una diseguglianza del tipo $ 0 \leq x \leq1 $; si tratta quindi di non-convex quadratic programming. La mia domanda é la seguente: esiste un risultato che dimostra che l'ottimo di un problema di questo tipo sia sempre sul bordo della feasible region? Oppure non esiste un risultato generale ed é case-dependent? Inoltre, se ció non é vero, sapete darmi un esempio di non-convex QP con ottimo non sul bordo della feasible region?

Se siete a conoscenza di libri o articoli che trattano questo problema, ve ne sono grato.

Grazie in anticipo per le risposte.

[BHK2]

Sfortunatamente per ora mi sono occupato esclusivamente di programmazione lineare, ergo non ho una risposta al tuo quesito.
Tuttavia studiando la programmazione lineare sono incappato in un libro: Linear Programming and Network Flows di Mokhtar S. Bazaraa, John J. Jarvis, Hanif D. Sherali; che a mio parere è un ottimo libro.
Due dei tre autori hanno realizzato (insieme a un terzo) un altro libro che potrebbe essere di tuo interesse: Nonlinear Programming: Theory And Algorithms di M. S. Bazaraa, Hanif D. Sherali e C. M. Shetty.
Ovviamente non avendolo mai letto non so dirti se fa al caso tuo ma magari vale la pena darci un’occhiata.

[gugo82]

@luc27: Leggendo il tuo post c’è un grosso dubbio che mi assale: perché non scrivi in italiano i termini tecnici?
Gli anglismi non necessari non di mostrano maggiore competenza (come credono alcuni bocconiani), danno solo molto fastidio.

Forza, traduciamo insieme…

• “linear programming”: programmazione lineare;
  
  
• “feasible region”: regione ammissibile;
  
  
• “convex quadratic programming”: programmazione quadratica convessa;
  
  
• “objective function”: funzione obiettivo;
  
  
• “non-convex quadratic programming”: programmazione quadratica non convessa;
  
  
• “case-dependent”: dipende dai casi.

Per quanto riguarda la domanda in sé, se la non convessità la vuoi nella funzione obiettivo puoi considerare il problema di estremo per $f(x) := x(1-|x|)$ in $[-1,1]$.

[luc27]

Chiedo scusa se rispondo solo ora, non mi ero accorto delle repliche di gugo e BHK2, che ringrazio molto.

Qualche settimana dopo aver creato il post ho finalmente trovato risposta alla mia domanda; ció che cercavo era un risultato presente in questo articolo:
Panos M. Pardalos, Global optimization algorithms for linearly constrained indefinite quadratic problems, 1991.

P.S: ho sempre studiato su libri scritti in lingua inglese e quasi tutti gli esami che ho fatto erano in lingua inglese. Ora lavoro all'estero e la lingua che si usa é l'inglese. Capisco che forse ne ho abusato ma tante volte mi trovo in difficultá a tradurre termini tecnici in italiano e per evitare confusione dovuta alla terminologia lo scrivo in lingua inglese. Cercheró di utilizzare il piú possibile la lingua italiana da ora in poi.