Lossless convexification of a class of optimal control problems with non-convex control constraints

We consider a class of finite time horizon optimal control problems for continuous time linear systems with a convex cost, convex state constraints and non-convex control constraints. We propose a convex relaxation of the non-convex control constraints, and prove that the optimal solution of the relaxed problem is also an optimal solution for the original problem, which is referred to as the lossless convexification of the optimal control problem. The lossless convexification enables the use of interior point methods of convex optimization to obtain globally optimal solutions of the original non-convex optimal control problem. The solution approach is demonstrated on a number of planetary soft landing optimal control problems.     

On the open-loop solution of linear stochastic optimal control problems

We consider open-loop solutions of linear stochastic optimal control problems with constraints on control variables and probabilistic constraints on state variables. It is shown that this problem reduces to an equivalent linear deterministic optimal control problem with similar constraints and with a new criterion to minimize. Concavity or convexity is preserved. Hence, the machinery available for solving deterministic optimal control problems can be used to get an open-loop solution of the stochastic problem. The convex case is investigated and a bound on the difference between closed-loop and open-loop optimal costs is given.     

DC optimization approach to robust controls: the optimal scaling value problem

The optimal scaling problem (OSP) for constant scaling in output feedback control is an inherently difficult nonconvex problem for which in general existing local search algorithms can at best locate a local solution. However, it can be restated as a problem of globally minimizing a convex function under DC constraints, i.e., constraints that can be expressed in terms of differences of convex functions. A particular structure of this DC optimization problem is that it becomes convex when a relatively small number of "complicating" variables are held fixed. We propose alternative branch and bound algorithms for OSP, which exploit this structure by branching upon the complicating variables and use adaptive sub-division strategies to speed-up the convergence to the global solution.     

Service Time Optimization of Mixed-Line Flow Shop Systems

We consider deterministic mixed-line flow shop systems that are composed of controllable and uncontrollable machines. Arrival times and completion deadlines of jobs are assumed to be known, and they are processed in the order they arrive at the machines. We model these flow shops as serial networks of queues operating under a non-preemptive first-come-first-served policy, and employ max-plus algebra to characterize the system dynamics. Defining completion-time costs for jobs and service costs at controllable machines, a non-convex optimization problem is formulated where the control variables are the constrained service times at the controllable machines. In order to simplify this optimization problem, under some cost assumptions, we show that no waiting is observed on the optimal sample path at the downstream of the first controllable machine. We also present a method to decompose the optimization problem into convex subproblems. A solution algorithm utilizing these findings is proposed, and a numerical study is presented to evaluate the performance improvement due to this algorithm.      

Optimization of a Flow Shop System of Initially Controllable Machines

We consider an optimization problem for deterministic flow shop systems of traditional machines with service costs penalizing small service times. A regular completion-time cost is also included so as to complete jobs as early as possible. The service times are assumed to be initially controllable, i.e., they are set at the startup time. Assuming convexity of the cost functions, we formulate a convex optimization problem after linearization of the max constraints. The numeric solution of this problem demands a large memory limiting the solvable system sizes. In order to relieve the memory bottleneck, some waiting characteristics of jobs served in fixed-service-time flow shop systems are exploited to result in a simpler equivalent convex optimization problem. These characteristics and the benefit of CNC machines are demonstrated in a numerical example. We also show that the simplifications result in significant improvements in solvable system sizes and solution times.      

Controller design with multiple objectives

In this paper we study multi-objective control problems that give rise to equivalent convex optimization problems. We develop a uniform treatment of such problems by showing their equivalence to linear programming problems with equality constraints and an appropriate positive cone. We present some specialized results on duality theory, and we apply them to the study of three multi-objective control problems: the optimal l₁ control with time-domain constraints on the response to some fixed input, the mixed H₂/l₁ -control problem, and the l₁ control with magnitude constraint on the frequency response. What makes these problems complicated is that they are often equivalent to infinite-dimensional optimization problems. The characterization of the duality relationship between the primal and dual problem allows us to derive several results. These results establish connections with special convex problems (linear programming or linear matrix inequality problems), uncover finite-dimensional structures in the optimal solution, when possible, and provide finite-dimensional approximations to any degree of accuracy when the problem does not appear to have a finite-dimensional structure. To illustrate the theory and highlight its potential, several numerical examples are presented     

