基于高斯伪谱的最优控制求解及其应用

研究一种基于高斯伪谱法的具有约束受限的最优控制数值计算问题.方法将状态演化和控制规律用多项式参数化近似,微分方程用正交多项式近似.将最优控制问题求解问题转化为一组有约束的非线性规划求解.详细论述了该种近似方法的有效性.作为该种方法的应用,讨论了一个障碍物环境下的机器人最优路径生成问题.将机器人路径规划问题转化为具有约束条件最优控制问题,然后用基于高斯伪谱的方法求解,并给出了仿真结果.     

基于小波分析的空间机械臂运动规划的最优控制

讨论了空间机械臂系统非完整运动规划的最优控制问题.利用小波分析方法,将离散正交小波函数引入最优控制,由小波级数展开式逼近替代传统的Fourier基函数,提出基于小波分析的最优控制数值算法.仿真结果表明,该方法对求解空间机械臂非完整运动规划问题是有效的.     

Effective program planning for multiple projects under limited resources

This work deals with an analytical approach to effective planning based upon the relative economics of projects contained in a program. A mathematical model is formulated to maximize the total return over the planning horizon subject to various annual cash flow and resource constraints. Stochastic mixed-integer programming is applied to determine the optimal sequence of project planning activities. To illustrate the use of the proposed procedure, a numerical example is solved using the mathematical programming software package SCICONIC/VM in a VAX-11/750 computer system.     

Convergence of a Scholtes-type regularization method for cardinality-constrained optimization problems with an application in sparse robust portfolio optimization

We consider general nonlinear programming problems with cardinality constraints. By relaxing the binary variables which appear in the natural mixed-integer programming formulation, we obtain an almost equivalent nonlinear programming problem, which is thus still difficult to solve. Therefore, we apply a Scholtes-type regularization method to obtain a sequence of easier to solve problems and investigate the convergence of the obtained KKT points. We show that such a sequence converges to an S-stationary point, which corresponds to a local minimizer of the original problem under the assumption of convexity. Additionally, we consider portfolio optimization problems where we minimize a risk measure under a cardinality constraint on the portfolio. Various risk measures are considered, in particular Value-at-Risk and Conditional Value-at-Risk under normal distribution of returns and their robust counterparts under moment conditions. For these investment problems formulated as nonlinear programming problems with cardinality constraints we perform a numerical study on a large number of simulated instances taken from the literature and illuminate the computational performance of the Scholtes-type regularization method in comparison to other considered solution approaches: a mixed-integer solver, a direct continuous reformulation solver and the Kanzow–Schwartz regularization method, which has already been applied to Markowitz portfolio problems.     

The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming

A new deterministic algorithm for solving convex mixed-integer nonlinear programming (MINLP) problems is presented in this paper: The extended supporting hyperplane (ESH) algorithm uses supporting hyperplanes to generate a tight overestimated polyhedral set of the feasible set defined by linear and nonlinear constraints. A sequence of linear or quadratic integer-relaxed subproblems are first solved to rapidly generate a tight linear relaxation of the original MINLP problem. After an initial overestimated set has been obtained the algorithm solves a sequence of mixed-integer linear programming or mixed-integer quadratic programming subproblems and refines the overestimated set by generating more supporting hyperplanes in each iteration. Compared to the extended cutting plane algorithm ESH generates a tighter overestimated set and unlike outer approximation the generation point for the supporting hyperplanes is found by a simple line search procedure. In this paper it is proven that the ESH algorithm converges to a global optimum for convex MINLP problems. The ESH algorithm is implemented as the supporting hyperplane optimization toolkit (SHOT) solver, and an extensive numerical comparison of its performance against other state-of-the-art MINLP solvers is presented.     

Chance constrained programming models for refinery short-term crude oil scheduling problem

The main objective of this work is to put forward chance constrained mixed-integer nonlinear stochastic and fuzzy programming models for refinery short-term crude oil scheduling problem under demands uncertainty of distillation units. The scheduling problem studied has characteristics of discrete events and continuous events coexistence, multistage, multiproduct, nonlinear, uncertainty and large scale. At first, the two models are transformed into their equivalent stochastic and fuzzy mixed-integer linear programming (MILP) models by using the method of Quesada and Grossmann [I. Quesada, I E. Grossmann, Global optimization of bilinear process networks with multicomponent flows, Comput. Chem. Eng. 19 (12) (1995) 1219–1242], respectively. After that, the stochastic equivalent model is converted into its deterministic MILP model through probabilistic theory. The fuzzy equivalent model is transformed into its crisp MILP model relies on the fuzzy theory presented by Liu and Iwamura [B.D. Liu, K. Iwamura, Chance constrained programming with fuzzy parameters, Fuzzy Sets Syst. 94 (2) (1998) 227–237] for the first time in this area. Finally, the two crisp MILP models are solved in LINGO 8.0 based on scheduling time discretization. A case study which has 267 continuous variables, 68 binary variables and 320 constraints is effectively solved with the solution approaches proposed.     

