Multidimensional Dual Dynamic Programming

In this paper, we develop a dual approach to the dynamic programming for the optimal control problem in a multidimensional case. The idea of our method consists in defining, instead of the value function, a new function which satisfies a dual first-order partial differential equation of dynamic programming. We then prove a suitable verification theorem and introduce the concept of a dual feedback control. The sufficient optimality conditions thus obtained are analogous to their one-dimensional counterparts.     

变量有广义界线性规划的直接对偶单纯形法

本文讨论变量有广义界线性规划问题借助标准形线性规划同单纯形法技术，建立问题的一个直接对偶单纯形法。分析了方法的性质，给出了初始对偶可行基的计算方法，并用实例说明方法的具体操作。     

A Dual Dynamic Programming for Multidimensional Elliptic Optimal Control Problems

This paper deals with the optimal control problems with multiple integrals and an elliptic partial differential equation. The sufficient conditions for optimality in these problems are proved through a dual dynamic programming. The concept of an optimal dual feedback is introduced, and the theorem guaranteeing its existence is established. For the purposes of numerical methods, the ε-version of the verification theorem provided appears to be very useful.     

多目标规划的对偶二阶条件

本文针对多目标规划 ( VP)的 Lagrange对偶规划 ( VD) ,从几何直观的角度出发 ,给出对偶规划( VD)的二阶最优性条件 ,即对偶二阶条件 ,并证明了相应的最优性定理 .     

Dynamic Programming Method for Constrained Discrete-Time Optimal Control

A dynamic programming method is presented for solving constrained, discrete-time, optimal control problems. The method is based on an efficient algorithm for solving the subproblems of sequential quadratic programming. By using an interior-point method to accommodate inequality constraints, a modification of an existing algorithm for equality constrained problems can be used iteratively to solve the subproblems. Two test problems and two application problems are presented. The application examples include a rest-to-rest maneuver of a flexible structure and a constrained brachistochrone problem.     

线性规划对偶问题的一个注记

指出了线性规划对偶问题定义中的一个小漏洞,并作了改正     

L-shaped decomposition of two-stage stochastic programs with integer recourse

We consider two-stage stochastic programming problems with integer recourse. The L-shaped method of stochastic linear programming is generalized to these problems by using generalized Benders decomposition. Nonlinear feasibility and optimality cuts are determined via general duality theory and can be generated when the second stage problem is solved by standard techniques. Finite convergence of the method is established when Gomory’s fractional cutting plane algorithm or a branch-and-bound algorithm is applied.     

A Dual Projective Pivot Algorithm for Linear Programming

Recently, a linear programming problem solver, called dual projective simplex method, was proposed (Pan, Computers and Mathematics with Applications, vol. 35, no. 6, pp. 119–135, 1998). This algorithm requires a crash procedure to provide an initial (normal or deficient) basis. In this paper, it is recast in a more compact form so that it can get itself started from scratch with any dual (basic or nonbasic) feasible solution. A new dual Phase-1 approach for producing such a solution is proposed. Reported are also computational results obtained with a set of standard NETLIB problems.     

Canonical Duality Theory and Solutions to Constrained Nonconvex Quadratic Programming

This paper presents a perfect duality theory and a complete set of solutions to nonconvex quadratic programming problems subjected to inequality constraints. By use of the canonical dual transformation developed recently, a canonical dual problem is formulated, which is perfectly dual to the primal problem in the sense that they have the same set of KKT points. It is proved that the KKT points depend on the index of the Hessian matrix of the total cost function. The global and local extrema of the nonconvex quadratic function can be identified by the triality theory [11]. Results show that if the global extrema of the nonconvex quadratic function are located on the boundary of the primal feasible space, the dual solutions should be interior points of the dual feasible set, which can be solved by deterministic methods. Certain nonconvex quadratic programming problems in {\open {R}}^{n} can be converted into a dual problem with only one variable. It turns out that a complete set of solutions for quadratic programming over a sphere is obtained as a by-product. Several examples are illustrated.     

关于线性规划问题熵障碍对偶法的注记

线性规划是目标优化问题中最常用的模型。关于大规模线性规划问题的有效求解问题一直受到人们的关注。熵障碍对偶法是继内点法之后,又一解线性规划问题的新的算法。本文讨论了熵障碍对偶法的推广形式及其梯度类算法的收敛性。     

Variable Programming: A Generalized Minimax Problem. Part I: Models and Theory

