TY - JOUR

T1 - Reduction of a Minimization Problem of a Separable Convex Function Under Linear Constraints to a Fixed Point Problem

AU - Krylatov, A. Yu

PY - 2018/1/1

Y1 - 2018/1/1

N2 - The paper is devoted to studying a constrained nonlinear optimization problem of a special kind. The objective functional of the problem is a separable convex function whose minimum is sought for on a set of linear constraints in the form of equalities. It is proved that, for this type of optimization problems, the explicit form can be obtained of a projection operator based on a generalized projection matrix. The projection operator allows us to represent the initial problem as a fixed point problem. The explicit form of the fixed point problem makes it possible to run a process of simple iteration. We prove the linear convergence of the obtained iterative method and, under rather natural additional conditions, its quadratic convergence. It is shown that an important application of the developed method is the flow assignment in a network of an arbitrary topology with one pair of source and sink.

AB - The paper is devoted to studying a constrained nonlinear optimization problem of a special kind. The objective functional of the problem is a separable convex function whose minimum is sought for on a set of linear constraints in the form of equalities. It is proved that, for this type of optimization problems, the explicit form can be obtained of a projection operator based on a generalized projection matrix. The projection operator allows us to represent the initial problem as a fixed point problem. The explicit form of the fixed point problem makes it possible to run a process of simple iteration. We prove the linear convergence of the obtained iterative method and, under rather natural additional conditions, its quadratic convergence. It is shown that an important application of the developed method is the flow assignment in a network of an arbitrary topology with one pair of source and sink.

KW - constrained nonlinear optimization

KW - fixed point problem

KW - generalized projection matrix

KW - network flow assignment

UR - http://www.scopus.com/inward/record.url?scp=85043256386&partnerID=8YFLogxK

U2 - 10.1134/S199047891801009X

DO - 10.1134/S199047891801009X

M3 - Article

AN - SCOPUS:85043256386

VL - 12

SP - 98

EP - 111

JO - Journal of Applied and Industrial Mathematics

JF - Journal of Applied and Industrial Mathematics

SN - 1990-4789

IS - 1

ER -