A double-multiplicative dynamic penalty approach for constrained evolutionary optimization

The present paper proposes a double-multiplicative penalty strategy for constrained optimization by means of genetic algorithms (GAs). The aim of this research is to provide a simple and efficient way of handling constrained optimization problems in the GA framework without the need for tuning the values of penalty factors for any given optimization problem. After a short review on the most popular and effective exterior penalty formulations, the proposed penalty strategy is presented and tested on five different benchmark problems. The obtained results are compared with the best solutions provided in the literature, showing the effectiveness of the proposed approach.     

Discrete Walsh operational matrices for analysis and optimal control of linear digital systems

By the introduction of the shift transformation matrix, direct product matrix and summation matrix of the discrete Walsh series, the analysis of time-varying digital control systems is facilitated and the approximate solution of time-invariant digital optimal control problems is achieved of this study. The design algorithms of digital optimal control are based on the discrete variational principle combined with the idea of penalty functions to obtain the conveniently computational formulations for evaluating the optimal control and trajectory. Three examples are illustrated by using the discrete Walsh approach.     

Constraint partitioning in penalty formulations for solving temporal planning problems

In this paper, we study the partitioning of constraints in temporal planning problems formulated as mixed-integer nonlinear programming (MINLP) problems. Constraint partitioning is attractive because it leads to much easier subproblems, where each is a significant relaxation of the original problem. Moreover, each subproblem is very similar to the original problem and can be solved by any existing solver with little or no modification. Constraint partitioning, however, introduces global constraints that may be violated when subproblems are evaluated independently. To reduce the overhead in resolving such global constraints, we develop in this paper new conditions and algorithms for limiting the search space to be backtracked in each subproblem. Using a penalty formulation of a MINLP where the constraint functions of the MINLP are transformed into non-negative functions, we present a necessary and sufficient extended saddle-point condition (ESPC) for constrained local minimization. When the penalties are larger than some thresholds, our theory shows a one-to-one correspondence between a constrained local minimum of the MINLP and an extended saddle point of the penalty function. Hence, one way to find a constrained local minimum is to increase gradually the penalties of those violated constraints and to look for a local minimum of the penalty function using any existing algorithm until a solution to the constrained model is found. Next, we extend the ESPC to constraint-partitioned MINLPs and propose a partition-and-resolve strategy for resolving violated global constraints across subproblems. Using the discrete-space ASPEN and the mixed-space MIPS planners to solve subproblems, we show significant improvements on some planning benchmarks, both in terms of the quality of the plans generated and the execution times to find them.     

The second generation of self-organizing adaptive penalty strategy for constrained genetic search

Penalty function approaches have been extensively applied to genetic algorithms for tackling constrained optimization problems. The effectiveness of the genetic searches to locate the global optimum on constrained optimization problems often relies on the proper selections of many parameters involved in the penalty function strategies. A successful genetic search is often completed after a number of genetic searches with varied combinations of penalty function related parameters. In order to provide a robust and effective penalty function strategy with which the design engineers use genetic algorithms to seek the optimum without the time-consuming tuning process, the self-organizing adaptive penalty strategy (SOAPS) for constrained genetic searches was proposed. This paper proposes the second generation of the self-organizing adaptive penalty strategy (SOAPS-II) to further improve the effectiveness and efficiency of the genetic searches on constrained optimization problems, especially when equality constraints are involved. The results of a number of illustrative testing problems show that the SOAPS-II consistently outperforms other penalty function approaches.     

基于演绎长度的学习子句删除策略

学习子句删除策略是CDCL-SAT求解器中的一个重要内容,可以避免内存爆炸和加速单元传播。评估学习子句有用性的标准不同导致所删除的学习子句是不同的,极大地影响求解效率。基于CDCL算法的求解过程可被形式化为增加管理学习子句策略的归结演绎过程,基于此,提出一种基于演绎长度的学习子句评估方法,并与现有的基于文字块距离的评估方法结合,根据排序子句的基准不同,形成两种不同的结合算法。采用国际SAT竞赛的基准实例,与目前主流的求解器进行了实验对比分析。结果表明,所提的结合算法能更好地评估学习子句的有用性,较基于文字块距离策略的求解个数提高了4.1%,说明所提策略具有一定的优势。     

