An indirect numerical method for the solution of a class of optimal control problems with singular arcs

An indirect numerical method is presented that solves a class of optimal control problems that have a singular arc occurring after an initial nonsingular arc. This method iterates on the subset of initial costate variables that enforce the junction conditions for switching to a singular arc, and the time of switching off of the singular arc to a final nonsingular arc, to reduce a terminal error function of the final conditions to zero. This results in the solution to the two-point boundary-value problem obtained using the minimum principle and some necessary conditions for singular arcs. The main advantage of this method is that the exact solution to the two-point boundary-value problem is obtained. The main disadvantage is that the sequence of controls for the problem must be known to apply this method. Two illustrative examples are presented.     

Optimization method for solving bang-bang and singular control problems

In this paper we study optimal control problems with the control variable appearing linearly.A novel method for optimization with respect to the switching times of controls containing both bang-bang and singular arcs is presented.This method transforms the control problem into a finite-dimensional optimization problem by reformulating the control problem as a multi-stage optimization problem.The optimal control problem is partitioned as several stages, with each stage corresponding to a particular control arc.A control vector parameterization approach is applied to convert the control problem to a static nonlinear programming(NLP) problem.The control profiles and stage lengths act as decision variables.Based on the Pontryagin maximal principle,a multi-stage adjoint system is constructed to calculate the gradients required by the NLP solvers.Two examples are studied to demonstrate the effectiveness of this strategy.     

On the interpolation of concentric curvature elements

A convex G² Hermite interpolation problem of concentric curvature elements is considered in this paper. It is first proved that there is no spiral arc solution with turning angle less than or equal to π and then, that any convex solution admits at least two vertices. The curvature and the evolute profiles of such an interpolant are analyzed. In particular, conditions for the existence of a G² convex interpolant with prescribed extremal curvatures are given.     

Approximate solutions for the capacitated arc routing problem

The capacitated arc routing problem (CARP), is a capacitated variation of the arc routing problems in which there is a capacity constraint associated with each vehicle. Due to the computational complexity of the problem, recent research has focussed on developing and testing heuristic algorithms which solve the CARP approximately. In this paper, we review some of the existing solution procedures, analyze their complexity, and present two modifications of the existing methods to obtain near-optimal solutions for the CARP. Extensive computational results are presented and analyzed.     

Solving the subset-sum problem with a light-based device

We propose an optical computational device which uses light rays for solving the subset-sum problem. The device has a graph-like representation and the light is traversing it by following the routes given by the connections between nodes. The nodes are connected by arcs in a special way which lets us to generate all possible subsets of the given set. To each arc we assign either a number from the given set or a predefined constant. When the light is passing through an arc it is delayed by the amount of time indicated by the number placed in that arc. At the destination node we will check if there is a ray whose total delay is equal to the target value of the subset sum problem (plus some constants). The proposed optical solution solves a NP-complete problem in time proportional with the target sum, but requires an exponential amount of energy.     

Determination of the candidate arc set for the asymmetric traveling salesman problem

As size of the traveling salesman problem (TSP) increases, it is unreasonable to find efficiently an optimum or near-optimum. Instead of considering all arcs, if we select and consider only some arcs more likely to be included in an optimal solution, we can find efficiently an optimum or near-optimum. A candidate arc set is a group of some good arcs. For the lack of study in the asymmetric TSP, it needs to research systematically for the candidate arc set of the asymmetric TSP. In this paper, we suggest a regression function determining a candidate arc set for the asymmetric TSP. We established the regression function based on 2100 experiments, and we proved the goodness of fit for it through various 787 problems. Also, we applied it to the Out-of-Kilter heuristic. We tested it on 220 random instances and 23 real-world instances. Because the complexity of the heuristic depends on the number of arcs and we considered only the candidate arc set, we found good solutions about 2–5 fold faster than considering all arcs.     

Application of multiple shooting to the numerical solution of optimal control problems with bounded state variables

Algorithms for the numerical solution of optimal control problems with bounded state variables are developed. Two main cases are considered: either the control variable appears nonlinearly or the control variable appears linearly. In the first case, an extremal are touching the boundary or containing a boundary arc, is shown to satisfy a suitable two-point boundary value problem. In the second case, a numerical idea for solving the problem in statespace is presented which dispenses with the Lagrange-multipliers. Three numerical examples are discussed illustrating the efficiency of the different algorithms. The encountered two-point boundary value problems are solved with the method of multiple shooting.     

On a class of optimal control problems with an almost cost-free solution

For a class of linear singular optimal control problems with a nonunique singular arc, the solution of the corresponding nearly singular problem is analyzed and a limit solution based on formal singular perturbations is derived. A rigorous proof of the correctness of the result is given by constructing a convergent power series satisfying the Riccati equation of the nearly singular problem.     

Matching sets of 3D line segments with application to polygonal arcmatching

In this paper, we consider two sets of corresponding 3D line segments of equal length. We derive a closed-form solution for the coordinate transform (rotation and translation) that gives the best match between the two sets; best in the sense of a least-squares distance measure between the sets. We use these results as the basis to construct efficient algorithms for solving other problems in computer vision. Specifically, we address the problem of matching polygonal arcs, that is, the problem of finding a match between a short arc and a piece of long arc     

凹角区域外问题基于椭圆弧人工边界的自然边界元与有限元耦合法

木文以具有凹角长条型内边界的调和方程外问题为例,研究一种以椭圆弧为人工边界的自然边界元与有限元耦合法,给出了耦合变分问题的适定性及近似解的误差估计．理论分析及数值结果表明,用该方法求解带凹角长条型内边界的外问题是十分有效的．