Explicit model of dual programming and solving method for a class of separable convex programming problems

An objective function for a dual model of nonlinear programming problems is an implicit function with respect to Lagrangian multipliers. This study aims to address separable convex programming problems. An explicit expression with respect to Lagrangian multipliers is derived for the dual objective function. The exact solution of the dual model can be achieved because an explicit objective function is more exact than an approximated objective function. Then, a set of improved Lagrangian multipliers can be used to obtain the optimal solution of the original nonlinear programming model. A corresponding dual programming and explicit model (DP-EM) method is proposed and applied to the structural topology optimization of continuum structures. The solution efficiency of the DPEM is compared with the dual sequential quadratic programming (DSQP) method and method of moving asymptotes (MMA). The results show that the DP-EM method is more efficient than the DSQP and MMA.     

Tetrahedral mesh generation in polyhedral regions based on convex polyhedron decompositions

A method using techniques of computational geometry for generating tetrahedral finite element meshes in three-dimensional polyhedral regions is presented. The input to the method consists of the boundary faces of the polyhedral region and possibly internal and hole interfaces, plus the desired number of tetrahedra and other scalar parameters. The region is decomposed into convex polyhedra in two stages so that tetrahedra of one length scale can be generated in each subregion. A mesh distribution function, which is either automatically constructed from the first-stage convex polyhedron decomposition or supplied by the user, is used to determine the tetrahedron sizes in the subregions. Then a boundary-constrained triangulation is constructed in each convex polyhedron, with local transformations being used to improve the quality of the tetrahedra. Experimental results from triangulations of three regions are provided.     

Solving Pseudo-Convex Mixed Integer Optimization Problems by Cutting Plane Techniques

In the present paper a cutting plane approach to solve mixed-integer non-linear programming (MINLP) problems, containing pseudo-convex functions, is given. It is shown how valid cutting planes for pseudo convex functions can be obtained and, furthermore, it is shown how a class of non-convex MINLP problems with a pseudo-convex objective function and pseudo-convex constraints, can be solved to global optimality with the considered cutting plane technique. Finally the numerical efficiency of the procedure, when solving some example problems, is illustrated.     

Finding multiple optimal solutions of signomial discrete programming problems with free variables

With the increasing reliance on mathematical programming based approaches in various fields, signomial discrete programming (SDP) problems occur frequently in real applications. Since free variables are often introduced to model problems and alternative optima are practical for decision making among multiple strategies, this paper proposes a generalized method to find multiple optimal solutions of SDP problems with free variables. By means of variable substitution and convexification strategies, an SDP problem with free variables is first converted into another convex mixed-integer nonlinear programming problem solvable to obtain an exactly global optimum. Then a general cut is utilized to exclude the previous solution and an algorithm is developed to locate all alternative optimal solutions. Finally, several illustrative examples are presented to demonstrate the effectiveness of the proposed approach.     

A new trust region–sequential quadratic programming approach for nonlinear systems based on nonlinear model predictive control

In this article, a superlinearly convergent trust region–sequential quadratic programming approach is first proposed, developed and investigated for nonlinear systems based on nonlinear model predictive control. The method incorporates a combination algorithm that allows both the trust region technique and the sequential quadratic programming method to be used. If the attempted search of the trust region method is not accepted, the line search rule will be adopted for the next iteration. Also, having to resolve the quadratic programming subproblem for nonlinear constrained optimization problems is avoided. This gives the potential for fast convergence in the neighbourhood of an optimal solution. Moreover, additional characteristics of the algorithm are that each quadratic programming subproblem is regularized and the quadratic programming subproblem always has a consistent point. The main result is illustrated on a nonlinear system with a variable parameter and a bipedal walking robot system through simulations and is utilized to achieve rapidly stability. Numerical results show that the trust region–sequential quadratic programming algorithm is feasible and effective for a nonlinear system with a variable parameter and a bipedal walking robot system. Therefore, the simulation results demonstrate the usefulness of the trust region–sequential quadratic programming approach with nonlinear model predictive control for real-time control systems.     

