A new infeasible interior-point algorithm with full step for linear optimization based on a simple function

In this paper, we design and analyse an infeasible interior-point algorithm based on a simple function for linear optimization. The infeasible algorithm contains two types of search directions: the feasibility search direction and the centrality search direction. Both of the directions are determined by the simple function. The algorithm uses full step, thus no need to perform the line-search procedure. Although the proposed function is simple, as it will be shown, the induced infeasible algorithm enjoys the best-known iteration complexity for infeasible interior-point algorithm.     

A corrector–predictor path-following method for second-order cone optimization

In this paper, we present a corrector–predictor path-following interior-point method for second-order cone optimization (SOCO) based on a new proximity measure. The algorithm produces a sequence of iterates in a neighbourhood of the central path based on a new proximity measure. We show that the algorithm is well-defined and derive the complexity bound for the algorithm. We obtain the best-known result for SOCO. The numerical results show that the proposed algorithm is effective.     

A full-step interior-point algorithm for second-order cone optimization based on a simple locally kernel function

In this paper, we investigate the properties of a simple locally kernel function. As an application, we present a full-step interior-point algorithm for second-order cone optimization (SOCO). The algorithm uses the simple locally kernel function to determine the search direction and define the neighbourhood of central path. The full step used in the algorithm has local quadratic convergence property according to the proximity function which is constructed by the simple locally kernel function. We derive the iteration complexity for the algorithm and obtain the best-known iteration bound for SOCO.     

Extension of a hybrid Genetic Algorithm for nonlinear programming problems with equality and inequality constraints

As an extension of the hybrid Genetic Algorithm-HGA proposed by Tang et al. (Comput. Math. Appl. 36 (1998) 11), this paper focuses on the critical techniques in the application of the GA to nonlinear programming (NLP) problems with equality and inequality constraints. Taking into account the equality constraints and embedding the information of infeasible points/chromosomes into the evaluation function, an extended fuzzy-based methodology and three new evaluation functions are proposed to formulate and evaluate the infeasible chromosomes. The extended version of concepts of dominated semi-feasible direction (DSFD), feasibility degree (FD₁) of semi-feasible direction, feasibility degree (FD₂) of infeasible points ‘belonging to’ feasible domain are introduced. Combining the new evaluation functions and weighted gradient direction search into the Genetic Algorithm, an extended hybrid Genetic Algorithm (EHGA) is developed to solve nonlinear programming (NLP) problems with equality and inequality constraints. Simulation shows that this new algorithm is efficient.Scope and purposeNon-linear Programming (NLP) problems with equality and inequality constraints is an important type of constrained optimization problems. Genetic Algorithm (GA) is one of the well known evolutionary computation techniques. In the application of GA to NLP problems, chromosomes randomly generated at the beginning and/or generated by genetic operators during the evolutionary process usually violate the constraints, resulting in infeasible chromosomes. Therefore, the handling of system constraints, particularly the nonlinear equation constraints, and the measurement and evaluation of infeasible chromosomes, are major concerns in GA. Penalty strategy in the construction of fitness function is commonly used to evaluate the infeasible chromosomes in some traditional AG methods. However, this approach essentially narrows down the search space by eliminating all infeasible chromosomes from the evolutionary process, and it may reduce the chances of finding better candidates for the global optimization. In particular, it absolutely ignores the information carried by the infeasible chromosomes itself. Therefore, formulating the infeasible chromosomes by embedding the relevant information into the evaluation function are important when applying GA to NLP.As an extension of the Hybrid Genetic Algorithm-HGA proposed by Tang et al. (1998), this paper focuses on the critical techniques in the application of GA to NLP problems with equality and inequality constraints. Taking into account the equality constraints and embedding the information of infeasible chromosomes into the evaluation function, an extended fuzzy-based methodology and three new evaluation functions are designed to formulate and evaluate the infeasible chromosomes. By introducing an extended version of the concepts of dominated semi-feasible direction (DSFD), feasibility degree (FD₁) of semi-feasible direction, feasibility degree (FD₂) of infeasible points ‘belonging to’ feasible domain, an extended hybrid Genetic Algorithm (EHGA) is developed for solving NLP problems with equality and inequality constraints.     

基于种群个体可行性的约束优化进化算法

