The exact penalty method for the solution of one problem of convex programming

D. M. Lebedev ; L. N. Polyakova

Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, no. 1 (2014), pp. 72-78

Résumé

The problem of conditional minimization of a quadratic function with positively defined matrix on the set specified by inequality is considered. The set is non-empty, compact and does not consists of isolated points. To solve this problem the article proposes to use the method of exact penalty functions. This method differs from the classical method of penalty functions that function, which determines the set which minimizes the objective function should be non-differentiable at boundary points, and there must be the exact penalty parameter at which the minimum built penalty functions coincides with the minimum of the original problem for constrained optimization. The paper constructs a method that minimizes the penalty function with constant step and having a geometric rate of convergence similar in the smooth case gradient method of minimization of the strongly convex function. To find the direction of descent the task of quadratic programming is solved. It provides analytical formulas to calculate the direction of descent and the step size. The described algorithm is relaxation. The result is illustrated by an example. Bibligr. 6.

Détail

Keywords: strongly convex functions, the task of convex programming, method of exact penalty functions, function maximum, relaxation method, geometric convergence rate.