最优化-lec9 Duality 最优化理论与方法课件（英文版－南京大学）.pptVIP

The Primal-Dual Interior-Point Method To present the primal-dual method, we consider a linear program in standard form (the primal problem) The corresponding dual linear program is The Primal-Dual Interior-Point Method The main idea of the primal-dual method is: to move through a sequence of strictly feasible primal and dual solutions that come increasingly closer to satisfying the complementary slackness conditions. The Primal-Dual Interior-Point Method Thus, the algorithm attempts to find a sequence of primal and dual feasible solutions with decreasing duality gaps If the duality gap were zero then the points would be optimal Closeness to the solution will be measured by the size of the duality gap The Primal-Dual Interior-Point Method In the primal-dual algorithm the main computational effort is solving the primal-dual equations (PD). To save computation, we shall not solve them exactly, but only approximately. The requirements for primal feasibility The requirements for dual feasibility The Primal-Dual Interior-Point Method The equations for complementary slackness Nonlinear Equations! Linear Equations! At each iteration of the primal-dual method we perform one iteration of Newton’s method for solving (PD). The Primal-Dual Interior-Point Method The Primal-Dual Interior-Point Method Then the solution vectors can be written as The algorithm is as follows: The Primal-Dual Interior-Point Method E.g., Monteiro and Adler (1989) indicated that using The Primal-Dual Interior-Point Method The update rule for the new point is modified to A strategy that has yielded good computational results is to take a large step which still maintains strict feasibility. For example, Primal-Dual Method – Example We will apply the primal-dual method to the linear program Primal-Dual Method – Example The Primal-Dual Interior-Point Method Modify the primal-dual method so that infeasible starting guesses can be used. The Primal-Dual Interior-Point Method There is on