On the terminal control problem

A minimum-time problem is considered, where the final point is locally controllable. It is shown that it is possible to construct a suboptimal control with a transfer time close to the optimal transfer time of the relaxed system. The resulting trajectory will satisfy initial and final conditions. Furthermore, it is shown that, if an optimal solution exists for the problem, then this optimal solution is also an optimal solution of the relaxed problem. In this case, the relaxed problem need not be solved.The authors wish to thank Dr. D. Hazan, Scientific Department, Ministry of Defense, Israel, for a fruitful discussion of this problem.     

Sufficient conditions for a minimum of the free-final-time optimal control problem

The sufficient conditions for a minimum of the free-final-time optimal control problem are the strengthened Legendre-Clebsch condition and the conjugate point condition. In this paper, a new approach for determining the location of the conjugate point is presented. The sweep method is used to solve the linear two-point boundary-value problem for the neighboring extremal path from a perturbed initial point to the final constraint manifold. The new approach is to solve for the final condition Lagrange multiplier perturbation and the final time perturbation simultaneously. Then, the resulting neighboring extremal control is used to write the second variation as a perfect square and obtain the conjugate point condition. Finally, two example problems are solved to illustrate the application of the sufficient conditions.     

Computational identification of the lowest space-wise dependent coefficient of a parabolic equation

In the present work, we consider a nonlinear inverse problem of identifying the lowest coefficient of a parabolic equation. The desired coefficient depends on spatial variables only. Additional information about the solution is given at the final time moment, i.e., we consider the final redefinition. An iterative process is used to evaluate the lowest coefficient, where at each iteration we solve the standard initial-boundary value problem for the parabolic equation. On the basis of the maximum principle for the solution of the differential problem, the monotonicity of the iterative process is established along with the fact that the coefficient is approached from above. The possibilities of the proposed computational algorithm are illustrated by numerical examples for a model two-dimensional problem.     

The dynamic vehicle rescheduling problem

The pre-planned schedules of a transportation company are often disrupted by unforeseen events. As a result of a disruption, a new schedule has to be produced as soon as possible. This process is called the vehicle rescheduling problem, which aims to solve a single disruption and restore the order of transportation. However, there are multiple disruptions happening over a “planning unit” (usually a day), and all of them have to be addressed to achieve a final feasible schedule. From an operations management point of view the quality of the final solution has to be measured by the combined quality of every change over the horizon of the “planning unit”, not by evaluating the solution of each disruption as a separate problem. The problem of finding an optimal solution where all disruptions of a “planning unit” are addressed will be introduced as the dynamic vehicle rescheduling problem (DVRSP). The disruptions of the DVRSP arrive in an online manner, but giving an optimal final schedule for the “planning unit” would mean knowing all information in advance. This is not possible in a real-life scenario, which means that heuristic solution methods have to be considered. In this paper, we present a recursive and a local search algorithm to solve the DVRSP. In order to measure the quality of the solutions given by the heuristics, we introduce the so-called quasi-static DVRSP, a theoretical problem where all the disruptions are known in advance. We give two mathematical models for this quasi-static problem, and use their optimal solutions to evaluate the quality of our heuristic results. The heuristic methods for the dynamic problem are tested on different random instances.     

A Convergence Proof for Constrained Finite Element Solutions

A convergence proof is given for the finite-element solutionof the infinite dimensional quadratic programming problem ofminimizing a quadratic functional subject to linear constraints.The proof for the unconstrained problem is briefly reviewed,and then extended to the constrained case. Only the first partof the proof is given, in which necessary conditions for convergenceare derived for the specific problem and its finite-elementapproximation. The final step of proving that any problem doesobey these conditions will depend on the specific problem, butit is shown that if the finite element formulation is pointwiseconvergent and the unconstrained problem is convergent, thenso too will be the constrained problem.     

A modified quasi-boundary value method for ill-posed problems