State-dependent Control of a Single Stage Hybrid System with Poisson Arrivals

We consider a single-stage hybrid manufacturing system where jobs arrive according to a Poisson process. These jobs undergo a deterministic process which is controllable. We define a stochastic hybrid optimal control problem and decompose it hierarchically to a lower-level and a higher-level problem. The lower-level problem is a deterministic optimal control problem solved by means of calculus of variations. We concentrate on the stochastic discrete-event control problem at the higher level, where the objective is to determine the service times of jobs. Employing a cost structure composed of process costs that are decreasing and strictly convex in service times, and system-time costs that are linear in system times, we show that receding horizon controllers are state-dependent controllers, where state is defined as the system size. In order to improve upon receding horizon controllers, we search for better state-dependent control policies and present two methods to obtain them. These stochastic-approximation-type methods utilize gradient estimators based on Infinitesimal Perturbation Analysis or Imbedded Markov Chain techniques. A numerical example demonstrates the performance improvements due to the proposed methods.     

The scenario approach to robust control design

This paper proposes a new probabilistic solution framework for robust control analysis and synthesis problems that can be expressed in the form of minimization of a linear objective subject to convex constraints parameterized by uncertainty terms. This includes the wide class of NP-hard control problems representable by means of parameter-dependent linear matrix inequalities (LMIs). It is shown in this paper that by appropriate sampling of the constraints one obtains a standard convex optimization problem (the scenario problem) whose solution is approximately feasible for the original (usually infinite) set of constraints, i.e., the measure of the set of original constraints that are violated by the scenario solution rapidly decreases to zero as the number of samples is increased. We provide an explicit and efficient bound on the number of samples required to attain a-priori specified levels of probabilistic guarantee of robustness. A rich family of control problems which are in general hard to solve in a deterministically robust sense is therefore amenable to polynomial-time solution, if robustness is intended in the proposed risk-adjusted sense.     

Distributed Multi-Parametric Quadratic Programming

One of the fundamental problems in the area of large-scale optimization is to study locality features of spatially distributed optimization problems in which the variables are coupled in the cost function as well as constraints. Such problems can motivate the development of fast and well-conditioned distributed algorithms. In this paper, we study spatial locality features of large-scale multi-parametric quadratic programming (MPQP) problems with linear inequality constraints. Our main application focus is receding horizon control of spatially distributed linear systems with input and state constraints. We propose a new approach for analysis of large-scale MPQP problems by blending tools from duality theory with operator theory. The class of spatially decaying matrices is introduced to capture couplings between optimization variables in the cost function and the constraints. We show that the optimal solution of a convex MPQP is piecewise affine- represented as convolution sums. More importantly, we prove that the kernel of each convolution sum decays in the spatial domain at a rate proportional to the inverse of the corresponding coupling function of the optimization problem.     

Control Liapunov function design of neural networks that solve convex optimization and variational inequality problems

This paper presents two neural networks to find the optimal point in convex optimization problems and variational inequality problems, respectively. The domain of the functions that define the problems is a convex set, which is determined by convex inequality constraints and affine equality constraints. The neural networks are based on gradient descent and exact penalization and the convergence analysis is based on a control Liapunov function analysis, since the dynamical system corresponding to each neural network may be viewed as a so-called variable structure closed loop control system.     

A characterization of convex problems in decentralized control

