Solving generalized equations via homotopies

Global Newton methods for computing solutions of nonlinear systems of equations have recently received a great deal of attention. By using the theory of generalized equations, a homotopy method is proposed to solve problems arising in complementarity and mathematical programming, as well as in variational inequalities. We introduce the concepts of generalized homotopies and regular values, characterize the solution sets of such generalized homotopies and prove, under boundary conditions similar to Smale’s [10], the existence of a homotopy path which contains an odd number of solutions to the problem. We related our homotopy path to the Newton method for generalized equations developed by Josephy [3]. An interpretation of our results for the nonlinear programming problem will be given.     

Some computational methods for systems of nonlinear equations and systems of polynomial equations

This paper gives a brief survey and assessment of computational methods for finding solutions to systems of nonlinear equations and systems of polynomial equations. Starting from methods which converge locally and which find one solution, we progress to methods which are globally convergent and find an a priori determinable number of solutions. We will concentrate on simplicial algorithms and homotopy methods. Enhancements of published methods are included and further developments are discussed.     

求解Hamilton约束的新算法

利用吴方法对多项式类型带约束的Hamilton系统作了研究.给出了判断系统是否正则的一个新算法.对于正则系统,可以得到Hamilton函数和运动方程,而对退化的系统给出了两个求解约束的新算法,得到带约束的Hamilton函数和运动方程.利用符号计算软件,这几个算法都可以在计算机上实现.     

A unified approach to global convergence of trust region methods for nonsmooth optimization

This paper investigates the global convergence of trust region (TR) methods for solving nonsmooth minimization problems. For a class of nonsmooth objective functions called regular functions, conditions are found on the TR local models that imply three fundamental convergence properties. These conditions are shown to be satisfied by appropriate forms of Fletcher's TR method for solving constrained optimization problems, Powell and Yuan's TR method for solving nonlinear fitting problems, Zhang, Kim and Lasdon's successive linear programming method for solving constrained problems, Duff, Nocedal and Reid's TR method for solving systems of nonlinear equations, and El Hallabi and Tapia's TR method for solving systems of nonlinear equations. Thus our results can be viewed as a unified convergence theory for TR methods for nonsmooth problems.Research supported by AFOSR 89-0363, DOE DEFG05-86ER25017 and ARO 9DAAL03-90-G-0093.Corresponding author.     

电力系统中地网腐蚀诊断的一种新的数学模型及其仿真计算

对电力系统中具有重大应用价值的地网腐蚀诊断问题抽象出仿真求解的一种新的数学模型:即求解带约束的非线性隐式方程组模型.但由于问题本身的物理特性决定了所建立的数学模型具有以下特点:一是非线性方程组为欠定方程组,而且非线性程度非常高;二是方程组的所有函数均为隐函数;三是方程组附加若干箱约束条件.这种特性给模型分析与算法设计带来巨大困难.对于欠定方程组的求解,文中根据工程实际背景,尽可能地扩充方程的个数,使之成为超定方程组,然后对欠定方程组和超定方程组分别求解并进行比较.将带约束的非线性隐函数方程组求解问题,转化为无约束非线性最小二乘问题,并采用矩阵求导等技术和各种算法设计技巧克服隐函数的计算困难,最后使用拟牛顿信赖域方法进行计算.大量的计算实例表明,文中所提出的数学模型及求解方法是可行的.与目前广泛采用的工程简化模型相比较,在模型和算法上具有很大优势.     

Quasi-Newton acceleration for equality-constrained minimization

Optimality (or KKT) systems arise as primal-dual stationarity conditions for constrained optimization problems. Under suitable constraint qualifications, local minimizers satisfy KKT equations but, unfortunately, many other stationary points (including, perhaps, maximizers) may solve these nonlinear systems too. For this reason, nonlinear-programming solvers make strong use of the minimization structure and the naive use of nonlinear-system solvers in optimization may lead to spurious solutions. Nevertheless, in the basin of attraction of a minimizer, nonlinear-system solvers may be quite efficient. In this paper quasi-Newton methods for solving nonlinear systems are used as accelerators of nonlinear-programming (augmented Lagrangian) algorithms, with equality constraints. A periodically-restarted memoryless symmetric rank-one (SR1) correction method is introduced for that purpose. Convergence results are given and numerical experiments that confirm that the acceleration is effective are presented. This work was supported by FAPESP, CNPq, PRONEX-Optimization (CNPq / FAPERJ), FAEPEX, UNICAMP.     

Sequential Systems of Linear Equations Algorithm for Nonlinear Optimization Problems with General Constraints