带非凸二次约束的二次规划问题的全局优化方法

利用二次函数的线形下界函数对带有非凸二次约束的二次规划(QP)提出一种新的求其全局最优解的分支定界算法.为改进算法的收敛性,根据问题的最优性和可行性提出一新的区域剪枝准则以排除(QP)的可行域中不存在全局解的部分.数值算例表明该准则能有效地加速算法的收敛性.     

Triangular meshes for regions of complicated shape

A method using techniques of computational geometry for triangular mesh generation for regions with complicated polygonal boundaries in the plane is presented. The input to the method includes the desired number of triangles and a mesh smoothness parameter to be specified, as well as the polygonal curves of the region's boundary and, possibly, internal interfaces. The triangulation generated conforms to the length scales of the edges of the boundary curves, but the method can be extended to provide additional control of the triangulation by a mesh distribution function. The region is decomposed into convex subregions in two stages, such that triangles of one length scale can be generated in each subregion. This decomposition uses algorithms which run in times that are linear in the number of vertices of the input polygons. Details of two major computational experiments are provided.     

Solving personnel tour scheduling problems using the dual all-integer cutting plane

Personnel tour scheduling problems are highly relevant to service organizations and have recently received considerable attention in both theory and practice. The inherent complexity of generalized set-covering formulations (GSCFs) of personnel tour scheduling problems has often resulted in the deployment of LP-based and local-search heuristic procedures, even for relatively small problems. This paper evaluates the performance of the dual all-integer cutting plane for solving such problems. A computational study revealed that the cutting plane, enhanced by an LP objective cut and sophisticated source row selection rule, substantially outperformed a commercial branch and bound code across four sets of test problems. The study also showed that an advanced starting solution based on the LP relaxation of the GSCF generally provided more rapid convergence of the algorithm.     

A new mathematical model for the Weber location problem with a probabilistic polyhedral barrier

With the wide application of location theory in a variety of industries, the presence of barriers ?merits the attention of managers and engineers.? In this paper, we assess the Weber location problem in the presence of a polyhedral barrier which probabilistically occurs on a given horizontal barrier route in the rectilinear space. A left triangular distribution function is used for the starting point of the barrier and therefore an expected rectilinear barrier distance function is formulated. In addition, a modification of the polyhedral barrier is presented which is equivalent to the original problem. Therefore, a mixed integer nonlinear programming model, which has a nonconvex solution space, is presented. Furthermore, by decomposing the feasible space into a finite number of convex solution spaces, an exact heuristic solution method is proposed. Then, a lower bound problem based on the forbidden region is applied. Some theorems and an example are reported.     

A Combined Convex Approximation—Interior Point Approach for Large Scale Nonlinear Programming

The method of moving asymptotes (MMA) and its globally convergent extension SCP (sequential convex programming) are known to work well in the context of structural optimization. The two main reasons are that the approximation scheme used for the objective function and the constraints fits very well to these applications and that at an iteration point a local optimization model is used such that additional expensive function and gradient evaluations of the original problem are avoided. The subproblems that occur in both methods are special nonlinear convex programs and have traditionally been solved using a dual approach. This is now replaced by an interior point approach. The latter one is more suitable for large problems because sparsity properties of the original problem can be preserved and the separability property of the approximation functions is exploited. The effectiveness of the new method is demonstrated by a few examples dealing with problems of structural optimization.     

Direct Search Methods for Nonlinearly Constrained Optimization Using Filters and Frames

