Smoothed penalty algorithms for optimization of nonlinear models

We introduce an algorithm for solving nonlinear optimization problems with general equality and box constraints. The proposed algorithm is based on smoothing of the exact l ₁-penalty function and solving the resulting problem by any box-constraint optimization method. We introduce a general algorithm and present theoretical results for updating the penalty and smoothing parameter. We apply the algorithm to optimization problems for nonlinear traffic network models and report on numerical results for a variety of network problems and different solvers for the subproblems.     

A Computational Study of the Homogeneous Algorithm for Large-scale Convex Optimization

Recently the authors have proposed a homogeneous and self-dual algorithm for solving the monotone complementarity problem (MCP) [5]. The algorithm is a single phase interior-point type method; nevertheless, it yields either an approximate optimal solution or detects a possible infeasibility of the problem. In this paper we specialize the algorithm to the solution of general smooth convex optimization problems, which also possess nonlinear inequality constraints and free variables. We discuss an implementation of the algorithm for large-scale sparse convex optimization. Moreover, we present computational results for solving quadratically constrained quadratic programming and geometric programming problems, where some of the problems contain more than 100,000 constraints and variables. The results indicate that the proposed algorithm is also practically efficient.     

Nonlinear goal programming using multi-objective genetic algorithms

Goal programming is a technique often used in engineering design activities primarily to find a compromised solution which will simultaneously satisfy a number of design goals. In solving goal programming problems, classical methods reduce the multiple goal-attainment problem into a single objective of minimizing a weighted sum of deviations from goals. This procedure has a number of known difficulties. First, the obtained solution to the goal programming problem is sensitive to the chosen weight vector. Second, the conversion to a single-objective optimization problem involves additional constraints. Third, since most real-world goal programming problems involve nonlinear criterion functions, the resulting single-objective optimization problem becomes a nonlinear programming problem, which is difficult to solve using classical optimization methods. In tackling nonlinear goal programming problems, although successive linearization techniques have been suggested, they are found to be sensitive to the chosen starting solution. In this paper, we pose the goal programming problem as a multi-objective optimization problem of minimizing deviations from individual goals and then suggest an evolutionary optimization algorithm to find multiple Pareto-optimal solutions of the resulting multi-objective optimization problem. The proposed approach alleviates all the above difficulties. It does not need any weight vector. It eliminates the need of having extra constraints needed with the classical formulations. The proposed approach is also suitable for solving goal programming problems having nonlinear criterion functions and having a non-convex trade-off region. The efficacy of the proposed approach is demonstrated by solving a number of nonlinear goal programming test problems and an engineering design problem. In all problems, multiple solutions (each corresponding to a different weight vector) to the goal programming problem are found in one single simulation run. The results suggest that the proposed approach is an effective and practical tool for solving real-world goal programming problems.     

Column enumeration based decomposition techniques for a class of non-convex MINLP problems

We propose a decomposition algorithm for a special class of nonconvex mixed integer nonlinear programming problems which have an assignment constraint. If the assignment decisions are decoupled from the remaining constraints of the optimization problem, we propose to use a column enumeration approach. The master problem is a partitioning problem whose objective function coefficients are computed via subproblems. These problems can be linear, mixed integer linear, (non-)convex nonlinear, or mixed integer nonlinear. However, the important property of the subproblems is that we can compute their exact global optimum quickly. The proposed technique will be illustrated solving a cutting problem with optimum nonlinear programming subproblems.     

Nonlinear Lagrangians for Nonlinear Programming Based on Modified Fischer-Burmeister NCP Functions

This paper proposes nonlinear Lagrangians based on modified Fischer-Burmeister NCP functions for solving nonlinear programming problems with inequality constraints. The convergence theorem shows that the sequence of points generated by this nonlinear Lagrange algorithm is locally convergent when the penalty parameter is less than a threshold under a set of suitable conditions on problem functions, and the error bound of solution, depending on the penalty parameter, is also established. It is shown that the condition number of the nonlinear Lagrangian Hessian at the optimal solution is proportional to the controlling penalty parameter. Moreover, the paper develops the dual algorithm associated with the proposed nonlinear Lagrangians. Numerical results reported suggest that the dual algorithm based on proposed nonlinear Lagrangians is effective for solving some nonlinear optimization problems.     

Handling equality constraints in evolutionary optimization

Over the last few decades several methods have been proposed for handling functional constraints while solving optimization problems using evolutionary algorithms (EAs). However, the presence of equality constraints makes the feasible space very small compared to the entire search space. As a consequence, the handling of equality constraints has long been a difficult issue for evolutionary optimization methods. This paper presents a Hybrid Evolutionary Algorithm (HEA) for solving optimization problems with both equality and inequality constraints. In HEA, we propose a new local search technique with special emphasis on equality constraints. The basic concept of the new technique is to reach a point on the equality constraint from the current position of an individual solution, and then explore on the constraint landscape. We believe this new concept will influence the future research direction for constrained optimization using population based algorithms. The proposed algorithm is tested on a set of standard benchmark problems. The results show that the proposed technique works very well on those benchmark problems.     

