Graduate Seminar Report on Quadratic Programming on Sphere
No Thumbnail Available
Date
2010-06-06
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Addis Ababa University
Abstract
Quadratic programming on a sphere is a special class of non linear programming quadratic objective function with a single quadratic constraint. To solve this problem we can apply different methods and the Lagrangian dual methods one of the easier methods to solve this problem. Lagrangian duality method is a procedure for approximating constrained optimization problems by unconstrained problems. The concept of duality is useful in developing effective computations algorithms for solving linear and quadratic programming problems.
Mathematical programming associates with every optimization problem a dual problem, the difference between the (optimal values being the duality gap, under convenient assumptions (so called constraint qualification); it is known that the width of the duality gap is zero when the criterion and the constraints are convex..
The Trust region (TR) sub problem ( the minimization of quadratic objective function subject to one quadratic constraint and denoted by TRS) has many applications in diverse areas such as; function minimization, sequential quadratic programming, regularization, ridge regression, and discrete optimization. Trust region algorithms are popular for their strong convergence properties.
Lagrangian duality underlies many efficient algorithms for convex minimization problems. A key ingredient is strong duality; Lagrangian relaxation is also provides lower bounds for non convex problems, where the quality of the lower bound depends on the duality gap. Quadratically constrained quadratic program provide important examples of non convex programs. For this simple case of one quadratic constraint (TRS) strong duality holds. In addition, a necessary and sufficient second order optimality condition exists.
Duality gaps in optimization problems arise because of the non-convexity involved in the objective function or constraints. The Lagrangian dual of a non-convex optimization problem can also be viewed as two people zero sum game. From this view point, the occurrence of duality gaps originates from the order in which the two players select their strategies.
Description
Keywords
Graduate Seminar, Report, Quadratic, Programming, Sphere