tailieunhanh - Some remarks on duality and optimality of a class of constrained convex quadratic minimization problems

In this paper the duality and optimality of a class of constrained convex quadratic optimization problems have been studied. Furthermore, the global optimality condition of a class of interval quadratic minimization problems has also been discussed. | Yugoslav Journal of Operations Research 27 (2017), Number 2, 219–225 DOI: SOME REMARKS ON DUALITY AND OPTIMALITY OF A CLASS OF CONSTRAINED CONVEX QUADRATIC MINIMIZATION PROBLEMS Sudipta ROY Department of Mathematics, Lady Brabourne College, Kolkata, India roy89sudipta@ Sandip CHATTERJEE Heritage Institute of Technology, Kolkata, India functionals@ R. N. MUKHERJEE Department of Mathematics, University of Burdwan, India rnm bu math@ Received: January 2017 / Accepted: May 2017 Abstract: In this paper the duality and optimality of a class of constrained convex quadratic optimization problems have been studied. Furthermore, the global optimality condition of a class of interval quadratic minimization problems has also been discussed. Keywords: Quadratic Forms, Semidefinite Matrices, Lagrangian Duality. MSC: 90C20, 90C26, 90C30. 1. INTRODUCTION A large number of non-linear programming problems can be formulated as quadratic programming problems ., max-clique problem, rank minimization problem, etc.[2, 3, 5, 6, 7, 8, 9, 12, 13]. A global unconstrained quadratic optimization problem is of the form Minimize xT Ax x∈S (1) 220 S. Roy, et al. / Some Remarks on Duality and Optimality where A is an arbitrary n × n symmetric matrix and S is the standard simplex in Rn . One of the most significant characteristics of the form (1) is that problems of such form are NP-hard [2]. Note that, without any loss of generality, all the entries of A can be assumed as non-negative[5]. The general constrained quadratic minimization problem consists of a quadratic objective function and a set of linear inequality constraints 1 T x Ax + bT x 2 Subject to Bx ≤ c Minimize (2) where b is an n-vector, c is an m-vector, A is an n×n matrix and B is an m×n matrix. If the matrix A is positive semidefinite or positive definite, then (2) becomes a convex programming problem and consequently, becomes solvable in .