A smoothing SQP method for nonlinear programs with?stability constraints arising from power systems

This paper investigates a new class of optimization problems arising from power systems, known as nonlinear programs with stability constraints (NPSC), which is an extension of ordinary nonlinear programs. Since the stability constraint is described generally by eigenvalues or norm of Jacobian matrices of systems, this results in the semismooth property of NPSC problems. The optimal conditions of both NPSC and its smoothing problem are studied. A smoothing SQP algorithm is proposed for solving such optimization problem. The global convergence of algorithm is established. A numerical example from optimal power flow (OPF) is done. The computational results show efficiency of the new model and algorithm.     

线性比式和规划问题的输出空间分支定界算法

本文旨在针对线性比式和规划这一NP-Hard非线性规划问题提出新的全局优化算法.首先,通过引入p个辅助变量把原问题等价的转化为一个非线性规划问题,这个非线性规划问题的目标函数是乘积和的形式并给原问题增加了p个新的非线性约束,再通过构造凸凹包络的技巧对等价问题的目标函数和约束条件进行相应的线性放缩,构成等价问题的一个下界线性松弛规划问题,从而提出了一个求解原问题的分支定界算法,并证明了算法的收敛性.最后,通过数值结果比较表明所提出的算法是可行有效的.     

A real coded genetic algorithm for solving integer and mixed integer optimization problems

In this paper, a real coded genetic algorithm named MI-LXPM is proposed for solving integer and mixed integer constrained optimization problems. The proposed algorithm is a suitably modified and extended version of the real coded genetic algorithm, LXPM, of Deep and Thakur [K. Deep, M. Thakur, A new crossover operator for real coded genetic algorithms, Applied Mathematics and Computation 188 (2007) 895-912; K. Deep, M. Thakur, A new mutation operator for real coded genetic algorithms, Applied Mathematics and Computation 193 (2007) 211-230]. The algorithm incorporates a special truncation procedure to handle integer restrictions on decision variables along with a parameter free penalty approach for handling constraints. Performance of the algorithm is tested on a set of twenty test problems selected from different sources in literature, and compared with the performance of an earlier application of genetic algorithm and also with random search based algorithm, RST2ANU, incorporating annealing concept. The proposed MI-LXPM outperforms both the algorithms in most of the cases which are considered.     

A nonlinear programming approach to a very large hydroelectric system optimization

A large scale hydroelectric system optimization is considered and solved by using a non-linear programming method. The largest numerical case involves approximately 6 000 variables, 4 000 linear equations, 11 000 linear and nonlinear inequality constraints and a nonlinear objective function. The solution method is based on

1. partial elimination of independent variables by solving linear equations,
2. essentially unconstrained optimization of a compound function that consists of the objective function, nonlinear inequality constraints and part of the linear inequality constraints. The compound function is obtained via penalty formulation.

The algorithm takes full advantage of the problem's structure and provides useful solutions for real life problems that, in general, are defined over empty feasible regions.     

A sub-feasible correction step for non-linear programming methods with equality constraints

Due to the sparsity of large–scale optimazation problems it can be useful to use the exact hessian matrix instead of update techniques for solving nonlinear optimization problems. Herewith it is possible to use techniques of the parametric sensitivity analysis to improve the feasibility of the NLP–problem in each iteration step of a solver. The main idea is to treat the measurable error between the general nonlinear equality constraints and the linear approximations inside the QP subproblems as a linear perturbation in the constraints. By special real–time optimization approximations this error can be reduced nearly without any extra computational costs. First results will be presented. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

求解非线性规划问题的两个微分方程系统

本文给出Evtushenko与Zhadan（1974）提出的求解数学规划问题微分方程系统的两个校正形式,它们可用于求解具有等式和不等式约束的非线性规化问题。第一个校正系统拓宽了Evtushenko与Zhadan微分方程方法;第二个校正系统通过引入新的方程系统导出乘子函数得到,它无需使用Evtushenko与Zhadan所用的那样强的约束规范。我们建立了这两个微分方程方法及其离散迭代方法的收敛性定理,给出了基于第二个微分方程离散格式的数值算法及其某些数值结果。     

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.     

求解约束优化问题的一个对偶算法

１．引言 考虑下述形式的不等式约束优化问题：其中 ＝０,１,…,ｍ,是连续可微函数．求解（１．１）的数值方法有很多,传统方法有乘子法,序列一次规划方法,等等（见 Ｂｅｒｔｓｅｋａｓ（１９８２）, Ｈａｎ（１９７６, １９７７））．近年来对求解（１．１）的原始－对偶算法的研究已成为非线性规划领域的新的热点,如ＥＩ－Ｂａｋｒｙ,Ｔａｐｉａ,Ｔｓｕｃｈｉｙａ　＆　Ｚｈａｎｇ（１９９６）,Ｙａｍａｓｈｉｔａ（１９９２,１９９６,１９９７）等;尽管这些原始－对偶算法具有好的收敛性质和计算效果,但其算法结构相对…     

