A Trust-region Method for Nonsmooth Nonconvex Optimization

We propose a trust-region type method for a class of nonsmooth nonconvex optimization problems where the objective function is a summation of a (probably nonconvex) smooth function and a (probably nonsmooth) convex function. The model function of our trust-region subproblem is always quadratic and the linear term of the model is generated using abstract descent directions. Therefore, the trust-region subproblems can be easily constructed as well as efficiently solved by cheap and standard methods. When the accuracy of the model function at the solution of the subproblem is not sufficient, we add a safeguard on the stepsizes for improving the accuracy. For a class of functions that can be "truncated'', an additional truncation step is defined and a stepsize modification strategy is designed. The overall scheme converges globally and we establish fast local convergence under suitable assumptions. In particular, using a connection with a smooth Riemannian trust-region method, we prove local quadratic convergence for partly smooth functions under a strict complementary condition. Preliminary numerical results on a family of $\ell_1$-optimization problems are reported and demonstrate the efficiency of our approach.     

An active-set projected trust-region algorithm with limited memory BFGS technique for box-constrained nonsmooth equations

In this article, by means of an active set and limited memory strategy, we propose a trust-region method for box-constrained nonsmooth equations. The global convergence and the superlinear convergence are established under suitable conditions.     

Gradient trust region algorithm with limited memory BFGS update for nonsmooth convex minimization

By means of a gradient strategy, the Moreau-Yosida regularization, limited memory BFGS update, and proximal method, we propose a trust-region method for nonsmooth convex minimization. The search direction is the combination of the gradient direction and the trust-region direction. The global convergence of this method is established under suitable conditions. Numerical results show that this method is competitive to other two methods.     

Active-Set Projected Trust-Region Algorithm for Box-Constrained Nonsmooth Equations

In this paper, by means of an active-set strategy, we present a trust-region method for solving box-constrained nonsmooth equations. Nice properties of the proposed method include: (a) all iterates remain feasible; (b) the search direction, as adequate combination of the projected gradient direction and the trust-region direction, is an asymptotic Newton direction under mild conditions; (c) the subproblem of the proposed method, possessing the form of an unconstrained trust-region subproblem, can be solved by existing methods; (d) the subproblem of the proposed method is of reduced dimension, which is potentially cheaper when applied to solve large-scale problems. Under appropriate conditions, we establish global and local superlinear/quadratic convergence of the method. Preliminary numerical results are given.     

A hybrid algorithm for nonlinear minimax problems

In this paper, a hybrid algorithm for solving finite minimax problem is presented. In the algorithm, we combine the trust-region methods with the line-search methods and curve-search methods. By means of this hybrid technique, the algorithm, according to the specific situation at each iteration, can adaptively performs the trust-region step, line-search step or curve-search step, so as to avoid possibly solving the trust-region subproblems many times, and make better use of the advantages of different methods. Moreover, we use second-order correction step to circumvent the difficulties of the Maratos effect occurred in the nonsmooth optimization. Under mild conditions, we prove that the new algorithm is of global convergence and locally superlinear convergence. The preliminary experiments show that the new algorithm performs efficiently.     

Superlinearly convergent affine scaling interior trust-region method for linear constrained LC<Superscript>1</Superscript> minimization

We extend the classical affine scaling interior trust region algorithm for the linear constrained smooth minimization problem to the nonsmooth case where the gradient of objective function is only locally Lipschitzian. We propose and analyze a new affine scaling trust-region method in association with nonmonotonic interior backtracking line search technique for solving the linear constrained LC1 optimization where the second-order derivative of the objective function is explicitly required to be locally Lipschitzian. The general trust region subproblem in the proposed algorithm is defined by minimizing an augmented affine scaling quadratic model which requires both first and second order information of the objective function subject only to an affine scaling ellipsoidal constraint in a null subspace of the augmented equality constraints. The global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions where twice smoothness of the objective function is not required. Applications of the algorithm to some nonsmooth optimization problems are discussed.     

Multiplier convergence in trust-region methods with application to convergence of decomposition methods for MPECs

