A simple SLP algorithm for solving a class of nonlinear programs

Successive linear programming (SLP) algorithms solve nonlinear optimization problems via a sequence of linear programs. We present an approach for a special class of nonlinear programming problems, which arise in multiperiod coal blending. The class of nonlinear programming problems and the solution approach considered in this paper are quite different from previous work. The algorithm is very simple, easy to apply and can be applied to as large a problem as the linear programming code can handle. The quality of solution, produced by the proposed algorithm, is discussed and the results of some test problems, in the real world environment, are provided.     

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.     

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.     

On the accurate identification of active set for constrained minimax problems

In this paper, the problem of identifying the active constraints for constrained nonlinear programming and minimax problems at an isolated local solution is discussed. The correct identification of active constraints can improve the local convergence behavior of algorithms and considerably simplify algorithms for inequality constrained problems, so it is a useful adjunct to nonlinear optimization algorithms. Facchinei et al. [F. Facchinei, A. Fischer, C. Kanzow, On the accurate identification of active constraints, SIAM J. Optim. 9 (1998) 14-32] introduced an effective technique which can identify the active set in a neighborhood of a solution for nonlinear programming. In this paper, we first improve this conclusion to be more suitable for infeasible algorithms such as the strongly sub-feasible direction method and the penalty function method. Then, we present the identification technique of active constraints for constrained minimax problems without strict complementarity and linear independence. Some numerical results illustrating the identification technique are reported.     

DC programming approaches for discrete portfolio optimization under concave transaction costs

The paper investigates DC programming and DCA for both modeling discrete portfolio optimization under concave transaction costs as DC programs, and their solution. DC reformulations are established by using penalty techniques in DC programming. A suitable global optimization branch and bound technique is also developed where a DC relaxation technique is used for lower bounding. Numerical simulations are reported that show the efficiency of DCA and the globality of its computed solutions, compared to standard algorithms for nonconvex nonlinear integer programs.     

A Declarative Modeling Framework that Integrates Solution Methods

Constraint programming offers modeling features and solution methods that are unavailable in mathematical programming but are often flexible and efficient for scheduling and other combinatorial problems. Yet mathematical programming is well suited to declarative modeling languages and is more efficient for some important problem classes. This raises this issue as to whether the two approaches can be combined in a declarative modeling framework. This paper proposes a general declarative modeling system in which the conditional structure of the constraints shows how to integrate any “checker” and any special-purpose “solver”. In particular this integrates constraint programming and optimization methods, because the checker can consist of constraint propagation methods, and the solver can be a linear or nonlinear programming routine.     

A Survey of Methods Available for the Numerical Optimization of Continuous Dynamic Systems

There has been significant progress in the development of numerical methods for the determination of optimal trajectories for continuous dynamic systems, especially in the last 20 years. In the 1980s, the principal contribution was new methods for discretizing the continuous system and converting the optimization problem into a nonlinear programming problem. This has been a successful approach that has yielded optimal trajectories for very sophisticated problems. In the last 15–20 years, researchers have applied a qualitatively different approach, using evolutionary algorithms or metaheuristics, to solve similar parameter optimization problems. Evolutionary algorithms use the principle of “survival of the fittest” applied to a population of individuals representing candidate solutions for the optimal trajectories. Metaheuristics optimize by iteratively acting to improve candidate solutions, often using stochastic methods. In this paper, the advantages and disadvantages of these recently developed methods are described and an attempt is made to answer the question of what is now the best extant numerical solution method.     

A convexification method for a class of global optimization problems with applications to reliability optimization

A convexification method is proposed for solving a class of global optimization problems with certain monotone properties. It is shown that this class of problems can be transformed into equivalent concave minimization problems using the proposed convexification schemes. An outer approximation method can then be used to find the global solution of the transformed problem. Applications to mixed-integer nonlinear programming problems arising in reliability optimization of complex systems are discussed and satisfactory numerical results are presented.     

An algorithm of sequential systems of linear equations for nonlinear optimization problems with arbitrary initial point

For current sequential quadratic programming (SQP) type algorithms, there exist two problems: (i) in order to obtain a search direction, one must solve one or more quadratic programming subproblems per iteration, and the computation amount of this algorithm is very large. So they are not suitable for the large-scale problems; (ii) the SQP algorithms require that the related quadratic programming subproblems be solvable per iteration, but it is difficult to be satisfied. By using ε-active set procedure with a special penalty function as the merit function, a new algorithm of sequential systems of linear equations for general nonlinear optimization problems with arbitrary initial point is presented. This new algorithm only needs to solve three systems of linear equations having the same coefficient matrix per iteration, and has global convergence and local superlinear convergence. To some extent, the new algorithm can overcome the shortcomings of the SQP algorithms mentioned above. Project partly supported by the National Natural Science Foundation of China and Tianyuan Foundation of China.     

Interval methods as a simulation tool for the dynamics of biological wastewater treatment processes with parameter uncertainties

This paper presents sophisticated interval algorithms for the simulation of discrete-time dynamical systems with bounded uncertainties of both initial conditions and system parameters. Since naive implementations of interval algorithms might lead to guaranteed enclosures of all system states which are too conservative to be practically useful, we present algorithmic extensions of classical approaches which are applicable to the simulation of non-cooperative systems with time-varying uncertain parameters. Overestimation arising in the interval evaluation of dynamical system models due to the wrapping effect is reduced by an exact pseudo-linear transformation of nonlinear state equations and by new heuristics for the subdivision of interval enclosures which especially prefer splitting of unstable intervals. To highlight the typical procedure for parameterization of interval-based simulation routines and to demonstrate their efficiency, a nonlinear model of biological wastewater treatment processes is discussed. For this application, we consider the maximum specific growth rate of substrate consuming bacteria as a time-varying uncertain parameter. Only worst-case bounds are assumed to be available for the range of this parameter while no information is provided about its actual variation rate.     

