A secant algorithm with line search filter method for nonlinear optimization

Filter methods were initially designed for nonlinear programming problems by Fletcher and Leyffer. In this paper we propose a secant algorithm with line search filter method for nonlinear equality constrained optimization. The algorithm yields the global convergence under some reasonable conditions. By using the Lagrangian function value in the filter we establish that the proposed algorithm can overcome the Maratos effect without using second order correction step, so that fast local superlinear convergence to second order sufficient local solution is achieved. The primary numerical results are presented to confirm the robustness and efficiency of our approach.     

A new inexact SQP algorithm for nonlinear systems of mixed equalities and inequalities

Traditional inexact SQP algorithm can only solve equality constrained optimization (Byrd et al. Math. Program. 122, 273–299 2010). In this paper, we propose a new inexact SQP algorithm with affine scaling technique for nonlinear systems of mixed equalities and inequalities, which arise in complementarity and variational inequalities. The nonlinear systems are transformed into a special nonlinear optimization with equality and bound constraints, and then we give a new inexact SQP algorithm for solving it. The new algorithm equipped with affine scaling technique does not require a quadratic programming subproblem with inequality constraints. The search direction is computed by solving one linear system approximately using iterative linear algebra techniques. Under mild assumptions, we discuss the global convergence. The preliminary numerical results show the effectiveness of the proposed algorithm.     

A derivative-free algorithm for systems of nonlinear inequalities

Recently a new derivative-free algorithm has been proposed for the solution of linearly constrained finite minimax problems. This derivative-free algorithm is based on a smoothing technique that allows one to take into account the non-smoothness of the max function. In this paper, we investigate, both from a theoretical and computational point of view, the behavior of the minmax algorithm when used to solve systems of nonlinear inequalities when derivatives are unavailable. In particular, we show an interesting property of the algorithm, namely, under some mild conditions regarding the regularity of the functions defining the system, it is possible to prove that the algorithm locates a solution of the problem after a finite number of iterations. Furthermore, under a weaker regularity condition, it is possible to show that an accumulation point of the sequence generated by the algorithm exists which is a solution of the system. Moreover, we carried out numerical experimentation and comparison of the method against a standard pattern search minimization method. The obtained results confirm that the good theoretical properties of the method correspond to interesting numerical performance. Moreover, the algorithm compares favorably with a standard derivative-free method, and this seems to indicate that extending the smoothing technique to pattern search algorithms can be beneficial.     

A line search filter algorithm with inexact step computations for equality constrained optimization

In this paper, a new line search filter algorithm for equality constrained optimization is presented. The approach belongs to the class of inexact Newton-like methods. It can also be regarded as an inexact version of generic sequential quadratic programming (SQP) methods. The trial step is obtained by truncatedly solving the primal-dual system based on any robust and efficient linear system solver. Practical termination tests for the linear system solver are established to ensure global convergence. Preliminary numerical results demonstrate the approach is potentially useful.     

Nonmonotone filter DQMM method for the system of nonlinear equations

In this paper, we propose a nonmonotone filter Diagonalized Quasi-Newton Multiplier (DQMM) method for solving system of nonlinear equations. The system of nonlinear equations is transformed into a constrained nonlinear programming problem which is then solved by nonmonotone filter DQMM method. A nonmonotone criterion is used to speed up the convergence progress in some ill-conditioned cases. Under reasonable conditions, we give the global convergence properties. The numerical experiments are reported to show the effectiveness of the proposed algorithm.     

A new adaptive trust-region method for system of nonlinear equations

This study presents a new trust-region procedure to solve a system of nonlinear equations in several variables. The proposed approach combines an effective adaptive trust-region radius with a nonmonotone strategy, because it is believed that this combination can improve the efficiency and robustness of the trust-region framework. Indeed, it decreases the computational cost of the algorithm by decreasing the required number of subproblems to be solved. The global and the quadratic convergence of the proposed approach is proved without any nondegeneracy assumption of the exact Jacobian. Preliminary numerical results indicate the promising behavior of the new procedure to solve systems of nonlinear equations.     

