Quadratic Programming
摘要
Quadratic objective functions are relatively frequent in optimization scenarios, in applications, for example, related to data fitting (squared errors), energy, financial approaches, etc. After introducing essential aspects of the optimization problem, like the KKT conditions for this case, the chapter tackles two types of situations, according to equality or inequality constraints. In this second context, the chapter introduces the Wolfe’s method (extended simplex), the active set method, the dual active set method, the Lemke’s method (linear complementary problem), the gradient projection method, the spectral projected gradient method, the conditional gradient method (Frank-Wolfe algorithm), and the criss-cross algorithm. Then, a section is devoted to sequential quadratic programming (SQP), of much practical importance. Two significant applications are considered next, in two sections: one for the portfolio optimization introduced by H. Markowitz, and another for the support vector machine (SVM) for data classification. A number of programs in MATLAB are included, in relation with the main topics of the chapter, and taking advantage of specific MATLAB functions for quadratic programming.