A two-stage feasible directions algorithm for nonlinear constrained optimization

We present a feasible directions algorithm, based on Lagrangian concepts, for the solution of the nonlinear programming problem with equality and inequality constraints. At each iteration a descent direction is defined; by modifying it, we obtain a feasible descent direction. The line search procedure assures the global convergence of the method and the feasibility of all the iterates. We prove the global convergence of the algorithm and apply it to the solution of some test problems. Although the present version of the algorithm does not include any second-order information, like quasi-Newton methods, these numerical results exhibit a behavior comparable to that of the best methods known at present for nonlinear programming. Research performed while the author was on a two years appointment at INRIA, Rocquencourt, France, and partially supported by the Brazilian Research Council (CNPq).     

Affine scaling inexact generalized Newton algorithm with interior backtracking technique for solving bound-constrained semismooth equations

We develop and analyze an affine scaling inexact generalized Newton algorithm in association with nonmonotone interior backtracking line technique for solving systems of semismooth equations subject to bounds on variables. By combining inexact affine scaling generalized Newton with interior backtracking line search technique, each iterate switches to inexact generalized Newton backtracking step to strict interior point feasibility. The global convergence results are developed in a very general setting of computing trial steps by the affine scaling generalized Newton-like method that is augmented by an interior backtracking line search technique projection onto the feasible set. Under some reasonable conditions we establish that close to a regular solution the inexact generalized Newton method is shown to converge locally p-order q-superlinearly. We characterize the order of local convergence based on convergence behavior of the quality of the approximate subdifferentials and indicate how to choose an inexact forcing sequence which preserves the rapid convergence of the proposed algorithm. A nonmonotonic criterion should bring about speeding up the convergence progress in some ill-conditioned cases.     

一类线性约束下不可微最优化问题的可行下降方法

本文给出了一类线性约束下不可微量优化问题的可行下降方法，这类问题的目标函数是凸函数和可微函数的合成函数，算法通过解系列二次规划寻找可行下降方向，新的迭代点由不精确线搜索产生，在较弱的条件下，我们证明了算法的全局收敛性     

线性反问题的一个改进CD算法

对线性反问题提出一个改进的CD共轭梯度算法.在不依赖任何线搜索的情况下,该算法满足充分下降条件.在一定条件下,证明了算法的全局收敛性.最后,相关的试验结果表明算法是有效的.     

An improved Wei–Yao–Liu nonlinear conjugate gradient method for optimization computation

In this paper, we take a little modification to the Wei–Yao–Liu nonlinear conjugate gradient method proposed by Wei et al. [Z. Wei, S. Yao, L. Liu, The convergence properties of some new conjugate gradient methods, Appl. Math. Comput. 183 (2006) 1341–1350] such that the modified method possesses better convergence properties. In fact, we prove that the modified method satisfies sufficient descent condition with greater parameter in the strong Wolfe line search and converges globally for nonconvex minimization. We also extend these results to the Hestenes–Stiefel method and prove that the modified HS method is globally convergent for nonconvex functions with the standard Wolfe conditions. Numerical results are reported by using some test problems in the CUTE library.     

Directional secant method for nonlinear equations

We present a directional secant method, a secant variant of the directional Newton method, for solving a single nonlinear equation in several variables. Under suitable assumptions, we prove the convergence and the quadratic convergence speed of this new method. Numerical examples show that the directional secant method is feasible and efficient, and has better numerical behaviour than the directional Newton method.     

Some non-interior path-following methods based on a scaled central path for linear complementarity problems

In this paper we present some non-interior path-following methods for linear complementarity problems. Instead of using the standard central path we use a scaled central path. Based on this new central path, we first give a feasible non-interior path-following method for linear complementarity problems. And then we extend it to an infeasible method. After proving the boundedness of the neighborhood, we prove the convergence of our method. Another point we should present is that we prove the local quadratic convergence of feasible method without the assumption of strict complementarity at the solution.     