We consider the problem of constructing optimal decentralized controllers. We formulate this problem as one of minimizing the closed-loop norm of a feedback system subject to constraints on the controller structure. We define the notion of quadratic invariance of a constraint set with respect to a system, and show that if the constraint set has this property, then the constrained minimum-norm problem may be solved via convex programming. We also show that quadratic invariance is necessary and sufficient for the constraint set to be preserved under feedback. These results are developed in a very general framework, and are shown to hold in both continuous and discrete time, for both stable and unstable systems, and for any norm. This notion unifies many previous results identifying specific tractable decentralized control problems, and delineates the largest known class of convex problems in decentralized control. As an example, we show that optimal stabilizing controllers may be efficiently computed in the case where distributed controllers can communicate faster than their dynamics propagate. We also show that symmetric synthesis is included in this classification, and provide a test for sparsity constraints to be quadratically invariant, and thus amenable to convex synthesis.     

A characterization of convex problems in decentralized Control/sup */

We consider the problem of constructing optimal decentralized controllers. We formulate this problem as one of minimizing the closed-loop norm of a feedback system subject to constraints on the controller structure. We define the notion of quadratic invariance of a constraint set with respect to a system, and show that if the constraint set has this property, then the constrained minimum-norm problem may be solved via convex programming. We also show that quadratic invariance is necessary and sufficient for the constraint set to be preserved under feedback. These results are developed in a very general framework, and are shown to hold in both continuous and discrete time, for both stable and unstable systems, and for any norm. This notion unifies many previous results identifying specific tractable decentralized control problems, and delineates the largest known class of convex problems in decentralized control. As an example, we show that optimal stabilizing controllers may be efficiently computed in the case where distributed controllers can communicate faster than their dynamics propagate. We also show that symmetric synthesis is included in this classification, and provide a test for sparsity constraints to be quadratically invariant, and thus amenable to convex synthesis.     

Convex Control Systems and Convex Optimal Control Problems With Constraints

This note discusses the concepts of convex control systems and convex optimal control problems. We study control systems governed by ordinary differential equations in the presence of state and target constraints. Our note is devoted to the following main question: under which additional assumptions is a "sophisticated" constrained optimal control problem equivalent to a "simple" convex minimization problem in a related Hilbert space. We determine some classes of convex control systems and show that, for suitable cost functionals and constraints, optimal control problems for these classes of systems correspond to convex optimization problems. The latter can be reliably solved using standard numerical algorithms and effective regularization schemes. In particular, we propose a conceptual computational approach based on gradient-type methods and proximal point techniques.     

An exact solution to general four-block discrete-time mixed ℋ2/ℋ∞ problems via convex optimization

The mixed ℋ₂ℋ_∞ control problem can be motivated as a nominal LQG optimal control problem subject to robust stability constraints, expressed in the form of an ℋ_∞ norm bound. This paper contains a solution to a general four-block mixed ℋ₂/ℋ_∞ problem, based upon constructing a family of approximating problems. Each one of these problems consists of a finite-dimensional convex optimization and an unconstrained standard ℋ_∞ problem. The set of solutions is such that in the limit the performance of the optimal controller is recovered, allowing one to establish the existence of an optimal solution. Although the optimal controller is not necessarily finite-dimensional, it is shown that a performance arbitrarily close to the optimal can be achieved with rational controllers. Moreover, the computation of a controller yielding a performance ϵ-away from optimal requires the solution of a single optimization problem, a task that can be accomplished in polynomial time     

Output feedback receding horizon control of constrained systems

This paper considers output feedback control of linear discrete-time systems with convex state and input constraints which are subject to bounded state disturbances and output measurement errors. We show that the non-convex problem of finding a constraint admissible affine output feedback policy over a finite horizon, to be used in conjunction with a fixed linear state observer, can be converted to an equivalent convex problem. When used in the design of a time-varying robust receding horizon control law, we derive conditions under which the resulting closed-loop system is guaranteed to satisfy the system constraints for all time, given an initial state estimate and bound on the state estimation error. When the state estimation error bound matches the minimal robust positively invariant (mRPI) set for the system error dynamics, we show that this control law is time-invariant, but its calculation generally requires solution of an infinite-dimensional optimization problem. Finally, using an invariant outer approximation to the mRPI error set, we develop a time-invariant control law that can be computed by solving a finite-dimensional tractable optimization problem at each time step that guarantees that the closed-loop system satisfies the constraints for all time.     

