COOPT — a software package for optimal control of large-scale differential–algebraic equation systems

This paper describes the functionality and implementation of COOPT. This software package implements a direct method with modified multiple shooting type techniques for solving optimal control problems of large-scale differential–algebraic equation (DAE) systems. The basic approach in COOPT is to divide the original time interval into multiple shooting intervals, with the DAEs solved numerically on the subintervals at each optimization iteration. Continuity constraints are imposed across the subintervals. The resulting optimization problem is solved by sparse sequential quadratic programming (SQP) methods. Partial derivative matrices needed for the optimization are generated by DAE sensitivity software. The sensitivity equations to be solved are generated via automatic differentiation.COOPT has been successfully used in solving optimal control problems arising from a wide variety of applications, such as chemical vapor deposition of superconducting thin films, spacecraft trajectory design and contingency/recovery problems, and computation of cell traction forces in tissue engineering.     

Minimizing makespan subject to minimum flowtime on two identical parallel machines

We consider the problem of scheduling jobs on two parallel identical machines where an optimal schedule is defined as one that gives the smallest makespan (the completion time of the last job) among the set of schedules with optimal total flowtime (the sum of the completion times of all jobs). We propose an algorithm to determine optimal schedules for the problem, and describe a modified multifit algorithm to find an approximate solution to the problem in polynomial computational time. Results of a computational study to compare the performance of the proposed algorithms with a known heuristic shows that the proposed heuristic and optimization algorithms are quite effective and efficient in solving the problem.Scope and purposeMultiple objective optimization problems are quite common in practice. However, while solving scheduling problems, optimization algorithms often consider only a single objective function. Consideration of multiple objectives makes even the simplest multi-machine scheduling problems NP-hard. Therefore, enumerative optimization techniques and heuristic solution procedures are required to solve multi-objective scheduling problems. This paper illustrates the development of an optimization algorithm and polynomially bounded heuristic solution procedures for the scheduling jobs on two identical parallel machines to hierarchically minimize the makespan subject to the optimality of the total flowtime.     

陈述式基于方程仿真模型的约简

为解决复杂多领域连续系统的高效仿真问题,研究了陈述式基于方程仿真模型的约简策略.基于符号处理技术,提出了一种模型约简方法.该方法从方程的规范转换入手,通过消除特定形式方程缩减系统规模,将整个方程系统规划分解为一个可顺序求解的子系统序列.给出的实例表明文中约简方法效果显著.文中策略与算法已在多领域物理系统混合建模与仿真平台EMWorks中实现.     

An augmented Lagrangian decomposition method for quasi-separable problems in MDO

Several decomposition methods have been proposed for the distributed optimal design of quasi-separable problems encountered in Multidisciplinary Design Optimization (MDO). Some of these methods are known to have numerical convergence difficulties that can be explained theoretically. We propose a new decomposition algorithm for quasi-separable MDO problems. In particular, we propose a decomposed problem formulation based on the augmented Lagrangian penalty function and the block coordinate descent algorithm. The proposed solution algorithm consists of inner and outer loops. In the outer loop, the augmented Lagrangian penalty parameters are updated. In the inner loop, our method alternates between solving an optimization master problem and solving disciplinary optimization subproblems. The coordinating master problem can be solved analytically; the disciplinary subproblems can be solved using commonly available gradient-based optimization algorithms. The augmented Lagrangian decomposition method is derived such that existing proofs can be used to show convergence of the decomposition algorithm to Karush–Kuhn–Tucker points of the original problem under mild assumptions. We investigate the numerical performance of the proposed method on two example problems.     

High-order compact boundary value method for the solution of unsteady convection–diffusion problems

In this paper, we propose a new class of high-order accurate methods for solving the two-dimensional unsteady convection–diffusion equation. These techniques are based on the method of lines approach. We apply a compact finite difference approximation of fourth order for discretizing spatial derivatives and a boundary value method of fourth order for the time integration of the resulted linear system of ordinary differential equations. The proposed method has fourth-order accuracy in both space and time variables. Also this method is unconditionally stable due to the favorable stability property of boundary value methods. Numerical results obtained from solving several problems include problems encounter in many transport phenomena, problems with Gaussian pulse initial condition and problems with sharp discontinuity near the boundary, show that the compact finite difference approximation of fourth order and a boundary value method of fourth order give an efficient algorithm for solving such problems.     

Efficient integration over discontinuities for differential-algebraic systems

