A Conic Trust-Region Method for Nonlinearly Constrained Optimization

Trust-region methods are powerful optimization methods. The conic model method is a new type of method with more information available at each iteration than standard quadratic-based methods. Can we combine their advantages to form a more powerful method for constrained optimization? In this paper we give a positive answer and present a conic trust-region algorithm for non-linearly constrained optimization problems. The trust-region subproblem of our method is to minimize a conic function subject to the linearized constraints and the trust region bound. The use of conic functions allows the model to interpolate function values and gradient values of the Lagrange function at both the current point and previous iterate point. Since conic functions are the extension of quadratic functions, they approximate general nonlinear functions better than quadratic functions. At the same time, the new algorithm possesses robust global properties. In this paper we establish the global convergence of the new algorithm under standard conditions.     

Preconditioning and globalizing conjugate gradients in dual space for quadratically penalized nonlinear-least squares problems

When solving nonlinear least-squares problems, it is often useful to regularize the problem using a quadratic term, a practice which is especially common in applications arising in inverse calculations. A solution method derived from a trust-region Gauss-Newton algorithm is analyzed for such applications, where, contrary to the standard algorithm, the least-squares subproblem solved at each iteration of the method is rewritten as a quadratic minimization subject to linear equality constraints. This allows the exploitation of duality properties of the associated linearized problems. This paper considers a recent conjugate-gradient-like method which performs the quadratic minimization in the dual space and produces, in exact arithmetic, the same iterates as those produced by a standard conjugate-gradients method in the primal space. This dual algorithm is computationally interesting whenever the dimension of the dual space is significantly smaller than that of the primal space, yielding gains in terms of both memory usage and computational cost. The relation between this dual space solver and PSAS (Physical-space Statistical Analysis System), another well-known dual space technique used in data assimilation problems, is explained. The use of an effective preconditioning technique is proposed and refined convergence bounds derived, which results in a practical solution method. Finally, stopping rules adequate for a trust-region solver are proposed in the dual space, providing iterates that are equivalent to those obtained with a Steihaug-Toint truncated conjugate-gradient method in the primal space.     

Modified Partial-Update Newton-Type Algorithms for Unary Optimization

In this paper, we propose two modified partial-update algorithms for solving unconstrained unary optimization problems based on trust-region stabilization via indefinite dogleg curves. The two algorithms partially update an approximation to the Hessian matrix in each iteration by utilizing a number of times the rank-one updating of the Bunch–Parlett factorization. In contrast with the original algorithms in Ref. 1, the two algorithms not only converge globally, but possess also a locally quadratic or superlinear convergence rate. Furthermore, our numerical experiments show that the new algorithms outperform the trust-region method which uses the partial update criteria suggested in Ref. 1.     

线性不等式约束的广义非线性互补问题的仿射内点信赖域方法

提供了一种新的非单调内点回代线搜索技术的仿射内点信赖域方法解线性不等式约束的广义非线性互补问题(GCP).基于广义互补问题构成的半光滑方程组的广义Jacobian矩阵,算法使用l2范数作为半光滑方程组的势函数,形成的信赖域子问题为一个带椭球约束的线性化的二次模型.利用广义牛顿方程计算试探迭代步,通过内点映射回代技术确保迭代点是严格内点,保证了算法的整体收敛性.在合理的条件下,证明了信赖域算法在接近最优点时可转化为广义拟牛顿步,进而具有局部超线性收敛速率.非单调技术将克服高度非线性情况加速收敛进展.最后,数值结果表明了算法的有效性.     

一类求解MPEC的全局收敛性算法

概述MPEC求解上存在的困难；提出将求解普通约束优化问题的信赖域方法用于求解MPEC；在适当条件下建立算法的全局收敛性定理。     

A trust region method for solving linearly constrained locally Lipschitz optimization problems

In this paper, we present a nonsmooth trust region method for solving linearly constrained optimization problems with a locally Lipschitz objective function. Using the approximation of the steepest descent direction, a quadratic approximation of the objective function is constructed. The null space technique is applied to handle the constraints of the quadratic subproblem. Next, the CG-Steihaug method is applied to solve the new approximation quadratic model with only the trust region constraint. Finally, the convergence of presented algorithm is proved. This algorithm is implemented in the MATLAB environment and the numerical results are reported.     

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 Limited-Memory Multipoint Symmetric Secant Method for Bound Constrained Optimization

A new algorithm for solving smooth large-scale minimization problems with bound constraints is introduced. The way of dealing with active constraints is similar to the one used in some recently introduced quadratic solvers. A limited-memory multipoint symmetric secant method for approximating the Hessian is presented. Positive-definiteness of the Hessian approximation is not enforced. A combination of trust-region and conjugate-gradient approaches is used to explore useful information. Global convergence is proved for a general model algorithm. Results of numerical experiments are presented.     

