最优化理论期末作业.docx

Final work for CVX optimizationBarrier Method and Primal-dual Interior-point Method for Linear ProgrammingName:****Student ID:********Major:Communication and Information System2015/7/16 ThursdayBarrier Method and Primal-dual Interior-point Method for Linear ProgrammingSchool of Information Science and Engineering,Shandong University, P.R. China,250100*@Abstract：Interior-point methods (IMP) for solving convex optimization problems that include inequality constraints. The most attractive features of IMP are its speed of convergence and its robust capability of handling equality and inequality constraints; making itself a practical tool for solving large-scale optimization problems. In this paper, two kinds of interior-point methods—barrier method and primal-dual interior-point method, are discussed. And Comparison of these two methods is given, based on solving the standard LP.Keywords: Interior-point method, Barrier method, Primal-dual interior-point method, LP. IntroductionThe interior-point method is almost used to solve convex optimization problems that include inequality constraints. Interior-point methods solve the problem (or the KKT conditions) by applying Newton’s method to a sequence of equality constrained problems, or to a sequence of modified versions of the KKT conditions. We can view interior-point methods as another level in the hierarchy of convex optimization algorithms. Linear equality constrained quadratic problems are the simplest. For these problems the KKT conditions are a set of linear equations, which can be solved analytically. Newton’s method is the next level in the hierarchy. We can think of Newton’s method as a technique for solving a linear equality constrained optimization problem, with twice differentiable objective, by reducing it to a sequence of linear equality constrained quadratic problems. Interior-point methods form the next level in the hierarchy: They solve an optimization problem with linear equality and inequality constraint