On solving convex programming problem

Abstract

In this paper an algorithm for solving convex programming problem is proposed. The specific feature of the considered problem is that its constraints contain only linear equalities. This feature is a basis for the replacement the nonlinear objective function in the neighbourhood of the tested point by a linear one, due to what solving an original problem is reduced to sequential solving linear programming problems. The obtained linear programming problem is solved by sequential correction the value of an objective function on a set of admissible solutions and an admissible as well as optimal solutions are found. Further values of an original objective function at the found admissible and optimal points are calculated and an auxiliary approach is determined. The next approach is defined as a convex combination of a previous and an auxiliary approaches. Note that unlike the Lagrange multipliers method the developed method is applied to problems with the Lagrange function which hasn’t a saddle point. The paper contains a description of the method, a proof of its convergence, schemes of algorithms and experimental results. The proposed algorithm combines ideas of the conditional gradient method [1] and a method for solving linear programming problem [2].