In Ref. 1, a new superlinearly convergent algorithm of sequential systems of linear equations (SSLE) for nonlinear optimization problems with inequality constraints was proposed. At each iteration, this new algorithm only needs to solve four systems of linear equations having the same coefficient matrix, which is much less than the amount of computation required for existing SQP algorithms. Moreover, unlike the quadratic programming subproblems of the SQP algorithms (which may not have a solution), the subproblems of the SSLE algorithm are always solvable. In Ref. 2, it is shown that the new algorithm can also be used to deal with nonlinear optimization problems having both equality and inequality constraints, by solving an auxiliary problem. But the algorithm of Ref. 2 has to perform a pivoting operation to adjust the penalty parameter per iteration. In this paper, we improve the work of Ref. 2 and present a new algorithm of sequential systems of linear equations for general nonlinear optimization problems. This new algorithm preserves the advantages of the SSLE algorithms, while at the same time overcoming the aforementioned shortcomings. Some numerical results are also reported.     

ABS methods and ABSPACK for linear systems and optimization: A review

ABS methods are a large class of methods, based upon the Egervary rank reducing algebraic process, first introduced in 1984 by Abaffy, Broyden and Spedicato for solving linear algebraic systems, and later extended to nonlinear algebraic equations, to optimization problems and other fields; software based upon ABS methods is now under development. Current ABS literature consists of about 400 papers. ABS methods provide a unification of several classes of classical algorithms and more efficient new solvers for a number of problems. In this paper we review ABS methods for linear systems and optimization, from both the point of view of theory and the numerical performance of ABSPACK.Work partially supported by ex MURST 60% 2001 funds.E. Spedicato     

On the optimization of Gegenbauer operational matrix of integration

The theory of Gegenbauer (ultraspherical) polynomial approximation has received considerable attention in recent decades. In particular, the Gegenbauer polynomials have been applied extensively in the resolution of the Gibbs phenomenon, construction of numerical quadratures, solution of ordinary and partial differential equations, integral and integro-differential equations, optimal control problems, etc. To achieve better solution approximations, some methods presented in the literature apply the Gegenbauer operational matrix of integration for approximating the integral operations, and recast many of the aforementioned problems into unconstrained/constrained optimization problems. The Gegenbauer parameter α associated with the Gegenbauer polynomials is then added as an extra unknown variable to be optimized in the resulting optimization problem as an attempt to optimize its value rather than choosing a random value. This issue is addressed in this article as we prove theoretically that it is invalid. In particular, we provide a solid mathematical proof demonstrating that optimizing the Gegenbauer operational matrix of integration for the solution of various mathematical problems by recasting them into equivalent optimization problems with α added as an extra optimization variable violates the discrete Gegenbauer orthonormality relation, and may in turn produce false solution approximations.     

Nonlinear and Geometric Programming – Current Status

Great strides have been made in nonlinear programming (NLP) in the last 5 years. In smooth NLP, there are now several reliable and efficient codes capable of solving large problems. Most of these implement GRG or SQP methods, and new software using interior point algorithms is under development. NLP software is now much easier to use, as it is interfaced with many modeling systems, including MSC/NASTRAN, and ANSYS for structural problems, GAMS and AMPL for general optimization, Matlab and Mathcad for general mathematical problems, and the widely used Microsoft Excel spreadsheet. For mixed integer problems, branch and bound and outer approximation codes are now available and are coupled to some of the above modeling systems, while search methods like Tabu Search and Genetic algorithms permit combinatorial, nonsmooth, and nonconvex problems to be attacked.     

Discrete Approximations to Continuum Optimal Flow Problems

Problems in partial differential equations with inequality constraints can be used to describe a continuum analog to various optimal flow/cut problems. While general concepts from convex optimization (like duality) carry over into continuum problems, the application of ideas and algorithms from linear programming and network flow problems is challenging. The capacity constraints are nonlinear (but convex).
In this article, we investigate a discretized version of the planar maximum flow problem that preserves the nonlinear capacity constraints of the continuum problem. The resulting finite-dimensional problem can be cast as a second-order cone programming problem or a quadratically constrained program. Good numerical results can be obtained using commercial solvers. These results are in agreement with the continuum theory of a "challenge" problem posed by Strang.     

Global solutions to a class of CEC benchmark constrained optimization problems

This paper aims to solve a class of CEC benchmark constrained optimization problems that have been widely studied by nature-inspired optimization algorithms. Based on canonical duality theory, these challenging problems can be reformulated as a unified canonical dual problem over a convex set, which can be solved deterministically to obtain global optimal solutions in polynomial time. Applications are illustrated by some well-known CEC benchmark problems, and comparisons with other methods have demonstrated the effectiveness of the proposed approach.     

Some software aspects of DAE simulation & optimization software

Considerable numerical software has been written for simulation and optimization of dynamical systems. From the beginning of their development, differential algebraic equations (DAEs) have often been proposed as a way to make modeling easier. The modeler need only write down equations relating the variables in the model. However, much DAE software requires at least as much user numerical and mathematical expertise as explicit methods. An important aspect of our research has been working toward helping the idea of DAEs achieve its promise in modeling and simulation by both pushing the software to handle more general problems and to also allow for less user expertise. Some recent examples are presented where this research impacts on software and their underlying algorithms. Space necessitates we assume the reader has a rough idea of what a DAE is. The examples are implicit Scicos, and optimization of DAE models. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Dynamic programming and Lagrange multipliers for active relaxation of resources in nonlinear non-equilibrium systems