In recent years, hybrid (discrete/continuous) dynamic systems that exhibit coupled continuous and discrete behavior have attracted much attention. Many engineering problems can be formulated as ODE/DAEs which can be solved by numerical methods. In process design, dynamic optimization and simulation, however, many systems of interest experience significant discontinuities during transients. This paper describes some simple strategies for discontinuity detecting and handling in DAE embedded systems. The described algorithm supports flexible representation of state conditions in propositional logic. By making full use of the discontinuity functions, both efficiency of integration and effectiveness of discontinuity detection are achieved. Considerable care is taken to handle problems that can arise during mode transitions. We outline the implementation in a general-purpose solver DASPKE for differential-algebraic equations containing discontinuities, and present some numerical experiments which illustrate its effectiveness.     

Heuristic particle filter: applying abstraction techniques to the design of visual tracking algorithms

Abstract: Many real‐world visual tracking applications have a high dimensionality, i.e. the system state is defined by a large number of variables. This kind of problem can be modelled as a dynamic optimization problem, which involves dynamic variables whose values change in time. Most applied research on optimization methods have focused on static optimization problems but these static methods often lack explicit adaptive methodologies. Heuristics are specific methods for solving problems in the absence of an algorithm for formal proof. Metaheuristics are approximate optimization methods which have been applied to more general problems with significant success. However, particle filters are Monte Carlo algorithms which solve the sequential estimation problem by approximating the theoretical distributions in the state space by simulated random measures called particles. However, particle filters lack efficient search strategies. In this paper, we propose a general framework to hybridize heuristics/metaheuristics with particle filters properly. The aim of this framework is to devise effective hybrid visual tracking algorithms naturally, guided by the use of abstraction techniques. Resulting algorithms exploit the benefits of both complementary approaches. As a particular example, a memetic algorithm particle filter is derived from the proposed hybridization framework. Finally, we show the performance of the memetic algorithm particle filter when it is applied to a multiple object tracking problem.     

State of the art in parallel search techniques for discreteoptimization problems

Discrete optimization problems arise in a variety of domains, such as VLSI design, transportation, scheduling and management, and design optimization. Very often, these problems are solved using state space search techniques. Due to the high computational requirements and inherent parallel nature of search techniques, there has been a great deal of interest in the development of parallel search methods since the dawn of parallel computing. Significant advances have been made in the use of powerful heuristics and parallel processing to solve large-scale discrete optimization problems. Problem instances that were considered computationally intractable only a few years ago are routinely solved currently on server-class symmetric multiprocessors and small workstation clusters. Parallel game-playing programs are challenging the best human minds at games like chess. In this paper, we describe the state of the art in parallel algorithms used for solving discrete optimization problems. We address heuristic and nonheuristic techniques for searching graphs as well as trees, and speed-up anomalies in parallel search that are caused by the inherent speculative nature of search techniques     

Deterministic approaches for solving practical black-box global optimization problems

In many important design problems, some decisions should be made by finding the global optimum of a multiextremal objective function subject to a set of constrains. Frequently, especially in engineering applications, the functions involved in optimization process are black-box with unknown analytical representations and hard to evaluate. Such computationally challenging decision-making problems often cannot be solved by traditional optimization techniques based on strong suppositions about the problem (convexity, differentiability, etc.). Nature and evolutionary inspired metaheuristics are also not always successful in finding global solutions to these problems due to their multiextremal character. In this paper, some innovative and powerful deterministic approaches developed by the authors to construct numerical methods for solving the mentioned problems are surveyed. Their efficiency is shown on solving both the classes of random test problems and some practical engineering tasks.     

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.     

Distributed primal–dual interior-point methods for solving tree-structured coupled convex problems using message-passing

In this paper, we propose a distributed algorithm for solving coupled problems with chordal sparsity or an inherent tree structure which relies on primal–dual interior-point methods. We achieve this by distributing the computations at each iteration, using message-passing. In comparison to existing distributed algorithms for solving such problems, this algorithm requires far fewer iterations to converge to a solution with high accuracy. Furthermore, it is possible to compute an upper-bound for the number of required iterations which, unlike existing methods, only depends on the coupling structure in the problem. We illustrate the performance of our proposed method using a set of numerical examples.     

Nonparametric time series forecasting with dynamic updating

We present a nonparametric method to forecast a seasonal univariate time series, and propose four dynamic updating methods to improve point forecast accuracy. Our methods consider a seasonal univariate time series as a functional time series. We propose first to reduce the dimensionality by applying functional principal component analysis to the historical observations, and then to use univariate time series forecasting and functional principal component regression techniques. When data in the most recent year are partially observed, we improve point forecast accuracy by using dynamic updating methods. We also introduce a nonparametric approach to construct prediction intervals of updated forecasts, and compare the empirical coverage probability with an existing parametric method. Our approaches are data-driven and computationally fast, and hence they are feasible to be applied in real time high frequency dynamic updating. The methods are demonstrated using monthly sea surface temperatures from 1950 to 2008.     