提出一种新的求解约束优化问题的进化算法.该算法在处理约束时不引入惩罚因子,使约束处理问题简单化.基于种群中个体的可行性,分别采用3种不同的交叉方式和混合变异机制用于指导算法快速搜索过程.为了求解位于边界附近的全局最优解,引入一种不可行解保存和替换机制,允许一定比例的最好不可行解进入下一代种群.标准测试问题的实验结果表明了该算法的可行性和有效性.     

An interior-point sequential approximate optimization methodology

The use of optimization in a simulation-based design environment has become a common trend in industry today. Computer simulation tools are commonplace in many engineering disciplines, providing the designers with tools to evaluate a designs performance without building a physical prototype. This has triggered the development of optimization techniques suitable for dealing with such simulations. One of these approaches is known as sequential approximate optimization. In sequential approximate minimization a sequence of optimizations are performed over local response surface approximations of the system. This paper details the development of an interior-point approach for trust-region-managed sequential approximate optimization. The interior-point approach will ensure that approximate feasibility is maintained throughout the optimization process. This facilitates the delivery of a usable design at each iteration when subject to reduced design cycle time constraints. In order to deal with infeasible starting points, homotopy methods are used to relax constraints and push designs toward feasibility. Results of application studies are presented, illustrating the applicability of the proposed algorithm.     

一种新的约束优化遗传算法及其工程应用

提出一种新的用于求解约束优化问题的遗传算法,该算法利用佳点集方法初始化个体以维持种群的多样性.在进化过程中,通过可行解与不可行解算术交叉对问题的决策空间进行搜索;对可行种群与不可行种群分别采用高斯变异和柯西变异,从而协调算法的勘探和开采能力.几个标准测试问题的实验结果表明该算法的有效性;应用新算法求解两个工程优化设计问题,结果表明该算法的可行性.     

复杂流程工业系统的优化操作

ＳＱＰ方法在中小规模非线性规划中已成为主流算法,但在求解大规模优化问题时存在Ｈｅｓｓｉａｎ矩阵规模过大,存储、计算困难,以及计算量随不等式约束数量呈指数上升等缺点,简约空间ＳＱＰ法将变量分解为独立变量和非猖变量两部分。优化时只考虑独立变量,从而大大降低了变量维数,减小了Ｈｅｓｓｉａｎ矩阵规模。内点法、修改障碍函数法在求解不等式约束问题时都具有迭代次数几乎不受不等式约束规模影响的特点,因此可以将它们集成入简约空间ＳＱＰ法,使之可以更有效地对大规模优化问题求解。     

求解非线性规划问题的混合粒子群算法

用粒子群算法求解非线性规划问题时不可避免的会产生不可行点,处理好不可行点是粒子群算法取得良好优化结果的关键。依据粒子的目标函数值与违反约束的程度提出了一种处理不可行点的合理选择方案,并运用融合差分演化的混合粒子群算法求解约束优化问题,数值实验表明该算法的有效性。     

一种改进型动态无功优化模型及其求解算法

动态无功优化是提高电力系统运行经济性和安全性的重要措施。在动态无功优化常规模型的基础上,将同一节点的若干组电容器等效为1个集中变量,用对集中电容器组的约束代替常规的单组电容器约束,给出与之完全等效的电容器组动作次数约束值和投切方法;针对动态无功优化模型的非线性、大规模性、控制变量的离散性和连续性共存的难题,对用于离散非线性优化的蚁群算法作了充分研究,提出了内点法与蚁群算法相结合的动态无功优化混合算法。IEEE14测试系统的仿真结果验证了改进模型及算法的有效性和可行性。     

The inverse electromagnetic shaping problem

The inverse problem concerning electromagnetic casting of molten metals consists of looking for an electric current density distribution such that the induced electromagnetic field makes a given mass of liquid metal acquire a predefined shape. This problem is formulated here as an optimization problem where the positions of a finite set of inductors are the design variables. Two different formulations for this optimization problem for the two-dimensional case are proposed. The first one minimizes the difference between the target and the equilibrium shapes while the second approach minimizes the L ² norm of a fictitious surface pressure that makes the target shape to be in mechanical equilibrium. The optimization problems are solved using Feasible Arc Interior Point Algorithm, a line search interior-point algorithm for nonlinear optimization. Some examples are presented to show the effectiveness of the proposed approaches.     

