Optimization Techniques for State-Constrained Control and Obstacle Problems

The design of control laws for systems subject to complex state constraints still presents a significant challenge. This paper explores a dynamic programming approach to a specific class of such problems, that of reachability under state constraints. The problems are formulated in terms of nonstandard minmax and maxmin cost functionals, and the corresponding value functions are given in terms of Hamilton-Jacobi-Bellman (HJB) equations or variational inequalities. The solution of these relations is complicated in general; however, for linear systems, the value functions may be described also in terms of duality relations of convex analysis and minmax theory. Consequently, solution techniques specific to systems with a linear structure may be designed independently of HJB theory. These techniques are illustrated through two examples.The first author was supported by the Russian Foundation for Basic Research, Grant 03-01-00663, by the program Universities of Russia, Grant 03.03.007, and by the program of the Russian Federation President for the support of scientific research in leading scientific schools, Grant NSh-1889.2003.1.The second author was supported by the National Science and Engineering Research Council of Canada and by ONR MURI Contract 79846-23800-44-NDSAS.The third and first authors were supported by NSF Grants ECS-0099824 and ECS-0424445.Communicated by G. Leitmann     

Representation of the Lagrange Multipliers for Optimal Control Problems Subject to Differential-Algebraic Equations of Index Two

Necessary conditions are derived for optimal control problems subject to index-2 differential-algebraic equations, pure state constraints, and mixed control-state constraints. Differential-algebraic equations are composite systems of differential equations and algebraic equations, which arise frequently in practical applications. The structure of the optimal control problem under consideration is exploited and special emphasis is laid on the representation of the Lagrange multipliers resulting from the necessary conditions for infinite optimization problems.The author thanks the referees for careful reading and helpful suggestions and comments.     

Numerical solution of minimax optimal control problems by multiple shooting technique

This paper presents the application of the multiple shooting technique to minimax optimal control problems (optimal control problems with Chebyshev performance index). A standard transformation is used to convert the minimax problem into an equivalent optimal control problem with state variable inequality constraints. Using this technique, the highly developed theory on the necessary conditions for state-restricted optimal control problems can be applied advantageously. It is shown that, in general, these necessary conditions lead to a boundary-value problem with switching conditions, which can be treated numerically by a special version of the multiple shooting algorithm. The method is tested on the problem of the optimal heating and cooling of a house. This application shows some typical difficulties arising with minimax optimal control problems, i.e., the estimation of the switching structure which is dependent on the parameters of the problem. This difficulty can be overcome by a careful application of a continuity method. Numerical solutions for the example are presented which demonstrate the efficiency of the method proposed.     

A Population-based Approach for Hard Global Optimization Problems based on Dissimilarity Measures

When dealing with extremely hard global optimization problems, i.e. problems with a large number of variables and a huge number of local optima, heuristic procedures are the only possible choice. In this situation, lacking any possibility of guaranteeing global optimality for most problem instances, it is quite difficult to establish rules for discriminating among different algorithms. We think that in order to judge the quality of new global optimization methods, different criteria might be adopted like, e.g.:

Optimization Techniques for Solving Elliptic Control Problems with Control and State Constraints: Part 1. Boundary Control

We study optimal control problems for semilinear elliptic equations subject to control and state inequality constraints. In a first part we consider boundary control problems with either Dirichlet or Neumann conditions. By introducing suitable discretization schemes, the control problem is transcribed into a nonlinear programming problem. It is shown that a recently developed interior point method is able to solve these problems even for high discretizations. Several numerical examples with Dirichlet and Neumann boundary conditions are provided that illustrate the performance of the algorithm for different types of controls including bang-bang and singular controls. The necessary conditions of optimality are checked numerically in the presence of active control and state constraints.     

Shooting method for the numerical solution of optimal control problems with bounded state variables

Abtract Various methods have been proposed for the numerical solution of optimal control problems with bounded state variables. In this paper, a new method is put forward and compared with two other methods, one of which makes use of adjoint variables whereas the other does not. Some conclusions are drawn on the usefulness of the three methods involved.     

Local Minimum Principle for Optimal Control Problems Subject to Differential-Algebraic Equations of Index Two

Necessary conditions in terms of a local minimum principle are derived for optimal control problems subject to index-2 differential-algebraic equations, pure state constraints, and mixed control-state constraints. Differential-algebraic equations are composite systems of differential equations and algebraic equations, which arise frequently in practical applications. The local minimum principle is based on the necessary optimality conditions for general infinite optimization problems. The special structure of the optimal control problem under consideration is exploited and allows us to obtain more regular representations for the multipliers involved. An additional Mangasarian-Fromowitz-like constraint qualification for the optimal control problem ensures the regularity of a local minimum. An illustrative example completes the article.The author thanks the referees for careful reading and helpful suggestions and comments.     

八阶奇异边值问题精确解的表达形式

该文在再生核空间W_2~9[0,1]中给出了求解八阶奇异边值问题的新算法.方程的精确解以级数形式给出.算例及数值结果验证了方法的实用性和有效性.     

Spline Techniques for the Numerical Solution of Singular Perturbation Problems

One-dimensional singularly-perturbed two-point boundary-value problems arising in various fields of science and engineering (for instance, fluid mechanics, quantum mechanics, optimal control, chemical reactor theory, aerodynamics, reaction-diffusion processes, geophysics, etc.) are treated. Either these problems exhibits boundary layer(s) at one or both ends of the underlying interval or they possess oscillatory behavior depending on the nature of the coefficient of the first derivative term. Some spline difference schemes are derived for these problems using splines in compression and splines in tension. Second-order uniform convergence is achieved for both kind of schemes. By making use of the continuity of the first-order derivative of the spline function, a tridiagonal system is obtained which can be solved efficiently by well-known algorithms. Numerical examples are given to illustrate the theory.     

