A Predictor-Corrector Algorithm for a Class of Nonlinear Saddle Point Problems.
An interior path-following algorithm is proposed for solving the nonlinear saddle point  problem $$ {\rm minimax}\ c^Tx+\ph(x)+b^Ty-\psi(y)-y^TAx $$ \vspace*{-18pt} $$ {\rm subject\ to\ }(x,y)\in \X\ti \Y\su R^n\ti R^m, $$ \noindent where $\ph(x)$ and $\ps(y)$ are smooth convex functions and $\X$ and $\Y$ are boxes (hyperrectangles). This problem is closely related to the models in stochastic programming and optimal control studied by Rockafellar and Wets (Math. Programming Studies, 28 (1986), pp. 63--93; SIAM J. Control Optim., 28 (1990), pp. 810--822). Existence and error-bound results on a central path are derived. Starting from an initial solution near the central path with duality gap $O(\mu)$, the algorithm finds an $\ep$-optimal solution of the problem in $O(\sqrt{m+n}\,|\log\mu/\ep|)$ iterations if both $\ph(x)$ and $\ps(y)$ satisfy a scaled Lipschitz condition.
Introduction
This paper discusses an interior path-following method for solving a class of nonlinear
saddle point problems in the following form:
Find a saddle point for
subject to x 2 X ae R n
where OE(x) and /(y) are C 2 -convex functions, c 2 R n , b and the
superscript T represents transpose. The sets of X and Y are boxes (hyper-rectangles).
According to convex analysis [15], problem (1.1) has a pair of associated optimization
problems - the primal problem
and the dual problem
maximize
Note that the function f(x) (called the primal objective function) is convex, the function
g(y) (called the dual objective function) is concave, and both are nondifferentiable in
general (for a detailed analysis for the case that both OE(x) and /(y) are quadratic,
see [16], where f(x) and g(y) turn out to be "piecewise quadratic" convex functions).
Therefore, problems (1.1) - (1.3) can be categorized as nonsmooth convex programming
problems. Some fundamental duality relationships among (1.1), (1.2) and (1.3) have
been established in [15], which include existence results on the saddle points of (1.1) and
the saddle point value - the common optimal value of (1.2) and (1.3).
Problems stem from a development beyond the conventional formulation
of optimization problems. These models provide a framework that allows penalty representations
of constraints as well as accommodates other sources of nonsmoothness
such as objectives produced by multistage optimization problems. For instance, linearly
constrained convex optimization problems are usually posed in the form
minimize OE(x) subject to Ax - b; x - 0:
The corresponding Lagrangian saddle point problem is
which is a special case of (1.1). Now let /(y) be a convex function such that
and /(y) - 0 and add \Gamma/(y) to the lagrangian function. Then the corresponding primal
program becomes
fy subject to x - 0;
where the function sup y-0 fy T (b is equal to zero for x satisfying Ax - b
and is greater or equal to zero for all x: Thus in this formulation the exact constraint
is replaced by a penalty representation that allows the modeler to deal with
more flexibly by selecting suitable /(y) and Y:
As an example of how multistage optimization could fit into the form of (1.1), we consider
a two-stage stochastic programming model studied by Rockafellar and Wets [21]. At the
first (current) stage, a decision x 2 R n has to be made, incurring a direct cost c T x+OE(x);
subject to x 2 X , where X is a box. At the second (future) stage, a random event is
observed with outcome !
where\Omega is a probability space. The decision x and
the outcome ! then determine an additional "recourse cost" ae ! (x): Under the practical
circumstances such as soft constraints [16][18] and simple recourse [27], the function
expressed by an optimal value function as follows:
fy T
In principle, the set Y ! , the vector b ! , the matrix A ! , and the function / ! are allowed
to be random. The objective in this model is to make the best decision x with respect
to the present cost and constraints as well as the expected cost
induced constrains. Assuming finite discrete distribution for !, the decision problem
can be described by
subject to x
is the probability of the random event !: Now let
Y
\DeltaC C C C C A
\DeltaC C C C C A
Then problem (1.5) takes the form of (1.2).
More about the motivation of models (1.1) - (1.3) and their applications in stochastic
programming and optimal control can be found in a series of pioneer papers of Rockafellar
and Wets [16][17][18][19][21][22].
Algorithms for linear-quadratic cases of problem (1.1), in which both OE(x) and /(y)
are linear or quadratic, have been studied extensively. Among them are the L-shaped
method [26], the decomposition methods [1][5], the finite generation method [9][21], the
projected gradient method [32], the steepest descent method [31], the SQP method [14],
and some interior point methods [2][3][23][28][29]. For the special case where both X and
Y are boxes and both OE(x) and /(y) are separable quadratic functions, a simplex-active-
set method has been developed [20]. The more general convex case of (1.1), however,
has not yet received enough attention in algorithmic development although the problem
can be traced back to the extended Fenchel duality model in 1970's [15].
The purpose of writing this paper is three fold.
(1) We develop a predictor-corrector algorithm for problem (1.1), together with existence
and error-bound results on a central path. Particularly, we show that, if functions OE(x)
and /(y) satisfy a scaled Lipschitz condition, then starting from an initial solution near
the central path, the algorithm converges to an ffl-optimal solution of the problem in
O(
is a number related to the initial duality gap.
(2) To the research community in stochastic programming and optimal control, we
demonstrate that the interior point method can be used as one of the theoretically
efficient methods for convex-concave saddle point problems.
(3) To the research community of interior point methods, this paper contributes a polynomial
algorithm for a special class of monotone complementarity problems (MCP). To
our knowledge, only few algorithms for nonlinear MCP have been shown to have polynomial
complexity (Nesterov and Nemirovskii [13], Tseng [24]) under different conditions.
The scaled Lipschitz condition, as shown in [33], is satisfied by a fairly large class of
convex functions.
Although problem (1.1) can be reduced to a monotone complementarity problem of a
special type (which we will see in the next section), there are two major differences
between the proposed algorithm and the algorithms for general MCP. First, the convergence
analysis is not based on the properties of a monotone mapping; rather, it is based
on specifications of the two functions OE(x) and /(y). Second, the proposed algorithm
can take advantage of the special structure of problem (1.1) arising from stochastic
programming and optimal control.
This paper is organized as follows. In Section 2 we discuss the conditions for the existence
of the optimal solution(s) and the central path. We establish an estimate on the
duality gap if (x; y) is near the central path. These results form a foundation for the
interior path-following method for problem (1.1). Section 3 is devoted to the proof of
polynomial convergence of the predictor-corrector algorithm. Finally, Section 4 contains
some concluding remarks.
The predictor-corrector algorithm studied in this paper is rooted in the primal-dual path-following
algorithm of Kojima, Mizuno and Yoshise in [10] for linear complementarity
problems. The algorithm and its variants have been extensively studied on their global,
local, and computational behaviors in the context of linear complementarity problems.
It is not possible for us to point out all references on this method, the interested reader
may look into the nice tutorial paper of Gonzaga[6] and the recent papers such as
[8][11][29][30] and the references therein. Our goal is limited to a proof of a global
convergence result on the proposed algorithm and to a discussion of some properties
about the central path. The computational behaviors and other issues are left for further
studies.
2. Results on Feasibility, Existence, and Error-bounds Related to the Central
Path
In the following analysis, we assume that both X and Y are nonnegative orthants in
order to simplify the statements. This is not an essential change from assuming that X
and Y are boxes. We will elaborate this point at the end of Section 3.
Suppose that a saddle point exists; that is
It can be shown [15] that x   and y   must be optimal solutions of (1.2) and (1.3), re-
spectively, and f(x   vice versa. In addition, the saddle point
satisfies the following variational relationships:
stands for the normal cone of X at x   : The notation N Y (y   ) has a similar
meaning. By introducing auxiliary vectors w   and s   , conditions (2.1) can be written in
an explicit form as follows:
Ax   +r/(y
We assume that both OE(x) and /(y) are finite and twice continuously differentiable on
X and Y, respectively.
The proposed algorithm finds an approximate saddle point of l(x; y) over X \Theta Y by
finding a sequence of approximate saddle points of the following saddle function
log
log y i
over X \Theta Y: Analogous to (2.2), the point (x(-); y(-)) is a saddle point of l - (x; y), if
and only if there exists (w(-); s(-)) such that (x(-); y(-); w(-); s(-)) satisfies
System (2.3) can be derived in a similar way to the deduction of system (2.2). It can be
seen that system (2.2) is the special case of system (2.3)
Naturally, as an interior point method, the proposed algorithm needs some kind of
interior points from which to start. We make the following assumption.
Assumption 2.1 There is a quadruple (x; such that the first two equations
of system (2.3) are satisfied.
Under this assumption, we can prove that the iterates generated by our algorithm are
feasible solutions to problems (1.2) and (1.3) and that the solutions to problem (2.3)
exists for all - 0:
We first discuss the feasibility problem. An x is feasible to (1.2) if x - 0 and
while a y is feasible to (1.3) if y - 0 and g(y) ? \Gamma1: We have the following result
under an assumption weaker than Assumption 2.1.
Proposition 2.2 Suppose that the following relations are valid:
Then x k is a feasible solution to problem (1.1) and y k is a feasible solution to problem
(1.2).
Proof. The second equation of (2.4) and the convexity of /(y) imply that, for any
Thus the second equation of (2.4), s k - 0, and x k - 0 imply that x k is feasible to (1.2).
Similarly, the first equation of (2.4), w k - 0; and y k - 0 imply that y k is feasible to
(1.3).
Because our algorithm will ensure that (2.4) is valid for all iterates (see details below),
the algorithm will generate a feasible sequence f(x k ; y k )g to problems (1.1) and (1.2)
according to Proposition 2.2.
Now we discuss the existence of the saddle points of l - (x; y): Unlike the linear-quadratic
case, the feasibility of both primal and dual problems is not enough for the existence
of a saddle point. However, we will show that under Assumption 2.1, for any - 0; a
saddle point of l - (x; y) exists. We first prove a lemma.
Lemma 2.3 Suppose that the following relations are valid:
are the recession functions of OE(x) and /(y), respectively:
(The two recession functions are invariant regardless of the choice of x 2 X and y 2 Y:)
Then l - (x; y) has a saddle point on X \Theta Y.
Proof. According to convex analysis ([15], Theorem 37.6), a sufficient condition for
l - (x; y) to have a saddle point on X \Theta Y is that the convex functions l - (\Delta; y) have no
common direction of recession for y 2 ri Y and that the convex functions \Gammal - (x; \Delta) have
no common direction of recession for x 2 ri X , where "ri" stands for the relative interior.
Denote by R n
the nonnegative orthants of R n and R m , respectively. Now for
fixed y 2 ri Y, the set of directions of recession of l - (\Delta; y) is given by
Similarly, for fixed x 2 ri X , the set of directions of recession of \Gammal(x; \Delta) is
The statement "for y 2 ri Y there is no common direction of recession" is then interpreted
as (2.5). We also get (2.6) in the same fashion.
Proposition 2.4 Under Assumption 2.1, for any - 0; l - (x; y) has a saddle point on
X \Theta Y.
Proof. Suppose that Assumption 2.1 is satisfied by a quadruple
Note that
We have for any p 2 P y 0
(w
the above inequality implies Therefore we have
Analogously we have Q has a saddle point
on X \Theta Y.
Proposition 2.4 says that Assumption 2.1 is sufficient for the existence of optimal solutions
of problem (1.1) - (1.3) as well as for the existence of the solutions of (2.3) for
any - ? 0: From the strict convexity of sup y-0 l - (x; y) and \Gamma inf x-0 l - (x; y), it can be
seen that (x(-); y(-)) is unique for - ? 0. We call the set f(x(-); y(-))j- ? 0g the
central path of problem (1.1) if (x(-); y(-)) is a saddle point of l - (x; y) on X \Theta Y:
It should be noted that system (2.3) can be viewed as a monotone complementarity
problem of the mapping
Several conditions have been discussed in the literature for the existence of the central
path under various situations. For example G-uler [7] studies conditions for monotone
complementarity problems. It can be shown that his conditions are equivalent to the
one in Proposition 2.4 in the context of mapping F: Since Proposition 2.4 is deduced
from Lemma 2.3, it seems that the conditions of Lemma 2.3 are weaker than G-uler's
conditions in the context of saddle point problem (1.1).
We now estimate the error if the solution of system (2.3) is used as an approximate
solution to the saddle point problem (1.1). We prove that the duality gap of the solutions
on the central path converges to zero as - goes to zero. This is the basic fact that justifies
interior path-following algorithms.
Proposition 2.5 Under Assumption 2.1, given any - 0, we have
Proof. The assumption implies the existence of (x(-); y(-)), which, together with a
certain (w(-); s(-)), satisfies system (2.4). By definitions of f(x) and g(y), we always
have (the weak duality). Therefore we only need to
prove the second inequality. Analogous to the proof of Proposition 2.2, we have
The last equality above is based on the second equation of (2.4). A symmetric argument
for the dual problem implies
Proposition 2.5 is proved by subtracting (2.9) from (2.8):
Proposition 2.5 provides the estimation on the duality gap for the points on the central
path. Denote the positive diagonal matrices diag(x
respectively. For any - ? 0,
we do not have to obtain x(-) and y(-) exactly. In practice a path-following algorithm
generates a sequence of close to (x(- k ); y(- k )). The closeness is defined by a
proximity function
Wx
Sy
where e is a vector of ones of compatible dimension. Notice that ffi(x;
implies that (x; y) is on the central path, i.e., (x; little abuse
of the notations, the same e is used in (2.10) and below no matter what the dimension
is. The following result provides an error bound for an approximate solution of (2.3)
which satisfies (2.4) but may not satisfy the other equations of (2.3).
Proposition 2.6 If (x;
Proof. Notice that the proof of inequalities (2.8) and (2.9) only uses the relationships
in (2.4). Thus by following the proof of Proposition 2.5, we have
On the other hand,
Hence
Proposition 2.6 provides an estimation of the duality gap for the solutions in a neighborhood
of the center path. With this estimation, in order to find a pair of ffl-optimal
solution to (1.1) in the following sense
x is feasible to (1:2); y is feasible to (1:3); and 0 -
we only need to find a pair of primal and dual feasible solutions in a neighborhood of
the central path satisfying ffi(x;
3. Convergence Analysis of the Predictor-Corrector Algorithm
Given any point (x; number - ? 0 satisfying (2.4) and ffi(x;
ff; we consider a path following method for problem (1.1). A typical iteration in the
algorithm applies one step of Newton's method to the system
where - is a certain constant. From the Newton approximation of system (3.1), the
improving direction (\Deltax; \Deltay; \Deltaw; \Deltas) is determined by
\Deltay
\Deltay
The associated direction is called the predictor (affine-scaling) direction if
is called the corrector (centering) direction if 1. The following algorithm moves a
solution from a tight neighborhood of the central path to a loose one in each predictor
step in order to reduce the central path parameter -. It then draws a solution from
the loose neighborhood back to the tight one in each corrector step. The algorithm
terminates when - ffl=[(1
We now present the algorithm.
Algorithm 3.1 Algorithm for Problem (1.1))
such that the first two equations of (3.1) are satisfied by
and such that ffi(x
(where ffl is the user assigned
tolerance), do
Step 1.1 Solve (3.2) with
by \Deltax \Deltas p the resulting directions. Let ' be a positive number such
that
where
and
This is the predictor step.
Step 1.2 Solve (3.2) with
resulting in \Deltax c ; \Deltay c ; \Deltaw c and \Deltas c . Let
and - This is the corrector step. Update k and go to next iteration of Step
1.
We proceed to show that the algorithm is of polynomial complexity. For this purpose,
we make further assumptions on functions OE(x) and /(y):
The Scaled Lipschitz Condition (SLC) for OE(x) and /(y) :
Given
and
\Deltay T r 2 /(y)\Deltay
hold for any x ? 0; \Deltax; y ? 0 and \Deltay satisfying jjX
This condition has been employed in the analysis of interior point methods for convex
programs [33]. Functions satisfying this condition include many useful functions such as
could be
Note that OE(x) is not necessarily separable in general. The same can be said about /(y):
In an elegant paper [24], Tseng proposes a path-following algorithm for some variational
inequality problems which include nonlinear complementarity problems (NCP). It is
worth noting that the SLC condition on OE(x) and /(y) is weaker than the smooth
condition in [24] on the mapping
Because the smooth condition in [24] allows jjX
as in our condition, the smooth constant M will have to be infinite for some function
like log x or 1=x if \Deltax happen to be very close to \Gammax. In fact, these examples satisfy
the SLC but do not satisfy the smooth condition in [24] for the associated mapping F .
In the derivations below, we will frequently use relationships defined by (3.2) and the
following simple relationship:
For all x; s such that ffi(x; s; -; there holds
Analysis on the predictor step
Given
(The superscript k is omitted), we want to know how to choose ' such that
This will give us important information on the complexity of the algorithm because the
algorithm sets -
explicit formula for ' will be given following our analysis. Let
and
Let the diagonal matrices diag(\Deltax
and diag(\Deltas respectively. We use the conventional
notations such as
real number - and
Note that
\DeltaY \Deltas
\DeltaY \Deltas
and that
if the SLC is satisfied. Let
\DeltaY \Deltas
Now we estimate j 1 and j 2 separately.
Lemma 3.1
\DeltaX \Deltaw
\DeltaY \Deltas
Proof. Let
'' \Deltax
\Deltay
'' \Deltaw
\Deltas
and
Then we have
s
and
Therefore we get
'' \Deltaw
\Deltas
Since we will apply the SLC in the estimate of j 2 ; we need to prove the following lemma.
Lemma 3.2 In the predictor step, if
Proof. Let multiply both sides of
by X \Gamma1=2 W \Gamma1=2 we have
Therefore by using (3.3), we have
which in turn implies
Thus we have
as long as
The part about jj'Y \Gamma1 \Deltayjj can be proved similarly.
By the SLC, we have
similarly,
so we have the following estimate related to
Lemma 3.3 If
then
Proof. Setting in (3.2), we have
\Deltay
Multiply both sides of the first equation by \Deltax the second by \Deltay
\Deltay \Gamma\Deltay T s:
Adding the two equations together, we have
\Deltay
\Gamma\Deltay T (Y \Gamma1=2 S 1=2 )(Y 1=2 s \Gamma1=2
The second to the last inequality above is due to
ae
jjX \Gamma1=2 W 1=2 \Deltaxjj \Gamma2
and ae
jjY \Gamma1=2 S 1=2 \Deltayjj \Gamma2
jjY
0:
Proposition 3.4 Taking
we have fl fl fl fl
Proof. From (3.4), Lemmas 3.1 and 3.3 we have
\DeltaY \Deltas
This quantity will be not greater than tff(1 \Gamma ')- as long as
by simply solving a quadratic equation and picking the large root.
Replacing by the estimates in Lemma 3.1 and 3.3, such a ' satisfies:
Corollary 3.5 In each predictor step the central path parameter - can be reduced at
least by a factor of
positive constant depending on the
choices of ff; fi; t and the smooth coefficient M in the SLC.
Analysis on the corrector step
We begin the corrector step by ffi(x('); y('); w('); s('); - tff, our target is to show
that after the step we will have
where
and
We will follow the same clue used in the analysis of the predictor step. We estimate
\DeltaY \Deltas
in Lemma 3.6 and Lemma 3.8, while Lemma 3.7 will guarantee the use of the SLC.
Lemma 3.6 If ffi(x;
\DeltaY \Deltas
-:
Proof. Let
'' \Deltax
\Deltay
'' \Deltaw
\Deltas
Then
similar to the proof of Lemma 3.1,
we have fl fl fl fl
\DeltaY \Deltas
-:
Lemma 3.7 In the corrector step, if tff - fi=(1
Proof. Set (3.2), we get
\Deltay
Let
Multiply both sides of (3.5) by
we have
\Deltay
\Deltas
s
Also by the formulae of \Deltaw and \Deltas in (3.2) we get
\Deltax \Deltay
so we have -
\Deltay
\Deltas
'-
and
\Deltay
\Deltay
\Deltas
s
On the other hand,
\Deltay
\Deltay
Hence we get
tff
and
tff
Lemma 3.8 If ffi(x;
Proof. From (3.2) we have
Y
which implies
\Deltay \Deltay
Add the two equations together and arrange the terms
\Deltay
\Deltay
-:
The second inequality above is due to
ae
and ae
0:
Proposition 3.9 If the parameters ff; t; and M satisfy
for example we can choose
then we have
Proof. Using similar derivations to that of (3.4) and invoking Lemmas 3.6 - 3.8, we
have
\DeltaY \Deltas
Thus we have ffi(x which further implies
It is easy to see that In
addition, the choices of in the algorithm will ensure that condition
(2.4) is satisfied for all k. Thus x k and y k are feasible to problems (1.1) and (1.2),
respectively.
In summary, the algorithm keeps
each k while reducing - at a linear rate of From Proposition 2.5,
it is readily to see that, in order to find an ffl-optimal solution
satisfying
iterations are necessary.
usually larger than polynomial complexity of
O(
Taking advantage of the problem structure
Practical problems formulated as problem (1.1) often have special structures. For in-
stance, in the two-stage model of stochastic programming mentioned in Section 1, the
matrix r 2 /(y) is very large and block-diagonal whereas the matrix r 2 OE(x) is of ordinary
size. So the key point is how to reduce the amount of work for solving system (3.2).
The special feature of system (3.2) allows us to reduce the amount of computations
substantially. Let us elucidate this point in detail.
Problems with large, block-diagonal r 2 /(y) and small r 2 OE(x)
Substituting \Deltaw and \Deltas into the last two equations and canceling \Deltay; we obtain an
equivalent system to (3.2)
\Deltay
The principal work is to solve the first equation in (3.6). Since the dimension of x is
low (less than 100, say) we can solve system (3.6) exactly even if the dimension of y is
high. Notice that the matrix (r has a block-diagonal structure. Hence
can be computed blockwise. In particular the computation can
be proceeded in parallel. The solution of the first equation in (3.6) can be obtained by
a factorization of r which might be a dense
matrix but must be a low-dimensional and symmetric positive definite matrix. After \Deltax
is obtained from the first equation, \Deltay can be calculated through the second equation
of (3.6), using (r computed in the first step. In fact, we may store the
block factorizations of r in the first step for later use in the second step.
Subsequently we get \Deltaw and \Deltas:
Problems with large, block-diagonal r 2 /(y), r 2 OE(x) and block-banded A
Discretized optimal control problems often have large, block-diagonal r 2 /(y) and r 2 OE(x)
as described in [18] and [22]. In addition, the matrix A in problem (1.1) can be partitioned
into blocks such that resulting matrix of blocks is banded [28][29]. For instance,
the dynamic constraint system
can be expressed as an additional term in the saddle function (1.1):
are some additional dual vectors. By doing this, we generate
an infinite penalty for the violation of constraints (3.7) in problem (1.2). Let
be the primal control vector and be the primal state
vector. It can be seen that the submatrix of A of problem (1.1) corresponding to the
primal vector (u; x) and the dual vector (y;
\GammaB \GammaF
A
The computation of A T (r will require to compute the sub-
matrices
A T
S y and -
S z are some auxiliary diagonal matrices. Note that
A T
\GammaB \GammaF
\GammaB \GammaF
According to the structures of M is a block diagonal matrix,
21 is a block-band matrix with bandwidth 2, and matrix H 22 is also a
block-band one with bandwidth 3. Therefore it is possible to solve equation system (3.6)
by using block operations applied to a banded system.
The case of X and Y being boxes
Now we explain why changing X and Y into boxes will not complicate the computation.
Consider a simple case that both X and Y are close-end boxes. By introducing auxiliary
variables conditions (2.1) can be written in an
explicit form as follows:
The corresponding Newton equations become
\Deltay
where a are certain fixed vectors. After canceling all variables with superscript
1, we get a system whose major equations are
are certain fixed vectors. After canceling \Deltay; system (3.8) becomes a
similar system to (3.6). Therefore the computations needed for solving system (3.7) are
roughly the same as solving system (3.2). Hence there is no significant changes in the
algorithm if X and Y are changed into boxes. The case that X and Y are half-open-end
and half-close-end boxes can be treated analogously.
4. Conclusions and Final Remarks
We have shown the polynomiality of a predictor-corrector algorithm for a class of non-linear
saddle point problems. The model is an extension of the traditional Lagrange
multiplier model in optimization. The existence results on the central path and the
relationship between the central path and the duality gap established in Section 2 are
useful in developing other interior path-following algorithms.
Several issues deserve a further investigation.
(1) The smooth condition. We have proposed the SLC as the smooth condition. In the
context of convex programming, various smooth conditions were proposed to characterize
the problems which will have polynomial interior point algorithms. We refer the reader
to references [4] and [13] for more details. A direction of future studies is to identify
different classes of practical saddle point problems, which will have polynomial interior
point algorithms under smooth conditions weaker than the SLC.
(2) Infeasible starting point. Algorithm 3.1 requires a starting point near the central
path. It could be a major obstacle if such a starting point is not provided. Recently,
much research has been done on interior point algorithms starting from an infeasible
interior point, see [12][25][29] for examples. The algorithms reduce both infeasibility
and duality gap simultaneously. It makes practical sense to develop infeasible interior
point methods for saddle point problems like (1.1).
(3) Computation-related developments Primary studies [23][28][29] show that interior
point methods might be fairly efficient in solving linear-quadratic problems, but comparison
studies between interior point methods and other existing methods have not
been done. For large scale problems, it is crucial to reduce the amount of computations
for matrix inverse and Hessian evaluation. It is meaningful to develop algorithms that,
for instance, can use inexact directions (e.g. [23]), inaccurate Hessians, and approximate
factorizations in predictor and corrector steps.



--R

"Decomposition and partitioning methods for multistage stochastic linear programs"
"Efficient solution of two-stage stochastic linear programs using interior point methods"
"Computing block-angular Karmarkar projections with application to stochastic programming"
"A unifying investigation of interior-point methods for convex programming"
"On the solution of two-stage linear programs under uncertainty"
"Interior point path following algorithms"
"Existence of interior point and interior paths in nonlinear monotone complementarity problems"
"A predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence"
"An implementation of the Lagrange finite generation method"
"A primal-dual algorithm for a class of linear complementarity problems"
"A unified approach to interior point algorithms for linear complementarity problems"
"A superlinearly convergent infeasible-interior-point algorithm for geometrical LCPs without strictly complementary condition"
Interior Point Polynomial Algorithms in Convex Programming
"An SQP algorithm for extended linear-quadratic problems in stochastic programming"
Convex Analysis
"Linear-quadratic programming and optimal control"
"Computational schemes for large-scale problems in extended linear-quadratic programming"
"Large-scale extended linear-quadratic programming and multi-stage optimization"
"Nonsmooth Optimization"
"A finite simplex-active-set method for monotropic piecewise quadratic programming"
" A Lagrangian finite generation technique for solving linear-quadratic problems in stochastic programming"
" Generalized linear-quadratic problems of deterministic and stochastic optimal control in discrete time"
" An inexact predictor-corrector method for extended linear-quadratic programs"
"Global linear convergence of a path-following algorithm for some monotone variational inequality problems,"
" An infeasible path-following method for monotone complementarity problem "
"L-shaped linear programs with applications to optimal control and stochastic linear programs"
" Solving stochastic programs with simple recourse"
"Interior point methods for optimal control of discrete-time systems"
"A superlinear infeasible-interior-point algorithm for Monotone complementarity problems"
"On quadratic and O( p nL) convergence of a predictor-corrector algorithm for LCP"
"On the primal-dual steepest descent algorithm for extended linear-quadratic programming"
" Primal-dual projected gradient algorithms for extended linear-quadratic programming"
"A path-following algorithm for a class of convex programming problems"
--TR
optimal control;nonlinear complementarity problem;interior point methods;saddle point problem;stochastic programming