FORCES NLP: an efficient implementation of interior-point methods for multistage nonlinear nonconvex programs

ABSTRACT

Real-time implementation of optimisation-based control and trajectory planning can be very challenging for nonlinear systems. As a result, if an implementation based on a fixed linearisation is not suitable, the nonlinear problems are typically locally approximated online, in order to leverage the speed and robustness of embedded solvers for convex quadratic programs (QP) developed during the last decade. The purpose of this paper is to demonstrate that, using simple standard building blocks from nonlinear programming, combined with a structure-exploiting linear system solver, it is possible to achieve computation times in the range typical of solvers for QPs, while retaining nonlinearities and solving the nonlinear programs (NLP) to local optimality. The implemented algorithm is an interior-point method with approximate Hessians and adaptive barrier rules, and is provided as an extension to the C code generator FORCES. Three detailed examples are provided that illustrate a significant improvement in control performance when solving NLPs, with computation times that are comparable with those achieved by fast approximate schemes and up to an order of magnitude faster than the state-of-the-art interior-point solver IPOPT.     

An improved critical constraint method for structural optimization of product families

This paper discusses important improvements in the efficient Critical Constraint Method (CCM) for the optimization of structural product families subjected to multiple crash load cases. The method was first presented by Öman and Nilsson (Struct Multidisc Optim 41(5):797–815, 2010). However, the algorithm often converged towards an infeasible solution, which considerably limited the applicability of the method. Therefore, improvements are presented here to make the method more robust regarding feasible solutions, resulting in only a minor decrease in efficiency compared to the original method. The improvements include; a penalty approach to control the feasibility of the method by continuously pushing the solution out of the infeasible region, a dynamic contraction algorithm to increase the accuracy and robustness of the method by considering the optimization progress and variable history in the reduction of the step size, and the implementation of a parallel approach to further increase the efficiency of the method by enabling the full potential of large-scale computer clusters. Finally, the potential of the improved CCM algorithm is demonstrated on a large-scale industrial family optimization problem and it is concluded that the high efficiency of the method enables the usage of large product family optimization in the design process.     

基于环境Pareto 支配选择策略的有约束多目标差分进化算法

在处理有约束多目标问题的进化算法中, 目前普遍采用Deb 教授提出的约束占优的直接支配选择策略. 在约束处理中, 优秀不可行解与优秀可行解同样重要, 但在直接支配选择策略中, 不可行解被选择的几率很小. 针对此问题, 设计一种环境Pareto 支配的选择策略, 并基于此提出用于解决有约束多目标问题的差分进化算法. 对经典测试函数进行仿真计算, 结果表明, 与其他算法相比, 所提出的算法具有更高的收敛性和稳定性.

     

An angle based evolutionary algorithm with infeasibility information for constrained many-objective optimization

Recently, angle-based approaches have shown promising for unconstrained many-objective optimization problems (MaOPs), but few of them are extended to solve constrained MaOPs (CMaOPs). Moreover, due to the difficulty in searching for feasible solutions in high-dimensional objective space, the use of infeasible solutions comes to be more important in solving CMaOPs. In this paper, an angle based evolutionary algorithm with infeasibility information is proposed for constrained many-objective optimization, where different kinds of infeasible solutions are utilized in environmental selection and mating selection. To be specific, an angle-based constrained dominance relation is proposed for non-dominated sorting, which gives infeasible solutions with good diversity the same priority to feasible solutions for escaping from the locally feasible regions. As for diversity maintenance, an angle-based density estimation is developed to give the infeasible solutions with good convergence a chance to survive for next generation, which is helpful to get across the large infeasible barrier. In addition, in order to utilize the potential of infeasible solutions in creating high-quality offspring, a modified mating selection is designed by considering the convergence, diversity and feasibility of solutions simultaneously. Experimental results on two constrained many-objective optimization test suites demonstrate the competitiveness of the proposed algorithm in comparison with five existing constrained many-objective evolutionary algorithms for CMaOPs. Moreover, the effectiveness of the proposed algorithm on a real-world problem is showcased.     

Dynamic stopping criteria for search-based test data generation for path testing