In this paper, we study a final value problem for first order abstract differential equation with positive self-adjoint unbounded operator coefficient. This problem is ill-posed. Perturbing the final condition we obtain an approximate nonlocal problem depending on a small parameter. We show that the approximate problems are well posed and that their solutions converge if and only if the original problem has a classical solution. We also obtain estimates of the solutions of the approximate problems and a convergence result of these solutions. Finally, we give explicit convergence rates.     

Optimal control of the multidimensional diffusion equation

The existence and numerical estimation of a boundary control for then-dimensional linear diffusion equation is considered. The problem is modified into one consisting of the minimization of a linear functional over a set of Radon measures. The existence of an optimal measure corresponding to the above problem is shown, and the optimal measure is approximated by a finite convex combination of atomic measures. This construction gives rise to a finite-dimensional linear programming problem, whose solution can be used to construct the combination of atomic measures, and thus a piecewise-constant control function which approximates the action of the optimal measure, so that the final state corresponding to the above control function is close to the desired final state, and the value it assigns to the performance criterion is close to the corresponding infimum. A numerical procedure is developed for the estimation of these controls, entailing the solution of large, finite-dimensional linear programming problems. This procedure is illustrated by several examples.     

The final order problem for repairable spare parts under condemnation

We consider a manufacturer of complex machines that offers service contracts to her customers, committing herself to repair failed spare parts throughout a fixed service period. The suppliers of spare parts often discontinue the production of some parts as technology advances and ask the manufacturer to place a final order. We address the problem of determining final orders for such spare parts. The parts that we consider are repairable, but they are subject to the risk of condemnation. We build a transient Markovian model to represent the problem for a repairable spare part with a certain repair probability and repair lead time and we present some approximations that allow for further real-life characteristics to be included. Furthermore, an approximate model that can be computed more efficiently is presented, and the sensitivity of the results obtained with respect to the problem parameters is discussed, helping us develop several managerial insights.     

新中考中的排课问题

为提高初中学业水平和综合素质教育,近几年有些地方中考进行改革,要求学生进行学科选择。新中考课程分为选修和必修两大类。必修课程为语文、数学、英语,选修课程为其他六门课程,从中选出三项。把最后总成绩作为中考录取的标准。跟传统排课不同,这里排课要求每人一张课表,问题变得复杂困难。本文以北京某初三课程为例,研究了新中考的排课问题。一般情况下约束和变量是上百万级的,无法求解。本文利用整数规划建模,然后把该问题转化成多阶段问题,每个阶段给出小问题的解,这样使得问题的求解变得可行。最终的排课结果,仅比预期增加三位老师就可以实现新中考的排课问题。本文的求解过程给新中考排课带来了新的启发。     

Inverse problem for the reaction diffusion system by optimization method

In this paper, we study an inverse problem of reconstructing two time independent coefficients in the reaction diffusion system from the final measurement. First the given problem is transformed into an optimization problem by using optimal control framework and the existence of the minimizer for the control functional is established. Then we prove the stability estimate for two coefficients with the upper bound given by some Sobolev norms of the final measurement.     

Accurate estimation of the number of binary partitions

Many authors have worked with the problem of binary partitions, but all estimates for the total number obtained so far are restricted to the exponential part only and hence very crude. The present paper is intended to give a final solution of the whole problem.     

Optimal investment–consumption problem: Post-retirement with minimum guarantee

We study the optimal investment–consumption problem for a member of defined contribution plan during the decumulation phase. For a fixed annuitization time, to achieve higher final annuity, we consider a variable consumption rate. Moreover, to have a minimum guarantee for the final annuity, a safety level for the wealth process is considered. To solve the stochastic optimal control problem via dynamic programming, we obtain a Hamilton–Jacobi–Bellman (HJB) equation on a bounded domain. The existence and uniqueness of classical solutions are proved through the dual transformation. We apply the finite difference method to find numerical approximations of the solution of the HJB equation. Finally, the simulation results for the optimal investment–consumption strategies, optimal wealth process and the final annuity for different admissible ranges of consumption are given. Furthermore, by taking into account the market present value of the cash flows before and after the annuitization, we compare the outcomes of different scenarios.     

基于非均匀参数化的自由终端时间最优控制问题求解

