« Previous « Start » Next »
6 The Algorithm
The program is an implementation of an interior–point algorithm for
linear constrained convex programming which when applied to
geometric programming solves both primal and dual
GP problems
simultaneously. Using the perturbed KKT system of the dual
GP, a
central–path is defined which converges to a solution of both the
primal and dual
GP programs. The algorithm does not require the
existence of an interior point for either program. Moreover, the
algorithm has the feature of generating
subfeasible solutions,
[
9, 8], when the primal geometric program is
inconsistent but subconsistent. Computing functional values of
subfeasible solutions gives rise to more conceivable duality states
for the primal-dual pair. In this manual we limit these
possibilities by considering “boundedly subfeasible” sequences for
which our algorithm delivers a path whose primal-dual gap can be
made arbitrarily small, even for the case where one of the pair of
dual problem is inconsistent.
In addition, the objective
functions need not be differentiable at an optimal solution of a
given consistent program.
Each iteration of the algorithm computes the Newton direction from a
perturbed KKT system involving two parameters, γ and η.
The affine direction (corresponding to a particular setting
γ=0, η=1) is used to predict reductions in both the
feasibility and complementarity residuals. Then proper parameters
γ,η are chosen for the KKT system which is solved for the
direction again. The indefinite reduced KKT matrix is factorized by
performing diagonal pivots whose orders are chosen in terms of
minimum degree to maintain the sparsity of the factors. A static
data structure associated with the chosen pivoting order is
allocated by a single symbolic factorization and used in subsequent
iterations. Tactics for taking large steps and reset dual slack
variables according to certain rules are implemented.
Computational results indicate that the algorithm, coupled with
these new techniques, leads to an efficient and stable
implementation for solving primal and dual geometric programs
simultaneously.
The results indicate that the standard geometric programming measure
of difficulty is no barrier to the methods.
« Previous « Start » Next »
TOMLAB
