A multi-parametric programming approach for constrained dynamic programming problems

In this work, we present a new algorithm for solving complex multi-stage optimization problems involving hard constraints and uncertainties, based on dynamic and multi-parametric programming techniques. Each echelon of the dynamic programming procedure, typically employed in the context of multi-stage optimization models, is interpreted as a multi-parametric optimization problem, with the present states and future decision variables being the parameters, while the present decisions the corresponding optimization variables. This reformulation significantly reduces the dimension of the original problem, essentially to a set of lower dimensional multi-parametric programs, which are sequentially solved. Furthermore, the use of sensitivity analysis circumvents non-convexities that naturally arise in constrained dynamic programming problems. The potential application of the proposed novel framework to robust constrained optimal control is highlighted.     

Optimal Consumption in a Growth Model with the CES Production Function

Abstract

This article studies the optimization problem of maximizing the expected discounted present value of lifetime utility of consumption in the framework of one-sector neoclassical growth model with the Constant Elasticity of Substitution (CES) production function. We establish the existence of a classical solution of the Hamilton–Jacobi–Bellman (HJB) equation associated with this problem by the technique of viscosity solutions under the strict concavity of the utility function, and hence derive an optimal consumption from the optimality conditions in the HJB equation.     

Endogenous optimization fisheries models

This paper deals with a special class of fisheries models referred to as endogenous optimization models. The distinctive feature of these models is that behaviour of the agents in the model is not predetermined by exogenous behavioural rules. In endogenous optimization models, the model agents are merely furnished with objectives such as profit or utility maximization. Given these objectives and the various constraints determined by the state of the model at each point of time, the agents solve their maximization problem. The corresponding values of their control variables then constitute their behaviour.Having generated individual agents' behaviour by endogenous optimization, summing over agents yields aggregate behaviour. Aggregate behaviour must conform with the overall constraints of the model, be they physical or otherwise. Within the market system, individual behaviour or rather plans are made compatible via changes in relative prices. Therefore, outside equilibrium, behavioural plans must be repeatedly modified to become mutually compatible. This implies iteratively solving the maximization problem of a number of different agents. Endogenous optimization models therefore tend to be computationally very demanding.Clearly, the basic principles of endogenous optimization are just as applicable to any model involving maximizing agents.     

Computation of the optimal tolls on the traffic network

The present paper is devoted to the computation of optimal tolls on a traffic network that is described as fuzzy bilevel optimization problem. As a fuzzy bilevel optimization problem we consider bilinear optimization problem with crisp upper level and fuzzy lower level. An effective algorithm for computation optimal tolls for the upper level decision-maker is developed under assumption that the lower level decision-maker chooses the optimal solution as well. The algorithm is based on the membership function approach. This algorithm provides us with a global optimal solution of the fuzzy bilevel optimization problem.     

A semidefinite programming approach for solving fractional optimal control problems

This paper presents a numerical scheme for solving fractional optimal control. The fractional derivative in this problem is in the Riemann–Liouville sense. The proposed method, based upon the method of moments, converts the fractional optimal control problem to a semidefinite optimization problem; namely, the nonlinear optimal control problem is converted to a convex optimization problem. The Grunwald–Letnikov formula is also used as an approximation for fractional derivative. The solution of fractional optimal control problem is found by solving the semidefinite optimization problem. Finally, numerical examples are presented to show the performance of the method.     

A filled function method for optimal discrete-valued control problems

In this paper, we present a new approach to solve a class of optimal discrete-valued control problems. This type of problem is first transformed into an equivalent two-level optimization problem involving a combination of a discrete optimization problem and a standard optimal control problem. The standard optimal control problem can be solved by existing optimal control software packages such as MISER 3.2. For the discrete optimization problem, a discrete filled function method is developed to solve it. A numerical example is solved to illustrate the efficiency of our method.     

An Optimization Problem with a Separable Non-Convex Objective Function and a Linear Constraint

