Zero Norm Solution for Quadratic Programming Problem
Explore the minimal zero norm solution for quadratic programming problems, discussing the solving method, outline of work, and numerical examples. Understand the importance of zero norm solutions in various applications such as bimatrix games and portfolio selection.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Title: Minimal Zero Norm Solution for Quadratic Programming Problem Authors: Hajar Alimorad Jahrom University
Contents: Introduction and introducing the problem Solving method of QP Outline of work Numerical examples
A Quadratic Programming (QP) would be stated as: min?(?) = ??? +1 2???? ?.??: ?? ? (1) ? 0 In which ? = ?1,?2, ,??, ? = ?1,?2, ,??, are vectors and ?? ?,?? ? are matrix. Since the constraints in problem are linear, the defined region by these conditions is convex. Therefore, if the objective function ? ? is convex and there is one local solution for problem (1), this solution will be global. If Q is positive definite (or positive semi- definite), the function ? ? is a convex one. ? = ?1,?2, ,??
Solving method of QP Several different methods have been presented for solving problem (1). The use of Karush- Kuhn-Tucker (KKT) methods is the main basis of some important families of existing methods to solve these problems KKT optimality conditions: Suppose that ? is a local optimal solution of the QP such that it satisfies ?? = ?, ? 0 and assume that Q is a positive semi-definite matrix. Then, there exist vectors ?,? and ? such that the following conditions hold: ??? + ?? ? = ?? ?? + ? = ? (2) ??? + ??? = 0 ? 0, ? 0, Furthermore, ? is a global optimal solution [8]. ? 0, ? 0.
Two last cases of these conditions are indicative of complementary relationships which are satisfied for ??= 0 or ??= 0, ( ? = 1,2, ,?) (or both of them). Also, which are satisfied for ??= 0 or ??= 0 , ( ? = 1,2, ,?) (or both of them).
Outline of work In this paper, for solving non-linear system (2), a simple and effective method is presented based on minimal zero norm. Then, for examining the effectiveness of the method, the numerical examples solved through previously presented methods, will be solved using the new method. Minimal zero norm solution are often desired in some real applications such as bimatrix game and portfolio selection [6]. Zero norm of a vector is defined by ? ?0= lim ?? = ???? ?? ? 0+ ?=1 which is equal to the number of non-zore elements of vector ?. If ? 1, it is usual to refer to ??as the ? norm of ? ??. The notation ???? . represents the operator such that, for any real number ?, ???? ? = 1 if ? > 0, ???? ? = 0 if ? = 0 and ???? ? = 1 if ? < 0 (see [6]). we can solve the problem by defining the objective function min ?,?,?,? 0
Numerical examples Example: Solve the following quadratic programming problem [3]: min: ? ? = 15?1+ 30 ?2+ 4 ?1?2 2 ?1 2+ 4 ?2 2 ?.??: ?1+ 2 ?2 30 ?1 0, ?2 0 Considering the KKT proposition, the problem would be rewritten as follow: 4?1 4?2+ ?1 ?1= 15 4?1+ 8 ?2+ 2 ?1 ?2= 30 ?1+ 2 ?2+ ?1= 30 ????= 0, ??,??,?1,?1 0, ?1?1= 0 ? = 1,2
By defining the objective function ??? ? = ???? ?1 + ???? ?1 (the minimal zero norm of the variables) we have a non-linear programming problem which is solvable with Matlab software and the fmincon formula. The optimal solution of the problem, with the new method is: ?1 Example: Solve the following problem [3]: min ? ? = 4?1+ 6 ?2 2 ?1 ?.??: ?1+ 2 ?2 2 ?1 0, The optimal solution is + ???? ?2 + ???? ?1 + ???? ?2 + ???? ?1 ,?2 ,?1 = 12,9,3 2 2 ?1?2 2 ?2 2 ?2 0 1 3,5 ,?2 ,?1 = ?1 6,1
Example: Solve the following problem [8]: 2+ 4?2 2 ??? ? ? = 8?1 16?2+ ?1 ?.??: ?1+ ?2 5 ?1 3 ?1 0, ?2 0 The optimal solution is ,?2 ,?1 ,?2 = 3,2,0,2 ?1
Conclusion In this article, a simple and effective method is introduced for solving quadratic programming problem, with the help of KKT constraints and definition of the objective function. In non-linear problems, the result might be approximate. Although, in the new method we have a non-linear programming problem, with the help of KKT constraints, the global optimal result would be found. With regard to the complement conditions in non-linear constraints, the objective function of zero norm, is the most suitable function for solving this problem. The results are completely satisfactory comparing to the others represented for QP problem.
[1] A. M. Bruce, M. Herbert, & F. Hartly, Quadratic programming applications, Omega (1977) 43-55. [2] G. Cornuejols, & R. Tutuncu, Optimization methods in finance, Cambridge University Press, 2007. [3] F. Hillier, & G. Liberman, Introduction to operation research, 3d edition, 1980. [4] K. Sh. Jae, A Survey of quadratic programming to businness and economics, International Journal of Systems Science (2007) 105-115. [5] M. Josip, & P. Tunjo, A new iterative method for solving multiobjective linear programming problem, Applied Mathematics and Computation, 243, (2014) 746 754. [6] Sh. Meijuan, Zh. Chao, & X. Naihua, Minimal zero norm solution of linear complementarity problems, Journal of Optimization Theory and Applications, (2014) 795-814. [7] K. G. Omprakash, Applications of quadratic programming}, Journal of Information and Optimization Sciences, (16), (1995) 177-194. [8] S. S. Rao, Optimization (Theory and Application), Wiley Eastern, 1984. [9] J. W. Stephen, Primal-dual interior-piont method, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA,1997.