Convexity and convex approximations of discrete-time stochastic control problems with constraints

We investigate constrained optimal control problems for linear stochastic dynamical systems evolving in discrete time. We consider minimization of an expected value cost subject to probabilistic constraints. We study the convexity of a finite-horizon optimization problem in the case where the control policies are affine functions of the disturbance input. We propose an expectation-based method for the convex approximation of probabilistic constraints with polytopic constraint function, and a Linear Matrix Inequality (LMI) method for the convex approximation of probabilistic constraints with ellipsoidal constraint function. Finally, we introduce a class of convex expectation-type constraints that provide tractable approximations of the so-called integrated chance constraints. Performance of these methods and of existing convex approximation methods for probabilistic constraints is compared on a numerical example.     

Computational Method for a Class of Switched System Optimal Control Problems

We consider an optimal control problem with dynamics that switch between several subsystems of nonlinear differential equations. Each subsystem is assumed to satisfy a linear growth condition. Furthermore, each subsystem switch is accompanied by an instantaneous change in the state. These instantaneous changes-called ldquostate jumpsrdquo-are influenced by a set of control parameters that, together with the subsystem switching times, are decision variables to be selected optimally. We show that an approximate solution for this optimal control problem can be computed by solving a sequence of conventional dynamic optimization problems. Existing optimization techniques can be used to solve each problem in this sequence. A convergence result is also given to justify this approach.     

On solutions of fuzzy random multiobjective quadratic programming with applications in portfolio problem

In this paper, a multiobjective quadratic programming problem fuzzy random coefficients matrix in the objectives and constraints and the decision vector are fuzzy variables is considered. First, we show that the efficient solutions fuzzy quadratic multiobjective programming problems series-optimal-solutions of relative scalar fuzzy quadratic programming. Some theorems are to find an optimal solution of the relative scalar quadratic multiobjective programming with fuzzy coefficients, having decision vectors as fuzzy variables. An application fuzzy portfolio optimization problem as a convex quadratic programming approach is discussed and an acceptable solution to such problem is given. At the end, numerical examples are illustrated in the support of the obtained results.     

一种高效的服务组合优化算法

随着功能性属性相同而非功能性属性各异的Web服务的大量涌现,如何在服务组合业务流程中为各个任务选择相应的组件服务以达到组合服务的QoS(quality of service)最大化,并在此基础上满足不同用户的需求,已成为了国内外研究的热点.由于该问题的复杂性(NP-hard),目前存在的大多数方法都并不十分适合需要相对精确、实时决策的Web服务组合系统.因此,本文提出了一种基于凸包构建的组合服务优化算法(CM-HEU)用以解决QoS感知的服务组合优化问题.CM-HEU首先通过对组合服务中的每组任务进行凸包构建,以减少搜索空间.然后通过对初始解向量的多次升级和一次降级操作以达到全局优化的目标.实验表明:相对于现阶段存在的一些主流方法,CM-HEU不仅能得到一个比较理想的结果,并且具有良好的效率.     

A perspective-based convex relaxation for switched-affine optimal control

We consider the switched-affine optimal control problem, i.e., the problem of selecting a sequence of affine dynamics from a finite set in order to minimize a sum of convex functions of the system state. We develop a new reduction of this problem to a mixed-integer convex program (MICP), based on perspective functions. Relaxing the integer constraints of this MICP results in a convex optimization problem, whose optimal value is a lower bound on the original problem value. We show that this bound is at least as tight as similar bounds obtained from two other well-known MICP reductions (via conversion to a mixed logical dynamical system, and by generalized disjunctive programming), and our numerical study indicates it is often substantially tighter. Using simple integer-rounding techniques, we can also use our formulation to obtain an upper bound (and corresponding sequence of control inputs). In our numerical study, this bound was typically within a few percent of the optimal value, making it attractive as a stand-alone heuristic, or as a subroutine in a global algorithm such as branch and bound. We conclude with some extensions of our formulation to problems with switching costs and piecewise affine dynamics.