A sequential quadratically constrained quadratic programming method with an augmented Lagrangian line search function

Based on an augmented Lagrangian line search function, a sequential quadratically constrained quadratic programming method is proposed for solving nonlinearly constrained optimization problems. Compared to quadratic programming solved in the traditional SQP methods, a convex quadratically constrained quadratic programming is solved here to obtain a search direction, and the Maratos effect does not occur without any other corrections. The “active set” strategy used in this subproblem can avoid recalculating the unnecessary gradients and (approximate) Hessian matrices of the constraints. Under certain assumptions, the proposed method is proved to be globally, superlinearly, and quadratically convergent. As an extension, general problems with inequality and equality constraints as well as nonmonotone line search are also considered.     

A linear programming-based optimization algorithm for solving nonlinear programming problems

In this paper a linear programming-based optimization algorithm called the Sequential Cutting Plane algorithm is presented. The main features of the algorithm are described, convergence to a Karush–Kuhn–Tucker stationary point is proved and numerical experience on some well-known test sets is showed. The algorithm is based on an earlier version for convex inequality constrained problems, but here the algorithm is extended to general continuously differentiable nonlinear programming problems containing both nonlinear inequality and equality constraints. A comparison with some existing solvers shows that the algorithm is competitive with these solvers. Thus, this new method based on solving linear programming subproblems is a good alternative method for solving nonlinear programming problems efficiently. The algorithm has been used as a subsolver in a mixed integer nonlinear programming algorithm where the linear problems provide lower bounds on the optimal solutions of the nonlinear programming subproblems in the branch and bound tree for convex, inequality constrained problems.     

On the Global Convergence of a Projective Trust Region Algorithm for Nonlinear Equality Constrained Optimization

A trust-region sequential quadratic programming (SQP) method is developed and analyzed for the solution of smooth equality constrained optimization problems. The trust-region SQP algorithm is based on filter line search technique and a composite-step approach, which decomposes the overall step as sum of a vertical step and a horizontal step. The algorithm includes critical modifications of horizontal step computation. One orthogonal projective matrix of the Jacobian of constraint functions is employed in trust-region subproblems. The orthogonal projection gives the null space of the transposition of the Jacobian of the constraint function. Theoretical analysis shows that the new algorithm retains the global convergence to the first-order critical points under rather general conditions. The preliminary numerical results are reported.     

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.     

An Extended Sequential Quadratically Constrained Quadratic Programming Algorithm for Nonlinear, Semidefinite, and Second-Order Cone Programming

This paper is concerned with nonlinear, semidefinite, and second-order cone programs. A general algorithm, which includes sequential quadratic programming and sequential quadratically constrained quadratic programming methods, is presented for solving these problems. In the particular case of standard nonlinear programs, the algorithm can be interpreted as a prox-regularization of the Solodov sequential quadratically constrained quadratic programming method presented in Mathematics of Operations Research (2004). For such type of methods, the main cost of computation amounts to solve a linear cone program for which efficient solvers are available. Usually, “global convergence results” for these methods require, as for the Solodov method, the boundedness of the primal sequence generated by the algorithm. The other purpose of this paper is to establish global convergence results without boundedness assumptions on any of the iterative sequences built by the algorithm.     

An interior-point trust-funnel algorithm for nonlinear optimization

We present an interior-point trust-funnel algorithm for solving large-scale nonlinear optimization problems. The method is based on an approach proposed by Gould and Toint (Math Prog 122(1):155–196, 2010) that focused on solving equality constrained problems. Our method is similar in that it achieves global convergence guarantees by combining a trust-region methodology with a funnel mechanism, but has the additional capability of being able to solve problems with both equality and inequality constraints. The prominent features of our algorithm are that (i) the subproblems that define each search direction may be solved with matrix-free methods so that derivative matrices need not be formed or factorized so long as matrix-vector products with them can be performed; (ii) the subproblems may be solved approximately in all iterations; (iii) in certain situations, the computed search directions represent inexact sequential quadratic optimization steps, which may be desirable for fast local convergence; (iv) criticality measures for feasibility and optimality aid in determining whether only a subset of computations need to be performed during a given iteration; and (v) no merit function or filter is needed to ensure global convergence.     

Global convergence of a derivative-free inexact restoration filter algorithm for nonlinear programming

In this work, we present an algorithm for solving constrained optimization problems that does not make explicit use of the objective function derivatives. The algorithm mixes an inexact restoration framework with filter techniques, where the forbidden regions can be given by the flat or slanting filter rule. Each iteration is decomposed into two independent phases: a feasibility phase which reduces an infeasibility measure without evaluations of the objective function, and an optimality phase which reduces the objective function value. As the derivatives of the objective function are not available, the optimality step is computed by derivative-free trust-region internal iterations. Any technique to construct the trust-region models can be used since the gradient of the model is a reasonable approximation of the gradient of the objective function at the current point. Assuming this and classical assumptions, we prove that the full steps are efficient in the sense that near a feasible nonstationary point, the decrease in the objective function is relatively large, ensuring the global convergence results of the algorithm. Numerical experiments show the effectiveness of the proposed method.     

