Lower bounds and duality in the optimal control of distributed systems

We develop a duality theory for problems of minimization of a convex functional on a convex set and apply this theory to optimal control problems with non-differentiable functional and state as well as control constraints. The dual problem is sometimes found to be simpler than the primal problem. The equivalence of the primal and the dual problem is established for problems in which the functional is strongly convex. A posteriori error are also given for such problems.     

Hidden Convex Minimization

A class of nonconvex minimization problems can be classified as hidden convex minimization problems. A nonconvex minimization problem is called a hidden convex minimization problem if there exists an equivalent transformation such that the equivalent transformation of it is a convex minimization problem. Sufficient conditions that are independent of transformations are derived in this paper for identifying such a class of seemingly nonconvex minimization problems that are equivalent to convex minimization problems. Thus, a global optimality can be achieved for this class of hidden convex optimization problems by using local search methods. The results presented in this paper extend the reach of convex minimization by identifying its equivalent with a nonconvex representation.     

Vector domain decomposition schemes for parabolic equations

A new class of domain decomposition schemes for finding approximate solutions of timedependent problems for partial differential equations is proposed and studied. A boundary value problem for a second-order parabolic equation is used as a model problem. The general approach to the construction of domain decomposition schemes is based on partition of unity. Specifically, a vector problem is set up for solving problems in individual subdomains. Stability conditions for vector regionally additive schemes of first- and second-order accuracy are obtained.     

Algorithm for verifying the equivalence of linear unary recursive programs on ordered semigroup scales

A new method for solving the problem of equivalence of linear unary recursive programs is proposed. The main idea behind this method is to reduce the equivalence problem to known problems on graphs and to problems in group theory. A class of program semantics is singled out for which the problem of the equivalence of the programs in question is solvable in polynomial time by the proposed method.     

Gradient-flow approach for computing a nonlinear-quadratic optimal-output feedback gain matrix

In this paper, an approach is proposed for solving a nonlinear-quadratic optimal regulator problem with linear static state feedback and infinite planning horizon. For such a problem, approximate problems are introduced and considered, which are obtained by combining a finite-horizon problem with an infinite-horizon linear problem in a certain way. A gradient-flow based algorithm is derived for these approximate problems. It is shown that an optimal solution to the original problem can be found as the limit of a sequence of solutions to the approximate problems. Several important properties are obtained. For illustration, two numerical examples are presented.This project was partially supported by a research grant from the Australian Research Council.     

Cost‐efficient monitoring of continuous‐time stochastic processes based on discrete observations

Planning a cost‐efficient monitoring policy of stochastic processes arises from many industrial problems. We formulate a simple discrete‐time monitoring problem of continuous‐time stochastic processes with its applications to several industrial problems. A key in our model is a doubling trick of the variables, with which we can construct an algorithm to solve the problem. The cost‐efficient monitoring policy balancing between the observation cost and information loss is governed by an optimality equation of a fixed point type, which is solvable with an iterative algorithm based on the Feynman‐Kac formula. This is a new linkage between monitoring problems and mathematical sciences. We show regularity results of the optimization problem and present a numerical algorithm for its approximation. A problem having model ambiguity is presented as well. The presented model is applied to problems of environment, ecology, and energy, having qualitatively different target stochastic processes with each other.     

Optimality Conditions for Nonregular Optimal Control Problems and Duality

We define a new class of optimal control problems and show that this class is the largest one of control problems where every admissible process that satisfies the Extended Pontryaguin Maximum Principle is an optimal solution of nonregular optimal control problems. In this class of problems the local and global minimum coincide. A dual problem is also proposed, which may be seen as a generalization of the Mond–Weir-type dual problem, and it is shown that the 2-invexity notion is a necessary and su?cient condition to establish weak, strong, and converse duality results between a nonregular optimal control problem and its dual problem. We also present an example to illustrate our results.     

特征值反问题的迭代解法

§1.引言 近年来,由于许多应用科学,如地球物理、海洋、地质、声学、光学、量子力学和识别等问题的需要,提出了特征值反问题和广义特征值反问题.这些问题形成一类区别于经典代数特征值问题的复杂非线性问题.这类问题中只有少量在理论上、数值上有一些求解的方法,前人的工作主要集中于sturm-Liouville反问题,见[1,2,3,4].本文讨论下列各种特征值反问题:     

On an effective solution of the Riemann problem for third order improperly elliptic equations

The paper considers a boundary value problem for a third order improperly elliptic equation. A numerical method that reduces this problem into six uniquely solvable problems is developed, and the finite differences method is applied to solve the resulting problems.     

A FEASIBLE DIRECTION ALGORITHM WITHOUT LINE SEARCH FOR SOLVING MAX-BISECTION PROBLEMS