On the rate of convergence of sequential quadratic programming with nondifferentiable exact penalty function in the presence of constraint degeneracy

We analyze the convergence of a sequential quadratic programming (SQP) method for nonlinear programming for the case in which the Jacobian of the active constraints is rank deficient at the solution and/or strict complementarity does not hold for some or any feasible Lagrange multipliers. We use a nondifferentiable exact penalty function, and we prove that the sequence generated by an SQP using a line search is locally R-linearly convergent if the matrix of the quadratic program is positive definite and constant over iterations, provided that the Mangasarian-Fromovitz constraint qualification and some second-order sufficiency conditions hold. Received: April 28, 1998 / Accepted: June 28, 2001?Published online April 12, 2002     

Sufficient Descent Riemannian Conjugate Gradient Methods

This paper considers sufficient descent Riemannian conjugate gradient methods with line search algorithms. We propose two kinds of sufficient descent nonlinear conjugate gradient method and prove that these methods satisfy the sufficient descent condition on Riemannian manifolds. One is a hybrid method combining a Fletcher–Reeves-type method with a Polak–Ribière–Polyak-type method, and the other is a Hager–Zhang-type method, both of which are generalizations of those used in Euclidean space. Moreover, we prove that the hybrid method has a global convergence property under the strong Wolfe conditions and the Hager–Zhang-type method has the sufficient descent property regardless of whether a line search is used or not. Further, we review two kinds of line search algorithm on Riemannian manifolds and numerically compare our generalized methods by solving several Riemannian optimization problems. The results show that the performance of the proposed hybrid methods greatly depends on the type of line search used. Meanwhile, the Hager–Zhang-type method has the fast convergence property regardless of the type of line search used.

     

利用Armijo型线性搜索HZ共轭梯度法的全局收敛性

由William W.Hager和张洪超提出的一种新的共轭梯度法(简称HZ方法),已被证明是一种有效的方法.本文证明了HZ共轭梯度法在Armijo型线性搜索下的全局收敛性.数值实验显示,在Armijo型线性搜索下的HZ共轭梯度法比在Wolfe线性搜索下更有效.     

Convergence and error bound analysis for the space‐time CESE method

In this work, we study the convergence behavior of a recently developed space‐time conservation element and solution element method for solving conservation laws. In particular, we apply the method to a one‐dimensional time‐dependent convection‐diffusion equation possibly with high Peclet number. We prove that the scheme converges and we obtain an error bound. This method performs well even for strong convection dominance over diffusion with good long‐time accuracy. Numerical simulations are performed to verify the results. © 2001 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 17: 64–78, 2001     

A short note on the global convergence of the unmodified PRP method

To guarantee global convergence of the standard (unmodified) PRP nonlinear conjugate gradient method for unconstrained optimization, the exact line search or some Armijo type line searches which force the PRP method to generate descent directions have been adopted. In this short note, we propose a non-descent PRP method in another way. We prove that the unmodified PRP method converges globally even for nonconvex minimization by the use of an approximate descent inexact line search.     

The regularized feasible directions method for nonconvex optimization

This paper develops and studies a feasible directions approach for the minimization of a continuous function over linear constraints in which the update directions belong to a predetermined finite set spanning the feasible set. These directions are recurrently investigated in a cyclic semi-random order, where the stepsize of the update is determined via univariate optimization. We establish that any accumulation point of this optimization procedure is a stationary point of the problem, meaning that the directional derivative in any feasible direction is nonnegative. To assess and establish a rate of convergence, we develop a new optimality measure that acts as a proxy for the stationarity condition, and substantiate its role by showing that it is coherent with first-order conditions in specific scenarios. Finally we prove that our method enjoys a sublinear rate of convergence of this optimality measure in expectation.     

Convergence analysis of projected fixed‐point iteration on a low‐rank matrix manifold

