A Quadratic Programming Method Based On Freudenthal Simplex Subdivision

Quadratic programming is an optimal problem with a quadratic function as the objective function and linear functions as the constraints,it includes linear programming,and is a kind of special nonlinear programming.The quadratic programming problem is a typical optimization problem,closely linked with the mathematics of economics,management science and other issues,has a wide and important application in the fields of finance,production and manufacturing.This paper deals with the solution method for solving the dual problem of convex quadratic programming problems.First,the method for solving surrogate and surrogate dual problem of inequality constrained nonlinear programming problem,proposed by Glover,Greenberg and Pierskalla,is used to derive the surrogate dual problem of quadratic programming.Each constrain is multiplied a surrogate multiplier that is greater than 0,the sum of these multipliers is 1.The quantity of each multiplier represents the active or efficient of corresponding constraint.The constraint is inactive if its corresponding multiplier is 0.The constraint that is formed by summing all constraints is regarded as a surrogate constraint.With some steps of derivations,we obtain a surrogate dual problem with a fraction function as the objective function,and the constraint being only a simplex.Second,as for the fractional objective function,both the numerator and the denominator are convex functions,so we can not determine the convexity of the objective function,it is verified that this is a non convex optimization problem.Third,as for the dual problem,there is only one constraint,that is a simplex,we propose a method that is based on Freudenthal simplex division for solve the dual problem.With the subdivision of the simplex,we obtain the coordinates of the nodes of the subdivision of the simplex,then substitute the coordinate to the objective function,find the global maximum to finish the optimal procedure.Last,the proposed method is verified by some examples.It is effective for the quadratic programming problem with the number of constraints less than the number of variables.This is because the number of constraints of dual problem is the number of constraints of the primal problem.But for the number of constraints is greater than the number of variables,it will lead to a high dimension simplex,the efficiency of the method will be quit low.This is because the subdivision of a high dimension simplex will lead to large quantity of computing.So in the next step,we will use branch and bound method to divide coarsely and then finely to solve this kind of problems.