A joint convex penalty for inverse covariance matrix estimation

The paper proposes a joint convex penalty for estimating the Gaussian inverse covariance matrix. A proximal gradient method is developed to solve the resulting optimization problem with more than one penalty constraints. The analysis shows that imposing a single constraint is not enough and the estimator can be improved by a trade-off between two convex penalties. The developed framework can be extended to solve wide arrays of constrained convex optimization problems. A simulation study is carried out to compare the performance of the proposed method to graphical lasso and the SPICE estimate of the inverse covariance matrix.     

Behavior of a micron-sized air bubble in operating FDBs using the discrete phase modeling method

This paper investigates the motion of a micron-sized air bubble in the operating fluid dynamic bearings (FDBs) of a spindle motor in a computer hard disk drive. The flow field of FDBs is calculated by solving the Navier–Stokes equation and the continuity equation. The two-phase flow in the air-oil interface is simultaneously solved by using the finite volume method and the volume of fluid (VOF) method. We then analyze the motion of a micron-sized air bubble by applying the discrete phase modeling (DPM) method to the calculated flow field of FDBs. The motion of a micron-sized air bubble determined using the DPM method is verified by comparison with the trajectory of the micron-sized air bubble determined using the VOF method. The trajectories of a micron-sized air bubble with different initial positions in the FDBs are discussed.     

Visualizing SAT Instances and Runs of the DPLL Algorithm

SAT-solvers have turned into essential tools in many areas of applied logic like, for example, hardware verification or satisfiability checking modulo theories. However, although recent implementations are able to solve problems with hundreds of thousands of variables and millions of clauses, much smaller instances remain unsolved. What makes a particular instance hard or easy is at most partially understood – and is often attributed to the instance’s internal structure. By converting SAT instances into graphs and applying established graph layout techniques, this internal structure can be visualized and thus serve as the basis of subsequent analysis. Moreover, by providing tools that animate the structure during the run of a SAT algorithm, dynamic changes of the problem instance become observable. Thus, we expect both to gain new insights into the hardness of the SAT problem and to help in teaching SAT algorithms.     

Self-organizing adaptive penalty strategy in constrained genetic search

This research aims to develop an effective and robust self-organizing adaptive penalty strategy for genetic algorithms to handle constrained optimization problems without the need to search for appropriate values of penalty factors for the given optimization problem. The proposed strategy is based on the idea that the constrained optimal design is almost always located at the boundary between feasible and infeasible domains. This adaptive penalty strategy automatically adjusts the value of the penalty parameter used for each of the constraints according to the ratio between the number of designs violating the specific constraint and the number of designs satisfying the constraint. The goal is to maintain equal numbers of designs on each side of the constraint boundary so that the chance of locating their offspring designs around the boundary is maximized. The new penalty function is self-defining and no parameters need to be adjusted for objective and constraint functions in any given problem. This penalty strategy is tested and compared with other known penalty function methods in mathematical and structural optimization problems, with favorable results.     

Convergence of Neural Networks for Programming Problems via a Nonsmooth Łojasiewicz Inequality

This paper considers a class of neural networks (NNs) for solving linear programming (LP) problems, convex quadratic programming (QP) problems, and nonconvex QP problems where an indefinite quadratic objective function is subject to a set of affine constraints. The NNs are characterized by constraint neurons modeled by ideal diodes with vertical segments in their characteristic, which enable to implement an exact penalty method. A new method is exploited to address convergence of trajectories, which is based on a nonsmooth Lstrokojasiewicz inequality for the generalized gradient vector field describing the NN dynamics. The method permits to prove that each forward trajectory of the NN has finite length, and as a consequence it converges toward a singleton. Furthermore, by means of a quantitative evaluation of the Lstrokojasiewicz exponent at the equilibrium points, the following results on convergence rate of trajectories are established: 1) for nonconvex QP problems, each trajectory is either exponentially convergent, or convergent in finite time, toward a singleton belonging to the set of constrained critical points; 2) for convex QP problems, the same result as in 1) holds; moreover, the singleton belongs to the set of global minimizers; and 3) for LP problems, each trajectory converges in finite time to a singleton belonging to the set of global minimizers. These results, which improve previous results obtained via the Lyapunov approach, are true independently of the nature of the set of equilibrium points, and in particular they hold even when the NN possesses infinitely many nonisolated equilibrium points     

