A constraint generation algorithm for large scale linear programs using multiple-points separation

In order to solve linear programs with a large number of constraints, constraint generation techniques are often used. In these algorithms, a relaxation of the formulation containing only a subset of the constraints is first solved. Then a separation procedure is called which adds to the relaxation any inequality of the formulation that is violated by the current solution. The process is iterated until no violated inequality can be found. In this paper, we present a separation procedure that uses several points to generate violated constraints. The complexity of this separation procedure and of some related problems is studied. Also, preliminary computational results about the advantages of using multiple-points separation procedures over traditional separation procedures are given for random linear programs and survivable network design. They illustrate that, for some specific families of linear programs, multiple-points separation can be computationally effective.     

Nondegenerate necessary conditions for nonlinear optimal control problems with higher-index state constraints

For some optimal control problems with pathwise state constraints the standard versions of the necessary conditions of optimality are unable to provide useful information to select minimizers. There exist some literature on stronger forms of the maximum principle, the so-called nondegenerate necessary conditions, that can be informative for those problems. These conditions can be applied when certain constraint qualifications are satisfied. However, when the state constraints have higher index (i.e. their first derivative with respect to time does not depend on the control) these nondegenerate necessary conditions cannot be used. This happens because constraint qualifications assumptions are never satisfied for higher index state constraints. We note that control problems with higher index state constraints arise frequently in practice. An example is a common mechanical systems for which there is a constraint on the position (an obstacle in the path, for example) and the control acts as a second derivative of the position (a force or acceleration) which is a typical case. Here, we provide a nondegenerate form of the necessary conditions that can be applied to nonlinear problems with higher index state constraints. When addressing a problem with a state constraint of index k, the result described is applicable under a constraint qualification that involves the k -th derivative of the state constraint, corresponding to the first time when derivative depends explicitly on the control. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A new method to control chaos in an economic system

In this paper, the method to control chaos by using phase space compression is applied to economic systems. Because of economic significance of state variable in economic dynamical systems, the values of state variables are positive due to capacity constraints and financial constraints, we can control chaos by adding upper bound or lower bound to state variables in economic dynamical systems, which is different from the chaos stabilization in engineering or physics systems. The knowledge about system dynamics and the exact variety of parameters are not needed in the application of this control method, so it is very convenient to apply this method. Two kinds of chaos in the dynamic duopoly output systems are stabilized in a neighborhood of an unstable fixed point by using the chaos controlling method. The results show that performance of the system is improved by controlling chaos. In practice, owing to capacity constraints, financial constraints and cautious responses to uncertainty in the world, the firm often restrains the output, advertisement expenses, research cost etc. to confine the range of these variables’ fluctuation. This shows that the decision maker uses this method unconsciously in practice.     

Linear Optimal Control Problems and Generalized Linear Programs

Linear optimal control problems with state inequality constraints is an important class of large systems. This paper shows that a generalized programming formulation of these problems does not result in a decomposition over time or a maximum principle as it does for problems without the state constraints. A semi-finite generalized programming formulation, however, can be used to formally produce the maximum principle, i.e. the necessary optimality conditions, for problems under consideration.     

Differential sensitivity of solutions of convex constrained optimal control problems for discrete systems

A family of optimal control problems for discrete systems that depend on a real parameter is considered. The problems are strongly convex and subject to state and control constraints. Some regularity conditions are imposed on the constraints.The control problems are reformulated as mathematical programming problems. It is shown that both the primal and dual optimal variables for these problems are right-differentiable functions of a parameter. The right-derivatives are characterized as solutions to auxiliary quadratic control problems. Conditions of continuous differentiability are discussed, and some estimates of the rate of convergence of the difference quotients to the respective derivatives are given.     

Recent advances in gradient algorithms for optimal control problems

