на русский

Quadratic programming

Arbitrary matrix of the quadratic form

We consider the problem of finding the largest or smallest values of the objective function F = (X,AX) + (L,X) + C in case of an arbitrary matrix "A" of the quadratic form. Domain of the arguments "X" defined by a system of linear constraints-equality and linear constraints-inequalities. Here is not imposed simplicity demand of positive definite quadratic form in the case minimization of the function or negative definite quadratic form in the case maximization of the function. Using quadratic functions can be approximated an arbitrary nonlinear function (solving the problem of mathematical programming), herewith as a rule are not expected the constant sign of the quadratic form. In this case it is necessary to solve the optimization problem with an arbitrary matrix of the quadratic form.

The exact solution

It is proposed the principle of exact solution not based on any modification of the gradient methods or other descent methods. The basis of finding the global extremum of the function is taken the well-known algorithm for computing the largest or smallest values of the function on a compact - selection of the global extremum of the set from all local extrema inside the feasible region and on the boundary. Of course, not always a domain defined by a system of restrictions, is compact. For an unbounded domain in the proposed method introduces additional conditions, cutting off the compact part. Then taking the limit as the shift of additional restrictions to infinity, we obtain an exact solution for a given unbounded domain.

Free of charge testing this method

All those wishing to offer free opportunity to test above specified idea at concrete examples. For the purity of the experiment you create the example yourself and offer to solve it to author. After receiving solution, you can analyze it thoroughly to make sure working capacity of the algorithm or abandon it.
Software testing. In order to avoid confusion in the description of examples of problems, is designed a program. You can download it here. This self-extracting archive file is containing four files: qpu.exe, qpu.aux, qpu.t0 and qpu.t1. All four files must be placed in one folder, executable file - qpu.exe. The program qpu.exe allows you to specify numerical parameters the quadratic programming problem and write them in a special format file. This file can be sent to the author bgs@krm.net.ua, which undertakes to solve any problem that was sent or declare of inability to obtain the result with the claimed algorithm. In any case, response will be sent to your e-mail.
Tasks to test online. Numerical parameters of the quadratic programming problem small dimension, in standard form can be entered directly: Structure of the task -> Numerical data. In this case, the answer will appear on this site in a few days by page Solving quadratic programming problems (author visits the site 1-2 times a week).


Example 1   Example 2   Example 3



Gennadij Bulanov, 1948 yr birth, Ph.D. phys.-math. sciences, docent department of higher mathematics Donbass State Engineering Academy, Kramatorsk, Donetsk region, Ukraine.


From the methodological developments G.Bulanov for educational purposes

Automated generator problems on functional analysis (in Russian)