On Some Properties of Quadratic Programs with a Convex Quadratic Constraint.
In this paper we consider the problem of minimizing a (possibly nonconvex) quadratic function with a quadratic constraint. We point out some new  properties of the problem. In particular, in the first part of the paper, we show that (i) given a KKT point that is not a global minimizer, it is easy to find a "better" feasible point; (ii) strict complementarity holds at the local-nonglobal minimizer. In the second part of this paper, we show that the original constrained problem is equivalent to the unconstrained minimization of a piecewise quartic merit function. Using the unconstrained formulation we give, in the nonconvex case, a new second order necessary condition for global minimizers. In the third part of this paper, algorithmic applications of the preceding results are briefly outlined and some preliminary numerical experiments are reported.
Introduction
In this paper we study the problem of minimizing a general quadratic function q :
subject to an ellipsoidal constraint, that is
where H is a symmetric positive definite n \Theta n matrix and a is a positive scalar.
The interest in this problem initially arose in the context of trust region methods for
solving unconstrained optimization problems. In fact, such methods require at each
iteration an approximate solution of Problem (1) where q(x) is a local quadratic model
of the objective function over a restricted ellipsoidal region centered around the current
iterate. However, recently, it has been shown that problems with the same structure of
y This work was partially supported by Agenzia Spaziale Italiana, Roma, Italy
z Universit'a di Roma "La Sapienza" - Dipartimento di Informatica e Sistemistica - via Buonarroti, 12
Italy and Gruppo Nazionale per l'Analisi Funzionale e le sue Applicazioni del Consiglio
Nazionale delle Ricerche.
(1) play an important role not only in the field of unconstrained minimization. In fact,
the solution of Problem (1) is at the basis of algorithms for solving general constrained
nonlinear problems (e.g. [3, 42, 20, 27]), and integer programming problems (e.g.
[21, 41, 22, 31, 19]).
Many papers have been devoted to point out the specific features of Problem (1).
Among the most important results there are the necessary and sufficient conditions
for a point x to be a global minimizer, due to Gay [12] and Sorensen [35], and the
characterization and uniqueness of the local-nonglobal minimizer due to Mart'inez [26].
The particular structure of the Problem (1) has led to the development of algorithms for
finding a global solution. The first algorithms proposed in literature were those of Gay
and Sorensen [12, 35]. Mor'e and Sorensen [29] developed an algorithm that produces
an approximate global minimizer in a finite number of steps. More recently, it has been
proved that an approximation to the global solution can be computed in polynomial
time (see for example [39, 38, 40, 41, 21]). Furthermore, Mor'e [28] has considered a
more general case by allowing in Problem (1) a general quadratic constraint and has
extended the results of [12, 35, 29].
In spite of all these results, there is still interest in studying Problem (1). In fact,
as we mentioned before, there is a growing use of Problem (1) as a tool for tackling
large nonlinear programming problems and combinatorial optimization problems. This
leads to the necessity of solving more and more efficiently large scale problems of
the type (1) and motivates further research on theoretical properties of Problem (1)
and on the definition of efficient methods for locating its global minimizers. Recently
some interesting algorithms for tackling large scale trust region problems have been
proposed in [36, 34, 33]. The basic idea behind these algorithms is to recast the trust
region problem in term of a parametrized eigenvalue problem and then to adjust the
parameter to find an optimal solution.
In this paper we point out further theoretical properties of Problem (1). In par-
ticular, our research develops along two lines: the study of some new properties of
its Karush-Kuhn-Tucker points and its equivalence to an unconstrained minimization
problem. Besides their own theorical interest, these results allows us to define new
classes of algorithms for solving large scale case trust region problems. These algorithms
use only matrix-vector product and do not require the solution of an eigenvalue
problem at each iteration (see [24] for details).
The paper is organized as follows. In Section 2 we recall some preliminary results. In
Section 3 we show that
(i) given a KKT point - x which is not a global minimizer, it is possible to find a
new feasible point -
x such that the objective function is strictly decreased, i.e.
(ii) the strict complementarity condition holds at the local minimizer, hence in the
nonconvex case, strict complementarity holds at local and global minimizers.
In Section 4 we show that there is a one to one correspondence between KKT
points (global minimizers) of Problem (1) and stationary points (global minimizers) of
a piecewise quartic merit function Therefore, Problem (1) is equivalent
to the unconstrained problem of P over IR n . In Section 5, by exploiting some results
of the preceding sections, we give a new second order necessary condition for global
minimizers of Problem (1). Finally, in Section 6, we sketch some possible applications
of the results of Section 3 and Section 4 for defining new classes of algorithms for solving
large scale trust region problems.
In the sequel we will use the following notation. Given a vector x 2 IR n , we
denote by kxk the ' 2 -norm on IR n . The ' 2 -norm of a n \Theta n matrix Q is defined by
1g. Moreover, we denote by - 1 - 2 - n the
eigenvalues of Q.
Preliminaries
Without loss of generality we can assume that the feasible set F is defined by
so that the problem under consideration is
and Q is a n \Theta n symmetric matrix and c 2 IR n .
In fact, since H is positive definite, we can reduce Problem (1) to the form (2) by employing
the transformation
we refer to [25] for the direct treatment
of Problem (1)).
The Lagrangian function associated with Problem (2) is the function
A Karush-Kuhn-Tucker point for Problem (2) is a pair (-x; -) 2 IR n \Theta IR such that:
Furthermore, we say that strict complementarity holds at a KKT pair (-x; -
for
It is well known that it is possible to completely characterize the global solutions
of Problem (2) without requiring any convexity assumption on the objective function.
In fact, the following result due to Gay [12] and Sorensen [35] holds (see also Vavasis
Proposition 2.1 A point x   such that kx   k 2 - a 2 is a global solution of Problem (2),
if and only if there exists a unique -   - 0 such that the pair (x   ; -   ) satisfies the KKT
conditions
and the matrix (Q positive semidefinite. If (Q positive definite
then Problem (2) has a unique global solution.
Moreover, Mart'inez [26] gave the following characterization of the local-nonglobal minimizer
for Problem (2).
Proposition 2.2 There exists at most one local-nonglobal minimizer -
x of Problem
(2). Moreover we have and the KKT necessary conditions holds with - 2
are the two smallest eigenvalues of Q.
3 Further features of KKT points
In this section we give some new properties of the KKT points for Problem (2). Our
interest in the characterization of KKT points is due to the fact that, in general,
algorithms for the solution of constrained problems, converge towards KKT points.
We show that the number of different values that the objective function can take at
KKT points is bounded from above by the number of negative eigenvalues of the matrix
Q. First we state a preliminary result that extends one given in [38].
Lemma 3.1 Let (b x; -) and (-x; -) be KKT pairs for Problem (2) with the same KKT
multiplier. Then q(b
Proof We observe that the function q(x) can be rewritten at every KKT pair (x; -)
as follows
By using the KKT conditions we obtain
Now, we can state the following proposition whose proof follows from a result of
Forsythe and Golub [11] on the number of stationary values of a second degree polynomial
on the unit sphere. For sake of completeness we give a sketch of the proof.
Proposition 3.2 There exist at most minf2m points with distinct
multipliers -, where m is the number of negative distinct eigenvalues of Q.
Proof First we observe that at every KKT point (x; -) such that kxk 2 ! a 2 the value
of the objective function q is constant. This easily follows from Lemma 3.1 by observing
that all these pairs are characterized by the fact that
Now, we consider the values of the function q(x) at all the points such that kxk
there exists an orthogonal matrix V such that V T
diag are the eigenvalues of Q. By considering
the transformation ff we can write the first equation of the KKT condition (4)
(premultiplied by V T ) as follows:
diag
with recalling that kxk we have that the KKT
multipliers must satisfy the system
where
The function g(-) has poles at \Gamma2- i
and it is convex on the subintervals
\Gamma2-
Thus there exists at most 2 roots of in each subinterval. Moreover, since
a 2 has one root in each exteme subinterval.
If all eigenvalues - i are positive there exists at most one non negative root; if all the
eigenvalues are negative there are at most 2n non negative roots; in the case of m ! n
negative eigenvalues, there are at most 2m negative roots. Hence the number
of the solutions of system (6) is at most minf2m
Finally, by summarizing the two cases, we can conclude that the number of distinct
KKT multipliers is bounded above by minf2m
Recalling Lemma 3.1, we get directly the following corollary.
Corollary 3.3 The number of distinct values of the objective function q(x) at KKT
points is bounded from above by minf2m 1g.
Now we can state the main result of this section. In particular, we show that the
peculiarity of Problem (2) can be exploited to escape from the KKT points that are
not global solutions in the sense that, whenever we have a KKT point - x, either -
x is
a global minimizer of Problem (2), or it is possible to compute the expression of a
feasible point with a strictly lower value of the objective function. This results is very
appealing from a computational point of view, as discussed in Section 6.
Proposition 3.4 Let (-x; -) be a KKT point for Problem (2). Let us define the point
x in the following way
(a) If c T -
x:
(b) If c T - x - 0 and a vector z 2 IR n such that z T (Q
with
z:
with
z
-I)z
Then we have q(-x) ! q(-x) and k-xk 2 - a 2 .
Proof In case (a), the point -
x is still feasible and
Now consider case (b). In case (i) we have by the KKT conditions that -
hence we have that z is a vector of negative curvature for q(x). Therefore, for every
satisfies the inequality
In particular, if we take ff - ~
ff with
~
we have that k-xk 2 - a 2 .
let us consider case (ii). Let -
x be the vector defined as follows
z
and consider the quadratic function
We note that k-xk and that z is a negative curvature direction for the quadratic
function L(x; -). By simple calculation, taking into account that (Q
get
-I)z
and hence L(-x; -) ! L(-x; -
-). Hence, recalling the expression (8) we can write
Hence we get the result for case (ii).
Let us consider the case (iii). Let us define the vector -
0: We can
find a value for ff such that -
s is a negative curvature direction for L(x; -) and - s T - x 6= 0,
so that we can proceed as in case (ii). In fact, by simple calculation we have:
and by using the KKT conditions
xj:
By solving the quadratic equation with respect to ff we get that - s T
ff where
\Gammac
Hence, by proceeding as in case (ii), we get the result by introducing the point
with ff ? -
ff.
Remark We note that the local-nonglobal minimizer can corresponds either to the
case (a) with k-xk or to the case (b)(ii).
The preceding proposition shows that, if the KKT point - x is not a global minimizer,
it is possible to determine a feasible point -
x such that q(-x) ! q(-x) by computing at
most a direction z such that z T (Q The existence of such a direction is
guaranteed by Proposition 2.1 and from the numerical point of view, its computation
is not an expensive task. In fact, we can obtain such a direction by using, for example,
the Bunch-Parlett decomposition [2, 30], modified Cholesky factorizations [10] or, for
large scale problem, methods based on Lanczos algorithms [4].
Now, as last result of this section, we investigate a regularity property of the local
and global minimizers. In particular, we focus our attention on the strict complementarity
property, that, roughly speaking, indicates that these points are "really
constrained". Also this property can be interesting from an algorithmic point of view.
Proposition 3.5 At the local-nonglobal minimizer for Problem (2) the strict complementarity
condition holds.
Proof Since - x is a local minimizer the KKT conditions (4) hold. Moreover the second
order necessary conditions require that
z
By Proposition 2.2 we have that -
there is no local-nonglobal minimizer. Furthermore, if necessarily
restrict ourselves to the case
since in this case 0 2 us assume by contradiction that -
(4) and Proposition 2.2 we have that
z
x is not a global minimizer, by Proposition 2.1 there exists a direction y such
that y T Qy ! 0 and from the second order necessary conditions y T -
x 6= 0. We assume,
without loss of generality, that y T -
us consider the point ffy with
We prove that for sufficiently small values of ff the point x(ff) is feasible and
produces a smaller value of the objective function, thus contradicting the assumption
of local optimality. In fact, we have
and hence for
we obtain kx(ff)k 2 ! a 2 . Moreover,
By this proposition and by Proposition 2.1 we directly obtain the following result.
Proposition 3.6 In the nonconvex case at every local or global minimizer the strict
complementarity holds.
Unconstrained formulation
In this section, we show that Problem (2) is equivalent to an unconstrained minimization
problem of a piecewise quartic merit function. A general constrained optimization
problem can be transformed into an unconstrained problem by defining a continuously
differentiable exact penalty function by following, for example, the approach proposed
in [6, 7]. However, in the special case of minimization of a quadratic function with
box constraints, it has been shown in [16] and [23] that it is possible to define simpler
penalty functions by exploiting the particular structure of the problem. In the same
spirit of these papers we show that also for Problem (2) it is possible to construct a
particular continuously differentiable penalty function. This new penalty function takes
full advantage of the peculiarities of the trust region problem and enjoys distinguishing
features that make its unconstrained minimization significantly simpler in comparison
with the unconstrained minimization of the penalty functions proposed in [6, 7]. The
main properties of the penalty function proposed in this section are:
ffl it is globally exact according to the definition of [7];
ffl it does not require any shifted barrier term hence it is defined on the whole space;
ffl it has a very simple expression (it is piecewise quartic);
ffl it is known, a priori, for which values of the penalty parameter the correspondence
between the constrained problem and the unconstrained one holds.
As a first step for the definition of the exact penalty function, we recall the Hestenes-
Powell-Rockafellar augmented Lagrangian function [32, 18]
L a (x; -;
""
ae
is a given positive parameter.
Now, according to the classical approach, we replace the multiplier vector - in the
function L a (x; -; ") with a multiplier function which yields an estimate
of the multiplier vector associated to Problem (2) as a function of the variables x. In the
literature different multiplier functions have been proposed (see e.g. [9, 13, 6, 7, 23]).
However, all the expression of the multiplier functions given in [9, 13, 6, 7] are not
defined in the origin of the space.
Here we define a new simpler multiplier function that is defined on the whole space IR n
whose expression is the following
Its properties are summarized in the following proposition.
Proposition 4.1
(i) -(x) is continuosly differentiable with gradient
(ii) If (-x; -) is a KKT point for Problem (2) then we have
(iii) For every x 2 IR n we have x
Proof Part (i) easily follows from the definition of the multiplier function (10). As
regards part (ii), from (4) we have that a pair (-x; -
It is easy to see that if k-xk corresponds exactly to the definition of the
multiplier function (10). Otherwise, if k-xk 2 ! a 2 , (4) imply that hence by
comparing (11) and (10) that
Now let us consider part (iii). By simple calculations we have
a 2
On the basis of the previous considerations we can replace the vector - in the function
L a with the multiplier function -(x). Furthermore, as regards the penalty parameter
", we can select, a priori, an interval of suitable values depending on the problem
data Q; c; a. Therefore, we are now ready to define our merit function P
L a (x; -(x); "(Q; c; a)), that is
ae
where -(x) is the quadratic function given by (10) and " is any parameter that satisfies
the following inequality:
a
First, we show some immediate properties of the merit function P .
Proposition 4.2
(i) P (x) is continuosly differentiable with gradient
ae
(ii) P (x) is twice continuosly differentiable except at points where"
(iii) P (x) is twice continuosly differentiable in a neighborhood of a KKT point -
x where
strict complementarity holds;
(iv) for every x such that kxk 2 - a 2 we have that P (x) - q(x);
(v) the penalty function P (x) is coercive and hence it admits a global minimizer.
Proof Part (i), (ii) and (iii) directly follows from the expression of the penalty function
P . As regards Part (iv) it follows from a classical results on penalty functions (see
Theorem 2 of [7]).
As regards part (v), we want to show that as kxk ! 1 the function P (x) goes to
infinity. First, we observe that"
hence for sufficiently large values of kxk the leading term of the preceding inequality is
strictly positive since, recalling that " satisfies (13), we have that " -
sufficiently large values of kxk, we can assume that
ae
oe
By simple calculation, the expression of the penalty function becomes in this case:
and the following inequalities hold:
As " satisfies (13), we have that " -
and hence we get lim
1. The
existence of the global minimizer immediately follows from the continuity of P and the
compactness of its level sets.
Now, we state the first result about the exactness properties of the penalty function
P . Since its proof is technical and lenghty we report it in the Appendix.
Proposition 4.3 A point -
is a stationary point of P (x) if and only if (-x; -x))
is a KKT pair for Problem (2).
Furthermore, at this point we have P
Now we prove that there is a one to one correspondence betweeen global minimizers
of Problem (2) and global minimizers of the penalty function P .
Proposition 4.4 Every global minimizer of Problem (2) is a global minimizer of P (x)
and conversely.
Proof By Proposition 4.3, the penalty function P admits a global minimizer -
which
is obviously a stationary point of P and hence by the preceding proposition we have
On the other hand, if x   is a global minimizer of Problem (2), it is also a KKT point and
hence the preceding proposition implies again that P (x   proceed
by contradiction. Assume that a global minimizer -
x of P (x) is not a global minimizer
of Problem (2), then there should exists a point x   , global minimizer of Problem (2),
such that
that contradicts the assumption that -
x is a global minimizer of P . The converse is true
by analogous considerations.
In order to complete the correspondence between the solution of Problem (2) and the
unconstrained minimization of the penalty function P we prove the following result
that considers the corrispondence between local minimizers.
Proposition 4.5 The function P (x) admits at most a local-nonglobal minimizer - x
which is a local minimizer of Problem (2) and -x) is the associated KKT multiplier.
Proof We first prove that if -
x is a local minimizer of P (x) then the pair (-x; -x)) satisfies
the KKT conditions for Problem (2). Moreover, by Proposition 4.3, we have that
x is a local minimizer of P , there exists a neighbourhood
of - x such that
Thus, by using (iv) of Proposition 4.2, we obtain
and hence -
x is a local minimizer for Problem (2). The proof can be easily completed
by recalling Proposition 2.2.
5 A new second order optimality condition
The results given in Section 3 and Section 4 can be combined to state new theoretical
properties of Problem (2). In this section we introduce a new second order necessary
optimality condition for Problem (2) for the nonconvex case that follows from the
unconstrained formulation.
Proposition 5.1 Assume that Q is not positive semidefinite, if - x is a global (local)
minimizer of Problem (2) then there exists a unique -
such that the KKT conditions
hold and
a 2
a 2
is positive semidefinite for every " satisfying (13).
Proof If - x is a global minimizer of Problem (2), by Proposition 3.6, we have that
. Then, there exists a neighborhood \Omega\Gamma - x) of -
x such that"
Thus, by (ii) of Proposition 4.2, the function P (x) is twice continuously differentiable
in \Omega\Gamma -
x). and the Hessian matrix evaluated at - x is given by:
a 2
By Proposition 4.4, -
x is also a global minimizer of P (x) and therefore - x satisfies the
second order necessary conditions to be a global unconstrained minimizer of P , that is
positive semidefinite. Then the result follows.
Recalling point (a) of Proposition 3.4, we have that in a global minimizer - x, it results
Hence, the matrixa 2
a 2
is not necessarily positive semidefinite. A similar second order necessary condition was
given in [1], where it has been proved, without requiring any assumptions on the matrix
Q, that if the global minimum is on the boundary, the matrix
a 2
is positive semidefinite where again the matrix 1
a 2
x)-x-x T is not
necessarily positive semidefinite.
6 Algorithmic application
Besides their own theorical interest, the results of the preceding sections are appealing
also from a computational point of view. Although the study of a numerical algorithm
for the solution of Problem (2) is out of the aim of this paper, in this section we give
a hint of possible algorithmic applications of the results of Section 3 and Section 4.
We recall that Proposition 3.4 ensures that given a KKT point which is not a global
solution for Problem (2), it is possible to find a new feasible point with a lower value of
the objective function and that Proposition 3.2 states that the number of KKT points
with different value of the objective function is finite.
These results indicate a new possibility to tackle large scale trust region problems.
In fact they show that a global minimum point of Problem (2) could be efficiently
computed by applying a finite number of times a constrained optimization algorithm
that presents the following features:
(i) given a feasible starting point, it is able to locate a KKT point with a lower value
of the objective function;
(ii) it presents a "good" (at least superlinearly) rate of convergence;
(iii) it does not require an heavy computational burden.
A possibility to ensure property (i) is to use any feasible method that forces the decrease
of the objective function, following, for example, the approach of [37, 17]. Another
possibility is to exploit the unconstrained reformulation of Problem (2) described in
Section 4 which allows us to use any unconstrained method for the minimization of the
penalty function P . In fact, starting from a point x 0 , any of this algorithm obtains a
stationary point -
x for P such that
Then, Proposition 4.3 ensures that -
x is a KKT point of Problem (2) and that P
q(-x). On the other hand, if x 0 is a feasible point, part (iv) of Proposition 4.2 yields
that
In conclusion by using an unconstrained algorithm, we get a KKT point of Problem
(2) with a value of the objective function lower than the value at the starting point.
Furthermore, the possibility of transforming the trust region problem into an unconstrained
one, seems to be quite appealing also as regards properties (ii) and (iii).
In fact Proposition 3.6 and (iii) of Proposition 4.2 guarantees that, in the nonconvex
case, the penalty function is twice continuosly differentiable in every local and global
minimizer of the problem. Therefore, in this case, any unconstrained Truncated Newton
algorithm (see for example [5, 37, 15]) can be easily adapted in order to define globally
convergent methods which show a superlinear rate of convergence in a neighbourhood
of every global or local minimizer.
Nevertheless, we can define algorithm with superlinear rate of convergence without
requiring that the penalty function is twice continuosly differentiable in the neighbourhood
of the points of interest, that is without requiring the strict complementarity in
these points. In fact we can drawn our inspiration from the results in [8].
In particular, we can define a search direction d k as follows:
!/
z k
The results of [8] ensure that the algorithm x locally superlinearly
convergent without requiring the strict complementarity. Following the approach of
truncated Newton method (see for example [5, 15]), in [24] it is shown that an approximate
solution ~
d k of (15)(16) is able to preserve the local superlinear rate of convergence
of the algorithmic scheme. Furthermore it is also proved that this direction ~
suitable descent conditions with respect to the penalty function P . This strict connection
between the direction ~
d k and the penalty function P (x) allow us to define globally
and superlinearly convergent algorithms of the type
~
where ff k can be determined by every stabilization technique and ~
d k is computed by
using a conjugate gradient based iterative method for solving approximately the linear
system (15)(16) .
The paper [24] is devoted to a complete description of this approach with the analysis
of its theoretical properties and to the definition of an efficient algorithm. Here, in
order to have only a preliminary idea of the viability of this unconstrained approach for
solving Problem (2), we have performed some numerical experiments with a rough implementation
of algorithm (17) where ff k is determined by the line-search technique of
[14] and ~
d k is computed by a conjugate gradient algorithm similar to the one proposed
in [5].
We coded the algorithm in MATLAB and run the experiments on a IBM/RISC 6000.
We run two sets of problems randomly generated that we take from the collection of
[34]. We solved ten related problems for each of the two classes both with the easy and
the hard case. According to [34], the hard case occurs when the vector c is orthogonal
to the subspace generated by the smallest eigenvalue of the matrix Q. In Table 1 we
report the results in terms of average number of iterations for problems with increasing
dimension
We run also a set of near hard-case problems (with that is with
c nearly orthogonal to the subspace of the smallest eigenvalue of Q. The results are
FIRST SET SECOND SET
100 11.3 21.9 10.7 25.6

Table

1: Average number of iterations
NEAR HARD CASE
mult. - min

Table

2: Average number of iterations
reported in Table 2. We tested the invariance with respect to the multiplicity of the
smallest eigenvalue (mult. of -
The results obtained are encouraging. The number of iteration is almost constant when
the dimension increases. This feature is appealing when solving large scale problems
taking into account that, at each iteration, the main effort is due to the approximate
solution of a linear system of dimension n or n \Gamma 1 that requires only matrix-vector
products. Furthermore the efficiency of the algorithm seems not to be seriously affected
by the occurrence of the hard case, while it is completely insensible to the near-hard
case.
Of course, even if no final conclusion can be drawn by these limited numerical exper-
iments, the results obtained encourage further research in defining new algorithms for
solving large scale trust region problems which use the results described in this paper.
In particular, as we said before, the possibility of defining efficient algorithms based on
the unconstrained reformulation is investigated in [24].

Acknowledgments

We wish to thank S. Santos, D. Sorensen, F. Rendl and H. Wolkowiz, for providing us
their Matlab codes and test problems. Moreover we thank the anonymous referees for
their helpful suggestions which led to improve the paper.



--R

New optimality conditions and algorithms for homogeneous and polynomial optimization over spheres.
Direct methods for solving symmetric indefinite systems of linear equations.
Computing a trust region step for a penalty function.
Lanczos Algorithms for Large Symmetric Eigenvalue Computation.

An exact penalty method with global convergence properties for nonlinear programming problems.
Exact penalty functions in constrained optimization.
Quadratically and superlinear convergent algorithms for the solution of inequality constrained optimization problems.
A class of methods for nonlinear programming with termination and convergence properties.
Computing modified Newton directions using a partial Cholesky factorization.
On the stationary values of a second-degree polynomial on the unit sphere
Computing optimal locally constrained steps.
A multiplier method with automatic limitation of penalty growth.
A nonmonotone line search technique for Newton's method.
A truncated Newton method with nonmonotone linesearch for unconstrained optimization.
A differentiable exact penalty function for bound constrained quadratic programming problems.
On the solution of a two ball trust region subproblem.
Multiplier and gradient methods.
A continuous approach to compute upper bounds in quadratic maximization problems with integer constraints.
Fast algorithms for convex quadratic programming and multicommodity flows.
An interior-point approach to NP-complete problems
An interior point algorithm to solve computationally difficult set covering problems.
A differentiable piecewise quadratic exact penalty functions for quadratic programs with simple bound constraints.
"La Sapienza"
"La Sapienza"
Local minimizers of quadratic functions on Euclidean balls and spheres.
Trust region algorithms on arbitrary domains.
Generalization of the trust region problem.
Computing a trust region step.
On the use of directions of negative curvature in a modified Newton method.
Algorithms for the solution of quadratic knapsack problems.
A method for nonlinear constraints in minimization problem.
A semidefinite framework to trust region subproblems with applications to large scale minimization.
A new matrix-free for the large scale trust region subproblem
Newton's method with a model trust region modification.
Minimization of a large scale quadratic function subject to an ellipsoidal constraint.
Towards an efficient sparsity exploiting Newton method for minimiza- tion
Nonlinear Optimization.
Proving polynomial-time for sphere-constrained quadratic programming
A new complexity result on minimization of a quadratic function with a sphere constraint.
On affine scaling algorithms for nonconvex quadratic programming.
An extension of Karmarkar's projective algorithm for convex quadratic programming.
--TR

--CTR
Pasquale L. De Angelis , Immanuel M. Bomze , Gerardo Toraldo, Ellipsoidal Approach to Box-Constrained Quadratic Problems, Journal of Global Optimization, v.28 n.1, p.1-15, January 2004
G. Birgin , Jos Mario Martnez , Marcos Raydan, Algorithm 813: SPG---Software for Convex-Constrained Optimization, ACM Transactions on Mathematical Software (TOMS), v.27 n.3, p.340-349, September 2001
Immanuel M. Bomze , Laura Palagi, Quartic Formulation of Standard Quadratic Optimization Problems, Journal of Global Optimization, v.32 n.2, p.181-205, June      2005
Le Thi Hoai An , Pham Dinh Tao, A Branch and Bound Method via d.c. Optimization Algorithms andEllipsoidal Technique for Box Constrained Nonconvex Quadratic Problems, Journal of Global Optimization, v.13 n.2, p.171-206, September 1998
merit function;quadratic function;ell2-norm constraint