We study piecewise decomposition methods for mathematical programs with equilibrium constraints (MPECs) for which all constraint functions are linear. At each iteration of a decomposition method, one step of a nonlinear programming scheme is applied to one piece of the MPEC to obtain the next iterate. Our goal is to understand global convergence to B-stationary points of these methods when the embedded nonlinear programming solver is a trust-region scheme, and the selection of pieces is determined using multipliers generated by solving the trust-region subproblem. To this end we study global convergence of a linear trust-region scheme for linearly-constrained NLPs that we call a trust-search method. The trust-search has two features that are critical to global convergence of decomposition methods for MPECs: a robustness property with respect to switching pieces, and a multiplier convergence result that appears to be quite new for trust-region methods. These combine to clarify and strengthen global convergence of decomposition methods without resorting either to additional conditions such as eventual inactivity of the trust-region constraint, or more complex methods that require a separate subproblem for multiplier estimation.      

一种非单调滤子信赖域算法解线性不等式约束优化

本文给出了一种新的多维滤子算法结合非单调信赖域策略解线性约束优化.目标函数及其投影梯度的分量组成了新的多维滤子，并且与信赖域半径有关.当信赖域半径充分小时，新的滤子能接受试探点，避免算法无限循环.非单调信赖域策略保证了新算法的整体收敛性.目前为止，多维滤子算法局部收敛性分析仍然没有解决，在合理假设下，我们分析了新算法的局部超线性收敛性.数值结果验证了算法的有效性.     

On the convergence of an inexact Gauss–Newton trust-region method for nonlinear least-squares problems with simple bounds

We introduce an inexact Gauss–Newton trust-region method for solving bound-constrained nonlinear least-squares problems where, at each iteration, a trust-region subproblem is approximately solved by the Conjugate Gradient method. Provided a suitable control on the accuracy to which we attempt to solve the subproblems, we prove that the method has global and asymptotic fast convergence properties. Some numerical illustration is also presented.     

A trust-region strategy for minimization on arbitrary domains

We present a trust-region method for minimizing a general differentiable function restricted to an arbitrary closed set. We prove a global convergence theorem. The trust-region method defines difficult subproblems that are solvable in some particular cases. We analyze in detail the case where the domain is a Euclidean ball. For this case we present numerical experiments where we consider different Hessian approximations.Work partially supported by FAPESP (Grants 90-3724-6 and 91-2441-3), FINEP, CNPq and FAEP-UNICAMP.     

Efficient use of parallelism in algorithmic parameter optimization applications

In the context of algorithmic parameter optimization, there is much room for efficient usage of computational resources. We consider the Opal framework in which a nonsmooth optimization problem models the parameter identification task, and is solved by a mesh adaptive direct search solver. Each evaluation of trial parameters requires the processing of a potentially large number of independent tasks. We describe and evaluate several strategies for using parallelism in this setting. Our test scenario consists in optimizing five parameters of a trust-region method for smooth unconstrained minimization.     

非线性等式约束优化问题的仿射信赖域方法

提出非线性等式和有界约束优化问题的结合非单调技术的仿射信赖域方法. 结合信赖域方法和内点回代线搜索技术, 每一步迭代转到由一般信赖域子问题产生的回代步中且满足严格内点可行条件. 在合理的假设条件下, 证明了算法的整体收敛性和局部超线性收敛速率. 最后, 数值结果表明了所提供的算法具有有效性.     

Generalized Newton’s method based on graphical derivatives

This paper concerns developing a numerical method of the Newton type to solve systems of nonlinear equations described by nonsmooth continuous functions. We propose and justify a new generalized Newton algorithm based on graphical derivatives, which have never been used to derive a Newton-type method for solving nonsmooth equations. Based on advanced techniques of variational analysis and generalized differentiation, we establish the well-posedness of the algorithm, its local superlinear convergence, and its global convergence of the Kantorovich type. Our convergence results hold with no semismoothness and Lipschitzian assumptions, which is illustrated by examples. The algorithm and main results obtained in the paper are compared with well-recognized semismooth and B-differentiable versions of Newton’s method for nonsmooth Lipschitzian equations.     

A progressive barrier derivative-free trust-region algorithm for constrained optimization

