Electronic Theses and Dissertation

Convex quadratic programming (cqp) merupakan salah satu bentuk pemrograman nonlinier yang memiliki fungsi tujuan berbentuk kuadrat dengan kendala linier. sebagai pendekatan penyelesaiannya, penelitian ini menerapkan metode primal dual interior point, yaitu metode yang memulai perhitungan dari dalam wilayah layak yang memenuhi semua kendala, kemudian mendekati batas kendala menuju solusi optimal. proses iterasi diawali dengan tebakan awal positif dan dihentikan ketika seluruh kendala primal dual terpenuhi dengan galat sangat kecil, lalu secara bertahap mengurangi parameter barrier dan mengarahkan nilai primal dan dual menuju titik yang memenuhi kondisi karush kuhn tucker (kkt) sebagai syarat optimalitas pada masalah cqp. penelitian ini bertujuan untuk menerapkan metode primal dual interior point pada tiga kasus cqp dengan jumlah variabel dan kendala yang berbeda, menganalisis hasil penerapannya dalam mencapai solusi optimal dan membandingkan hasil penerapannya dengan metode beale. nilai primal dan dual yang awalnya berbeda secara bertahap bergerak mendekati titik yang sama seiring proses iterasi, sementara nilai residual menurun mendekati nol, menandakan bahwa seluruh kendala dan kondisi kkt terpenuhi. pada kasus 1 diperoleh nilai fungsi tujuan primal sebesar -1,249984 dan nilai dual -1,250036 dengan selisih 0,000052, pada kasus 2 nilai primal -1,458319 dan nilai dual -1,458362 dengan selisih 0,000043, serta pada kasus 3 nilai primal 26,709187 dan nilai dual 26,709161 dengan selisih 0,000026. hasil penelitian menunjukkan bahwa metode primal dual interior point mencapai solusi optimal pada ketiga kasus secara konsisten membutuhkan 9 iterasi. jumlah iterasi ini dipengaruhi oleh beberapa faktor, yaitu pemilihan nilai batas toleransi, nilai parameter step length dan nilai awal variabel x, u, dan v.

Convex Quadratic Programming (CQP) is a form of nonlinear programming with a quadratic objective function and linear constraints. As a solution approach, this study applies the Primal Dual Interior Point method, which begins the computation from a feasible region that satisfies all constraints and then moves toward the boundary to reach the optimal solution. The iterative process starts with a positive initial guess and terminates when all primal-dual constraints are satisfied with a very small error. The barrier parameter is gradually reduced, directing the primal and dual values toward a point that satisfies the Karush-Kuhn-Tucker (KKT) conditions as the optimality criteria in CQP problems. This study aims to implement the Primal Dual Interior Point method on three CQP cases with different numbers of variables and constraints, analyze its performance in achieving optimal solutions, and compare its results with the Beale method. The primal and dual values, initially different, progressively converge to the same point as the iterations proceed, while the residual values decrease toward zero, indicating that all constraints and KKT conditions are satisfied. In case 1, the primal objective value was -1,249984 and the dual -1,250036 with a difference of 0,000052, in case 2, the primal was -1,458319 and the dual -1,458362 with a difference of 0,000043, and in case 3, the primal was 26,709187 and the dual 26,709161 with a difference of 0,000026. The results show that the Primal Dual Interior Point method consistently achieved optimal solutions in all three cases with nine iterations. The number of iterations is influenced by several factors, including the chosen tolerance level, the step length parameter, and the initial values of the variables x, u, and v.