A method for solving nonlinear time-dependent drainage model

The purpose of this paper is to present a method for solving nonlinear time-dependent drainage model. This method is based on the perturbation theory and Laplace transformation. The proposed technique allows us to obtain an approximate solution in a series form. The computed results are in good agreement with the results of Adomian decomposition method. Results are presented graphically and in tabulated forms to study the efficiency and accuracy of method. The present approach provides a reliable technique, which avoids the tedious work needed by classical techniques and existing numerical methods. The nonlinear time-dependent drainage model is solved without linearizing or discretizing the nonlinear terms of the equation. The method does not require physically unrealistic assumptions, linearization or discretization in order to find the solutions of the given problems.     

Explicit/multi-parametric model predictive control (MPC) of linear discrete-time systems by dynamic and multi-parametric programming

This work presents a new algorithm for solving the explicit/multi-parametric model predictive control (or mp-MPC) problem for linear, time-invariant discrete-time systems, based on dynamic programming and multi-parametric programming techniques. The algorithm features two key steps: (i) a dynamic programming step, in which the mp-MPC problem is decomposed into a set of smaller subproblems in which only the current control, state variables, and constraints are considered, and (ii) a multi-parametric programming step, in which each subproblem is solved as a convex multi-parametric programming problem, to derive the control variables as an explicit function of the states. The key feature of the proposed method is that it overcomes potential limitations of previous methods for solving multi-parametric programming problems with dynamic programming, such as the need for global optimization for each subproblem of the dynamic programming step.     

Heterogeneous representation learning with separable structured sparsity regularization

Motivated by real applications, heterogeneous learning has emerged as an important research area, which aims to model the coexistence of multiple types of heterogeneity. In this paper, we propose a heterogeneous representation learning model with structured sparsity regularization (HERES) to learn from multiple types of heterogeneity. It aims to leverage the rich correlations (e.g., task relatedness, view consistency, and label correlation) and the prior knowledge (e.g., the soft-clustering of tasks) of heterogeneous data to improve learning performance. To this end, HERES integrates multi-task, multi-view, and multi-label learning into a principled framework based on representation learning to model the complex correlations and employs the structured sparsity to encode the prior knowledge of data. The objective is to simultaneously minimize the reconstruction loss of using the factor matrices to recover the heterogeneous data, and the structured sparsity imposed on the model. The resulting optimization problem is challenging due to the non-smoothness and non-separability of structured sparsity. We reformulate the problem by using the auxiliary function and prove that the reformulation is separable, which leads to an efficient algorithm family for solving structured sparsity penalized problems. Furthermore, we propose various HERES models based on different loss functions and subsume them into the weighted HERES, which is able to handle missing data. The experimental results in comparison with state-of-the-art methods demonstrate the effectiveness of the proposed approach.     

机器学习随机优化方法的个体收敛性研究综述

随机优化方法是求解大规模机器学习问题的主流方法,其研究的焦点问题是算法是否达到最优收敛速率与能否保证学习问题的结构。目前,正则化损失函数问题已得到了众多形式的随机优化算法,但绝大多数只是对迭代进行 平均的输出方式讨论了收敛速率,甚至无法保证最为典型的稀疏结构。与之不同的是,个体解能很好保持稀疏性,其最优收敛速率已经作为open问题被广泛探索。另外,随机优化普遍采用的梯度无偏假设往往不成立,加速方法收敛界中的偏差在有偏情形下会随迭代累积,从而无法应用。本文对一阶随机梯度方法的研究现状及存在的问题进行综述,其中包括个体收敛速率、梯度有偏情形以及非凸优化问题,并在此基础上指出了一些值得研究的问题。     

Efficient task assignment for spatial crowdsourcing: A combinatorial fractional optimization approach with semi-bandit learning

