Barrier function method and correction algorithms for improper convex programming problems
type: Item
instance of: scholarly article
title: Barrier function method and correction algorithms for improper convex programming problems
zbMATH Open document ID: 1182.90068
DOI: 10.1134/S0081543808060126
author: V. D. Skarin
published in: Proceedings of the Steklov Institute of Mathematics
publication date: 2009-10-23T00:00:00Z
review text: 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\i…
reviewed by: Rita Pini
Mathematics Subject Classification ID: 90C25
zbMATH DE Number: 5619814
zbMATH Keywords: inverse barrier function
zbMATH Keywords: convergence estimates
MaRDI profile type: Publication
cites work: Q5588268
cites work: Computational methods in optimization. A unified approach.
cites work: Q3673541
cites work: Q4739659
cites work: Q3686427
cites work: A new polynomial-time algorithm for linear programming
cites work: On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
cites work: Modified barrier functions (theory and methods)
cites work: Convex Analysis
cites work: A stable interior penalty method for convex extremal problems
cites work: Q3738923
full work available at URL: s0081543808060126
OpenAlex ID: W2066234634
description: scientific article; zbMATH DE number 5619814