ContextEvolutionary algorithms have proved to be successful for generating test data for path coverage testing. However in this approach, the set of target paths to be covered may include some that are infeasible. It is impossible to find test data to cover those paths. Rather than searching indefinitely, or until a fixed limit of generations is reached, it would be desirable to stop searching as soon it seems likely that feasible paths have been covered and all remaining un-covered target paths are infeasible.ObjectiveThe objective is to develop criteria to halt the evolutionary test data generation process as soon as it seems not worth continuing, without compromising testing confidence level.MethodDrawing on software reliability growth models as an analogy, this paper proposes and evaluates a method for determining when it is no longer worthwhile to continue searching for test data to cover un-covered target paths. We outline the method, its key parameters, and how it can be used as the basis for different decision rules for early termination of a search. Twenty-one test programs from the SBSE path testing literature are used to evaluate the method.ResultsCompared to searching for a standard number of generations, an average of 30–75% of total computation was avoided in test programs with infeasible paths, and no feasible paths were missed due to early termination. The extra computation in programs with no infeasible paths was negligible.ConclusionsThe method is effective and efficient. It avoids the need to specify a limit on the number of generations for searching. It can help to overcome problems caused by infeasible paths in search-based test data generation for path testing.     

Controlling selection areas of useful infeasible solutions for directed mating in evolutionary constrained multi-objective optimization

As an evolutionary approach to solve constrained multi-objective optimization problems (CMOPs), recently an algorithm using the two-stage non-dominated sorting and the directed mating (TNSDM) was proposed. In TNSDM, the directed mating utilizes infeasible solutions dominating feasible solutions in the objective space to generate offspring. The directed mating significantly contributes to the search performance improvement in evolutionary constrained multi-objective optimization. However, the conventional directed mating has two problems. First, since the conventional directed mating selects a pair of parents based on the conventional Pareto dominance, two parents having different search directions may be mated. Second, the directed mating cannot be performed in some cases especially when the population has few useful infeasible solutions. In this case, the conventional mating using only feasible solutions is performed instead. Thus, the effectiveness of the directed mating cannot always be achieved depending on the number of useful infeasible solutions. To overcome these problems and further enhance the effect of the directed mating in TNSDM, in this work we propose a method to control the selection area of useful infeasible solutions by controlling dominance area of solutions (CDAS). We verify the effectiveness of the proposed method in TNSDM, and compare its search performance with the conventional CNSGA-II on discrete m-objective k-knapsack problems and continuous mCDTLZ problems. The experimental results show that the search performance of TNSDM is further improved by controlling the selection area of useful infeasible solutions in the directed mating.     

Inductor shape optimization for electromagnetic casting

The design of inductors in electromagnetic shaping of molten metals consists in looking for the position and the shape of a set of electric wires such that the induced electromagnetic field makes a given mass of liquid metal acquire a predefined shape. In this paper we formulate an inverse optimization problem where the position and shape of the inductors are defined by a set of design variables. In a first formulation of the inverse optimization problem we minimize the difference between the target and the equilibrium shapes while in a second approach we minimize the L ² norm of a fictitious surface pressure that makes the target shape to be in mechanical equilibrium. Geometric constraints that prevent the inductors from penetrating the liquid metal are considered in both formulations. The optimization problems are solved using FAIPA, a line search interior-point algorithm for nonlinear optimization. Some examples are presented to show the effectiveness of the proposed approaches.     

A programming approach for nonsmooth structural optimization

A two-level programming algorithm for some nonsmooth structural optimization problems is presented. When an optimization problem has both stress and unilateral displacement constraints, we combine the structural optimization with unilateral analysis to formulate a two-level model. Quadratic programming (QP) is used in analysis level, which is solved with dual interior-point method, and linear programming (LP) is used in optimization level. Several examples with unilateral or bilateral constraints are provided to verify the proposed algorithm.     

基于变量转换的并行优化算法

针对大规模边界约束优化问题,现有并行变量转换(PVT)算法不适于直接求解。基于此,采用内点法和逐步下降的思想,提出一个并行求解边界约束最优化问题的可行算法。在下降方向满足梯度相关、步长满足Goldstein规则的条件下,证明该算法的收敛性。当约束失效时,该算法退化为求解无约束的PVT算法,从而成为原有算法向约束优化问题的一个推广。