A general class of penalty/barrier path-following Newton methods for nonlinear programming

In the present article rather general penalty/barrier-methods (e.g. logarithmic barriers, SUMT, exponential penalties), which define a local continuously differentiable primal and dual path, are analyzed in case of strict local minima of nonlinear problems with inequality as well as equality constraints. In particular, the radius of convergence of Newton's method depending on the penalty/barrier-parameter is estimated. Unlike using self-concordance properties, the convergence bounds are derived by direct estimations of the solutions of the Newton equations. By means of the obtained results parameter selection rules are studied which guarantee the local convergence of the considered penalty/barrier-techniques with only a finite number of Newton steps at each parameter level. Numerical examples illustrate the practical behavior of the proposed class of methods.     

Duality for semi-definite and semi-infinite programming

In this article, we study semi-definite and semi-infinite programming problems (SDSIP), which includes semi-infinite linear programs and semi-definite programs as special cases. We establish that a uniform duality between the homogeneous (SDSIP) and its Lagrangian-type dual problem is equivalent to the closedness condition of certain cone. Moreover, this closedness condition was assured by a generalized canonically closedness condition and a Slater condition. Corresponding results for the nonhomogeneous (SDSIP) problem were obtained by transforming it into an equivalent homogeneous (SDSIP) problem.     

Discrete Newton's method with local variations for solving large-scale nonlinear systems

A globally convergent discrete Newton method is proposed for solving large-scale nonlinear systems of equations. Advantage is taken from discretization steps so that the residual norm can be reduced while the Jacobian is approximated, besides the reduction at Newtonian iterations. The Curtis–Powell–Reid (CPR) scheme for discretization is used for dealing with sparse Jacobians. Global convergence is proved and numerical experiments are presented.     

An augmented penalty function method with penalty parameter updates for nonconvex optimization

Given an augmented Lagrangian scheme for a general optimization problem, we use an epsilon subgradient step for improving the dual function. This can be seen as an update for an augmented penalty method, which is more stable because it does not force the penalty parameter to tend to infinity. We establish for this update primal-dual convergence for our augmented penalty method. As illustration, we apply our method to the test-bed kissing number problem.     

Global optimization of rational functions: a semidefinite programming approach

We consider the problem of global minimization of rational functions on (unconstrained case), and on an open, connected, semi-algebraic subset of , or the (partial) closure of such a set (constrained case). We show that in the univariate case (n = 1), these problems have exact reformulations as semidefinite programming (SDP) problems, by using reformulations introduced in the PhD thesis of Jibetean [16]. This extends the analogous results by Nesterov [13] for global minimization of univariate polynomials. For the bivariate case (n = 2), we obtain a fully polynomial time approximation scheme (FPTAS) for the unconstrained problem, if an a priori lower bound on the infimum is known, by using results by De Klerk and Pasechnik [1]. For the NP-hard multivariate case, we discuss semidefinite programming-based relaxations for obtaining lower bounds on the infimum, by using results by Parrilo [15], and Lasserre [12].     

New properties of a nonlinear conjugate gradient method

Summary. This paper provides several new properties of the nonlinear conjugate gradient method in [5]. Firstly, the method is proved to have a certain self-adjusting property that is independent of the line search and the function convexity. Secondly, under mild assumptions on the objective function, the method is shown to be globally convergent with a variety of line searches. Thirdly, we find that instead of the negative gradient direction, the search direction defined by the nonlinear conjugate gradient method in [5] can be used to restart any optimization method while guaranteeing the global convergence of the method. Some numerical results are also presented. Received March 12, 1999 / Revised version received April 25, 2000 / Published online February 5, 2001     

Mixed duality without a constraint qualification for minimax fractional programming

Without the need of a constraint qualification, we establish the necessary and sufficient optimality conditions for minimax fractional programming. Using these optimality conditions, we construct a mixed dual model which unifies the Mond–Weir dual, Wolfe dual and a parameter dual models. Several duality theorems are established. Consequently, this article partly solves the problem posed by Lai et al. [H.C. Lai, J.C. Liu and K. Tanaka (1999). Duality without a constraint qualification for minimax fractional programming. Journal of Optimization Theory and Applications, 101, 109–125.].     

A new condition number for linear programming

In this paper we define a new condition number ?(A) for the following problem: given a m by n matrix A, find x∈ℝ ⁿ , s.t. Ax<0. We characterize this condition number in terms of distance to ill-posedness and we compare it with existing condition numbers for the same problem. Received: November 5, 1999 / Accepted: November 2000?Published online September 17, 2001     

Exact penalty functions and calmness for mathematical programming under nonlinear perturbations

In the present paper, the effects of nonlinear perturbations of constraint systems are considered over the relationship between calmness and exact penalization, within the context of mathematical programming with equilibrium constraints. Two counterexamples are provided showing that the crucial link between the existence of penalty functions and the property of calmness for perturbed problems is broken in the presence of general perturbations. Then, some properties from variational analysis are singled out, which are able to restore to a certain extent the broken link. Consequently, conditions on the value function associated to perturbed optimization problems are investigated in order to guarantee the occurrence of the above properties.     

