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.     

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 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.     

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.