This paper concerns the solution of the NP-hard max-bisection problems. NCP func-tions are employed to convert max-bisection problems into continuous nonlinear program-ming problems. Solving the resulting continuous nonlinear programming problem generatesa solution that gives an upper bound on the optimal value of the max-bisection problem.From the solution, the greedy strategy is used to generate a satisfactory approximate so-lution of the max-bisection problem. A feasible direction method without line searches isproposed to solve the resulting continuous nonlinear programming, and the convergenceof the algorithm to KKT point of the resulting problem is proved. Numerical experimentsand comparisons on well-known test problems, and on randomly generated test problemsshow that the proposed method is robust, and very efficient.     

Dynamic location problems

A class of dynamic location problems is introduced. The relationship between a static problem and its corresponding dynamic one is studied. We concentrate on two types of dynamic problems. The first is the global optimization problem, in which one looks for the all-times optimum. The second is the steady-state problem in which one seeks to determine the steady-state behavior of the system if one exists. General approaches to these problems are discussed.Supported in part by the National Science Foundation under grants MCS-8300984, ECS-8218181 and ECS-8121741.     

An algorithm and efficient data structures for the binary knapsack problem

A branch-and-bound algorithm for the binary knapsack problem is presented which uses a combined stack and deque for storing the tree and the corresponding LP-relaxation. A reduction scheme is used to reduce the problem size. The algorithm was implemented in FORTRAN. Computational experience is based on 600 randomly generated test problems with up to 9000 zero-one variables. The average solution times (excluding an initial sorting step) increase linearly with problem size and compare favorably with other codes designed to solve binary knapsack problems.     

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)     

Differential evolution framework for big data optimization

During the last two decades, dealing with big data problems has become a major issue for many industries. Although, in recent years, differential evolution has been successful in solving many complex optimization problems, there has been research gaps on using it to solve big data problems. As a real-time big data problem may not be known in advance, determining the appropriate differential evolution operators and parameters to use is a combinatorial optimization problem. Therefore, in this paper, a general differential evolution framework is proposed, in which the most suitable differential evolution algorithm for a problem on hand is adaptively configured. A local search is also employed to increase the exploitation capability of the proposed algorithm. The algorithm is tested on the 2015 big data optimization competition problems (six single objective problems and six multi-objective problems). The results show the superiority of the proposed algorithm to several state-of-the-art algorithms.     

Case-based reasoning for repetitive combinatorial optimization problems, part I: Framework

This article presents a case-based reasoning approach for the development of learning heuristics for solving repetitive operations research problems. We first define the subset of problems we will consider in this work: repetitive combinatorial optimization problems. We then present several general forms that can be used to select previously solved problems that might aid in the solution of the current problem, and several different techniques for actually using this information to derive a solution for the current problem. We describe both fixed forms and forms that have the ability to change as we solve more problems. A simple example for the 0–1 knapsack problem is presented.     

A Branch-and-Bound Approach for Solving a Class of Generalized Semi-infinite Programming Problems

A nonconvex generalized semi-infinite programming problem is considered, involving parametric max-functions in both the objective and the constraints. For a fixed vector of parameters, the values of these parametric max-functions are given as optimal values of convex quadratic programming problems. Assuming that for each parameter the parametric quadratic problems satisfy the strong duality relation, conditions are described ensuring the uniform boundedness of the optimal sets of the dual problems w.r.t. the parameter. Finally a branch-and-bound approach is suggested transforming the problem of finding an approximate global minimum of the original nonconvex optimization problem into the solution of a finite number of convex problems.     

Heuristic approaches to discrete-continuous project scheduling problems to minimize the makespan

In this paper some discrete-continuous project scheduling problems to minimize the makespan are considered. These problems are characterized by the fact that activities of a project simultaneously require for their execution discrete and continuous resources. A class of these problems is considered where the number of discrete resources is arbitrary, and one continuous, renewable, limited resource occurs. A methodology for solving the defined problems is presented. The continuous resource allocation problem is analyzed. An exact, as well as a heuristic approach to the problem is discussed. The idea of the continuous resource discretization is described, and a special case of the problem with identical processing rate functions is analyzed. Some computational experiments for evaluating the efficiency of the proposed heuristic approaches are presented. Conclusions and directions for future research are given.     

Bounded knapsack sharing

A bounded knapsack sharing problem is a maximin or minimax mathematical programming problem with one or more linear inequality constraints, an objective function composed of single variable continuous functions called tradeoff functions, and lower and upper bounds on the variables. A single constraint problem which can have negative or positive constraint coefficients and any type of continuous tradeoff functions (including multi-modal, multiple-valued and staircase functions) is considered first. Limiting conditions where the optimal value of a variable may be plus or minus infinity are explicitly considered. A preprocessor procedure to transform any single constraint problem to a finite form problem (an optimal feasible solution exists with finite variable values) is developed. Optimality conditions and three algorithms are then developed for the finite form problem. For piecewise linear tradeoff functions, the preprocessor and algorithms are polynomially bounded. The preprocessor is then modified to handle bounded knapsack sharing problems with multiple constraints. An optimality condition and algorithm is developed for the multiple constraint finite form problem. For multiple constraints, the time needed for the multiple constraint finite form algorithm is the time needed to solve a single constraint finite form problem multiplied by the number of constraints. Some multiple constraint problems cannot be transformed to multiple constraint finite form problems.