In this paper, we analyze the convergence of a projected fixed‐point iteration on a Riemannian manifold of matrices with fixed rank. As a retraction method, we use the projector splitting scheme. We prove that the convergence rate of the projector splitting scheme is bounded by the convergence rate of standard fixed‐point iteration without rank constraints multiplied by the function of initial approximation. We also provide counterexample to the case when conditions of the theorem do not hold. Finally, we support our theoretical results with numerical experiments.     

Nested Partitions Method for Stochastic Optimization

The nested partitions (NP) method is a recently proposed new alternative for global optimization. Primarily aimed at problems with large but finite feasible regions, the method employs a global sampling strategy that is continuously adapted via a partitioning of the feasible region. In this paper we adapt the original NP method to stochastic optimization where the performance is estimated using simulation. We prove asymptotic convergence of the new method and present a numerical example to illustrate its potential.     

A Runge–Kutta type modified Landweber method for nonlinear ill-posed operator equations

In this paper, we investigate the convergence behavior of a Runge–Kutta type modified Landweber method for nonlinear ill-posed operator equations. In order to improve the stability and convergence of the Landweber iteration, a 2-stage Gauss-type Runge–Kutta method is applied to the continuous analogy of the modified Landweber method, to give a new modified Landweber method, called R–K type modified Landweber method. Under some appropriate conditions, we prove the convergence of the proposed method. We conclude with a numerical example confirming the theoretical results, including comparisons to the modified Landweber iteration.     

On the effect of selection in genetic algorithms

To study the effect of selection with respect to mutation and mating in genetic algorithms, we consider two simplified examples in the infinite population limit. Both algorithms are modeled as measure valued dynamical systems and are designed to maximize a linear fitness on the half line. Thus, they both trivially converge to infinity. We compute the rate of their growth and we show that, in both cases, selection is able to overcome a tendency to converge to zero. The first model is a mutation‐selection algorithm on the integer half line, which generates mutations along a simple random walk. We prove that the system goes to infinity at a positive speed, even in cases where the random walk itself is ergodic. This holds in several strong senses, since we show a.s. convergence, L^p convergence, convergence in distribution, and a large deviations principle for the sequence of measures. For the second model, we introduce a new class of matings, based upon Mandelbrot martingales. The mean fitness of the associated mating‐selection algorithms on the real half line grows exponentially fast, even in cases where the Mandelbrot martingale itself converges to zero. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 185–200, 2001     

Integral equations in the wave scattering problem at an irregular interface of domains

Modeling the scattering of electromagnetic waves at an interface of media with different characteristics, one encounters the conjugation problem. Using the method of boundary integral equations and the theory of generalized potentials, we prove the classical resolvability of this problem. The boundary is assumed to be irregular. This means that the plane is divided into two domains by a curve which coincides with a straight line, except for a finite part, producing the irregularity. We propose algorithms for the approximate solution of the conjugation problem based on the spline methods for the solution of integral equations. We theoretically substantiate the computational scheme, namely, we prove the convergence and estimate the convergence rate.     

A constructive Schwarz reflection principle

We prove a constructive version of the Schwarz reflection principle. Our proof techniques are in line with Bishop's development of constructive analysis. The principle we prove enables us to reflect analytic functions in the real line, given that the imaginary part of the function converges to zero near the real line in a uniform fashion. This form of convergence to zero is classically equivalent to pointwise convergence, but may be a stronger condition from the constructivist point of view.

     

A QP Free Feasible Method

In [12], a QP free feasible method was proposed for the minimization of a smooth function subject to smooth inequality constraints. This method is based on the solutions of linear systems of equations, the reformulation of the KKT optimality conditions by using the Fischer-Burmeister NCP function. This method ensures the feasibility of all iterations. In this paper, we modify the method in [12] slightly to obtain the local convergence under some weaker conditions. In particular, this method is implementable and globally convergent without assuming the linear independence of the gradients of active constrained functions and the uniformly positive definiteness of the submatrix obtained by the Newton or Quasi Newton methods. We also prove that the method has superlinear convergence rate under some mild conditions. Some preliminary numerical results indicate that this new QP free feasible method is quite promising.