A sequential quadratic programming algorithm for equality-constrained optimization without derivatives

In this paper, we present a new model-based trust-region derivative-free optimization algorithm which can handle nonlinear equality constraints by applying a sequential quadratic programming (SQP) approach. The SQP methodology is one of the best known and most efficient frameworks to solve equality-constrained optimization problems in gradient-based optimization [see e.g. Lalee et al. (SIAM J Optim 8:682–706, 1998), Schittkowski (Optim Lett 5:283–296, 2011), Schittkowski and Yuan (Wiley encyclopedia of operations research and management science, Wiley, New York, 2010)]. Our derivative-free optimization (DFO) algorithm constructs local polynomial interpolation-based models of the objective and constraint functions and computes steps by solving QP sub-problems inside a region using the standard trust-region methodology. As it is crucial for such model-based methods to maintain a good geometry of the set of interpolation points, our algorithm exploits a self-correcting property of the interpolation set geometry. To deal with the trust-region constraint which is intrinsic to the approach of self-correcting geometry, the method of Byrd and Omojokun is applied. Moreover, we will show how the implementation of such a method can be enhanced to outperform well-known DFO packages on smooth equality-constrained optimization problems. Numerical experiments are carried out on a set of test problems from the CUTEst library and on a simulation-based engineering design problem.     

Scaled Optimal Path Trust-Region Algorithm

Trust-region algorithms solve a trust-region subproblem at each iteration. Among the methods solving the subproblem, the optimal path algorithm obtains the solution to the subproblem in full-dimensional space by using the eigenvalues and eigenvectors of the system. Although the idea is attractive, the existing optimal path method seems impractical because, in addition to factorization, it requires either the calculation of the full eigensystem of a matrix or repeated factorizations of matrices at each iteration. In this paper, we propose a scaled optimal path trust-region algorithm. The algorithm finds a solution of the subproblem in full-dimensional space by just one Bunch–Parlett factorization for symmetric matrices at each iteration and by using the resulting unit lower triangular factor to scale the variables in the problem. A scaled optimal path can then be formed easily. The algorithm has good convergence properties under commonly used conditions. Computational results for small-scale and large-scale optimization problems are presented which show that the algorithm is robust and effective.     

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

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

Trust-region problems with linear inequality constraints: exact SDP relaxation,global optimality and robust optimization

The trust-region problem, which minimizes a nonconvex quadratic function over a ball, is a key subproblem in trust-region methods for solving nonlinear optimization problems. It enjoys many attractive properties such as an exact semi-definite linear programming relaxation (SDP-relaxation) and strong duality. Unfortunately, such properties do not, in general, hold for an extended trust-region problem having extra linear constraints. This paper shows that two useful and powerful features of the classical trust-region problem continue to hold for an extended trust-region problem with linear inequality constraints under a new dimension condition. First, we establish that the class of extended trust-region problems has an exact SDP-relaxation, which holds without the Slater constraint qualification. This is achieved by proving that a system of quadratic and affine functions involved in the model satisfies a range-convexity whenever the dimension condition is fulfilled. Second, we show that the dimension condition together with the Slater condition ensures that a set of combined first and second-order Lagrange multiplier conditions is necessary and sufficient for global optimality of the extended trust-region problem and consequently for strong duality. Through simple examples we also provide an insightful account of our development from SDP-relaxation to strong duality. Finally, we show that the dimension condition is easily satisfied for the extended trust-region model that arises from the reformulation of a robust least squares problem (LSP) as well as a robust second order cone programming model problem (SOCP) as an equivalent semi-definite linear programming problem. This leads us to conclude that, under mild assumptions, solving a robust LSP or SOCP under matrix-norm uncertainty or polyhedral uncertainty is equivalent to solving a semi-definite linear programming problem and so, their solutions can be validated in polynomial time.     

A hybrid algorithm for linearly constrained minimax problems

Many real life problems can be stated as a minimax problem, such as economics, finance, management, engineering and other fields, which demonstrate the importance of having reliable methods to tackle minimax problems. In this paper, an algorithm for linearly constrained minimax problems is presented in which we combine the trust-region methods with the line-search methods and curve-search methods. By means of this hybrid technique, it avoids possibly solving the trust-region subproblems many times, and make better use of the advantages of different methods. Under weaker conditions, the global and superlinear convergence are achieved. Numerical experiments show that the new algorithm is robust and efficient.