For a class of global optimization (maximization) problems, with a separable non-concave objective function and a linear constraint a computationally efficient heuristic has been developed.The concave relaxation of a global optimization problem is introduced. An algorithm for solving this problem to optimality is presented. The optimal solution of the relaxation problem is shown to provide an upper bound for the optimal value of the objective function of the original global optimization problem. An easily checked sufficient optimality condition is formulated under which the optimal solution of concave relaxation problem is optimal for the corresponding non-concave problem. An heuristic algorithm for solving the considered global optimization problem is developed.The considered global optimization problem models a wide class of optimal distribution of a unidimensional resource over subsystems to provide maximum total output in a multicomponent systems.In the presented computational experiments the developed heuristic algorithm generated solutions, which either met optimality conditions or had objective function values with a negligible deviation from optimality (less than 1/10 of a percent over entire range of problems tested).     

Value-Estimation Function Method for Constrained Global Optimization

A novel value-estimation function method for global optimization problems with inequality constraints is proposed in this paper. The value-estimation function formulation is an auxiliary unconstrained optimization problem with a univariate parameter that represents an estimated optimal value of the objective function of the original optimization problem. A solution is optimal to the original problem if and only if it is also optimal to the auxiliary unconstrained optimization with the parameter set at the optimal objective value of the original problem, which turns out to be the unique root of a basic value-estimation function. A logarithmic-exponential value-estimation function formulation is further developed to acquire computational tractability and efficiency. The optimal objective value of the original problem as well as the optimal solution are sought iteratively by applying either a generalized Newton method or a bisection method to the logarithmic-exponential value-estimation function formulation. The convergence properties of the solution algorithms guarantee the identification of an approximate optimal solution of the original problem, up to any predetermined degree of accuracy, within a finite number of iterations.     

Modelling and solving optimal placement problems in wireless sensor networks

In this work, the optimal sensor displacement problem in wireless sensor networks is addressed. It is assumed that a network, consisting of independent, collaborative and mobile nodes, is available. Starting from an initial configuration, the aim is to define a specific sensors displacement, which allows the network to achieve high performance, in terms of energy consumption and travelled distance. To mathematically represent the problem under study, different innovative optimization models are proposed and defined, by taking into account different performance objectives. An extensive computational phase is carried out in order to assess the behaviour of the developed models in terms of solution quality and computational effort. A comparison with distributed approaches is also given, by considering different scenarios.     

On an optimal shape design problem to control a thermoelastic deformation under a prescribed thermal treatment

A shape optimization problem concerned with thermal deformation of elastic bodies is considered. In this article, measure theory approach in function space is derived, resulting in an effective algorithm for the discretized optimization problem. First the problem is expressed as an optimal control problem governed by variational forms on a fixed domain. Then by using an embedding method, the class of admissible shapes is replaced by a class of positive Borel measures. The optimization problem in measure space is then approximated by a linear programming problem. The optimal measure representing optimal shape is approximated by the solution of this finite-dimensional linear programming problem. Numerical examples are also given.     

Scalarization of the fuzzy optimization problems

Scalarization of the fuzzy optimization problems using the embedding theorem and the concept of convex cone (ordering cone) is proposed in this paper. Two solution concepts are proposed by considering two convex cones. The set of all fuzzy numbers can be embedded into a normed space. This motivation naturally inspires us to invoke the scalarization techniques in vector optimization problems to solve the fuzzy optimization problems. By applying scalarization to the optimization problem with fuzzy coefficients, we obtain its corresponding scalar optimization problem. Finally, we show that the optimal solution of its corresponding scalar optimization problem is the optimal solution of the original fuzzy optimization problem.     

Fuzzy Optimization Problems Based on Ordering Cones

The solution concepts of the fuzzy optimization problems using ordering cone (convex cone) are proposed in this paper. We introduce an equivalence relation to partition the set of all fuzzy numbers into the equivalence classes. We then prove that this set of equivalence classes turns into a real vector space under the settings of vector addition and scalar multiplication. The notions of ordering cone and partial ordering on a vector space are essentially equivalent. Therefore, the optimality notions in the set of equivalence classes (in fact, a real vector space) can be naturally elicited by using the similar concept of Pareto optimal solution in vector optimization problems. Given an optimization problem with fuzzy coefficients, we introduce its corresponding (usual) optimization problem. Finally, we prove that the optimal solutions of its corresponding optimization problem are the Pareto optimal solutions of the original optimization problem with fuzzy coefficients.     

Successive Optimization Method via Parametric Monotone Composition Formulation*