Discrete thickness optimization via piecewise constraint penalization

Structural engineers are often constrained by cost or manufacturing considerations to select member thicknesses from a discrete set of values. Conventional, gradient-free techniques to solve these discrete problems cannot handle large problem sizes, while discrete material optimization (DMO) techniques may encounter difficulties, especially for bending-dominated problems. To resolve these issues, we propose an efficient gradient-based technique to obtain engineering solutions to the discrete thickness selection problem. The proposed technique uses a series of constraints to enforce an effective stiffness-to-mass and strength-to-mass penalty on intermediate designs. In conjunction with these constraints, we apply an exact penalty function which drives the solution towards a discrete design. We utilize a continuation approach to obtain approximate solutions to the discrete thickness selection problem by solving a sequence of relaxed continuous problems with increasing penalization. We also show how this approach can be applied to combined discrete thickness selection and topology optimization design problems. To demonstrate the effectiveness of the proposed technique, we present both compliance and stress-constrained results for in-plane and bending-dominated problems.     

Evaluating differential evolution with penalty function to solve constrained engineering problems

Over the years, several metaheuristics have been developed to solve hard constrained and unconstrained optimization problems. In general, a metaheuristic is proposed and following researches are made to improve the original algorithm. In this paper, we evaluate a not so new metaheuristic called differential evolution (DE) to solve constrained engineering design problems and compare the results with some recent metaheuristics. Results show that the classical DE with a very simple penalty function to handle constraints is still very competitive in the tested problems.     

A Dual Consistent Finite Difference Method with Narrow Stencil Second Derivative Operators

We study the numerical solutions of time-dependent systems of partial differential equations, focusing on the implementation of boundary conditions. The numerical method considered is a finite difference scheme constructed by high order summation by parts operators, combined with a boundary procedure using penalties (SBP–SAT). Recently it was shown that SBP–SAT finite difference methods can yield superconvergent functional output if the boundary conditions are imposed such that the discretization is dual consistent. We generalize these results so that they include a broader range of boundary conditions and penalty parameters. The results are also generalized to hold for narrow-stencil second derivative operators. The derivations are supported by numerical experiments.     

A simplifier for propositional formulas with many binary clauses

Deciding whether a propositional formula in conjunctive normal form is satisfiable (SAT) is an NP-complete problem. The problem becomes linear when the formula contains binary clauses only. Interestingly, the reduction to SAT of a number of well-known and important problems--such as classical AI planning and automatic test pattern generation for circuits--yields formulas containing many binary clauses. In this paper we introduce and experiment with 2-SIMPLIFY, a formula simplifier targeted at such problems. 2-SIMPLIFY constructs the transitive closure of the implication graph corresponding to the binary clauses in the formula and uses this graph to deduce new unit literals. The deduced literals are used to simplify the formula and update the graph, and so on, until stabilization. Finally, we use the graph to construct an equivalent, simpler set of binary clauses. Experimental evaluation of this simplifier on a number of bench-mark formulas produced by encoding AI planning problems prove 2-SIMPLIFY to be a useful tool in many circumstances.     

基于内部罚函数的进化算法求解约束优化问题

为解决现有约束处理方法可行解的适应度函数不包含约束条件的问题,提出了一种内部罚函数候选解筛选规则.该候选解筛选规则分别对可行解和不可行解采用内部罚函数和约束违反度进行筛选,从而达到平衡最小化目标函数和满足约束条件的目的.以进化策略算法为基础,给出了基于内部罚函数候选解筛选规则的进化算法的一个实现.进一步地,从理论和实验角度分别验证了内部罚函数候选解筛选规则的有效性:以(1+1)进化算法为例,从进化成功率方面验证了内部罚函数候选解筛选规则的理论有效性;通过13个测试问题的数值实验,从进化成功率、候选解后代是可行解的比例、进化步长和收敛速度方面验证了内部罚函数候选解筛选规则的实验有效性.     