A Newton inexact interior-point method for large scale nonlinear optimization problems

In this paper, we describe a variant of the Newton Interior-Point method in [8] for nonlinear programming problems. In this scheme, the perturbation parameter can be chosen within a range of, values and we can use an iterative method for approximately solving the reduced linear system arising at each step. We have devised the inner termination rule which guarantees the global convergence of this Newton Inexact Interior-Point method. We remark that the required assumptions are weaker than those stated in [8], as shown by some numerical examples. This research was supported by the Italian Ministry for Education, University and Research (MIUR), FIRB Project No. RBAU01JYPN.     

A global quadratic algorithm for solving a system of mixed equalities and inequalities

A new algorithm is proposed which, under mild assumptions, generates a sequence{x _i } that starting at any point inR ⁿ will converge to a setX defined by a mixed system of equations and inequalities. Any iteration of the algorithm requires the solution of a linear programming problem with relatively few constraints. By only assuming that the functions involved are continuously differentiable a superlinear rate of convergence is achieved. No convexity whatsoever is required by the algorithm.     

A reduced Hessian algorithm with line search filter method for nonlinear programming

This paper proposes a line search filter reduced Hessian method for nonlinear equality constrained optimization. The feature of the presented algorithm is that the reduced Hessian method is used to produce a search direction, a backtracking line search procedure to generate step size, some filtered rules to determine step acceptance, second order correction technique to reduce infeasibility and overcome the Maratos effects. It is shown that this algorithm does not suffer from the Maratos effects by using second order correction step, and under mild assumptions fast convergence to second order sufficient local solutions is achieved. The numerical experiment is reported to show the effectiveness of the proposed algorithm.     

An Affine Scaling Interior Trust-Region Algorithm Combining Backtracking Line Search with Filter Technique for Nonlinear Constrained Optimization

In this article, an affine scaling interior trust-region algorithm which employs backtracking line search with filter technique is presented for solving nonlinear equality constrained programming with nonnegative constraints on variables. At current iteration, the general full affine scaling trust-region subproblem is decomposed into a pair of trust-region subproblems in vertical and horizontal subspaces, respectively. The trial step is given by the solutions of the pair of trust-region subproblems. Then, the step size is decided by backtracking line search together with filter technique. This is different from traditional trust-region methods and has the advantage of decreasing the number of times that a trust-region subproblem must be resolved in order to determine a new iteration point. Meanwhile, using filter technique instead of merit function to determine a new iteration point can avoid the difficult decisions regarding the choice of penalty parameters. Under some reasonable assumptions, the new method possesses the property of global convergence to the first-order critical point. Preliminary numerical results show the effectiveness of the proposed algorithm.     

非单调滤子曲率线搜索算法解无约束非凸优化

宇和濮在文[Yu Z S,Pu D G.A new nonmonotone line search technique for unconstrained optimization[J].J Comput Appl Math,2008,219:134-144]中提出了一种非单调的线搜索算法解无约束优化问题.和他们的工作不同,当优化问题非凸时,本文给出了一种非单调滤子曲率线搜索算法.通过使用海森矩阵的负曲率信息,算法产生的迭代序列被证明收敛于一个满足二阶充分性条件的点.在不需要假设极限点存在的情况下,证明了算法具有整体收敛性,而且分析了该算法的收敛速率.数值试验表明算法的有效性.     

A filter inexact-restoration method for nonlinear programming