This paper summarizes recent advances in the area of gradient algorithms for optimal control problems, with particular emphasis on the work performed by the staff of the Aero-Astronautics Group of Rice University. The following basic problem is considered: minimize a functionalI which depends on the statex(t), the controlu(t), and the parameter π. Here,I is a scalar,x ann-vector,u anm-vector, and π ap-vector. At the initial point, the state is prescribed. At the final point, the statex and the parameter π are required to satisfyq scalar relations. Along the interval of integration, the state, the control, and the parameter are required to satisfyn scalar differential equations. First, the sequential gradient-restoration algorithm and the combined gradient-restoration algorithm are presented. The descent properties of these algorithms are studied, and schemes to determine the optimum stepsize are discussed. Both of the above algorithms require the solution of a linear, two-point boundary-value problem at each iteration. Hence, a discussion of integration techniques is given. Next, a family of gradient-restoration algorithms is introduced. Not only does this family include the previous two algorithms as particular cases, but it allows one to generate several additional algorithms, namely, those with alternate restoration and optional restoration. Then, two modifications of the sequential gradient-restoration algorithm are presented in an effort to accelerate terminal convergence. In the first modification, the quadratic constraint imposed on the variations of the control is modified by the inclusion of a positive-definite weighting matrix (the matrix of the second derivatives of the Hamiltonian with respect to the control). The second modification is a conjugate-gradient extension of the sequential gradient-restoration algorithm. Next, the addition of a nondifferential constraint, to be satisfied everywhere along the interval of integration, is considered. In theory, this seems to be only a minor modification of the basic problem. In practice, the change is considerable in that it enlarges dramatically the number and variety of problems of optimal control which can be treated by gradient-restoration algorithms. Indeed, by suitable transformations, almost every known problem of optimal control theory can be brought into this scheme. This statement applies, for instance, to the following situations: (i) problems with control equality constraints, (ii) problems with state equality constraints, (iii) problems with equality constraints on the time rate of change of the state, (iv) problems with control inequality constraints, (v) problems with state inequality constraints, and (vi) problems with inequality constraints on the time rate of change of the state. Finally, the simultaneous presence of nondifferential constraints and multiple subarcs is considered. The possibility that the analytical form of the functions under consideration might change from one subarc to another is taken into account. The resulting formulation is particularly relevant to those problems of optimal control involving bounds on the control or the state or the time derivative of the state. For these problems, one might be unwilling to accept the simplistic view of a continuous extremal arc. Indeed, one might want to take the more realistic view of an extremal arc composed of several subarcs, some internal to the boundary being considered and some lying on the boundary. The paper ends with a section dealing with transformation techniques. This section illustrates several analytical devices by means of which a great number of problems of optimal control can be reduced to one of the formulations presented here. In particular, the following topics are treated: (i) time normalization, (ii) free initial state, (iii) bounded control, and (iv) bounded state.     

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.     

Hidden invariant convexity for global and conic-intersection optimality guarantees in discrete-time optimal control

Non-convex discrete-time optimal control problems in, e.g., water or power systems, typically involve a large number of variables related through nonlinear equality constraints. The ideal goal is to find a globally optimal solution, and numerical experience indicates that algorithms aiming for Karush–Kuhn–Tucker points often find solutions that are indistinguishable from global optima. In our paper, we provide a theoretical underpinning for this phenomenon, showing that on a broad class of problems the objective can be shown to be an invariant convex function (invex function) of the control decision variables when state variables are eliminated using implicit function theory. In this way, optimality guarantees can be obtained, the exact nature of which depends on the position of the solution within the feasible set. In a numerical example, we show how high-quality solutions are obtained with local search for a river control problem where invexity holds.

     

A lexicographic minimax algorithm for multiperiod resource allocation

Resource allocation problems are typically formulated as mathematical programs with some special structure that facilitates the development of efficient algorithms. We consider a multiperiod problem in which excess resources in one period can be used in subsequent periods. The objective minimizes lexicographically the nonincreasingly sorted vector of weighted deviations of cumulative activity levels from cumulative demands. To this end, we first develop a new minimax algorithm that minimizes the largest weighted deviation among all cumulative activity levels. The minimax algorithm handles resource constraints, ordering constraints, and lower and upper bounds. At each iteration, it fixes certain variables at their lower bounds, and sets groups of other variables equal to each other as long as no lower bounds are violated. The algorithm takes advantage of the problem's special structure; e.g., each term in the objective is a linear decreasing function of only one variable. This algorithm solves large problems very fast, orders of magnitude faster than well known linear programming packages. (The latter are, of course, not designed to solve such minimax problems efficiently.) The lexicographic procedure repeatedly employs the minimax algorithm described above to solve problems, each of the same format but with smaller dimension.     

Newsvendor-type models with decision-dependent uncertainty

