Fast Algorithm For A Class Of Quadratic Programming Problems With Single Linear Constraints

With the rapid development of production and scientific research,theory and algorithm of optimization is playing an important role especially in the era of artificial intelligence.Machine learning and deep learning technology is highly dependent on the algorithm theory and optimization theory,the status has been improved greatly,furthermore the optimization method based on gradient is particularly brisk.As an important form of optimization,quadratic programming problems occupy a very high position in the machine learning model.Relative prototypes can be attributed to the quadratic programming optimization problem,such as support vector machine,the perceptron,Markov model,conditional random field model.This paper first summarizes the algorithm optimization form of the above classical models,then proposes a class of quadratic programming standard models with single linear box-like constraints,finally provides an efficient semismooth Newton iteration optimization algorithm.Summarizing a large number of machine learning algorithm model references,a class of single linear box-like constrained quadratic programming standard models is constructed,while the corresponding efficient solutions were provided.The box-like constraint subproblem is first constructed to optimize the model,and its closed form solution is given.The quadratic programming optimization model is simplified while considering the box-like constraints condition only,the solution of the subproblem can be obtained by optimizing the KKT condition of the complementary relaxation property.And the existence and uniqueness of the optimal solution are proved by using disproof method.Since the analytic solution of the subproblem is obtained,the solution of the original problem can be equivalently solved using Parametric Method.Aiming at the optimal solution of the original problem,this paper applies the Lagrange duality method to solve the dual form problem of the standard quadratic programming model.As the Lagrange parameter function with convex properties,the parameters optimal solution of the original problem can be determined according to Fermat's theorem.Due to the equivalence of the parametric primal and dual problems of conditions,the nature of the equivalent functions make it that the semismooth Newton method can be used to solve the parameter and substitute it into the original problem.Then the optimal solution of the standard quadratic programming problem is obtained.The convergence and convergence speed of the line search aided semismooth Newton iterative algorithm are both analyzed in the paper,and the measurements includes the time complexity and convergence order.Not only the theories are studied,but also the experiments have been conducted.Three typical forms of high order stochastic numerical experiments shows that the proposed algorithm is more efficient than the existing optimal algorithms and the highest level of optimization software.