线性无关假设如何影响非线性约束最优化算法

首先综述非线性约束最优化最近的一些进展. 首次定义了约束最优化算法的全局收敛性. 注意到最优性条件的精确性和算法近似性之间的差异, 并回顾等式约束最优化的原始的Newton 型算法框架, 即可理解为什么约束梯度的线性无关假设应该而且可以被弱化. 这些讨论被扩展到不等式约束最优化问题. 然后在没有线性无关假设条件下, 证明了一个使用精确罚函数和二阶校正技术的算法可具有超线性收敛性. 这些认知有助于接下来开发求解包括非线性半定规划和锥规划等约束最优化问题的更加有效的新算法.     

Numerically stable methods for quadratic programming

Numerically stable algorithms for quadratic programming are discussed. A new algorithm is described for indefinite quadratic programming which utilizes methods for updating positivedefinite factorizations only. Consequently all the updating procedures required are common to algorithms for linearly-constrained optimization. The new algorithm can be used for the positive-definite case without loss of efficiency.     

Variable Programming: A Generalized Minimax Problem. Part I: Models and Theory

In this two-part series of papers, a new generalized minimax optimization model, termed variable programming (VP), is developed to solve dynamically a class of multi-objective optimization problems with non-decomposable structure. It is demonstrated that such type of problems is more general than existing optimization models. In this part, the VP model is proposed first, and the relationship between variable programming and the general constrained nonlinear programming is established. To illustrate its practicality, problems on investment and the low-side-lobe conformal antenna array pattern synthesis to which VP can be appropriately applied are discussed for substantiation. Then, theoretical underpinnings of the VP problems are established. Difficulties in dealing with the VP problems are discussed. With some mild assumptions, the necessary conditions for the unconstrained VP problems with arbitrary and specific activated feasible sets are derived respectively. The necessary conditions for the corresponding constrained VP problems with the mild hypotheses are also examined. Whilst discussion in this part is concentrated on the formulation of the VP model and its theoretical underpinnings, construction of solution algorithms is discussed in Part II.This work was supported by the RGC grant CUHK 152/96H of the Hong Kong Research Grant Council.     

Solving Planning and Design Problems in the Process Industry Using Mixed Integer and Global Optimization

This contribution gives an overview on the state-of-the-art and recent advances in mixed integer optimization to solve planning and design problems in the process industry. In some case studies specific aspects are stressed and the typical difficulties of real world problems are addressed. Mixed integer linear optimization is widely used to solve supply chain planning problems. Some of the complicating features such as origin tracing and shelf life constraints are discussed in more detail. If properly done the planning models can also be used to do product and customer portfolio analysis. We also stress the importance of multi-criteria optimization and correct modeling for optimization under uncertainty. Stochastic programming for continuous LP problems is now part of most optimization packages, and there is encouraging progress in the field of stochastic MILP and robust MILP. Process and network design problems often lead to nonconvex mixed integer nonlinear programming models. If the time to compute the solution is not bounded, there are already a commercial solvers available which can compute the global optima of such problems within hours. If time is more restricted, then tailored solution techniques are required.     

非线性半定规划若干算法介绍

介绍近几年国际上求解非线性半定规划的若干有效新算法, 包括增广Lagrangian函数法、序列半定规划法、序列线性方程组法以及交替方向乘子法. 最后, 对非线性半定规划的算法研究前景进行了探讨.     

Development of a Toolbox for Model‐Based Real‐Time Simulation and Analysis of Legged Robots

Multibody systems such as legged robots require sophisticated and efficient methods for their modeling, control and simulation. This paper discusses the development of a software library based on modern tools such as C++, OpenGL and XML for highly efficient dynamics modeling. A primary focus lies on modularity permitting its easy extensibility in connection with different actuation and contact models, optimization algorithms, localized and centralized on‐line control schemes as well as animation and simulation environments.     

SEQUENTIAL SYSTEMS OF LINEAR EQUATIONS ALGORITHM FOR NONLINEAR OPTIMIZATION PROBLEMS-INEQUALITY CONSTRAINED PROBLEMS

AbstractIn this paper, a new superlinearly convergent algorithm of sequential systems of linear equations (SSLE) for nonlinear optimization problems with inequality constraints is proposed. Since the new algorithm only needs to solve several systems of linear equations having a same coefficient matrix per iteration, the computation amount of the algorithm is much less than that of the existing SQP algorithms per iteration. Moreover, for the SQP type algorithms, there exist so-called inconsistent problems, i.e., quadratic programming subproblems of the SQP algorithms may not have a solution at some iterations, but this phenomenon will not occur with the SSLE algorithms because the related systems of linear equations always have solutions. Some numerical results are reported.     

Canonical duality for solving general nonconvex constrained problems

This paper presents a canonical duality theory for solving a general nonconvex constrained optimization problem within a unified framework to cover Lagrange multiplier method and KKT theory. It is proved that if both target function and constraints possess certain patterns necessary for modeling real systems, a perfect dual problem (without duality gap) can be obtained in a unified form with global optimality conditions provided.While the popular augmented Lagrangian method may produce more difficult nonconvex problems due to the nonlinearity of constraints. Some fundamental concepts such as the objectivity and Lagrangian in nonlinear programming are addressed.