Analisis Karakteristik Fungsi Lagrange

Abstract

The Lagrange problem, with a non-differentiable convex objective function, is usually solved by using the subgradient method, whose convergence is guaranteed if the optimal value of the dual objective function is know. In practice, thisoptimal value is approximated by a previously computed bound. In this work, we combine the subgradient method with a different choice of steplength, based on the recently developed spectral projected gradient method, that does not require either exact or approximated estimates of the optimal value. We also add a momentum term to the subgradient dirction that accelerates the convergence process towards global solutions. To illustrate the behavior of our new algoritm we solve Lagrange problem associated with integer programming problem. In particular, we present encouraging numerical result for set covering problems and generalzed assignment problems.

Masalah fungsi Lagrange, dengan fungsi objektif tidak linier, biasanya diselesaikan dengan menggunakan metode subgradien, yang konfergensinya dijamin jika nilai optimasi dari dua fungsi objektif diketahui. Pada prkateknya nilai optimal kurang diketahui dalam menghitung batas sebelumnya. Dalam penelitian ini, kita menggabungkan metode subgradein dengan pilihan dari nilai optimal. Biasanya kita menambahkan daya gerak pada arah subgradien yang proses akselerasinya dipusatkan ke dalam masalah yang umum dan untuk uraian dari algoritma yang baru, kita selesaikan dengan komponen Lagrange dengan program bilangan bulat. Faktanya, kita menyajikan hasil dari sekumpulan masalah dan masalah umum.