Finding Minimal Branchings With a Given Number of Arcs
In this paper results concerning structural and approximability properties of the subclass of NP-Complete Optimization Problems, defined over a lattice are considered. First, various approaches to the concept of Fully Polynomial Approximation Scheme are presented with application to several known problems in the class of NP-Complete Optimization Problems.Secondly, a characterization of full Approximability for the class of Max Subset Problems is introduced.
In the paper necessary optimality conditions are derived for the minimization of a locally Lipschitz objective with respect to the consttraints , where is a closed set and is a set-valued map. No convexity requirements are imposed on . The conditions are applied to a generalized mathematical programming problem and to an abstract finite-dimensional optimal control problem.
Some iterative methods of mathematical programming use a damping sequence {αt} such that 0 ≤ αt ≤ 1 for all t, αt → 0 as t → ∞, and Σ αt = ∞. For example, αt = 1/(t+1) in Brown's method for solving matrix games. In this paper, for a model class of iterative methods, the convergence rate for any damping sequence {αt} depending only on time t is computed. The computation is used to find the best damping sequence.
The motivation for this work is the real-time solution of a standard optimal control problem arising in robotics and aerospace applications. For example, the trajectory planning problem for air vehicles is naturally cast as an optimal control problem on the tangent bundle of the Lie Group which is also a parallelizable riemannian manifold. For an optimal control problem on the tangent bundle of such a manifold, we use frame co-ordinates and obtain first-order necessary conditions employing calculus...
The motivation for this work is the real-time solution of a standard optimal control problem arising in robotics and aerospace applications. For example, the trajectory planning problem for air vehicles is naturally cast as an optimal control problem on the tangent bundle of the Lie Group SE(3), which is also a parallelizable Riemannian manifold. For an optimal control problem on the tangent bundle of such a manifold, we use frame co-ordinates and obtain first-order necessary conditions...