Models for decision-making under uncertainty use probability distributions to represent variables whose values are unknown when the decisions are to be made. Often the distributions are estimated with observed data. Sometimes these variables depend on the decisions but the dependence is ignored in the decision maker??s model, that is, the decision maker models these variables as having an exogenous probability distribution independent of the decisions, whereas the probability distribution of the variables actually depend on the decisions. It has been shown in the context of revenue management problems that such modeling error can lead to systematic deterioration of decisions as the decision maker attempts to refine the estimates with observed data. Many questions remain to be addressed. Motivated by the revenue management, newsvendor, and a number of other problems, we consider a setting in which the optimal decision for the decision maker??s model is given by a particular quantile of the estimated distribution, and the empirical distribution is used as estimator. We give conditions under which the estimation and control process converges, and show that although in the limit the decision maker??s model appears to be consistent with the observed data, the modeling error can cause the limit decisions to be arbitrarily bad.     

An Exact Penalty Function Method for Continuous Inequality Constrained Optimal Control Problem

In this paper, we consider a class of optimal control problems subject to equality terminal state constraints and continuous state and control inequality constraints. By using the control parametrization technique and a time scaling transformation, the constrained optimal control problem is approximated by a sequence of optimal parameter selection problems with equality terminal state constraints and continuous state inequality constraints. Each of these constrained optimal parameter selection problems can be regarded as an optimization problem subject to equality constraints and continuous inequality constraints. On this basis, an exact penalty function method is used to devise a computational method to solve these optimization problems with equality constraints and continuous inequality constraints. The main idea is to augment the exact penalty function constructed from the equality constraints and continuous inequality constraints to the objective function, forming a new one. This gives rise to a sequence of unconstrained optimization problems. It is shown that, for sufficiently large penalty parameter value, any local minimizer of the unconstrained optimization problem is a local minimizer of the optimization problem with equality constraints and continuous inequality constraints. The convergent properties of the optimal parameter selection problems with equality constraints and continuous inequality constraints to the original optimal control problem are also discussed. For illustration, three examples are solved showing the effectiveness and applicability of the approach proposed.     

Ensuring service levels in routing problems with time windows and stochastic travel times

In the stochastic variant of the vehicle routing problem with time windows, known as the SVRPTW, travel times are assumed to be stochastic. In our chance-constrained approach to the problem, restrictions are placed on the probability that individual time window constraints are violated, while the objective remains based on traditional routing costs. In this paper, we propose a way to offer this probability, or service level, for all customers. Our approach carefully considers how to compute the start-service time and arrival time distributions for each customer. These distributions are used to create a feasibility check that can be “plugged” into any algorithm for the VRPTW and thus be used to solve large problems fairly quickly. Our computational experiments show how the solutions change for some well-known data sets across different levels of customer service, two travel time distributions, and several parameter settings.     

Quadratic weak-minimum conditions for optimal control problems with intermediate constraints

Optimal control problems with constraints at intermediate trajectory points are considered. By using a certain natural method (of reproduction of state and control variables), these problems reduce to the standard optimal control problem of Pontryagin type, which allows one to obtain quadratic weak-minimum conditions for them.     

A Discrete Lagrangian-Based Global-Search Method for Solving Satisfiability Problems

Satisfiability is a class of NP-complete problems that model a wide range of real-world applications. These problems are difficult to solve because they have many local minima in their search space, often trapping greedy search methods that utilize some form of descent. In this paper, we propose a new discrete Lagrange-multiplier-based global-search method (DLM) for solving satisfiability problems. We derive new approaches for applying Lagrangian methods in discrete space, we show that an equilibrium is reached when a feasible assignment to the original problem is found and present heuristic algorithms to look for equilibrium points. Our method and analysis provides a theoretical foundation and generalization of local search schemes that optimize the objective alone and penalty-based schemes that optimize the constraints alone. In contrast to local search methods that restart from a new starting point when a search reaches a local trap, the Lagrange multipliers in DLM provide a force to lead the search out of a local minimum and move it in the direction provided by the Lagrange multipliers. In contrast to penalty-based schemes that rely only on the weights of violated constraints to escape from local minima, DLM also uses the value of an objective function (in this case the number of violated constraints) to provide further guidance. The dynamic shift in emphasis between the objective and the constraints, depending on their relative values, is the key of Lagrangian methods. One of the major advantages of DLM is that it has very few algorithmic parameters to be tuned by users. Besides the search procedure can be made deterministic and the results reproducible. We demonstrate our method by applying it to solve an extensive set of benchmark problems archived in DIMACS of Rutgers University. DLM often performs better than the best existing methods and can achieve an order-of-magnitude speed-up for some problems.     

Numerical computation of singular control problems with application to optimal heating and cooling by solar energy

