Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 0759.90064
Fang, S.-C.
An unconstrained convex programming view of linear programming.
(English)
[J] Z. Oper. Res. 36, No.2, 149-161 (1992). ISSN 0340-9422; ISSN 1432-5217/e

For a linear program in Karmarkar standard form (P) $\min\{c\sp Tx; Ax=0, e\sp T x=1, x\ge 0\}$ the author considers a program with entropic barrier function $(\text{P}\sb \mu)$ $\min\{c\sp T x+\mu\sum\sb j x\sb j\log x\sb j; Ax=0, e\sp T x=1, x\ge 0\}$ and shows by using a geometric programming technique that the dual problem $(\text{D}\sb \mu)$ to $(\text{P}\sb \mu)$ is an unconstrained convex programming problem. Explicit formulae are derived for the computation of $\varepsilon$- optimal solutions to (P) and to its dual (D) from the optimal solution to $(\text{D}\sb \mu)$. Solving $(\text{D}\sb \mu)$ via unconstrained minimization techniques is discussed briefly.
[J.Rohn (Praha)]
MSC 2000:
*90C05 Linear programming
90C25 Convex programming
90-08 Computational methods (optimization)
90C30 Nonlinear programming

Keywords: interior-point method; entropic barrier function; dual problem; unconstrained convex programming; computation of $\varepsilon$-optimal solutions

Highlights
Master Server