A new iterative algorithm based on the inexact-restoration (IR) approach combined with the filter strategy to solve nonlinear constrained optimization problems is presented. The high level algorithm is suggested by Gonzaga et al. (SIAM J. Optim. 14:646–669, 2003) but not yet implement—the internal algorithms are not proposed. The filter, a new concept introduced by Fletcher and Leyffer (Math. Program. Ser. A 91:239–269, 2002), replaces the merit function avoiding the penalty parameter estimation and the difficulties related to the nondifferentiability. In the IR approach two independent phases are performed in each iteration, the feasibility and the optimality phases. The line search filter is combined with the first one phase to generate a “more feasible” point, and then it is used in the optimality phase to reach an “optimal” point. Numerical experiences with a collection of AMPL problems and a performance comparison with IPOPT are provided.      

On the Vykhandu-Levin iterative method for numerical solution of nonlinear systems

An iterative method for the solution of systems of nonlinear equations initiated by Vykhandu and investigated by Levin is discussed. It is shown that there is a flaw in the proof of Levin that the method is third-order convergent. Moreover, it is proved that the correct order of the method is only two.     

A penalty-free method with line search for nonlinear equality constrained optimization

A new line search method is introduced for solving nonlinear equality constrained optimization problems. It does not use any penalty function or a filter. At each iteration, the trial step is determined such that either the value of the objective function or the measure of the constraint violation is sufficiently reduced. Under usual assumptions, it is shown that every limit point of the sequence of iterates generated by the algorithm is feasible, and there exists at least one limit point that is a stationary point for the problem. A simple modification of the algorithm by introducing second order correction steps is presented. It is shown that the modified method does not suffer from the Maratos’ effect, so that it converges superlinearly. The preliminary numerical results are reported.     

一种求解混合约束优化问题的半可行序列线性方程组滤子算法的全局收敛性

本文提出了一种半可行的序列线性方程组(SSLE)滤子方法.在文献[6]的基础上,将QP-free方法推广到混合约束优化问题,对不等式约束部分保持其可行性,而对等式约束部分用滤子方法处理,从而避免了罚参数的选取.本文提出的算法只需求解四个具有相同的非退化的系统矩阵的线性方程组以得到搜索方向.在一定程度上克服了SQP方法的缺点.另外,为了提高计算效率,算法中使用了χ -有效集.本文给出了该算法的全局收敛性证明.     

A globally convergent inexact Newton method with a new choice for the forcing term

In inexact Newton methods for solving nonlinear systems of equations, an approximation to the step s _k of the Newton’s system J(x _k )s=−F(x _k ) is found. This means that s _k must satisfy a condition like ‖F(x _k )+J(x _k )s _k ‖≤η _k ‖F(x _k )‖ for a forcing term η _k ∈[0,1). Possible choices for η _k have already been presented. In this work, a new choice for η _k is proposed. The method is globalized using a robust backtracking strategy proposed by Birgin et al. (Numerical Algorithms 32:249–260, 2003), and its convergence properties are proved. Several numerical experiments with boundary value problems are presented. The numerical performance of the proposed algorithm is analyzed by the performance profile tool proposed by Dolan and Moré (Mathematical Programming Series A 91:201–213, 2002). The results obtained show a competitive inexact Newton method for solving academic and applied problems in several areas. Supported by FAPESP, CNPq, PRONEX-Optimization.     

Inexact trust region method for large sparse systems of nonlinear equations

The main purpose of this paper is to prove the global convergence of the new trust region method based on the smoothed CGS algorithm. This method is surprisingly convenient for the numerical solution of large sparse systems of nonlinear equations, as is demonstrated by numerical experiments. A modification of the proposed trust region method does not use matrices, so it can be used for large dense systems of nonlinear equations.     

A nonmonotone globalization algorithm with preconditioned gradient path for unconstrained optimization

The aim of this paper is to incorporate the preconditioned gradient path in a nonmonotone stabilization algorithm for unconstrained optimization. The global convergence and locally superlinear convergence are established for this class of algorithms. Finally, we report in details the numerical results which show the effectiveness of the proposed algorithm.     

An observer for a class of disturbance driven nonlinear systems

An observer design for a class of nonlinear systems driven by disturbances or uncertainties is presented. The design is based on a high gain strategy, and the gain of the proposed observer is explicitly given.