The method presented here is an extension of the multiple shooting algorithm in order to handle multipoint boundary-value problems and problems of optimal control in the special situation of singular controls or constraints on the state variables. This generalization allows a direct treatment of (nonlinear) conditions at switching points. As an example a model of optimal heating and cooling by solar energy is considered. The model is given in the form of an optimal control problem with three control functions appearing linearly and a first order constraint on the state variables. Numerical solutions of this problem by multiple shooting techniques are presented.     

Some branch and bound techniques for nonlinear optimization

The range of nonlinear optimization problems which can be solved by Linear Programming and the Branch and Bound algorithm is extended by introducing Chains of Linked Ordered Sets and by allowing automatic interpolation of new variables. However this approach involves solving a succession of linear subproblems, whose solutions in general violate the logical requirements of the nonlinear formulation and may lie far from any local or global optimum. The paper describes techniques which are designed to improve the performance of the Branch and Bound algorithm on problems containing chains, and which also yield benefits in integer programming.Each linear subproblem is tightened towards the corresponding nonlinear problem by removing variables which must logically be nonbasic in any feasible solution. This is achieved by a presolve procedure, and also by post-optimal Lagrangian relaxation which tightens the bound on the objective function by assessing the cheapest way to satisfy any violated chain constraints. Frequently fewer subsequent branches are required to find a feasible solution or to prove infeasibility.Formerly of Scicon Ltd.     

Simulated annealing with asymptotic convergence for nonlinear constrained optimization

In this paper, we present constrained simulated annealing (CSA), an algorithm that extends conventional simulated annealing to look for constrained local minima of nonlinear constrained optimization problems. The algorithm is based on the theory of extended saddle points (ESPs) that shows the one-to-one correspondence between a constrained local minimum and an ESP of the corresponding penalty function. CSA finds ESPs by systematically controlling probabilistic descents in the problem-variable subspace of the penalty function and probabilistic ascents in the penalty subspace. Based on the decomposition of the necessary and sufficient ESP condition into multiple necessary conditions, we present constraint-partitioned simulated annealing (CPSA) that exploits the locality of constraints in nonlinear optimization problems. CPSA leads to much lower complexity as compared to that of CSA by partitioning the constraints of a problem into significantly simpler subproblems, solving each independently, and resolving those violated global constraints across the subproblems. We prove that both CSA and CPSA asymptotically converge to a constrained global minimum with probability one in discrete optimization problems. The result extends conventional simulated annealing (SA), which guarantees asymptotic convergence in discrete unconstrained optimization, to that in discrete constrained optimization. Moreover, it establishes the condition under which optimal solutions can be found in constraint-partitioned nonlinear optimization problems. Finally, we evaluate CSA and CPSA by applying them to solve some continuous constrained optimization benchmarks and compare their performance to that of other penalty methods.     

The Mayer and Minimum Time Problems with Stratified State Constraints

This paper studies optimal control problems with state constraints by imposing structural assumptions on the constraint domain coupled with a tangential restriction with the dynamics. These assumptions replace pointing or controllability assumptions that are common in the literature, and provide a framework under which feasible boundary trajectories can be analyzed directly. The value functions associated with the state constrained Mayer and minimal time problems are characterized as solutions to a pair of Hamilton-Jacobi inequalities with appropriate boundary conditions. The novel feature of these inequalities lies in the choice of the Hamiltonian.     

An LP approach to dynamic programming principles for stochastic control problems with state constraints

We study a class of nonlinear stochastic control problems with semicontinuous cost and state constraints using a linear programming (LP) approach. First, we provide a primal linearized problem stated on an appropriate space of probability measures with support contained in the set of constraints. This space is completely characterized by the coefficients of the control system. Second, we prove a semigroup property for this set of probability measures appearing in the definition of the primal value function. This leads to dynamic programming principles for control problems under state constraints with general (bounded) costs. A further linearized DPP is obtained for lower semicontinuous costs.     

Real-Time Solution of Bi-Level Optimal Control Problems

Bi-level optimal control problems are presented as an extension to classical optimal control problems. Hereby, additional constraints for the primary problem are considered, which depend on the optimal solution of a secondary optimal control problem. A demanding problem is the numerical complexity, since at any point in time the solution of the optimal control problem as well as a complete solution of the secondary problem have to be determined. Hence we deal with two dependent variables in time. The numerical solution of the bi-level problem is illustrated by an application of a container crane. Jerk and energy optimal trajectories with free final time are calculated under the terminal condition that the crane system comes to be at rest at a predefined location. In enlargement additional constraints are investigated to ensure that the crane system can be brought to a rest position by a safety stop at a free but admissible location in minimal time from any state of the trajectory. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)