In this paper a successive optimization method for solving inequality constrained optimization problems is introduced via a parametric monotone composition reformulation. The global optimal value of the original constrained optimization problem is shown to be the least root of the optimal value function of an auxiliary parametric optimization problem, thus can be found via a bisection method. The parametric optimization subproblem is formulated in such a way that it is a one-parameter problem and its value function is a monotone composition function with respect to the original objective function and the constraints. Various forms can be taken in the parametric optimization problem in accordance with a special structure of the original optimization problem, and in some cases, the parametric optimization problems are convex composite ones. Finally, the parametric monotone composite reformulation is applied to study local optimality.     

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.     

Extremal points and optimal solutions for general capacity problems

This paper studies the infinite dimensional linear programming problems in the integration type. The variable is taken in the space of bounded regular Borel measures on compact Hausdorff spaces. It will find an optimal measure for a constrained optimization problem, namely a capacity problem. Relations between extremal points of the feasible region and optimal solutions of the optimization problem are investigated. The necessary/sufficient conditions for a measure to be optimal are established. The algorithm for optimal solution of the general capacity problem onX = Y = [0, 1] is formulated.     

Exact penalty functions method for mathematical programming problems involving invex functions

In this paper, some new results on the exact penalty function method are presented. Simple optimality characterizations are given for the differentiable nonconvex optimization problems with both inequality and equality constraints via exact penalty function method. The equivalence between sets of optimal solutions in the original mathematical programming problem and its associated exact penalized optimization problem is established under suitable invexity assumption. Furthermore, the equivalence between a saddle point in the invex mathematical programming problem and an optimal point in its exact penalized optimization problem is also proved.     

双值约束非凸三次规化问题的全局最优性条件

考虑一类带有双值约束的非凸三次优化问题, 给出了该问题的一个全局最优充分必要条件. 结果改进并推广了一些文献中所给出的全局最优性条件, 同时还通过数值例子来说明所给出的全局最优充要条件是易验证的.     

Separations and Optimality of Constrained Multiobjective Optimization via Improvement Sets

In this paper, we investigate the separations and optimality conditions for the optimal solution defined by the improvement set of a constrained multiobjective optimization problem. We introduce a vector-valued regular weak separation function and a scalar weak separation function via a nonlinear scalarization function defined in terms of an improvement set. The nonlinear separation between the image of the multiobjective optimization problem and an improvement set in the image space is established by the scalar weak separation function. Saddle point type optimality conditions for the optimal solution of the multiobjective optimization problem are established, respectively, by the nonlinear and linear separation methods. We also obtain the relationships between the optimal solution and approximate efficient solution of the multiobjective optimization problem. Finally, sufficient and necessary conditions for the (regular) linear separation between the approximate image of the multiobjective optimization problem and a convex cone are also presented.     

Approximations of Relaxed Optimal Control Problems

In the present paper, we investigate an approximation technique for relaxed optimal control problems. We study control processes governed by ordinary differential equations in the presence of state, target, and integral constraints. A variety of approximation schemes have been recognized as powerful tools for the theoretical studying and practical solving of Infinite-dimensional optimization problems. On the other hand, theoretical approaches to the relaxed optimal control problem with constraints are not sufficiently advanced to yield numerically tractable schemes. The explicit approximation of the compact control set makes it possible to reduce the sophisticated relaxed problem to an auxiliary optimization problem. A given trajectory of the relaxed problem can be approximated by trajectories of the auxiliary problem. An optimal solution of the introduced optimization problem provides a basis for the construction of minimizing sequences for the original optimal control problem. We describe how to carry out the numerical calculations in the context of nonlinear programming and establish the convergence properties of the obtained approximations.The authors thank the referees for helpful comments and suggestions.     

Multiperiod portfolio optimization models in stochastic markets using the mean–variance approach

We consider several multiperiod portfolio optimization models where the market consists of a riskless asset and several risky assets. The returns in any period are random with a mean vector and a covariance matrix that depend on the prevailing economic conditions in the market during that period. An important feature of our model is that the stochastic evolution of the market is described by a Markov chain with perfectly observable states. Various models involving the safety-first approach, coefficient of variation and quadratic utility functions are considered where the objective functions depend only on the mean and the variance of the final wealth. An auxiliary problem that generates the same efficient frontier as our formulations is solved using dynamic programming to identify optimal portfolio management policies for each problem. Illustrative cases are presented to demonstrate the solution procedure with an interpretation of the optimal policies.