Two-Step Algorithms for Nonlinear Optimization with Structured Applications.
In this paper we propose extensions to trust-region algorithms in which the classical step is augmented with a second step that we insist yields a decrease in the value of the objective function. The classical convergence theory for trust-region algorithms is adapted to this class of two-step algorithms.  The algorithms can be applied to any problem with whose contribution to the objective function is a known functional form.  In the nonlinear programming package LANCELOT, they have been applied to update slack variables and variables introduced to solve minimax problems, leading to enhanced optimization efficiency.  Extensive numerical results are presented to show the effectiveness of these techniques.
Introduction
In nonlinear optimization problems with expensive function and gradient evaluations, it is desirable
to extract as much improvement as possible at each iteration of an algorithm. When the objective
function contains a subset of variables that occurs in a predictable functional form, a second,
computationally relatively inexpensive, update can be applied to these variables following a classical
optimization step. The additional step provides a further reduction in the objective function
and can lead to superior optimization e-ciency. The two-step algorithms have been successfully
applied to the updating of slack variables and to a particular formulation of minimax problems, as
is indicated by numerical results on a variety of problems. In these instances a subset of variables
(slack variables and variables introduced to solve minimax problems) appears in a xed, known
algebraic form in the objective function. However, since it can be applied to any problem where
a subset of the variables can be optimized relatively cheaply compared with the cost of evaluating
the entire function (for example if some terms require simulation and other independent terms are
Department of Mathematical Sciences, IBM T. J. Watson Research Center, Route 134 and Taconic, Room 33-206,
Yorktown Heights NY 10598.
y Departamento de Matematica, Universidade de Coimbra, 3000 Coimbra, Portugal. This work started when this
author was visiting the IBM T. J. Watson Research Center at Yorktown Heights and was supported in part by Centro
de Matematica da Universidade de Coimbra, Instituto de Telecomunicac~oes, FCT, Praxis XXI 2/2.1/MAT/346/94,
and IBM Portugal.
z Computer Architecture and Design Automation, IBM T. J. Watson Research Center, Route 134 and Taconic,
Room 33-156, Yorktown Heights NY 10598.
available analytically), their applicability is really rather broad. We propose modications to existing
nonlinear optimization algorithms. An alternative approach, when feasible, is to reformulate
the original problem by eliminating a subset of variables and then to apply the algorithms in the
remaining variables (see, for example, Golub and Pereyra [17]).
This paper deals with two-step algorithms where the second step is required to yield a decrease
in the value of the objective function. The analysis given here covers the global convergence of
two-step trust-region algorithms and it is presented for the unconstrained minimization problem:
continuously dierentiable function. For both trust
regions and line searches, one can consider two versions of the two-step algorithms, one called
greedy and the other called conservative. The greedy version exploits as much as possible the
decrease obtained by the second step, whereas the conservative approach calculates the second step
only after the rst step has been conrmed to satisfy the traditional criteria required for global
convergence. We point out that the conservative two-step line-search algorithm is not new and can
be found in the books by Bertsekas [1], Section 1.3.1, and Luenberger [19], Section 7.10, where the
second step is called a spacer step. A description of the greedy and conservative two-step line-search
algorithms can be found in [11].
In trust regions, if the second step is guaranteed to decrease the value of the objective function,
global convergence of the type lim inf k !+1 krf(y k immediately attained. Further, in
the cases where the rst step would be rejected, the sum of the rst and second steps has a better
chance of being accepted (see Remark 3.1). To obtain lim k !+1 krf(y k either the norm of
the second step has to be controlled by the trust region (see condition (13)) or the decrease on the
objective function attained by the second step has to be of the order of magnitude of the norm of
this step (see condition (12)).
The update of the slack variables referred to above motivated the study of the local rate of
convergence of a two-step Newton's method. We show that a second Newton step in some of the
variables retains the q-quadratic rate of convergence of the traditional Newton's method.
This paper is structured as follows. In Section 2 we introduce the two-step trust-region al-
gorithms, and in Section 3 we analyze their global convergence properties. The local rate of the
two-step Newton's method is studied in Section 4. The application of the two-step ideas to update
slack variables and variables introduced for the solution of minimax problems is described in Section
5. Section 6 presents the numerical results obtained with LANCELOT using these updates for analytic
problems and dynamic-simulation-based and analytic static-timing-based circuit optimization
problems. Finally, some conclusions are drawn in Section 7.
Two-step trust-region algorithms
We rst consider the trust-region framework presented in the paper by More [20] for unconstrained
minimization. The (classical) trust-region algorithm builds a quadratic model of the form
at the current point y k , where H k is an approximation to r 2 f(y k ) (note that m k (y k
Then a step s k is computed by approximately solving the trust-region subproblem
subject to ksk   k ;
where  k is called the trust-region radius and kk is an arbitrary norm. The new point y
is tested for acceptance. If the actual reduction f(y k larger than a given fraction of
the predicted reduction m k (y k then the step s k and the new point y k+1 are accepted.
In this situation, the quadratic model m k (y is considered to be a good approximation to the
function f(y) in the region . The trust radius may be increased. Otherwise, the
is considered not to be a good approximation to the function f(y) in
the region . In this case, the new point y k+1 is rejected, and a new trust-region
subproblem of the form (2) is solved for a smaller value of the trust radius. This simple trust-region
algorithm is described below.
Algorithm 2.1 (Trust-region algorithm)
1. Given y 0 , the value f(y 0 ), the gradient rf(y 0 ) and an approximation H 0 to the Hessian of f
at y 0 , and the initial trust-region radius  0 . Set
and  in (0; 1).
2. Compute a step s k based on the trust-region problem (2).
3. Compute
4. In the case where
set
compute H k+1 , and select  k+1 satisfying  k+1   k .
Otherwise, set
5. Increment k by one and go to Step 2.
The mechanism used to update the trust radius that is described in Algorithm 2.1 is simple and
su-ces to prove convergence results. In practice, with the goal of improving optimization e-ciency,
one uses updating schemes that are more complex involving several subcases according to the value
of  k .
We propose in this paper a modication of this trust-region algorithm. We are motivated by a
situation where it is desirable to update slack variables and variables introduced to solve minimax
problems, at every iteration of the trust-region algorithm [7] implemented in LANCELOT [9]. See
Section 5 for more details on practical applications.
The two-step trust-region algorithm is quite easy to describe. Suppose that after computing a
step  s k based on the trust-region subproblem (2) we know some properties of the function f(y) that
enables us to compute a new step ^ s k for which we can guarantee that f(y k
In this situation we would certainly like to have y and to test whether this new
point should be accepted or not. This modication requires a careful redenition of the actual and
predicted reductions given for Algorithm 2.1. The new actual and predicted reductions that we
propose are:
ared(y
pred(y
The new predicted reduction is the predicted reduction obtained by the rst step plus the (actual)
reduction obtained by the second step. The choice pred(y k ;  s
not appropriate since the second step ^ s k is not computed using the model m k (y k
The two-step trust-region algorithm is given below.
Algorithm 2.2 (Two-step trust-region algorithm { Greedy)
1. Same as in Algorithm 2.1.
2. Compute a step
s k based on the trust-region problem (2).
3. If possible, nd another step ^ s k such that
4. Compute
pred(y
5. In the case where
set
compute H k+1 , and select  k+1 satisfying  k+1   k .
Otherwise, set
6. Increment k by one and go to Step 2.
The two-step trust-region Algorithm 2.2 evaluates the new point y acceptance
after both steps  s k and ^ s k have been computed. We call this version \greedy" because it tries
to take as much advantage as possible of the decrease obtained by the second step ^ s k . Note that
although the function f is evaluated twice in Algorithm 2.2, the reevaluation is often computationally
inexpensive. The context in which we are particularly interested involves relatively expensive
evaluations at y k and evaluations at y k
involving only a subset of the variables that
are cheap to compute (see Section 5).
We could also consider a two-step trust-region algorithm where rst an acceptable step  s k is
determined, and only afterwards a second step ^ s k is computed. This algorithm is outlined below.
Algorithm 2.3 (Two-step trust-region algorithm { Conservative)
1. Same as in Algorithm 2.1.
2. Repeat
(a) Compute a step
s k based on the trust-region problem (2).
(b) Compute
(c) If  k > , then set
compute  k+1 satisfying  k+1   k , and set accepted = true.
If  k  , set
k and accepted = false.
Until accepted.
3. If possible, nd another step ^ s k such that
4. Set y
s k .
5. Update H k . Increment k by one and go to Step 2.
The same comments about the function evaluations apply to Algorithm 2.3 after the computation
of a successful step  s k . However, in the case of Algorithm 2.3, the function f has to be
evaluated twice only in iterations corresponding to successful rst steps  s k .
3 Global convergence of the two-step trust-region algorithms
We analyze rst the two-step trust-region Algorithm 2.2, i.e., the greedy version. The analysis for
the conservative Algorithm 2.3 is similar.
In this section we make the assumption that fH k g is a bounded sequence. So, there exists a
> 0 for which
We require the step
s k to satisfy a fraction of Cauchy decrease on the trust-region problem (2). In
other words we ask  s k to satisfy
for  2 (0; 1]. The step c k is called the Cauchy step, and it is dened as the solution of the scalar
problem in the unknown
subject to ksk   k ;
There is a variety of algorithms that compute steps satisfying this condition (see [3], [22], [23], [25],
and [26]).
Proposition 3.1 If
a fraction of Cauchy decrease then:
krf(y k )k
where  and  are as in (6) and (5) respectively.
Proof: See Powell [24], Theorem 4, or More [20], Lemma 4.8. 2
If we use this proposition and the fact that f(y k
pred(y
krf(y k )k
krf(y k )k
This inequality is crucial to prove global convergence of the two-step algorithm. In particular, if
the iteration k is successful, then
ared(y
We are ready to prove the rst convergence result.
Theorem 3.1 Consider a sequence fy k g generated by Algorithm 2.2 where  s k satises (6). If f is
continuously dierentiable and bounded below on
and fH k g is a bounded sequence, then
lim inf
krf(y
So, if the sequence fy k g is bounded, there exists at least one limit point y  for which rf(y
Proof: The proof is similar to the proof given in [20], Theorem 4.10.
Assume by contradiction that fkrf(y k )kg is bounded away from zero, i.e., that there exists an
> 0 such that krf(y k )k   for all k. As in [20], Theorem 4.10, we make direct use of (9) and of
the rules that update the trust radius, to obtain:
and so lim k !+1
The next step is to show that lim k
Note that from the denitions (3) and
(4), we have
ared(y
which in turn, by using a Taylor series expansion and ks k k   k , implies
This inequality and (8) show that
converges to zero. The rest of the proof follows a
classical argument in trust regions: if ^
k converges to one, the rules that update the trust radius
show that  k cannot converge to zero. So, a contradiction is attained and the proof is completed. 2
The result of Theorem 3.1 does not require the step ^ s k to be O( k ) which may seem surprising.
This result shows the appropriateness of the denitions given in (3) and (4) for the actual and
predicted reductions. These denitions allow us to obtain the conditions (9) and (11) that are
crucial to establish (10).
Remark 3.1 It is also important to note that the denitions (3) and (4) can improve the acceptability
of a step. In fact, we have
before. We now note that ^
k and the function ^
strictly increasing if  k < 1. In other words, in cases where a
standard trust-region algorithm rejects a step the modied criterion is always better than the usual
one. Further, it can be noted that ^
which indicates that all successful iterations of
the the standard algorithm will also be successful in the modied two-step algorithm. In particular,
The next step in the analysis is to prove that, with additional conditions on the second step,
Theorem 3.2 Consider a sequence fy k g generated by Algorithm 2.2 where
that f is continuously dierentiable and bounded below on L(y 0 ) and that fH k g is a bounded
sequence. If rf is uniformly continuous on L(y 0 ) and if either
or
are positive constants independent of k, then
lim
krf(y
So, if the sequence fy k g is bounded, every limit point y  satises rf(y
Proof: The proof is similar to the proof given in [20], Theorem 4.14. See also Thomas [27].
We show the result by contradiction. Assume therefore that there exists an  1 2 (0; 1) and
a subsequence indexed by fm i g of successful iterates such that, for all m i in this subsequence,
Theorem 3.1 guarantees the existence of another subsequence indexed by fl i g
such that krf(y k )k   2 , for m i  k < l i and krf(y l i )k <  2 (where fm i g is without loss
of generality the subsequence previously mentioned). Here  2 is any real number chosen to be in
converges to zero, for k su-ciently large corresponding to successful
iterations
holds if (12) is satised, and
holds otherwise with
.
We consider the cases (12) and (13) separately. In both cases we make use of:
In the sums
we consider only indices corresponding to successful iterations.
If (12) holds then we use (15) to obtain
[ks
If (13) holds then we appeal to (16) and write
[ks
In either case we obtain
and since the right hand side of this inequality goes to zero, so does the left hand side
Since the gradient of f is uniformly continuous, we have for i su-ciently large that
can be any number in (0;  1 ) this inequality contradicts the supposition. 2
In the theorem above we required the norm of the step ^
s k to either be O( k ) or O (f(y k
)). The former condition can be enforced in Step 2 of the Algorithm 2.2, although
this might not be benecial and could lead to an inferior decrease.
We can obtain global convergence to a point that also satises the necessary second-order
conditions for optimality. For this purpose, we require the step  s k to satisfy a fraction of optimal
decrease for the trust-region problem (2). In other words we ask  s k to satisfy
where  2 (0; 1], and s
k is an optimal solution of (2). (This condition can be weakened in several
ways [20].) A step  s k satisfying a fraction of optimal decrease can be computed by using the
algorithms proposed in [22] and [25] in the case where the trust-region norm is Euclidean. The
global convergence result is the following.
Theorem 3.3 Consider a sequence fy k g generated by Algorithm 2.2 where H
satises (17). If L(y 0 ) is compact and f is twice continuously dierentiable on L(y 0 ), then there
exists at least one limit point y  for which rf(y  positive semi-denite.
Proof: The proof is basically the same as the proof of Theorem 4.7 in [22]. 2
To obtain stronger global convergence results to second-order points, for instance the results in
Theorems 4.11 and 4.13 in [22] (see also [21], Theorem 4.17, c and d), other conditions are required
like k^s k k being of O( k ).
The next results show that the second step can preserve the nice local properties of the behavior
of the trust radius that are typical in trust-region algorithms.
Theorem 3.4 Let fy k g be a sequence generated by Algorithm 2.2 where
In addition, assume that the step ^
s k satises either condition (12) or condition (13). If
f is twice continuously dierentiable and bounded below on L(y 0 ) and fy k g has a limit point y
such that H positive denite, then fy k g converges to y  , all iterations are eventually
successful, and f k g is bounded away from zero.
Proof: From Theorem 3.2 we can guarantee that lim k !+1 krf(y k the proof is
basically the same as the proof of Theorem 4.19 in [20]. 2
An alternative to this result where we do not impose conditions (12) or (13) on the second step
is given below. However we need to assume that fy k g converges to y  .
Theorem 3.5 Let fy k g be a sequence generated by Algorithm 2.2 where
continuously dierentiable on L(y 0 ) and fy k g converges to a point y  such
that H positive denite, then all iterations are eventually successful and f k g is
bounded away from zero.
Proof: The rst step
s k yields a decrease in the quadratic model:
Thus, the assumptions made on H k and H  guarantee
ks
for su-ciently large k, which in turn, by using (8), implies
pred(y ks k
(The constants c 3 and c 4 are independent of k.)
A Taylor series expansion for the expression (11) gives
The fact that fy k g converges and the result lim inf k !+1 krf(y k Theorem 3.1, together
imply lim k !+1 krf(y k Thus, from (18) we get lim k !+1 ks k
The proof is terminated with a typical argument in trust regions. From (19), (20) and lim k !+1
ks we obtain the limit
lim
pred(y
which shows, by appealing to the rules that update the trust radius, that all iterations are eventually
successful and the trust radius is uniformly bounded away from zero. 2
The global convergence analysis for Algorithm 2.3 is identical to the analysis given above for
Algorithm 2.2. We point out that Algorithm 2.3 is well dened since at a nonstationary point it is
always possible to nd an acceptable rst step. Also, for every k,
krf(y k )k
krf(y k )k
Thus, the results given in Theorems 3.1-3.5 hold for Algorithm 2.3. The lim inf-type result (10) is
obtained under the classical assumptions for trust-region algorithms for unconstrained optimization.
To obtain the lim-type result (14) one of the two conditions (12) and (13) is required.
In the case of the applications considered in Section 5, the decrease obtained by the second step
s k is always guaranteed to satisfy
Moreover, the objective function strictly decreases along the segment between the points y k
and
s k . In this case we can modify Step 3 of Algorithms 2.2 and 2.3 in such a way that
we meet the requirements of Theorem 3.2. This modication is given below. It is easy to verify
that
either (12) or (13).
Algorithm 3.1 (Step 3 for Algorithms 2.2 and 2.3 { Quadratic decrease case)
3. Compute a step ^
s k such that
g so that k^s k k  c 2  k and ^
s k is not enlarged.
(Otherwise (12) holds with c
The positive parameters  and c 2 should be set a priori in Step 1 of Algorithms 2.2 and 2.3.
Of course, we would like to prove the result of Theorem 3.2 for the case where the condition
(12) is replaced by the condition (21). However, such a result is unlikely to be true.
4 Local rate of convergence of a two-step Newton's method
In the next section we are interested in two-step algorithms where the second step is calculated
as a Newton-type step in some of the variables. In this section we investigate the local rate of
convergence for an algorithm where each step is composed of two Newton steps, the second being
computed only for a subset of the variables. For this purpose let

x
Suppose the rst step  s k is a full Newton step, i.e.,  s

At the intermediate point  y k , a Newton step is applied in the variables u with
x k xed. This
two-step Newton's method is described below.
Algorithm 4.1 (Two-step Newton's method)
1. Choose y 0 .
2. For do
2.1 Compute
s k .
2.2 Compute
and set s
s k .
2.3 Set y
The proof of the local convergence rate of the two-step Newton's method requires a few modications
from the standard proof of Newton's method [12], Theorem 5.2.1. Recall that that proof
of Newton's method is by induction.
Corollary 4.1 Let f be twice continuously dierentiable in an open set D where the second partial
derivatives are Lipschitz continuous. If fy k g is a sequence generated by Algorithm 4.1 converging
to a point y  2 D for which rf(y  positive denite, then fy k g converges with
a q-quadratic rate.
Proof: If y k is su-ciently close to y  , the perturbation result [12], Theorem 3.1.4, can be used to
prove the nonsingularity of the Hessian matrix r 2 f(y k ). Furthermore,
Now we show that r 2
First we point out that r 2
uu f(y) is Lipschitz
continuous on D and r 2
uu f(y  ) is positive denite. Thus, inequality (22) and the perturbation
lemma cited above, together imply the nonsingularity of r 2
Hence the method is locally
well-dened, and the second step yields
since r u f(y) is Lipschitz continuous near y  . Now we use inequalities (22) and (23), and write
This last inequality establishes the q-quadratic rate of convergence. 2
Applications
We begin by considering updating the slack variables in LANCELOT. Suppose the problem we are
trying to solve has the form
minimize f(x)
subject to c i (x)
are positive integers. The technique implemented in the LANCELOT
package [9] is the augmented Lagrangian algorithm proposed by Conn, Gould, and Toint in [8]. For
the application of the augmented Lagrangian algorithm this problem is reformulated as:
minimize f(x)
subject to c i (x)
by adding the slack variables u i , m. This algorithm considers the following augmented
Lagrangian merit function:
where:
i is an estimate for the Lagrange multiplier associated with the i-th constraint,
is a (positive) penalty parameter,
s ii is a (positive) scaling factor that is associated with the i-th constraint, and
solves a sequence of minimization problems with simple bounds of the
following
subject to u
for xed values of , s ii , and  i , m. The two-step trust-region framework and analysis
described in this paper for unconstrained minimization problems can be extended in an entirely
straightforward way to a number of algorithms for minimization problems with simple bounds, in
particular to the algorithms [7] used by LANCELOT to solve problem (25).
If x is xed, the function (x; in the slack variables u. Let us denote this
quadratic by q(u; x):
where d(x) and e(x) depend on x but F is constant. (The dependency on  i , s ii , and  is not
important since these are constants xed before the minimization process is started.)
The key idea is to update these slack variables at every iteration k of the trust-region algorithm
[7] that is used in LANCELOT to solve problem (25). The trust-region algorithm computes, at the
current point y k , a rst step  s k . Now, at the new point y
s k we compute the step ^ s k by updating
the slack variables u. So, we have


where
(Here f represents the objective function of Sections 1-4.) Note that the second step ^ s k is exclusively
in the components associated with slack variables. This step is computed as u k+1
is the optimal solution of
subject to u
Due to the simple form of this quadratic, the solution is explicit:
s ii
It is important to remark that these updates require no further function or gradient evaluations.
They have also been considered in the codes NPSOL and SNOPT [15], [16] to update slack variables
after the application of a line search to the augmented Lagrangian merit function and prior to the
solution of the next quadratic programming problem. Other ways of dealing with slack variables
have been studied in the literature (see Gould [18] and the references therein).
For the study of the impact of the slack variable update on the global convergence of the trust-region
algorithm, the step in these variables is required only to decrease the quadratic q(u;
u k to  u k +u k . In such a case, we can always guarantee that the decrease in the objective function
is larger than k^s k k 2 , that is that (21) holds. This result is shown in the following proposition. We
drop
x k from q(  ;  x k ) to simplify the notation.
Proposition 5.1 There exists a positive constant c 5 such that, whenever q(u k +u k ) < q(u k ), we
have
Proof: First we write down a few properties of the quadratic q(u). Simple algebraic manipulations
lead to:
Also, since q(u) is convex:
Let c be a positive constant such that c < min
is the smallest eigenvalue of
F . Now we consider two cases.
1.
cku k k 2 . In this case we use (29), to obtain
2.
. In this case we appeal to (28) and
to get
min
The proof is completed by setting c
cg. 2
Another example of the application of two-step algorithms arises in one approach to the solution
of minimax problems. Consider the following
where each f i is a real-valued function dened in IR n . One way of solving this minimax problem is
to reformulate it as a nonlinear programming problem by adding an articial variable z. See [18]
for more details. This leads to
minimize z
subject to z f i (x)
where the slack variables have also been introduced. If LANCELOT is used to solve this nonlinear
programming problem, then the augmented Lagrangian algorithm requires the solution of a
sequence of problems with simple bounds of the type:
subject to u
where
In this situation the function (x; z; in the variables u and z for xed values
of x. (Again, , S, and  are constants and not variables for problem (32).) The application of the
two-step trust-region algorithm follows in a similar way. The Hessian of the quadratic is positive
semi-denite with the following form
where the last row and the last column correspond to the variable z. The solution of the quadratic
program
minimize q(z; u;
subject to u
is given by
s ii
where z k+1 is the solution of the equation
s ii
s ii
with right hand side
s ii
The equation (35) is solved easily with O(m)
oating point operations and comparisons, showing
that the solution of the quadratic program (33) is a relatively inexpensive calculation.
There are several nonlinear optimization problems in which some subset of the problem variables
occur linearly, for example, arrival times in static-timing-based circuit optimization problems [6].
Such problems can also benet from two-step updating.
6 Numerical tests
6.1 Analytic problems
We modied LANCELOT (Release A) [9] to include the slack variable update (27) and the slack
and minimax variable updates (34)-(36). These updates were incorporated in LANCELOT using
a greedy two-step modication of the trust-region algorithm [7] for minimization problems with
simple bounds that is implemented in the subroutine SBMIN. (The greedy two-step trust-region
algorithm for unconstrained minimization problems is Algorithm 2.2.) We tested the following
versions of LANCELOT:
1. LANCELOT (Release A) with the default parameter conguration SPEC.SPC le, except that
we increased the maximum number of iterations to 4000.
2. Version 1 with the slack and minimax variable updates (27) and (34)-(36) incorporated in
SBMIN using a greedy two-step trust-region algorithm.
3. The same as Version 2 but with no update of the variable z for minimax problems, i.e., z
xed in (34)-(36).
We compared the numerical performance of these three versions on a set of problems 1 from
the CUTE collection [2]. This set of problems is listed in Table 1, and in the case of minimax
formulations in Table 2, where we mention the number of variables (including slacks and, where
applicable, the minimax variable z), the number of slack variables, and the number of equality and
inequality constraints (excluding simple bounds on the variables). Note that the minimax problems
were reformulated as nonlinear programming problems by the introduction of an additional minimax
variable z as shown above (31).
The computational results are presented in Tables 3, 4, and 5. All tests were conducted on an
IBM Risc/System 6000 model 390 workstation. In Table 3 we compare the results of Versions 1
and 2 for problems that are not minimax problems. In Table 4 we present the results of Versions
1 and 2 for minimax problems. In Table 5 we include the results of Versions 1 and 3 for minimax
problems. In Tables 4 and 5 we include the majority of the minimax problems but not all (see
Section 6.3 for numerical results on the remaining problems). In these tables we report the value of
the
ag INFORM, the number of iterations, the total CPU time, and the determined values (a single
value if they are both the same) of the objective function. The values of INFORM have the following
meaning:
meaning that the norm of the projected gradient of the augmented
Lagrangian function has become smaller than 10 5 .
cases where the maximum number of iterations (4000) has been reached.
cases where the norm of the step has become too small.
Our conclusion based on these sets of problems is that the version with the slack and minimax
variable updates exhibits superior numerical behavior. In fact, this version required an average of
15% fewer iterations than the version without these updates (the problems HS109, HAIFAM, and
POLAK6 were excluded from this calculation, mainly because the comparison was extraordinarily
favorable in the case of the rst two and worse in the last). Comparing Tables 4 and 5, updating the
variable z in addition to two-step updates on just the slacks is seen to yield a signicant
benet. However, there are some minimax problems where the two-step algorithm performs poorly
and this situation is analyzed in detail in Section 6.3.
Although CUTE contains more than 56 problems with general constraints the majority of these are equality
constrained problems. We excluded all problems that took more than 4000 iterations with both Versions 1 and 2.
We included the rest, with the exception of some problems that are too easy, making a total of 56 problems of which
are minimax problems and 26 are non-minimax problems.
Problem Name Variables Slacks Constraints
CORE1
CORE2 157 26 134
CORKSCRW
HADAMARD 769 512 648
HS85 26 21 21

Table

1: Non-minimax problems from the CUTE collection that were used.
6.2 Circuit optimization problems
We have built extensive experience with circuit optimization problems, where { due to expensive
function evaluations, modest numerical noise levels, and practical stopping criteria { the implementation
is designed to terminate before many \asymptotic" iterations are taken. The algorithms
described in this paper have been used in a dynamic-simulation-based circuit optimization tool
called JiyTune (see [4], [5], and [10]). JiyTune optimizes transistor and wire sizes of digital integrated
circuits to meet delay, power, and area goals. It is based on fast circuit simulation and
time-domain sensitivity computation in SPECS (see [13] and [28]). To optimize multiple path delays
through a high-performance circuit, the tuning is often formulated as a minimax problem or a
minimization problem with nonlinear inequality constraints.
We remark that many of the analytic problems (especially the minimax problems) are rather
small and involve inexpensive function evaluations. Moreover, it is clear that two-step updating is
unlikely to be helpful asymptotically in these situations. Consequently we also report numerical
results with circuit optimization problems which are indicative of problems with expensive function
evaluations, where termination (because of inherent noise and practical considerations) is encouraged
to be before any signicant asymptotic behavior. The numerical results are presented in Table
6. As in Version 1, the second step consisted of the slack and minimax variable updates (27) and
(34)-(36). However the gradient and constraint tolerances used were 10 respectively,
Problem Name Variables Slacks Constraints
COSHFUN 81 20 20
GOFFIN 101 50 50
HAIFAL 9301 8958 8958
HALDMADS 48 42 42
MINMAXBD

Table

2: Minimax problems from the CUTE collection that were used.
with some safeguards related to an expected level of numerical noise. We can clearly observe from

Table

6 that the two-step algorithm leads to better nal objective function values. In practical
applications where a simple function evaluation takes more than ten minutes of CPU time the
eectiveness of such a simple addition is indeed signicant. (There are situations where the greedy
two-step trust-region algorithm is able to take advantage of the decrease given by the slack and
variable updates and, by doing so, this algorithm can accept steps that otherwise would
have been rejected, see Remark 3.1.)
We also applied the algorithms of this paper to analytic static-timing-based circuit optimization
problems (see Table 7), where it is clear that the advantage of the two-step approach is increasingly
apparent for larger problems.
Problem Name Inform Iterations Total CPU Obj. Function
CORE1 0/0 953/983 7.41/17 91.1
CORE2 0/0 1048/1086 25.6/25.7 72.9
CORKSCRW 0/0 41/42 0.55/0.54 1.16
HADAMARD 0/0 1709/548 2290/276 1.14/1
TFI3 0/0 23/34 0.38/0.38 4.3

Table

3: Comparison between Versions 1 and 2 for non-minimax problems (LANCELOT with-
out/with two-step updating).
6.3 Further experiments with minimax problems
In this section we consider those minimax problems in our test set for which the two-step algorithm
not only does not improve numerically the results obtained in the one-step case, but also makes
them considerably worse (see the rst part of Table 8). We analyze the reasons for the failure of the
two-step updating on some minimax problems and discuss a few ways to enforce better numerical
behavior.
We consider the general minimax problem (30). Our aim is to show that for some types of
problems the second step has a tendency to make the Hessian of  ill-conditioned. Let us
assume that  (as happens by default for the rst LANCELOT
major iteration). Under these circumstances, we have:
By using the notation g i (x; z; we have the following expressions for the elements
TWO-STEP ALGORITHMS FOR NONLINEAR OPTIMIZATION 20
Problem Name Inform Iterations Total CPU Obj. Function
CONGIGMZ 0/0 32/19 0.04/0.05 28
COSHFUN 0/0 127/69 1.31/1.06 -0.773
GOFFIN 0/0 14/4 1.03/0.67 0

Table

4: Comparison between Versions 1 and 2 for minimax problems (LANCELOT without/with
two-step updating).
of the gradient of :
r z
r
Similarly the elements of the Hessian matrix of  are given by:
for If the magnitudes of the products r 2
are small compared to those of the products r x then the Hessian of  is given
Problem Name Inform Iterations Total CPU Obj. Function
CONGIGMZ 0/0 32/25 0.04/0.1 28
COSHFUN 0/0 127/92 1.31/1.08 -0.773
GOFFIN 0/0 14/8 1.03/0.66 0

Table

5: Comparison of Versions 1 and 3 for minimax problems (LANCELOT without/with two-step
updating only on slacks).
approximately
a i1 a
a i1 a in
a i1 a
i a in a
i a in a in
i a in a
i a in
a
and the indices i in the sums go from 1 to m. This matrix is clearly
singular. In fact, the n 1-st row is the negative sum of the last m rows. Moreover, any of the
rst n rows is a linear combination of the last m rows. As result of these observations, the Hessian
(and the projected Hessian) of  is ill-conditioned if
(37)
happens for \many" indices j and k. This is the key point in this analysis: the second step has
a tendency to produce iterates that worsen property (37) because it produces a decrease on the
Problem Name Variables Ineq. Iterations Total CPU Obj. Function
IOmuxpower 102 42 21/29 7230/9220 -15100/-16000
coulman cold 33 17 22/22 69.5/68.3 271/262
clkgen 22 5 25/5 35/10.8 1.98/1.82
coulman hot 33 17 16/32 46.2/100 283/253
coulman delay 33 17 26/24 72.6/73.5 116/111
Minimax:
bultmann latch
stall1
coulman cold minmax 34 17 61/80 184/229 69.4/66.9
coulman hot minmax 34 17 66/44 197/134 74.4/75.1
eischer
northrop xor
coulman delay minmax 34 17 100/100 290/306 67.4/70.5

Table

updating for dynamic-simulation-based circuit optimization
problems. Ineq. stands for the number of inequality constraints.
values of g i (x; z; u) for some indices i. The Hessian of  might very well be ill-conditioned if no
second steps are applied, but there is no doubt (and the numerical results are a evidence of this
claim) that the second step for some problems worsens the situation by making the Hessian of
more ill-conditioned.
In the presence of nonzero Lagrange multipliers  i , m, the formulae for the gradient
and Hessian of  are the same with g i (x; z; u) substituted by g i (x; z; u)+ i and similar conclusions
could be drawn.
The second step may produce very bad results on some minimax problems because it points
towards the set f(x; z; (where the Hessian of the augmented Lagrangian
is ill-conditioned) and this eect in
uences negatively the calculation of the rst step at
the next iteration. Given this undesirable feature of the Hessian of  at points close to this set,
one possible improvement to the two-step algorithm is to make sure that the calculation of the rst
step is accurate (in the LANCELOT context this could be achieved by choosing a smaller tolerance
for the stopping criterion of the conjugate-gradient technique). Another possible improvement is to
reduce the ill-conditioning of the Hessian of  (for instance by increasing the value of the penalty
parameter  as can be seen in examples with a few variables). Indeed, these modications improve
the bad numerical results presented before: in the second part of Table 8 we compare the results
obtained by the following modications of Versions 1 and 2:
4. Version 1 with an initial value for the penalty parameter  of 100 (the default value is 0:1).
5. Version 2 with an initial value for the penalty parameter  of 100 and a tolerance of 10 12 in
Problem Name Variables Ineq. Iterations Total CPU Obj. Function
Symmetric 9

Table

7: LANCELOT without/with two-step updating for analytic (minimax) static-timing-based
circuit optimization problems. Ineq. stands for the number of inequality constraints.
the stopping criterion for conjugate gradients.
The study of strategies that can make two-step updating more eective for minimax problems in
general is the subject for future research.
7 Concluding remarks
In this paper we presented and analyzed a framework under which classical algorithms for nonlinear
optimization can be modied to allow second computationally e-cient steps that are not generated
in the conventional way but that are guaranteed to yield decrease in the objective function. We
gave as examples of the two-step algorithms the update of slack variables in LANCELOT, and the
update of variables introduced to solve minimax problems. However, we emphasize that the two-step
algorithms can be very generally applied, for example, whenever the functions dening the
problem are in a known functional form in some of the variables.
We considered trust-region algorithms for which we proposed a greedy and a conservative two-step
algorithm. We analyzed the convergence properties of the trust-region two-step algorithms
(see [11] for line-search two-step algorithms), deriving the conditions under which they attain
global convergence. We also showed that a two-step Newton's method (for which the second step
is computed only for a subset of the variables) has a q-quadratic rate of convergence.
The greedy two-step algorithms are designed to exploit as much as possible the decrease attained
by the second step. The trust-region framework allowed to us to design a greedy two-step trust-region
algorithm that is particularly well tailored to achieve this purpose.
Finally, we included numerical evidence that this technique is eective, particularly for problems
with expensive function evaluations. The two-step algorithms have already found practical
applications in optimization of high-performance custom microprocessor integrated circuits.
Problem Name Inform Iterations Total CPU Obj. Function
MINMAXBD 0/0 267/952 1.34/3.59 116
POLAK3 0/0 71/125 0.4/0.8 5.93
MINMAXBD 0/0 47/43 0.25/0.22 116

Table

8: In the rst part, comparison of Versions 1 and 2 for minimax problems (LANCELOT
without/with two-step updating). In the second part, comparison of Versions 4 and 5 for minimax
problems (LANCELOT without/with two-step updating).

Acknowledgments

We are grateful to N. I. M. Gould (Rutherford Appleton Laboratory) for his comments and suggestions
on an earlier version of this paper that led to many improvements. We are also grateful
to K. Scheinberg (IBM T. J. Watson Research Center) for helping with the numerical results and
explanation in Section 6.3. We would like to thank I. M. Elfadel (IBM T. J. Watson Research
Center) for providing the analytic static-timing-based optimization circuit problems. Finally, we
are grateful to the referees for their useful comments and suggestions.



--R

Computer Science and Applied Mathematics
CUTE: Constrained and Unconstrained Testing Environment
Approximate solution of the trust-region problem by minimization over two-dimensional subspaces
Optimization of custom MOS circuits by transistor sizing


Global convergence of a class of trust-region algorithms for optimization problems with simple bounds


Circuit optimization via adjoint Lagrangians

Numerical Methods for Unconstrained Optimization and Nonlinear Equations
Sensitivity computation in piecewise approximate circuit simulation
Practical Methods of Optimization
SNOPT: An SQP algorithm for large-scale constrained optimization
User's guide for NPSOL 5.0: A Fortran package for nonlinear programming

On solving three classes of nonlinear programming problems via simple di
Linear and Nonlinear Programming



A new algorithm for unconstrained optimization

Minimization of a large-scale quadratic function subject to a spherical con- straint
The conjugate gradient method and trust regions in large scale optimization
Sequential Estimation Techniques for Quasi-Newton Algorithms
Piecewise approximate circuit simulation
--TR

--CTR
Tong Zhang, On the Dual Formulation of Regularized Linear Systems with Convex Risks, Machine Learning, v.46 n.1-3, p.91-129, 2002
Andreas Wchter , Chandu Visweswariah , Andrew R. Conn, Large-scale nonlinear optimization in circuit tuning, Future Generation Computer Systems, v.21 n.8, p.1251-1262, October 2005
Xiaoliang Bai , Chandu Visweswariah , Philip N. Strenski, Uncertainty-aware circuit optimization, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA
Nicholas I. M. Gould , Dominique Orban , Philippe L. Toint, CUTEr and SifDec: A constrained and unconstrained testing environment, revisited, ACM Transactions on Mathematical Software (TOMS), v.29 n.4, p.373-394, December
A. R. Conn , I. M. Elfadel , W. W. Molzen, Jr. , P. R. O'Brien , P. N. Strenski , C. Visweswariah , C. B. Whan, Gradient-based optimization of custom circuits using a static-timing formulation, Proceedings of the 36th ACM/IEEE conference on Design automation, p.452-459, June 21-25, 1999, New Orleans, Louisiana, United States
Andrew R. Conn , Ruud A. Haring , Chandu Visweswariah, Noise considerations in circuit optimization, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.220-227, November 08-12, 1998, San Jose, California, United States
Andrew R. Conn , Chandu Visweswariah, Overview of continuous optimization advances and applications to circuit tuning, Proceedings of the 2001 international symposium on Physical design, p.74-81, April 01-04, 2001, Sonoma, California, United States
spacer steps;expensive function evaluations;LANCELOT;circuit optimization;trust regions;two-step algorithms;minimax problems;line searches;slack variables