In this two-part series of papers, a new generalized minimax optimization model, termed variable programming (VP), is developed to solve dynamically a class of multi-objective optimization problems with non-decomposable structure. It is demonstrated that such type of problems is more general than existing optimization models. In this part, the VP model is proposed first, and the relationship between variable programming and the general constrained nonlinear programming is established. To illustrate its practicality, problems on investment and the low-side-lobe conformal antenna array pattern synthesis to which VP can be appropriately applied are discussed for substantiation. Then, theoretical underpinnings of the VP problems are established. Difficulties in dealing with the VP problems are discussed. With some mild assumptions, the necessary conditions for the unconstrained VP problems with arbitrary and specific activated feasible sets are derived respectively. The necessary conditions for the corresponding constrained VP problems with the mild hypotheses are also examined. Whilst discussion in this part is concentrated on the formulation of the VP model and its theoretical underpinnings, construction of solution algorithms is discussed in Part II.This work was supported by the RGC grant CUHK 152/96H of the Hong Kong Research Grant Council.     

适应编程需要的一种动态规划模型解法

由计算机软件编程需要出发,对库存管理中的一种动态规划方法进行了讨论,推导出了统一规范表达的允许状态集合和允许决策集合,并由此给出了计算程序框图,为计算机处理类似问题提供了依据。     

大型动态规划的分解算法

An approach about large dynamic programming based on discrete linear system with a quadratic index function is proposed by importing two Lagrange multipliers.     

动态模糊规划模型的构建及应用

常规规划模型通常存在如下两种缺陷:首先,它的目标系数及约束条件都是在硬性限制下的确定值,因而在建模方面弹性小、硬度大;其次,它的目标系数与时间无关,因此不能有效地刻划时时刻刻变化着的目标系数,而动态模糊规划模型可以有效地解决上述缺陷.首先应用模糊动态AHP确定目标系数;然后根据L-R模糊数的强序关系准则,将动态模糊规划模型分解为最优与最劣两个模糊规划模型;再根据以α水平截集为基础的求解方法,将上述两个模型进行相应的转换,建立具有风险分析功能的动态模糊规划模型;最后将其应用到一个实际算例中,收到较好的结果.     

Generalized geometric programming applied to problems of optimal control: I. Theory

The interest in convexity in optimal control and the calculus of variations has gone through a revival in the past decade. In this paper, we extend the theory of generalized geometric programming to infinite dimensions in order to derive a dual problem for the convex optimal control problem. This approach transfers explicit constraints in the primal problem to the dual objective functional.The authors are indebted to the referees for suggestions leading to improvement of the paper.     

一类值型双层凸规划的Johri一般对偶

本文首先给出一类特殊的值型凸二次双层规划一其下层子规划只含有线性约束(简记为VBCP)；然后证明了一般形式的VBCP可以等价变换为非增值型凸二次双层规划的形式；最后给出该类双层规划VBCP的Johri对偶规划及其对偶性质．     

Existence of Neighboring Feasible Trajectories: Applications to Dynamic Programming for State-Constrained Optimal Control Problems

In this paper, the value function for an optimal control problem with endpoint and state constraints is characterized as the unique lower semicontinuous generalized solution of the Hamilton-Jacobi equation. This is achieved under a constraint qualification (CQ) concerning the interaction of the state and dynamic constraints. The novelty of the results reported here is partly the nature of (CQ) and partly the proof techniques employed, which are based on new estimates of the distance of the set of state trajectories satisfying a state constraint from a given trajectory which violates the constraint.     

A New Quadratic Semi-infinite Programming Algorithm Based on Dual Parametrization

The so called dual parameterization method for quadratic semi-infinite programming (SIP) problems is developed recently. A dual parameterization algorithm is also proposed for numerical solution of such problems. In this paper, we present and improved adaptive algorithm for quadratic SIP problems with positive definite objective and multiple linear infinite constraints. In each iteration of the new algorithm, only a quadratic programming problem with a limited dimension and a limited number of constraints is required to be solved. Furthermore, convergence result is given. The efficiency of the new algorithm is shown by solving a number of numerical examples.     

The Dual Active Set Algorithm and Its Application to Linear Programming

The Dual Active Set Algorithm (DASA), presented in Hager, Advances in Optimization and Parallel Computing, P.M. Pardalos (Ed.), North Holland: Amsterdam, 1992, pp. 137–142, for strictly convex optimization problems, is extended to handle linear programming problems. Line search versions of both the DASA and the LPDASA are given.     

Exact Algorithm for the Surrogate Dual of an Integer Programming Problem: Subgradient Method Approach

One of the critical issues in the effective use of surrogate relaxation for an integer programming problem is how to solve the surrogate dual within a reasonable amount of computational time. In this paper, we present an exact and efficient algorithm for solving the surrogate dual of an integer programming problem. Our algorithm follows the approach which Sarin et al. (Ref. 8) introduced in their surrogate dual multiplier search algorithms. The algorithms of Sarin et al. adopt an ad-hoc stopping rule in solving subproblems and cannot guarantee the optimality of the solutions obtained. Our work shows that this heuristic nature can actually be eliminated. Convergence proof for our algorithm is provided. Computational results show the practical applicability of our algorithm.