On the solution of a two ball trust region subproblem

In this paper we investigate the structure of a two ball trust region subproblem arising frequently in nonlinear parameter identification problems and propose a method for its solution. The method decomposes the subproblem and allows the application of efficient, well studied methods for the solution of trust region subproblems arising in unconstrained optimization. In the discussion of the structure we focus on the case where both constraints are active and on the treatment of the unconstrained problem.The research of this author was partially supported bygottlieb-daimler andkarl-benz-stiftung, Ladenburg and NSF, Cooperate of Agreement No. CCR-8809615.     

Concurrent stochastic methods for global optimization

The global optimization problem, finding the lowest minimizer of a nonlinear function of several variables that has multiple local minimizers, appears well suited to concurrent computation. This paper presents a new parallel algorithm for the global optimization problem. The algorithm is a stochastic method related to the multi-level single-linkage methods of Rinnooy Kan and Timmer for sequential computers. Concurrency is achieved by partitioning the work of each of the three main parts of the algorithm, sampling, local minimization start point selection, and multiple local minimizations, among the processors. This parallelism is of a coarse grain type and is especially well suited to a local memory multiprocessing environment. The paper presents test results of a distributed implementation of this algorithm on a local area network of computer workstations. It also summarizes the theoretical properties of the algorithm.Research supported by AFOSR grant AFOSR-85-0251, ARO contract DAAG 29-84-K-0140, NSF grant DCR-8403483, and NSF cooperative agreement DCR-8420944.     

Minimum norm solution to the positive semidefinite linear complementarity problem

In this article, we present an algorithm to compute the minimum norm solution of the positive semidefinite linear complementarity problem. We show that its solution can be obtained using the alternative theorems and a convenient characterization of the solution set of a convex quadratic programming problem. This problem reduces to an unconstrained minimization problem with once differentiable convex objective function. We propose an extension of Newton's method for solving the unconstrained optimization problem. Computational results show that convergence to high accuracy often occurs in just a few iterations.     

A subspace implementation of quasi-Newton trust region methods for unconstrained optimization

This paper studies subspace properties of trust region methods for unconstrained optimization, assuming the approximate Hessian is updated by quasi- Newton formulae and the initial Hessian approximation is appropriately chosen. It is shown that the trial step obtained by solving the trust region subproblem is in the subspace spanned by all the gradient vectors computed. Thus, the trial step can be defined by minimizing the quasi-Newton quadratic model in the subspace. Based on this observation, some subspace trust region algorithms are proposed and numerical results are also reported.     

A class of collinear scaling algorithms for bound-constrained optimization: Derivation and computational results

A family of algorithms for the approximate solution of the bound-constrained minimization problem is described. These algorithms employ the standard barrier method, with the inner iteration based on trust region methods. Local models are conic functions rather than the usual quadratic functions, and are required to match first and second derivatives of the barrier function at the current iterate. The various members of the family are distinguished by the choice of a vector-valued parameter, which is the zero vector in the degenerate case that quadratic local models are used. Computational results are used to compare the efficiency of various members of the family on a selection of test functions.     

Combining nonmonotone conic trust region and line search techniques for unconstrained optimization

In this paper, we propose a trust region method for unconstrained optimization that can be regarded as a combination of conic model, nonmonotone and line search techniques. Unlike in traditional trust region methods, the subproblem of our algorithm is the conic minimization subproblem; moreover, our algorithm performs a nonmonotone line search to find the next iteration point when a trial step is not accepted, instead of resolving the subproblem. The global and superlinear convergence results for the algorithm are established under reasonable assumptions. Numerical results show that the new method is efficient for unconstrained optimization problems.     

A new trust region method with adaptive radius

In this paper we develop a new trust region method with adaptive radius for unconstrained optimization problems. The new method can adjust the trust region radius automatically at each iteration and possibly reduces the number of solving subproblems. We investigate the global convergence and convergence rate of this new method under some mild conditions. Theoretical analysis and numerical results show that the new adaptive trust region radius is available and reasonable and the resultant trust region method is efficient in solving practical optimization problems. The work was supported in part by NSF grant CNS-0521142, USA.     

