Non-convex QP
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.
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.
Risposte
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.
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.
@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…
Gli anglismi non necessari non di mostrano maggiore competenza (come credono alcuni bocconiani), danno solo molto fastidio.
Forza, traduciamo insieme…
[*:97k5kw4h] “linear programming”: programmazione lineare;
[/*:m:97k5kw4h]
[*:97k5kw4h] “feasible region”: regione ammissibile;
[/*:m:97k5kw4h]
[*:97k5kw4h] “convex quadratic programming”: programmazione quadratica convessa;
[/*:m:97k5kw4h]
[*:97k5kw4h] “objective function”: funzione obiettivo;
[/*:m:97k5kw4h]
[*:97k5kw4h] “non-convex quadratic programming”: programmazione quadratica non convessa;
[/*:m:97k5kw4h]
[*:97k5kw4h] “case-dependent”: dipende dai casi.[/*:m:97k5kw4h][/list:u:97k5kw4h]
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]$.
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.
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.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo