Projected gradient trust-region method for solving nonlinear systems with convex constraints

In this paper, a projected gradient trust region algorithm for solving nonlinear equality systems with convex constraints is considered. The global convergence results are developed in a very general setting of computing trial directions by this method combining with the line search technique. Close to the solution set this method is locally Q-superlinearly convergent under an error bound assumption which is much weaker than the standard nonsingularity condition.     

A Smoothing Projected Levenberg-Marquardt Type Algorithm for Solving Constrained Equations

In this article, we consider the problem of finding a solution of a nonsmooth constrained (and not necessarily square) system of equations. We first reformulate the original problem as an equivalent system of equations with nonnegative constraints, and then present a smoothing projected Levenberg-Marquardt type algorithm to solve the reformulated system, which solves a strictly convex quadratic program at each iteration. We show that this algorithm not only converges globally, but also converges locally superlinearly under an error bound assumption that is much weaker than the standard nonsingularity condition. Some numerical results for the presented algorithm indicate that the algorithm works quite well in practice.     

Superrelaxation and the rate of convergence in minimizing quadratic functions subject to bound constraints

The paper resolves the problem concerning the rate of convergence of the working set based MPRGP (modified proportioning with reduced gradient projection) algorithm with a long steplength of the reduced projected gradient step. The main results of this paper are the formula for the R-linear rate of convergence of MPRGP in terms of the spectral condition number of the Hessian matrix and the proof of the finite termination property for the problems whose solution does not satisfy the strict complementarity condition. The bound on the R-linear rate of convergence of the projected gradient is also included. For shorter steplengths these results were proved earlier by Dostál and Schöberl. The efficiency of the longer steplength is illustrated by numerical experiments. The result is an important ingredient in developming scalable algorithms for numerical solution of elliptic variational inequalities and substantiates the choice of parameters that turned out to be effective in numerical experiments.     

一类非光滑凸优化问题的邻近梯度算法

考虑求解目标函数为光滑损失函数与非光滑正则函数之和的凸优化问题的一种基于线搜索的邻近梯度算法及其收敛性分析,证明了在梯度局部Lipschitz连续条件下该算法是R-线性收敛的,并在非光滑部分为稀疏块LASSO正则函数情况下给出了误差界条件成立的证明,得到了线性收敛率.最后,数值实验结果验证了方法的有效性.     

A smoothing Levenberg-Marquardt method for the complementarity problem over symmetric cone

In this paper, we propose a smoothing Levenberg-Marquardt method for the symmetric cone complementarity problem. Based on a smoothing function, we turn this problem into a system of nonlinear equations and then solve the equations by the method proposed. Under the condition of Lipschitz continuity of the Jacobian matrix and local error bound, the new method is proved to be globally convergent and locally superlinearly/quadratically convergent. Numerical experiments are also employed to show that the method is stable and efficient.

     

On the constrained error bound condition and the projected Levenberg–Marquardt method

In this paper, we first derive a characterization of the solution set of a continuously differentiable system of equations subject to a closed feasible set. Assuming that a constrained local error bound condition is satisfied, we prove that the solution set can locally be written as the intersection of a differentiable manifold with the feasible set. Based on the derivation of this result, we then show that the projected Levenberg–Marquardt method converges locally R-linearly to a possibly nonisolated solution under significantly weaker conditions than previously done.     

Affine scaling interior Levenberg–Marquardt method for bound-constrained semismooth equations under local error bound conditions

We develop and analyze a new affine scaling Levenberg–Marquardt method with nonmonotonic interior backtracking line search technique for solving bound-constrained semismooth equations under local error bound conditions. The affine scaling Levenberg–Marquardt equation is based on a minimization of the squared Euclidean norm of linear model adding a quadratic affine scaling matrix to find a solution that belongs to the bounded constraints on variable. The global convergence results are developed in a very general setting of computing trial directions by a semismooth Levenberg–Marquardt method where a backtracking line search technique projects trial steps onto the feasible interior set. We establish that close to the solution set the affine scaling interior Levenberg–Marquardt algorithm is shown to converge locally Q-superlinearly depending on the quality of the semismooth and Levenberg–Marquardt parameter under an error bound assumption that is much weaker than the standard nonsingularity condition, that is, BD-regular condition under nonsmooth case. A nonmonotonic criterion should bring about speed up the convergence progress in the contours of objective function with large curvature.     

Modified Iterative Runge-Kutta-Type Methods for Nonlinear Ill-Posed Problems

This work is devoted to the convergence analysis of a modified Runge-Kutta-type iterative regularization method for solving nonlinear ill-posed problems under a priori and a posteriori stopping rules. The convergence rate results of the proposed method can be obtained under a Hölder-type sourcewise condition if the Fréchet derivative is properly scaled and locally Lipschitz continuous. Numerical results are achieved by using the Levenberg-Marquardt, Lobatto, and Radau methods.     

On the linear convergence of the alternating direction method of multipliers

We analyze the convergence rate of the alternating direction method of multipliers (ADMM) for minimizing the sum of two or more nonsmooth convex separable functions subject to linear constraints. Previous analysis of the ADMM typically assumes that the objective function is the sum of only two convex functions defined on two separable blocks of variables even though the algorithm works well in numerical experiments for three or more blocks. Moreover, there has been no rate of convergence analysis for the ADMM without strong convexity in the objective function. In this paper we establish the global R-linear convergence of the ADMM for minimizing the sum of any number of convex separable functions, assuming that a certain error bound condition holds true and the dual stepsize is sufficiently small. Such an error bound condition is satisfied for example when the feasible set is a compact polyhedron and the objective function consists of a smooth strictly convex function composed with a linear mapping, and a nonsmooth \(\ell _1\) regularizer. This result implies the linear convergence of the ADMM for contemporary applications such as LASSO without assuming strong convexity of the objective function.     

Projected viscosity subgradient methods for variational inequalities with equilibrium problem constraints in Hilbert spaces

In this paper, we introduce and study some low computational cost numerical methods for finding a solution of a variational inequality problem over the solution set of an equilibrium problem in a real Hilbert space. The strong convergence of the iterative sequences generated by the proposed algorithms is obtained by combining viscosity-type approximations with projected subgradient techniques. First a general scheme is proposed, and afterwards two practical realizations of it are studied depending on the characteristics of the feasible set. When this set is described by convex inequalities, the projections onto the feasible set are replaced by projections onto half-spaces with the consequence that most iterates are outside the feasible domain. On the other hand, when the projections onto the feasible set can be easily computed, the method generates feasible points and can be considered as a generalization of Maingé’s method to equilibrium problem constraints. In both cases, the strong convergence of the sequences generated by the proposed algorithms is proven.     

An augmented Lagrangian method for optimization problems with structured geometric constraints

This paper is devoted to the theoretical and numerical investigation of an augmented Lagrangian method for the solution of optimization problems with geometric constraints. Specifically, we study situations where parts of the constraints are nonconvex and possibly complicated, but allow for a fast computation of projections onto this nonconvex set. Typical problem classes which satisfy this requirement are optimization problems with disjunctive constraints (like complementarity or cardinality constraints) as well as optimization problems over sets of matrices which have to satisfy additional rank constraints. The key idea behind our method is to keep these complicated constraints explicitly in the constraints and to penalize only the remaining constraints by an augmented Lagrangian function. The resulting subproblems are then solved with the aid of a problem-tailored nonmonotone projected gradient method. The corresponding convergence theory allows for an inexact solution of these subproblems. Nevertheless, the overall algorithm computes so-called Mordukhovich-stationary points of the original problem under a mild asymptotic regularity condition, which is generally weaker than most of the respective available problem-tailored constraint qualifications. Extensive numerical experiments addressing complementarity- and cardinality-constrained optimization problems as well as a semidefinite reformulation of MAXCUT problems visualize the power of our approach.

     

On the efficient solution of nonlinear finite element equations. II

Summary We consider nonlinear variational inequalities corresponding to a locally convex minimization problem with linear constraints of obstacle type. An efficient method for the solution of the discretized problem is obtained by combining a slightly modified projected SOR-Newton method with the projected version of thec g-accelerated relaxation method presented in a preceding paper. The first algorithm is used to approximately reach in relatively few steps the proper subspace of active constraints. In the second phase a Kuhn-Tucker point is found to prescribed accuracy. Global convergence is proved and some numerical results are presented.     

A MODIFIED LEVENBERG-MARQUARDT ALGORITHM FOR SINGULAR SYSTEM OF NONLINEAR EQUATIONS

Based on the work of paper,we propose a modified Levenberg-Marquardt algoithm for solving singular system of nonlinear equations F(x)=0,where F(x):R^n→R^n is continuously differentiable and F‘(x)is Lipschitz continuous.The algorithm is equivalent to a trust region algorithm in some sense,and the global convergence result is given.The sequence generated by the algorithm converges to the solution quadratically,if ||F(x)||2 provides a local error bound for the system of nonlinear equations.Numerical results show that the algorithm performs well.     

Log-Sigmoid nonlinear Lagrange method for nonlinear optimization problems over second-order cones

This paper analyzes the rate of local convergence of the Log-Sigmoid nonlinear Lagrange method for nonconvex nonlinear second-order cone programming. Under the componentwise strict complementarity condition, the constraint nondegeneracy condition and the second-order sufficient condition, we show that the sequence of iteration points generated by the proposed method locally converges to a local solution when the penalty parameter is less than a threshold and the error bound of solution is proportional to the penalty parameter. Finally, we report numerical results to show the efficiency of the method.     

一类改进的非凸二次规划有效集方法

一类改进的非凸二次规划有效集方法修乃华（河北师范学院数学系）ＡＣＬＡＳＳＯＦＩＭＰＲＯＶＥＤＡＣＴＩＶＥＳＥＴＭＥＴＨＯＤＳＦＯＲＮＯＮＣＯＮＶＥＸＱＵＡＤＲＡＴＩＣＰＲＯＧＲＡＭＭＩＮＧＰＲＯＢＬＥＭ￥ＸｉｕＮａｉ－ｈｕａ（Ｄｅｐｔ．ｏｆＭａｔｈ．...     

Levenberg-Marquardt method with a general LM parameter and a nonmonotone trust region technique

We propose a new Levenberg-Marquardt (LM) method for solving the nonlinear equations. The new LM method takes a general LM parameter \lambda_k=\mu_k[(1-\theta)\|F_k\|^\delta+\theta\|J_k^TF_k\|^\delta] where \theta\in[0,1] and \delta\in(0,3) and adopts a nonmonotone trust region technique to ensure the global convergence. Under the local error bound condition, we prove that the new LM method has at least superlinear convergence rate with the order \min\{1+\delta,4-\delta,2\}. We also apply the new LM method to solve the nonlinear equations arising from the weighted linear complementarity problem. Numerical experiments indicate that the new LM method is efficient and promising.     

约束最优化问题中投影梯度的全局误差界及其应用

文章利用序列二次规划(SQP)方法中的价值函数为约束最优化问题的投影梯度提供了一个全局误差界,并利用这个全局误差界给出了可行解点列具有收敛性的充分与必要条件.     

Convergence of a projected gradient method with trust region for nonlinear constrained optimization†

In this paper we describe a projected gradient algorithm with trust region, introducing a nondifferentiable merit function for solving nonlinear constrained optimization problems. We show that this method is globally convergent even if conditions are weak. It is also proved that, when the strict complementarity condition holds, the proposed algorithm can be solved by an equality constrained problem, allowing locally rate of superlinear convergence.     

Nonlinear Lagrangians for Nonlinear Programming Based on Modified Fischer-Burmeister NCP Functions

This paper proposes nonlinear Lagrangians based on modified Fischer-Burmeister NCP functions for solving nonlinear programming problems with inequality constraints. The convergence theorem shows that the sequence of points generated by this nonlinear Lagrange algorithm is locally convergent when the penalty parameter is less than a threshold under a set of suitable conditions on problem functions, and the error bound of solution, depending on the penalty parameter, is also established. It is shown that the condition number of the nonlinear Lagrangian Hessian at the optimal solution is proportional to the controlling penalty parameter. Moreover, the paper develops the dual algorithm associated with the proposed nonlinear Lagrangians. Numerical results reported suggest that the dual algorithm based on proposed nonlinear Lagrangians is effective for solving some nonlinear optimization problems.     

The Lagrangian Globalization Method for Nonsmooth Constrained Equations

The difficulty suffered in optimization-based algorithms for the solution of nonlinear equations lies in that the traditional methods for solving the optimization problem have been mainly concerned with finding a stationary point or a local minimizer of the underlying optimization problem, which is not necessarily a solution of the equations. One method to overcome this difficulty is the Lagrangian globalization (LG for simplicity) method. This paper extends the LG method to nonsmooth equations with bound constraints. The absolute system of equations is introduced. A so-called Projected Generalized-Gradient Direction (PGGD) is constructed and proved to be a descent direction of the reformulated nonsmooth optimization problem. This projected approach keeps the feasibility of the iterates. The convergence of the new algorithm is established by specializing the PGGD. Numerical tests are given. This author's work was done when she was visiting The Hong Kong Polytechnic University. His work is also supported by the Research Grant Council of Hong Kong.