A new nonmonotone adaptive trust region method based on simple quadratic models

Based on simple quadratic models of the trust region subproblem, we combine the trust region method with the nonmonotone and adaptive techniques to propose a new nonmonotone adaptive trust region algorithm for unconstrained optimization. Unlike traditional trust region method, our trust region subproblem is very simple by using a new scale approximation of the minimizing function??s Hessian. The new method needs less memory capacitance and computational complexity. The convergence results of the method are proved under certain conditions. Numerical results show that the new method is effective and attractive for large scale unconstrained problems.     

A new minimization protocol for solving nonlinear Poisson–Boltzmann mortar finite element equation

The nonlinear Poisson–Boltzmann equation (PBE) is a widely-used implicit solvent model in biomolecular simulations. This paper formulates a new PBE nonlinear algebraic system from a mortar finite element approximation, and proposes a new minimization protocol to solve it efficiently. In particular, the PBE mortar nonlinear algebraic system is proved to have a unique solution, and is equivalent to a unconstrained minimization problem. It is then solved as the unconstrained minimization problem by the subspace trust region Newton method. Numerical results show that the new minimization protocol is more efficient than the traditional merit least squares approach in solving the nonlinear system. At least 80 percent of the total CPU time was saved for a PBE model problem. AMS subject classification (2000)  65N30, 65H10, 65K10, 92-08     

广义几何规划的压缩共轭梯度路径非单调信赖域算法(英文)

In this paper,on the basis of making full use of the characteristics of unconstrained generalized geometric programming（GGP）,we establish a nonmonotonic trust region algorithm via the conjugate path for solving unconstrained GGP problem.A new type of condensation problem is presented,then a particular conjugate path is constructed for the problem,along which we get the approximate solution of the problem by nonmonotonic trust region algorithm,and further prove that the algorithm has global convergence and quadratic convergence properties.     

AN INTERIOR TRUST REGION ALGORITHM FOR NONLINEAR MINIMIZATION WITH LINEAR CONSTRAINTS

AbstractAn interior trust-region-based algorithm for linearly constrained minimization problems is proposed and analyzed. This algorithm is similar to trust region algorithms for unconstrained minimization: a trust region subproblem on a subspace is solved in each iteration. We establish that the proposed algorithm has convergence properties analogous to those of the trust region algorithms for unconstrained minimization. Namely, every limit point of the generated sequence satisfies the Krush-Kuhn-Tucker (KKT) conditions and at least one limit point satisfies second order necessary optimality conditions. In addition, if one limit point is a strong local minimizer and the Hessian is Lipschitz continuous in a neighborhood of that point, then the generated sequence converges globally to that point in the rate of at least 2-step quadratic. We are mainly concerned with the theoretical properties of the algorithm in this paper. Implementation issues and adaptation to large-scale problems will be addressed in a     

A new type of condensation curvilinear path algorithm for unconstrained generalized geometric programming

A new type of condensation curvilinear path algorithm is proposed for unconstrained generalized geometric programming (GGP). First, a new type of condensation problem is presented based on the special structure of GGP. Then a particular curvilinear path for the problem is constructed, along which we get the approximate solution of the problem within a trust region. It is proved that the method is globally convergent and that the convergence rate is quadratic. Numerical experiments are given to show the effectiveness and feasibility of the algorithm.     

A primal-dual trust region algorithm for nonlinear optimization

This paper concerns general (nonconvex) nonlinear optimization when first and second derivatives of the objective and constraint functions are available. The proposed method is based on finding an approximate solution of a sequence of unconstrained subproblems parameterized by a scalar parameter. The objective function of each unconstrained subproblem is an augmented penalty-barrier function that involves both primal and dual variables. Each subproblem is solved using a second-derivative Newton-type method that employs a combined trust region and line search strategy to ensure global convergence. It is shown that the trust-region step can be computed by factorizing a sequence of systems with diagonally-modified primal-dual structure, where the inertia of these systems can be determined without recourse to a special factorization method. This has the benefit that off-the-shelf linear system software can be used at all times, allowing the straightforward extension to large-scale problems. Numerical results are given for problems in the COPS test collection.Mathematics Subject Classification (2000): 49M37, 65F05, 65K05, 90C30This paper is dedicated to Roger Fletcher on the occasion of his 65th birthday     