A direct search method for nonlinear optimization problems with nonlinear inequality constraints is presented. A filter based approach is used, which allows infeasible starting points. The constraints are assumed to be continuously differentiable, and approximations to the constraint gradients are used. For simplicity it is assumed that the active constraint normals are linearly independent at all points of interest on the boundary of the feasible region. An infinite sequence of iterates is generated, some of which are surrounded by sets of points called bent frames. An infinite subsequence of these iterates is identified, and its convergence properties are studied by applying Clarke's non-smooth calculus to the bent frames. It is shown that each cluster point of this subsequence is a Karush-Kuhn-Tucker point of the optimization problem under mild conditions which include strict differentiability of the objective function at each cluster point. This permits the objective function to be non-smooth, infinite, or undefined away from these cluster points. When the objective function is only locally Lipschitz at these cluster points it is shown that certain directions still have interesting properties at these cluster points.     

Structural reliability assessment by salp swarm algorithm–based FORM

The first-order reliability method (FORM) is well recognized as an efficient approach for reliability analysis. Rooted in considering the reliability problem as a constrained optimization of a function, the traditional FORM makes use of gradient-based optimization techniques to solve it. However, the gradient-based optimization techniques may result in local convergence or even divergence for the highly nonlinear or high-dimensional performance function. In this paper, a hybrid method combining the Salp Swarm Algorithm (SSA) and FORM is presented. In the proposed method, a Lagrangian objective function is constructed by the exterior penalty function method to facilitate meta-heuristic optimization strategies. Then, SSA with strong global optimization ability for highly nonlinear and high-dimensional problems is utilized to solve the Lagrangian objective function. In this regard, the proposed SSA-FORM is able to overcome the limitations of FORM including local convergence and divergence. Finally, the accuracy and efficiency of the proposed SSA-FORM are compared with two gradient-based FORMs and several heuristic-based FORMs through eight numerical examples. The results show that the proposed SSA-FORM can be generally applied for reliability analysis involving low-dimensional, high-dimensional, and implicit performance functions.     

有间隙多层板接触分析的广义协调元法

从有间隙多层板接触系统分区广义势能泛函出发,以广义协调理论为基础,通过建立和分析板单元区、接触单元区的势能泛函,提出求解多层板接触问题的广义协调元法;并构造了广义协调矩形板-板接触单元PZC21。数值结果表明,单元PZC21具有较好的稳定性和收敛性。     

Automatic quadrilateral/triangular free-form mesh generation for planar regions

Automation of finite element mesh generation holds great benefits for mechanical product development and analysis. In addition to freeing engineers from mundane tasks, automation of mesh generation reduces product cycle design and eliminates human-related errors. Most of the existing mesh generation methods are either semi-automatic or require specific topological information. A fully automatic free-form mesh generation method is described in this paper to alleviate some of these problems. The method is capable of meshing singly or multiply connected convex/concave planar regions. These regions can be viewed as crosssectional areas of 2 1/2 D objects analysed as plane stress, plane strain or axisymmetric stress problems. In addition to being fully automatic, the method produces quadrilateral or triangular elements with aspect rations near one. Moreover, it does not require any topological constraints on the regions to be meshed; i.e. it provides free-form mesh generation. The input to the method includes the region's boundary curves, the element size and the mesh grading information. The method begins by decomposing the planar region to be meshed into convex subregions. Each subregion is meshed by first generating nodes on its boundaries using the input element size. The boundary nodes are then offset to mesh the subregion. The resulting meshes are merged together to form the final mesh. The paper describes the method in detail, algorithms developed to implement it and sample numerical examples. Results on parametric studies of the method performance are also discussed.     

基于区间法的发动机曲轴不确定性优化研究

该文基于非线性区间数规划方法和区间分析方法,针对某型发动机曲轴的不确定性优化问题进行了研究。载荷中的不确定参数采用区间描述,极限工况下的最大等效应力作为目标函数且通过有限元方法求解。非线性区间数规划方法用以处理不确定目标函数,区间分析方法用以快速求解目标函数在每一个设计矢量下的区间,隔代映射遗传算法作为优化求解器。应用算例说明了该文算法的有效性。     