Improved logarithmic linearizing method for optimization problems with free-sign pure discrete signomial terms

Free-sign pure discrete signomial (FPDS) terms are vital to and are frequently observed in many nonlinear programming problems, such as geometric programming, generalized geometric programming, and mixed-integer non-linear programming problems. In this study, all variables in the FPDS term are discrete variables. Any improvement to techniques for linearizing FPDS term contributes significantly to the solving of nonlinear programming problems; therefore, relative techniques have continually been developed. This study develops an improved exact method to linearize a FPDS term into a set of linear programs with minimal logarithmic numbers of zero-one variables and constraints. This method is tighter than current methods. Various numerical experiments demonstrate that the proposed method is significantly more efficient than current methods, especially when the problem scale is large.     

An efficient deterministic optimization approach for rectangular packing problems

The rectangular packing problem aims to seek the best way of placing a given set of rectangular pieces within a large rectangle of minimal area. Such a problem is often constructed as a quadratic mixed-integer program. To find the global optimum of a rectangular packing problem, this study transforms the original problem as a mixed-integer linear programming problem by logarithmic transformations and an efficient piecewise linearization approach that uses a number of binary variables and constraints logarithmic in the number of piecewise line segments. The reformulated problem can be solved to obtain an optimal solution within a tolerable error. Numerical examples demonstrate the computational efficiency of the proposed method in globally solving rectangular packing problems.     

Conic mixed-integer rounding cuts

A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical learning, and probabilistic optimization are modeled using conic constraints. Here we study mixed-integer sets defined by second-order conic constraints. We introduce general-purpose cuts for conic mixed-integer programming based on polyhedral conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that solve either second-order conic programming or linear programming relaxations of conic integer programs at the nodes of the branch-and-bound tree. Central to our approach is a reformulation of the second-order conic constraints with polyhedral second-order conic constraints in a higher dimensional space. In this representation the cuts we develop are linear, even though they are nonlinear in the original space of variables. This feature leads to a computationally efficient implementation of nonlinear cuts for conic mixed-integer programming. The reformulation also allows the use of polyhedral methods for conic integer programming. We report computational results on solving unstructured second-order conic mixed-integer problems as well as mean–variance capital budgeting problems and least-squares estimation problems with binary inputs. Our computational experiments show that conic mixed-integer rounding cuts are very effective in reducing the integrality gap of continuous relaxations of conic mixed-integer programs and, hence, improving their solvability. This research has been supported, in part, by Grant # DMI0700203 from the National Science Foundation.     

Mathematical modeling and trajectory planning of mobile manipulators with flexible links and joints

This paper is concerned with mathematical modeling and optimal motion designing of flexible mobile manipulators. The system is composed of a multiple flexible links and flexible revolute joints manipulator mounted on a mobile platform. First, analyzing on kinematics and dynamics of the model is carried out then; open-loop optimal control approach is presented for optimal motion designing of the system. The problem is known to be complex since combined motion of the base and manipulator, non-holonomic constraint of the base and highly non-linear and complicated dynamic equations as a result of the flexible nature of both links and joints are taken into account. In the proposed method, the generalized coordinates and additional kinematic constraints are selected in such a way that the base motion coordination along the predefined path is guaranteed while the optimal motion trajectory of the end-effector is generated. This method by using Pontryagin’s minimum principle and deriving the optimality conditions converts the optimal control problem into a two point boundary value problem. A comparative assessment of the dynamic model is validated through computer simulations, and then additional simulations are done for trajectory planning of a two-link flexible mobile manipulator to demonstrate effectiveness and capability of the proposed approach.     

Directional fields algebraic non-linear solution equations for mobile robot planning

In this study, a novel approach to robot navigation/planning by using half-cell electrochemical potentials is presented. The half-cell electrode’s potential is modelled by the Nernst equation to yield automatic search/detection of pipeline flaws by using the direct current voltage gradient (DCVG) technique. We introduce a theory of spherical volumetric electric density in the soil to sustain our postulates for navigational potential fields. The Nernst potential is correlated with the distance to a pipe’s flaw by proposing a fitted theoretical-empirical nonlinear regression model. From this, volumetric derivatives are solved as gradient-based fields to control wheeled robot’s motion. A nonlinear system for trajectory planning is proposed, and analytically solved by an algebraic solution. This solution directly adjust robot’s speed kinematic values to lead it toward the flaw. The inverse/forward kinematic constraints are non-holonomic, and are recursively integrated into the general potential equation. Analytical modelling is reported, and a set of numerical simulations are presented to prove the feasibility of the proposed formulations.     