针对自由终端时间最优控制问题,提出了一种基于非均匀控制向量参数化的数值解法.将控制时域离散化为不同长度的时间段,各时间段长度作为新的控制变量.通过引入标准化的时间变量,原问题转化为均匀参数化的固定终端时间最优控制问题.建立目标和约束函数的Hamilton函数,通过求解伴随方程获得目标和约束函数的梯度,采用序列二次规划(SQP)获得数值解.针对两个经典的化工过程自由终端时间最优控制问题进行仿真研究,验证了所提出算法的可行性和有效性.     

Numerical Solution of the Retrospective Inverse Problem of Heat Conduction with the Help of the Poisson Integral

We consider the retrospective inverse problem that consists in determining the initial solution of the one-dimensional heat conduction equation with a given condition at the final instant of time. The solution of the problem is given in the form of the Poisson integral and is numerically realized by means of a quadrature formula leading to a system of linear algebraic equations with dense matrix. The results of numerical experiments are presented and show the efficiency of the numerical method including the case of the final condition with random errors.     

Stability estimates for a class of semi-linear ill-posed problems

We study a final value problem for a nonlinear parabolic equation with positive self-adjoint unbounded operator coefficients. The problem is ill-posed. The regularized equation is given by a modified quasi-reversibility method. For this regularization solution, the Hölder type stability estimate between the regularization solution and the exact solution is obtained.     

Simultaneous Identification of Two Time Independent Coefficients in a Nonlinear Phase Field System

In this article, we study a simultaneous reconstruction of two time independent parameters in a nonlinear phase field system by final overdetermination data. To this end, the given problem is transformed into an optimization problem by using the optimal control framework; then the existence of the minimizer for the control functional is established. Further, we deduce the necessary condition for the minimizer of the control functional. Finally we derive the stability estimate for two coefficients with the upper bound given by some Sobolev norms of the final measurement of the solutions.     

An improved branching rule for the symmetric travelling salesman problem

This paper presents an improvement to an existing branch and bound algorithm for solving the symmetric travelling salesman problem. The lower bound used is the standard one obtained from the sequence of minimal spanning 1-trees computed via subgradient optimization, but the branching rule is new. Rather than selecting for inclusion or exclusion those edges which violate the tour constraints in the final 1-tree of the sequence, we consider edges which are present in roughly half of the final few 1-trees. This results in a decision tree whose number of nodes grows by powers of two rather than three, hence significantly reducing the total number of decision nodes required to solve the problem.     

On the reduction of elementary bitisors of local cones-an aggregation-type approach

Using a number theoretic approach a method of reducing the elementary divisors of a local cone is presented. This will be done by generating a finite series of integer local optimization problems. The final problem is equivalent to an unidimensional group knapsack problem. It is an aggregation-type approach where the usual condition of identical solutions is replaced by the demand for equal values of objective functions.     

Mixed L 2-Wasserstein Optimal Mapping Between Prescribed Density Functions

A time-dependent minimization problem for the computation of a mixed L ²-Wasserstein distance between two prescribed density functions is introduced in the spirit of Ref. 1 for the classical Wasserstein distance. The optimum of the cost function corresponds to an optimal mapping between prescribed initial and final densities. We enforce the final density conditions through a penalization term added to our cost function. A conjugate gradient method is used to solve this relaxed problem. We obtain an algorithm which computes an interpolated L ²-Wasserstein distance between two densities and the corresponding optimal mapping.     

An optimal control problem for the multidimensional diffusion equation with a generalized control variable

The present paper is concerned with an optimal control problem for then-dimensional diffusion equation with a sequence of Radon measures as generalized control variables. Suppose that a desired final state is not reachable. We enlarge the set of admissible controls and provide a solution to the corresponding moment problem for the diffusion equation, so that the previously chosen desired final state is actually reachable by the action of a generalized control. Then, we minimize an objective function in this extended space, which can be characterized as consisting of infinite sequences of Radon measures which satisfy some constraints. Then, we approximate the action of the optimal sequence by that of a control, and finally develop numerical methods to estimate these nearly optimal controls. Several numerical examples are presented to illustrate these ideas.