Optimisasi Berkendala Menggunakan Metode Gradien Terproyeksi

Abstract

Dalam tulisan ini dibahas tentang metode gradien terproyeksi untuk menyelesaikan masalah optimisasi berkendala dengan kendala yang berbentuk persamaan linear. Pembahasan dimulai dengan memperkenalkan metode gradien untuk menyelesaikan masalah optimisasi tanpa kendala, kemudian metode gradien tersebut digeneralisasikan untuk menyelesaikan masalah optimisasi yang meminimumkan ) ( x f dengan kendala b Ax  , dan f R R A R m n n mxn :  ,  ,  , rank A=m, b 1 mx R  , nx1 xR , dengan menambahkan suatu proyektor orthogonal P I A AA A t t n 1 ( )   .Pada algoritma ( ) ( 1) ( ) (k ) k k k x  x  f x   , diperoleh algoritma gradien terproyeksi ( ) ( 1) ( ) (k ) k k k x  x  Pf x   dengan 0  k  yang merupakan ukuran langkah. Ukuran langkah yang digunakan adalah arg min ( ( )) ( ) ( ) 0k k k  f x  Pf x     , yaitu 0   yang meminimumkan ( ( )) (k ) (k ) f x Pf x , dapat dicari menggunakan metode Secant. Algoritma gradien ini dapat dihentikan jika memenuhi kondisi ( ) 0 ( )   k P f x , dengan kata lain jika ( ) 0 ( )   k P f x , maka titik (k ) x merupakan titik peminimal dan merupakan titik peminimal global untuk fungsi f yang konveks.