Combination of trust region method and simplicial decomposition for convex constrained nonlinear optimization

The algorithm presented in this article incorporates the trust region method (TR) into the restricted decomposition algorithm for convex-constrained nonlinear problems (RSDCC) to solve the master problem of RSDCC. The global convergence is proved. The computational comparison between the presented algorithm and RSDCC is given. The results show that the former is much better than the latter.     

A smoothing Newton method for a type of inverse semi-definite quadratic programming problem

We consider an inverse problem arising from the semi-definite quadratic programming (SDQP) problem. We represent this problem as a cone-constrained minimization problem and its dual (denoted ISDQD) is a semismoothly differentiable (SC¹${\text{SC}}^1$) convex programming problem with fewer variables than the original one. The Karush–Kuhn–Tucker conditions of the dual problem (ISDQD) can be formulated as a system of semismooth equations which involves the projection onto the cone of positive semi-definite matrices. A smoothing Newton method is given for getting a Karush–Kuhn–Tucker point of ISDQD. The proposed method needs to compute the directional derivative of the smoothing projector at the corresponding point and to solve one linear system per iteration. The quadratic convergence of the smoothing Newton method is proved under a suitable condition. Numerical experiments are reported to show that the smoothing Newton method is very effective for solving this type of inverse quadratic programming problems.     

Errata: On semidefinite linear complementarity problems

We correct an error in the statement of Theorem 8 in [1]. Received: January 3, 2001 / Accepted: February 26, 2001?Published online May 18, 2001     

Generalized semi-infinite programming: A tutorial

This tutorial presents an introduction to generalized semi-infinite programming (GSIP) which in recent years became a vivid field of active research in mathematical programming. A GSIP problem is characterized by an infinite number of inequality constraints, and the corresponding index set depends additionally on the decision variables. There exist a wide range of applications which give rise to GSIP models; some of them are discussed in the present paper. Furthermore, geometric and topological properties of the feasible set and, in particular, the difference to the standard semi-infinite case are analyzed. By using first-order approximations of the feasible set corresponding constraint qualifications are developed. Then, necessary and sufficient first- and second-order optimality conditions are presented where directional differentiability properties of the optimal value function of the so-called lower level problem are used. Finally, an overview of numerical methods is given.     

An exact lower order penalty function and its smoothing in nonlinear programming

In this article, we consider a lower order penalty function and its ε-smoothing for an inequality constrained nonlinear programming problem. It is shown that any strict local minimum satisfying the second-order sufficiency condition for the original problem is a strict local minimum of the lower order penalty function with any positive penalty parameter. By using an ε-smoothing approximation to the lower order penalty function, we get a modified smooth global exact penalty function under mild assumptions.     

An interior Newton method for quadratic programming

We propose a new (interior) approach for the general quadratic programming problem. We establish that the new method has strong convergence properties: the generated sequence converges globally to a point satisfying the second-order necessary optimality conditions, and the rate of convergence is 2-step quadratic if the limit point is a strong local minimizer. Published alternative interior approaches do not share such strong convergence properties for the nonconvex case. We also report on the results of preliminary numerical experiments: the results indicate that the proposed method has considerable practical potential. Received October 11, 1993 / Revised version received February 20, 1996 Published online July 19, 1999     

A proximal bundle method with inexact data for convex nondifferentiable minimization

A proximal bundle method with inexact data is presented for minimizing an unconstrained nonsmooth convex function f$f$. At each iteration, only the approximate evaluations of f$f$ and its ε$\epsilon$-subgradients are required and its search directions are determined via solving quadratic programmings. Compared with the pre-existing results, the polyhedral approximation model that we offer is more precise and a new term is added into the estimation term of the descent from the model. It is shown that every cluster of the sequence of iterates generated by the proposed algorithm is an exact solution of the unconstrained minimization problem.     

On two homogeneous self-dual approaches to linear programming and its extensions

We investigate the relation between interior-point algorithms applied to two homogeneous self-dual approaches to linear programming, one of which was proposed by Ye, Todd, and Mizuno and the other by Nesterov, Todd, and Ye. We obtain only a partial equivalence of path-following methods (the centering parameter for the first approach needs to be equal to zero or larger than one half), whereas complete equivalence of potential-reduction methods can be shown. The results extend to self-scaled conic programming and to semidefinite programming using the usual search directions. Received: July 1998 / Accepted: September 2000?Published online November 17, 2000     

A new trust region method for unconstrained optimization

In this paper, we propose a new trust region method for unconstrained optimization problems. The new trust region method can automatically adjust the trust region radius of related subproblems at each iteration and has strong global convergence under some mild conditions. We also analyze the global linear convergence, local superlinear and quadratic convergence rate of the new method. Numerical results show that the new trust region method is available and efficient in practical computation.     

Liapunov Functionals for Smoluchowski’s Coagulation Equation and Convergence to Self-Similarity

An alternative proof of the convergence to self-similar profiles for solutions to the Smoluchowski coagulation equation with constant coagulation kernel is provided. In contrast to the previous approaches which rely on the Laplace transform, a dynamical systems approach is used on the equation written in self-similar variables, for which several Liapunov functionals are identified.