求符号几何规划全局解的新方法

符号几何规划(SGP)问题经常出现在工程设计和管理中。本文利用目标函数和约束函数的线性下界估计,提出一种求(SGP)问题全局解的线性松弛方法。与凸松弛方法相比,本文方法在计算上更加简单和容易,且在产生线性松弛的过程中没有引入新的变量和约束。数值例子表明所给方法是可行和有效的。     

Load Allocation Research in a Manufacturing System

Based on queuing theory, a nonlinear optimization model is proposed in this paper, which has the service load as its objective function and includes three inequality constraints of Work In Progress （WIP）. A novel transformation of optimization variables is also devised and the constraints are properly combined so as to make this model into a convex one from which the Lagrangian function and the Karurh Kuhn Tucker （KKT） conditions are derived. The interior-point method for convex optimization is presented here as a computationaUy efficient tool. Finally, this model is evaluated on a real example, from which such conclusions are reached that the optimum result can ensure the full utilization of machines and the least amount of WIP in manufacturing systems; the interior-point method needs fewer iterations with significant computational savings and it is possible to make nonlinear and complicated optimization problems convexified so as to obtain the optimum.     

THE HOUSEHOLDER TRIDIAGONALIZATION STRATEGY FOR SOLVING A CONSTRAINED QUADRATIC MINIMIZATION PROBLEM

This paper presents an enhanced version of the dual response optimization algorithm, DR2, for constrained quadratic programs where the goal is to minimize the quadratic objective function subject to a quadratic equality constraint while the search is bounded inside an ellipsoidal region. In the first part of the study, several computational experiments of DR2 against an implementation of sequential quadratic programming, MINOS, are conducted via simulations. The computational results show that DR2 is more effective at locating optimal operating conditions than MINOS for the constrained quadratic programming problems aforementioned. Subsequently, a computation strategy is proposed that utilizes the Householder tridiagonalization procedure (prior to performing the Cholesky factorization for a clever implementation of the Newton method) while solving the trust-region (TR) subproblems on which the main body of DR2 is primarily based. In the final section, this more advanced algorithm is compared to the elementary implementation of DR2 and exhibits faster convergence in solving larger problems     

Upper bound shakedown analysis with the nodal natural element method

In this paper, a novel numerical solution procedure is developed for the upper bound shakedown analysis of elastic-perfectly plastic structures. The nodal natural element method (nodal-NEM) combines the advantages of the NEM and the stabilized conforming nodal integration scheme, and is used to discretize the established mathematical programming formulation of upper bound shakedown analysis based on Koiter’s theorem. In this formulation, the displacement field is approximated by using the Sibson interpolation and the difficulty caused by the time integration is solved by König’s technique. Meanwhile, the nonlinear and non-differentiable characteristic of objective function is overcome by distinguishing non-plastic areas from plastic areas and modifying associated constraint conditions and goal function at each iteration step. Finally, the objective function subjected to several equality constraints is linearized and the upper bound shakedown load multiplier is obtained. This direct iterative process can ensure the shakedown load to monotonically converge to the upper bound of true solution. Several typical numerical examples confirm the efficiency and accuracy of the proposed method.     

A tree-search method for solving a cutting stock assignment problem

Many production environments such as carpet or flat glass manufacturing have linked operations that perform completely different activities. In this paper, we consider a two-stage manufacturing process involving a cutting operation, followed by an assignment operation. Raw material is cut to meet product demand with minimum trim loss, and assignments are made to minimize resource requirements. This cutting stock assignment problem is formulated as a large-scale, mixed-integer nonlinear programming problem. We propose a solution methodology based on decomposition and tree search heuristic strategies. We report on extensive computational experiments on a wide range of problems, and apply statistical techniques to determine significant factors. For all small-size problems tested, our method found the exact optimal solution. For practical-size problems, our method was about two orders of magnitude faster and produced solutions that were one-third better than tabu search.