The design of a planar robotic manipulator for optimum performance of prescribed tasks

The application of a general optimization methodology, previously proposed by the authors, is extended here to the design of a three link revolute-joint planar manipulator performing more practical and complicated prescribed tasks. In particular a tool moving task and a spray painting task are considered. Both the minimization of average torque and energy usage required for execution of the tasks are addressed and the optimization is carried out with the link lengths and base coordinates taken as the five design variables. In addition to simple physical bounds placed on the variables, the maximum deliverable torques of the driving motors represent further constraints on the system. Joint angle constraints, not previously considered but of great practical importance, are also imposed in this study. This results in significantly more challenging optimization problems than those previously tackled. The complications arising from lock-up and nonassembly are handled by specially devised procedures. The optimization is carried out via penalty function formulations of the constrained problems to which the Snyman unconstrained trajectory optimization algorithm is applied in a special way. For both tasks and for both objective functions, with the full complement of constraints imposed, feasible designs with low objective function values are obtained by using, in each case, four different infeasible designs as starting points for the algorithm.     

Fundamentals of optimization

The structural design problem is formulated as a general nonlinear optimization problem with constraints. Characteristics of such problems and the solutions are discussed. Methods of solution for constrained as well as unconstrained problems are reviewed, with special emphasis on penalty function methods for constrained problems. A simple example on the solution of a design problem with discrete variables is shown, and a realistic example on the application of optimization methods in midship section design of OBO-carriers is presented.     

具有控制时滞的离散系统的无抖振滑模控制

研究含时滞的线性离散系统的变结构控制问题. 首先将之简化为不含时滞项的线性离散系统. 然后对简化系统提出一种新的无抖振滑动模态控制算法. 该算法使滑模控制分为两个阶段,当系统轨迹在滑模某邻域以外时, 利用传统的到达控制律使系统状态轨迹单调趋近滑模面; 当系统轨迹进入该邻域内, 无抖振控制律使其轨迹一步到达滑模面. 该控制律有效地削除了由离散系统解轨迹的不连续性产生的抖振现象. 仿真结果表明了这种方法的有效性.     

Experimental Study on Strategy of CombiningSAT Algorithms

The effectiveness of many SAT algorithms is mainly reflected by their significant performances on one or several classes of specific SAT problems.Different kinds of SAT algorithms all have their own hard instances respectively.Therefore,to get the better performance on all kinds of problems,SAT solver should know how to select different algorithms according to the feature of instances.In this paper the differences of several effective SAT algorithms are analyzed and two new parameters φand δ are proposed to characterize the feature of SAT instances.Experiments are performed to study the relationship between SAT algorithms and some statistical parameters including φ，δ.Based on this analysis,a strategy is presented for designing a faster SAT tester by carefully combining some existing SAT algorithms.With this strategy,a faster SAT tester to solve many kinds of SAT problem is obtained.     

ADMM for multiaffine constrained optimization

ABSTRACT

We expand the scope of the alternating direction method of multipliers (ADMM). Specifically, we show that ADMM, when employed to solve problems with multiaffine constraints that satisfy certain verifiable assumptions, converges to the set of constrained stationary points if the penalty parameter in the augmented Lagrangian is sufficiently large. When the Kurdyka–?ojasiewicz (K–?) property holds, this is strengthened to convergence to a single constrained stationary point. Our analysis applies under assumptions that we have endeavoured to make as weak as possible. It applies to problems that involve nonconvex and/or nonsmooth objective terms, in addition to the multiaffine constraints that can involve multiple (three or more) blocks of variables. To illustrate the applicability of our results, we describe examples including nonnegative matrix factorization, sparse learning, risk parity portfolio selection, nonconvex formulations of convex problems and neural network training. In each case, our ADMM approach encounters only subproblems that have closed-form solutions.