带约束条件集值优化问题近似Henig有效解集的连通性

研究了带约束条件集值优化问题近似Henig有效解集的连通性.在实局部凸Hausdorff空间中,讨论了可行域为弧连通紧的,目标函数为C-弧连通的条件下,带约束条件集值优化问题近似Henig有效解集的存在性和连通性.并给出了带约束条件集值优化问题近似Henig有效解集的连通性定理.     

集值映射向量优化问题的锥弱有效解的镇定性和稳定性(英文)

本文研究了集值映射向量优化问题的锥弱有效解的镇定性和稳定性,我们引进了集值映射向量优化问题的镇定性和稳定性的定义,并证明了集值映射向量优化问题的镇定性和稳定性的一些主要定理.     

基于非拟牛顿方法无约束最优化问题的全局收敛性

In this paper, the non-quasi-Newton's family with inexact line search applied to unconstrained optimization problems is studied. A new update formula for non-quasi-Newton's family is proposed. It is proved that the constituted algorithm with either Wolfe-type or Armijotype line search converges globally and Q-superlinearly if the function to be minimized has Lipschitz continuous gradient.     

A Numerical Evaluation of Several Stochastic Algorithms on Selected Continuous Global Optimization Test Problems

There is a need for a methodology to fairly compare and present evaluation study results of stochastic global optimization algorithms. This need raises two important questions of (i) an appropriate set of benchmark test problems that the algorithms may be tested upon and (ii) a methodology to compactly and completely present the results. To address the first question, we compiled a collection of test problems, some are better known than others. Although the compilation is not exhaustive, it provides an easily accessible collection of standard test problems for continuous global optimization. Five different stochastic global optimization algorithms have been tested on these problems and a performance profile plot based on the improvement of objective function values is constructed to investigate the macroscopic behavior of the algorithms. The paper also investigates the microscopic behavior of the algorithms through quartile sequential plots, and contrasts the information gained from these two kinds of plots. The effect of the length of run is explored by using three maximum numbers of function evaluations and it is shown to significantly impact the behavior of the algorithms.     

Selective Search for Global Optimization of Zero or Small Residual Least-Squares Problems: A Numerical Study

In this paper, we consider approximating global minima of zero or small residual, nonlinear least-squares problems. We propose a selective search approach based on the concept of selective minimization recently introduced in Zhang et al. (Technical Report TR99-12, Rice University, Department of Computational and Applied Mathematics MS-134, Houston, TX 77005, 1999). To test the viability of the proposed approach, we construct a simple implementation using a Levenberg-Marquardt type method combined with a multi-start scheme, and compare it with several existing global optimization techniques. Numerical experiments were performed on zero residual nonlinear least-squares problems chosen from structural biology applications and from the literature. On the problems of significant sizes, the performance of the new approach compared favorably with other tested methods, indicating that the new approach is promising for the intended class of problems.     

Studying the Complexity of Global Verification for NP-Hard Discrete Optimization Problems

This paper examines the complexity of global verification for MAX-SAT, MAX-k-SAT (for k3), Vertex Cover, and Traveling Salesman Problem. These results are obtained by adaptations of the transformations that prove such problems to be NP-complete. The class of problems PGS is defined to be those discrete optimization problems for which there exists a polynomial time algorithm such that given any solution , either a solution can be found with a better objective function value or it can be concluded that no such solution exists and is a global optimum. This paper demonstrates that if any one of MAX-SAT, MAX-k-SAT (for k3), Vertex Cover, or Traveling Salesman Problem are in PGS, then P=NP.     

Stochastic Method for the Solution of Unconstrained Vector Optimization Problems

We propose a new stochastic algorithm for the solution of unconstrained vector optimization problems, which is based on a special class of stochastic differential equations. An efficient algorithm for the numerical solution of the stochastic differential equation is developed. Interesting properties of the algorithm enable the treatment of problems with a large number of variables. Numerical results are given.     

Verification of Second-Order Sufficient Optimality Conditions for Semilinear Elliptic and Parabolic Control Problems

We study optimal control problems for semilinear parabolic equations subject to control constraints and for semilinear elliptic equations subject to control and state constraints. We quote known second-order sufficient optimality conditions (SSC) from the literature. Both problem classes, the parabolic one with boundary control and the elliptic one with boundary or distributed control, are discretized by a finite difference method. The discrete SSC are stated and numerically verified in all cases providing an indication of optimality where only necessary conditions had been studied before.     

A Controlled Random Search Technique Incorporating the Simulated Annealing Concept for Solving Integer and Mixed Integer Global Optimization Problems

In this paper, a computational algorithm, named RST2ANU algorithm, has been developed for solving integer and mixed integer global optimization problems. This algorithm, which primarily is based on the original controlled random search approach of Price [22i], incorporates a simulated annealing type acceptance criterion in its working so that not only downhill moves but also occasional uphill moves can be accepted. In its working it employs a special truncation procedure which not only ensures that the integer restrictions imposed on the decision variables are satisfied, but also creates greater possibilities for the search leading to a global optimal solution. The reliability and efficiency of the proposed RST2ANU algorithm has been demonstrated on thirty integer and mixed integer optimization problems taken from the literature. The performance of the algorithm has been compared with the performance of the corresponding purely controlled random search based algorithm as well as the standard simulated annealing algorithm. The performance of the method on mathematical models of three realistic problems has also been demonstrated.     

三阶微分方程边值问题的高效数值算法

基于再生核空间法提出了一个高效的数值算法来解决三阶微分方程的边值问题.利用再生性以及正交基的构造,得到了模型精确解的级数表示形式,并通过截断级数获得了其近似解.通过数值算例说明了此方法的有效性.