In power production problems maximum power and minimum entropy production and inherently connected by the Gouy–Stodola law. In this paper various mathematical tools are applied in dynamic optimization of power-maximizing paths, with special attention paid to nonlinear systems. Maximum power and/or minimum entropy production are governed by Hamilton–Jacobi–Bellman (HJB) equations which describe the value function of the problem and associated controls. Yet, in many cases optimal relaxation curve is non-exponential, governing HJB equations do not admit classical solutions and one has to work with viscosity solutions. Systems with nonlinear kinetics (e.g. radiation engines) are particularly difficult, thus, discrete counterparts of continuous HJB equations and numerical approaches are recommended. Discrete algorithms of dynamic programming (DP), which lead to power limits and associated availabilities, are effective. We consider convergence of discrete algorithms to viscosity solutions of HJB equations, discrete approximations, and the role of Lagrange multiplier λ associated with the duration constraint. In analytical discrete schemes, the Legendre transformation is a significant tool leading to original work function. We also describe numerical algorithms of dynamic programming and consider dimensionality reduction in these algorithms. Indications showing the method potential for other systems, in particular chemical energy systems, are given.     

A class of nonlinear nonseparable continuous knapsack and multiple-choice knapsack problems

This paper considers a general class of continuous, nonlinear, and nonseparable knapsack problems, special cases of which arise in numerous operations and financial contexts. We develop important properties of optimal solutions for this problem class, based on the properties of a closely related class of linear programs. Using these properties, we provide a solution method that runs in polynomial time in the number of decision variables, while also depending on the time required to solve a particular one-dimensional optimization problem. Thus, for the many applications in which this one-dimensional function is reasonably well behaved (e.g., unimodal), the resulting algorithm runs in polynomial time. We next develop a related solution approach to a class of continuous, nonlinear, and nonseparable multiple-choice knapsack problems. This algorithm runs in polynomial time in both the number of variables and the number of variants per item, while again dependent on the complexity of the same one-dimensional optimization problem as for the knapsack problem. Computational testing demonstrates the power of the proposed algorithms over a commercial global optimization software package.     

Solution of Delay Differential Equation by Means of Homotopy Analysis Method

The algorithm of approximate analytical solution for delay differential equations (DDE) is obtained via homotopy analysis method (HAM) and modified homotopy analysis method (MHAM). Various examples of linear, nonlinear and system of initial value problems of DDE are solved and the results obtained show that these algorithms are accurate and efficient for the DDE. The convergence of this algorithm is also proved.     

无线通信中的最优资源分配―复杂性分析与算法设计

最优资源分配问题是无线通信系统设计中的基本问题之一.最优地分配功率、传输波形和频谱等资源能够极大地提高整个通信系统的传输性能.目前,相对于通信技术在现实生活中的蓬勃发展,通信系统优化的数学理论和方法显得相对滞后,在某些方面已经成为影响其发展和应用的关键因素.无线通信中的最优资源分配问题常常可建模为带有特殊结构的非凸非线性约束优化问题.一方面,这些优化问题常常具有高度的非线性性,一般情况下难于求解;另一方面,它们又有自身的特殊结构,如隐含的凸性和可分结构等.本文着重考虑多用户干扰信道中物理层资源最优分配问题的复杂性刻画,以及如何利用问题的特殊结构设计有效且满足分布式应用等实际要求的计算方法.     

Bound constrained interval global optimization in the COCONUT Environment

We introduce a new interval global optimization method for solving bound constrained problems. The method originates from a small standalone software and is implemented in the COCONUT Environment, a framework designed for the development of complex algorithms, containing numerous state-of-the-art methods in a common software platform. The original algorithm is enhanced by various new methods implemented in COCONUT, regarding both interval function evaluations (such as first and second order derivatives with backward automatic differentiation, slopes, slopes of derivatives, bicentered forms, evaluations on the Karush–John conditions, etc.) and algorithmic elements (inclusion/exclusion boxes, local search, constraint propagation). This resulted in a substantial performance increase as compared to the original code. During the selection of the best combination of options, we performed comparison tests that gave empirical answers to long-lasting algorithmic questions (such as whether to use interval gradients or use slopes instead), that have never been studied numerically in such detail before. The new algorithm, called coco_gop_ex, was tested against the prestigious BARON software on an extensive set of bound constrained problems. We found that in addition to accepting a wider class of bound constrained problems and providing more output information (by locating all global minimizers), coco_gop_ex is competitive with BARON in terms of the solution success rates (with the exception of a set of nonlinear least squares problems), and it often outperforms BARON in running time. In particular, coco_gop_ex was around 21 % faster on average over the set of problems solved by both software systems.     

结构动力学逆特征值问题的同伦解法

将结构动力学反问题视为拟乘法逆特征值问题,利用求解非线性方程组的同伦方法来解决结构动力学逆特征值问题,这种方法由于沿同伦路径求解,对初值的选取没有本质的要求,算例说明了这种方法是可行的．