We study derivative-free constrained optimization problems and propose a trust-region method that builds linear or quadratic models around the best feasible and around the best infeasible solutions found so far. These models are optimized within a trust region, and the progressive barrier methodology handles the constraints by progressively pushing the infeasible solutions toward the feasible domain. Computational experiments on 40 smooth constrained problems indicate that the proposed method is competitive with COBYLA, and experiments on two nonsmooth multidisciplinary optimization problems from mechanical engineering show that it can be competitive with the NOMAD software.     

Semismooth Newton Schwarz iterative methods for the linear complementarity problem

Semismooth Newton method is an effective method for solving a nonsmooth equation, which arises from a reformulation of the complementarity problem. Under appropriate conditions, we verify the monotone convergence of the method. We also present semismooth Newton Schwarz iterative methods for the nonsmooth equation. Under suitable conditions, the methods exhibit monotone and superlinear convergence properties.     

An affine scaling interior trust-region method combining with line search filter technique for optimization subject to bounds on variables

This paper proposes and analyzes an affine scaling trust-region method with line search filter technique for solving nonlinear optimization problems subject to bounds on variables. At the current iteration, the trial step is generated by the general trust-region subproblem which is defined by minimizing a quadratic function subject only to an affine scaling ellipsoidal constraint. Both trust-region strategy and line search filter technique will switch to trail backtracking step which is strictly feasible. Meanwhile, the proposed method does not depend on any external restoration procedure used in line search filter technique. A new backtracking relevance condition is given which is weaker than the switching condition to obtain the global convergence of the algorithm. The global convergence and fast local convergence rate of this algorithm are established under reasonable assumptions. Preliminary numerical results are reported indicating the practical viability and show the effectiveness of the proposed algorithm.     

A nonmonotone trust-region line search method for large-scale unconstrained optimization

We consider an efficient trust-region framework which employs a new nonmonotone line search technique for unconstrained optimization problems. Unlike the traditional nonmonotone trust-region method, our proposed algorithm avoids resolving the subproblem whenever a trial step is rejected. Instead, it performs a nonmonotone Armijo-type line search in direction of the rejected trial step to construct a new point. Theoretical analysis indicates that the new approach preserves the global convergence to the first-order critical points under classical assumptions. Moreover, superlinear and quadratic convergence are established under suitable conditions. Numerical experiments show the efficiency and effectiveness of the proposed approach for solving unconstrained optimization problems.     

Metrically regular mappings and its application to convergence analysis of a confined Newton-type method for nonsmooth generalized equations

Notion of metrically regular property and certain types of point-based approximations are used for solving the nonsmooth generalized equation f(x)+F(x)?0,where X and Y are Banach spaces,and U is an open subset of X,f:U→Y is a nonsmooth function and F:X■Y is a set-valued mapping with closed graph.We introduce a confined Newton-type method for solving the above nonsmooth generalized equation and analyze the semilocal and local convergence of this method.Specifically,under the point-based approximation of f on U and metrically regular property of f+F,we present quadratic rate of convergence of this method.Furthermore,superlinear rate of convergence of this method is provided under the conditions that f admits p-point-based approximation on U and f+F is metrically regular.An example of nonsmooth functions that have p-point-based approximation is given.Moreover,a numerical experiment is given which illustrates the theoretical result.     

解新锥模型信赖域子问题的折线法

本文以新锥模型信赖域子问题的最优性条件为理论基础,认真讨论了新子问题的锥函数性质,分析了此函数在梯度方向及与牛顿方向连线上的单调性.在此基础上本文提出了一个求解新锥模型信赖域子问题折线法,并证明了这一子算法保证解无约束优化问题信赖域法全局收敛性要满足的下降条件.本文获得的数值实验表明该算法是有效的.     

Pseudotransient Continuation for Solving Systems of Nonsmooth Equations with Inequality Constraints

This paper investigates a pseudotransient continuation algorithm for solving a system of nonsmooth equations with inequality constraints. We first transform the inequality constrained system of nonlinear equations to an augmented nonsmooth system, and then employ the pseudotransient continuation algorithm for solving the corresponding augmented nonsmooth system. The method gets its global convergence properties from the dynamics, and inherits its local convergence properties from the semismooth Newton method. Finally, we illustrate the behavior of our approach by some numerical experiments.