Spatial crowdsourcing has emerged as a new paradigm for solving problems in the physical world with the help of human workers. A major challenge in spatial crowdsourcing is to assign reliable workers to nearby tasks. The goal of such task assignment process is to maximize the task completion in the face of uncertainty. This process is further complicated when tasks arrivals are dynamic and worker reliability is unknown. Recent research proposals have tried to address the challenge of dynamic task assignment. Yet the majority of the proposals do not consider the dynamism of tasks and workers. They also make the unrealistic assumptions of known deterministic or probabilistic workers’ reliabilities. In this paper, we propose a novel approach for dynamic task assignment in spatial crowdsourcing. The proposed approach combines bi-objective optimization with combinatorial multi-armed bandits. We formulate an online optimization problem to maximize task reliability and minimize travel costs in spatial crowdsourcing. We propose the distance-reliability ratio (DRR) algorithm based on a combinatorial fractional programming approach. The DRR algorithm reduces travel costs by 80% while maximizing reliability when compared to existing algorithms. We extend the DRR algorithm for the scenario when worker reliabilities are unknown. We propose a novel algorithm (DRR-UCB) that uses an interval estimation heuristic to approximate worker reliabilities. Experimental results demonstrate that the DRR-UCB achieves high reliability in the face of uncertainty. The proposed approach is particularly suited for real-life dynamic spatial crowdsourcing scenarios. This approach is generalizable to the similar problems in other areas in expert systems. First, it encompasses online assignment problems when the objective function is a ratio of two linear functions. Second, it considers situations when intelligent and repeated assignment decisions are needed under uncertainty.     

An adaptive nonmonotone truncated Newton method for optimal control of a class of parabolic distributed parameter systems

A black-box method using the finite elements, the Crank–Nicolson and a nonmonotone truncated Newton (TN) method is presented for solving optimal control problems (OCPs) governed by partial differential equations (PDEs). The proposed method finds the optimal control of a class of linear and nonlinear parabolic distributed parameter systems with a quadratic cost functional. To this end, the piecewise linear finite elements method and the well-known Crank–Nicolson method are used for discretizing in space and in time, respectively. Afterwards, regarding the implicit function theorem (IFT), the optimal control problem is transformed into an unconstrained nonlinear optimization problem. Considering that in a gradient-based method for solving optimal control problems, the evaluations of gradients and Hessians of the cost functional is important, hence, an adjoint technique is used to evaluate them effectively. In addition, to make a globalization strategy, we first introduce an adaptive nonmonotone strategy which properly controls the degree of nonmonotonicity and then incorporate it into an inexact Armijo-type line search approach to construct a more relaxed line search procedure. Finally, the obtained unconstrained nonlinear optimization problem is solved by utilizing the proposed nonmonotone truncated Newton method. Results gained from the new offered method compared with existing methods show that the new method is promising.     

Parallel methods for optimality criteria-based topology optimization

Topology optimization problems require the repeated solution of finite element problems that are often extremely ill-conditioned due to highly heterogeneous material distributions. This makes the use of iterative linear solvers inefficient unless appropriate preconditioning is used. Even then, the solution time for topology optimization problems is typically very high. These problems are addressed by considering the use of non-overlapping domain decomposition-based parallel methods for the solution of topology optimization problems. The parallel algorithms presented here are based on the solid isotropic material with penalization (SIMP) formulation of the topology optimization problem and use the optimality criteria method for iterative optimization. We consider three parallel linear solvers to solve the equilibrium problem at each step of the iterative optimization procedure. These include two preconditioned conjugate gradient (PCG) methods: one using a diagonal preconditioner and one using an incomplete LU factorization preconditioner with a drop tolerance. A third substructuring solver that employs a hybrid of direct and iterative (PCG) techniques is also studied. This solver is found to be the most effective of the three solvers studied, both in terms of parallel efficiency and in terms of its ability to mitigate the effects of ill-conditioning. In addition to examining parallel linear solvers, we consider the parallelization of the iterative optimality criteria method. To tackle checkerboarding and mesh dependence, we propose a multi-pass filtering technique that limits the number of “ghost” elements that need to be exchanged across interprocessor boundaries.     

A Non-monotone Line Search Algorithm for?Unconstrained Optimization

The monotone line search schemes have been extensively used in the iterative methods for solving various optimization problems. It is well known that the non-monotone line search technique can improve the likelihood of finding a global optimal solution and the numerical performance of the methods, especially for some difficult nonlinear problems. The traditional non-monotone line search approach requires that a maximum of recent function values decreases. In this paper, we propose a new line search scheme which requires that a convex combination of recent function values decreases. We apply the new line search technique to solve unconstrained optimization problems, and show the proposed algorithm possesses global convergence and R-linear convergence under suitable assumptions. We also report the numerical results of the proposed algorithm for solving almost all the unconstrained testing problems given in CUTEr, and give numerical comparisons of the proposed algorithm with two famous non-monotone methods.