Scatter search for chemical and bio-process optimization

Scatter search is a population-based method that has recently been shown to yield promising outcomes for solving combinatorial and nonlinear optimization problems. Based on formulations originally proposed in 1960s for combining decision rules and problem constraints such as the surrogate constraint method, scatter search uses strategies for combining solution vectors that have proved effective in a variety of problem settings. In this paper, we develop a general purpose heuristic for a class of nonlinear optimization problems. The procedure is based on the scatter search methodology and treats the objective function evaluation as a black box, making the search algorithm context-independent. Most optimization problems in the chemical and bio-chemical industries are highly nonlinear in either the objective function or the constraints. Moreover, they usually present differential-algebraic systems of constraints. In this type of problem, the evaluation of a solution or even the feasibility test of a set of values for the decision variables is a time-consuming operation. In this context, the solution method is limited to a reduced number of solution examinations. We have implemented a scatter search procedure in Matlab (Mathworks, 2004) for this special class of difficult optimization problems. Our development goes beyond a simple exercise of applying scatter search to this class of problems, but presents innovative mechanisms to obtain a good balance between intensification and diversification in a short-term search horizon. Computational comparisons with other recent methods over a set of benchmark problems favor the proposed procedure.     

Omni-optimizer: A generic evolutionary algorithm for single and multi-objective optimization

Due to the vagaries of optimization problems encountered in practice, users resort to different algorithms for solving different optimization problems. In this paper, we suggest and evaluate an optimization procedure which specializes in solving a wide variety of optimization problems. The proposed algorithm is designed as a generic multi-objective, multi-optima optimizer. Care has been taken while designing the algorithm such that it automatically degenerates to efficient algorithms for solving other simpler optimization problems, such as single-objective uni-optimal problems, single-objective multi-optima problems and multi-objective uni-optimal problems. The efficacy of the proposed algorithm in solving various problems is demonstrated on a number of test problems chosen from the literature. Because of its efficiency in handling different types of problems with equal ease, this algorithm should find increasing use in real-world optimization problems.     

Handling equality constraints with agent-based memetic algorithms

In addition to inequality constraints, many mathematical models require equality constraints to represent the practical problems appropriately. The existence of equality constraints reduces the size of the feasible space significantly, which makes it difficult to locate feasible and optimal solutions. This paper presents a new equality constraint handling technique which enhances the performance of an agent-based evolutionary algorithm in solving constrained optimization problems with equality constraints. The technique is basically used as an agent learning process in the agent-based evolutionary algorithm. The performance of the proposed algorithm is tested on a set of well-known benchmark problems including seven new problems. The experimental results confirm the improved performance of the proposed technique.     

Multiple reduced gradient method for multiobjective optimization problems

Multiobjective optimization has a large number of real-life applications. Under this motivation, in this paper, we present a new method for solving multiobjective optimization problems with both linear constraints and bound constraints on the variables. This method extends, to the multiobjective setting, the classical reduced gradient method for scalar-valued optimization. The proposed algorithm generates a feasible descent direction by solving an appropriate quadratic subproblem, without the use of any scalarization approaches. We prove that the sequence generated by the algorithm converges to Pareto-critical points of the problem. We also present some numerical results to show the efficiency of the proposed method.     

An algorithm for solving global optimization problems with nonlinear constraints

In this paper we propose an algorithm using only the values of the objective function and constraints for solving one-dimensional global optimization problems where both the objective function and constraints are Lipschitzean and nonlinear. The constrained problem is reduced to an unconstrained one by the index scheme. To solve the reduced problem a new method with local tuning on the behavior of the objective function and constraints over different sectors of the search region is proposed. Sufficient conditions of global convergence are established. We also present results of some numerical experiments.     

An interior affine scaling projective algorithm for nonlinear equality and linear inequality constrained optimization

In this paper, we propose a new nonmonotonic interior point backtracking strategy to modify the reduced projective affine scaling trust region algorithm for solving optimization subject to nonlinear equality and linear inequality constraints. The general full trust region subproblem for solving the nonlinear equality and linear inequality constrained optimization is decomposed to a pair of trust region subproblems in horizontal and vertical subspaces of linearize equality constraints and extended affine scaling equality constraints. The horizontal subproblem in the proposed algorithm is defined by minimizing a quadratic projective reduced Hessian function subject only to an ellipsoidal trust region constraint in a null subspace of the tangential space, while the vertical subproblem is also defined by the least squares subproblem subject only to an ellipsoidal trust region constraint. By introducing the Fletcher's penalty function as the merit function, trust region strategy with interior point backtracking technique will switch to strictly feasible interior point step generated by a component direction of the two trust region subproblems. The global convergence of the proposed algorithm while maintaining fast local convergence rate of the proposed algorithm are established under some reasonable conditions. A nonmonotonic criterion should bring about speeding up the convergence progress in some high nonlinear function conditioned cases.