A class of optimal state-delay control problems

We consider a general nonlinear time-delay system with state-delays as control variables. The problem of determining optimal values for the state-delays to minimize overall system cost is a non-standard optimal control problem–called an optimal state-delay control problem–that cannot be solved using existing optimal control techniques. We show that this optimal control problem can be formulated as a nonlinear programming problem in which the cost function is an implicit function of the decision variables. We then develop an efficient numerical method for determining the cost function’s gradient. This method, which involves integrating an auxiliary impulsive system backwards in time, can be combined with any standard gradient-based optimization method to solve the optimal state-delay control problem effectively. We conclude the paper by discussing applications of our approach to parameter identification and delayed feedback control.     

Realtime control of robots with initial value perturbations via nonlinear programming methods

The mathematical model of an industrial robot with initial value perturbations is considered as a parametric nonlinear control problem subject to control and state constraints. Based on recent stability results for parametric control problems, a robust nonlinear programming method is proposed for computing the sensitivity derivatives of optimal solutions. Real-time control approximations of perturbed optimal solutions are obtained by evaluating a first order Taylor expansion of the perturbed solution. The efficiency of the real-time approximation is demonstrated for the robot model     

A decomposition approach for optimal control problems with integer innerpoint state constraints

A large class of optimal control problems for hybrid dynamic systems can be formulated as mixed‐integer optimal control problems (MIOCPs). A decomposition approach is suggested to solve a special subclass of MIOCPs with mixed integer inner point state constraints. It is the intrinsic combinatorial complexity of the discrete variables in addition to the high nonlinearity of the continuous optimal control problem that forms the challenges in the theoretical and numerical solution of MIOCPs. During the solution procedure the problem is decomposed at the inner time points into a multiphase problem with mixed integer boundary constraints and phase transitions at unknown switching points. Due to a discretization of the state space at the switching points the problem can be decoupled into a family of continuous optimal control problems (OCPs) and a problem similar to the asymmetric group traveling salesman problem (AGTSP). The OCPs are transcribed by direct collocation to large‐scale nonlinear programming problems, which are solved efficiently by an advanced SQP method. The results are used as weights for the edges of the graph of the corresponding TSP‐like problem, which is solved by a Branch‐and‐Cut‐and‐Price (BCP) algorithm. The proposed approach is applied to a hybrid optimal control benchmark problem for a motorized traveling salesman. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A new mixed integer programming formulation for facility layout design using flexible bays

This paper presents a mixed-integer programming formulation to find optimal solutions for the block layout problem with unequal departmental areas arranged in flexible bays. The nonlinear department area constraints are modeled in a continuous plane without using any surrogate constraints. The formulation is extensively tested on problems from the literature.     

An exact penalty function method for nonlinear mixed discrete programming problems

In this paper, we consider a general class of nonlinear mixed discrete programming problems. By introducing continuous variables to replace the discrete variables, the problem is first transformed into an equivalent nonlinear continuous optimization problem subject to original constraints and additional linear and quadratic constraints. Then, an exact penalty function is employed to construct a sequence of unconstrained optimization problems, each of which can be solved effectively by unconstrained optimization techniques, such as conjugate gradient or quasi-Newton methods. It is shown that any local optimal solution of the unconstrained optimization problem is a local optimal solution of the transformed nonlinear constrained continuous optimization problem when the penalty parameter is sufficiently large. Numerical experiments are carried out to test the efficiency of the proposed method.     

Wavelet Collocation Method for Optimal Control Problems

A Haar wavelet technique is discussed as a method for discretizing the nonlinear system equations for optimal control problems. The technique is used to transform the state and control variables into nonlinear programming (NLP) parameters at collocation points. A nonlinear programming solver can then be used to solve optimal control problems that are rather general in form. Here, general Bolza optimal control problems with state and control constraints are considered. Examples of two kinds of optimal control problems, continuous and discrete, are solved. The results are compared to those obtained by using other collocation methods.     

Solving nonlinear programming problems with very many constraints

For solving the smooth constrained nonlinear programming problem, sequential quadratic programming (SQP) methods are considered to be the standard tool, as long as they are applicable. However one possible situation preventing the successful solution by a standard SQP-technique, arises if problems with a very large number of constraints are to be solved. Typical applications are semi-infinite or min-max optimization, optimal control or mechanical structural optimization. The proposed technique proceeds from a user defined number of linearized constraints, that is to be used internally to determine the size of the quadratic programming subproblem. Significant constraints are then selected automatically by the algorithm. Details of the numerical implementation and some experimental results are presented