Barrier function method and correction algorithms for improper convex programming problems
In the present paper the author considers a convex programming problem \[ \min\{f_0(x): x\in X\}, \tag{CP} \] where \(X=\{x:f_i(x)\leq 0\), \(i=1,2,\dots, m\},\) and \(f_i\) are convex functions defined on \({\mathbb R}^n\) for \(i=0,1,\dots, m\). The optimal value will be denoted by \(f^*\). The aim of the paper is to investigate the generalization of the inverse barrier function method, i.e. finding \[ \inf_{X^0}\left\{B(x,\varepsilon)=f_0(x)+\sum_{i=1}^m{\varepsilon_i\over |f_i(x)|^{p_i}}\right\}, \] where \(0<\varepsilon_i<1\), \(p_i\geq 1\) for every \(i=1,\dots, m\), and \(X^0=\{x:f_i(x)<0\) \(\forall i\}\); \(B_\varepsilon^*\) denote its optimal value. In Section 1, an estimate of \(B_\varepsilon^*-f^*\) is provided (Th. 1). Moreover, in Th. 2 it is proved that it is possible to approximately find saddle points of the Lagrange function for the original problem CP. If \(f_0\) is strongly convex, Th. 4 provides an estimate of \(\|x(\varepsilon)-x^*\|\), where \(x(\varepsilon)\) is the unique point in \(\text{arg\,min}_{x\in X^0}B(x,\varepsilon)\), and \(x^*\) denotes the unique point such that \((x^*,\lambda^*)\) is a saddle point of the Lagrange function for some \(\lambda^*\). Moreover, under the assumptions of differentiability of \(f_i\) \((i=1,2,\dots, m)\) in some neighbourhood of \(X\), Th. 6 investigates the convergence of approximations for the Lagrange multipliers. In Section 2 the author formulates a statement that shows the way to construct a regularization method for a CP problem using generalized inverse functions. Indeed, with the problem CP, he associates the problem of finding \[ \inf \{B_{\gamma}(x,\varepsilon):x\in X^0\}, \] where \(B_{\gamma}(x,\varepsilon)={\mathcal F}_{\gamma}(x)+\sum_{i=1}^m{\varepsilon\over |f_i(x)|^p}\), \({\mathcal F}_{\gamma}(x)=f_0(x)+\gamma \|x\|^2\), \(1\geq \overline{\varepsilon}>\varepsilon>0\), \(p\geq 1\), \(\gamma>0\) (\(\overline{\varepsilon}\) is given in Th. 1); \(x(\gamma,\varepsilon)= \text{arg\,min}_{x\in X^0} B_{\gamma}(x,\varepsilon)\). In Th. 6, it is stated that \(x(\gamma, \varepsilon)\to x_0^*\) as \(\gamma,\varepsilon\to 0\), where \(x^*_0\) is the normal solution of the problem CP. In Section 3 the author applies the previous estimates in order to discuss the issue of controlling the penalty coefficient \(\varepsilon\) for the purpose of providing the convergence of the barrier function method to a solution of the original problem at a given rate, while in Section 4 he proposes two iterative realizations of the inverse barrier function method for the optimal correction of improper CP problems.
scientific article; zbMATH DE number 5619814