A NEW TRUST REGION DOGLEG METHOD FOR UNCONSTRAINED OPTIMIZATION

Abstract. This paper presents a new trust region dogleg method for unconstrained optimization.The method can deal with the case when the Hessian B of quadratic models is indefinite. It isproved that the method is globally convergent and has a quadratic convergence rate if Under certain conditions, the solution obtained by the method is even a second order     

A ROBUST TRUST REGION ALGORITHM FOR SOLVING GENERAL NONLINEAR PROGRAMMING

1. Introductioncrust region methods are iterative. As a strategy of globalization, the trust region approach was introduced into solving unconstrained optimization and proved to be efficient androbust. An excellent survey was given by Mor6(1983). The associated research with trustregion methods for unconstrained optimization can be found in Fletcher(1980), Powell(1975),Sorensen(1981), Shultz, Schnabel and Byrd(1985), Yuan(1985). The solution of the trust region subproblem is still an activ…     

On piecewise quadratic Newton and trust region problems

Some recent algorithms for nonsmooth optimization require solutions to certain piecewise quadratic programming subproblems. Two types of subproblems are considered in this paper. The first type seeks the minimization of a continuously differentiable and strictly convex piecewise quadratic function subject to linear equality constraints. We prove that a nonsmooth version of Newton’s method is globally and finitely convergent in this case. The second type involves the minimization of a possibly nonconvex and nondifferentiable piecewise quadratic function over a Euclidean ball. Characterizations of the global minimizer are studied under various conditions. The results extend a classical result on the trust region problem. Partially supported by National University of Singapore under grant 930033.     

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.     

A conjugate gradient method for the unconstrained minimization of strictly convex quadratic splines

In this paper, we show that an analogue of the classical conjugate gradient method converges linearly when applied to solving the problem of unconstrained minimization of a strictly convex quadratic spline. Since a strictly convex quadratic program with simple bound constraints can be reformulated as unconstrained minimization of a strictly convex quadratic spline, the conjugate gradient method is used to solve the unconstrained reformulation and find the solution of the original quadratic program. In particular, if the solution of the original quadratic program is nondegenerate, then the conjugate gradient method finds the solution in a finite number of iterations. This author's research is partially supported by the NASA/Langley Research Center under grant NCC-1-68 Supplement-15.     

Minimum Norm Solution to the Absolute Value Equation in the Convex Case

In this paper, we give an algorithm to compute the minimum norm solution to the absolute value equation (AVE) in a special case. We show that this solution can be obtained from theorems of the alternative and a useful characterization of solution sets of convex quadratic programs. By using an exterior penalty method, this problem can be reduced to an unconstrained minimization problem with once differentiable convex objective function. Also, we propose a quasi-Newton method for solving unconstrained optimization problem. Computational results show that convergence to high accuracy often occurs in just a few iterations.     

Truncated-newtono algorithms for large-scale unconstrained optimization

We present an algorithm for large-scale unconstrained optimization based onNewton's method. In large-scale optimization, solving the Newton equations at each iteration can be expensive and may not be justified when far from a solution. Instead, an inaccurate solution to the Newton equations is computed using a conjugate gradient method. The resulting algorithm is shown to have strong convergence properties and has the unusual feature that the asymptotic convergence rate is a user specified parameter which can be set to anything between linear and quadratic convergence. Some numerical results on a 916 vriable test problem are given. Finally, we contrast the computational behavior of our algorithm with Newton's method and that of a nonlinear conjugate gradient algorithm. This research was supported in part by DOT Grant CT-06-0011, NSF Grant ENG-78-21615 and grants from the Norwegian Research Council for Sciences and the Humanities and the Norway-American Association. This paper was originally presented at the TIMS-ORSA Joint National Meeting, Washington, DC, May 1980.