Control applications of nonlinear convex programming

Since 1984 there has been a concentrated effort to develop efficient interior-point methods for linear programming (LP). In the last few years researchers have begun to appreciate a very important property of these interior-point methods (beyond their efficiency for LP): they extend gracefully to nonlinear convex optimization problems. New interior-point algorithms for problem classes such as semidefinite programming (SDP) or second-order cone programming (SOCP) are now approaching the extreme efficiency of modern linear programming codes. In this paper we discuss three examples of areas of control where our ability to efficiently solve nonlinear convex optimization problems opens up new applications. In the first example we show how SOCP can be used to solve robust open-loop optimal control problems. In the second example, we show how SOCP can be used to simultaneously design the set-point and feedback gains for a controller, and compare this method with the more standard approach. Our final application concerns analysis and synthesis via linear matrix inequalities and SDP.     

Fast Computation of Optimal Contact Forces

We consider the problem of computing the smallest contact forces, with point-contact friction model, that can hold an object in equilibrium against a known external applied force and torque. It is known that the force optimization problem (FOP) can be formulated as a semidefinite programming problem (SDP) or a second-order cone problem (SOCP), and thus, can be solved using several standard algorithms for these problem classes. In this paper, we describe a custom interior-point algorithm for solving the FOP that exploits the specific structure of the problem, and is much faster than these standard methods. Our method has a complexity that is linear in the number of contact forces, whereas methods based on generic SDP or SOCP algorithms have complexity that is cubic in the number of forces. Our method is also much faster for smaller problems. We derive a compact dual problem for the FOP, which allows us to rapidly compute lower bounds on the minimum contact force and certify the infeasibility of a FOP. We use this dual problem to terminate our optimization method with a guaranteed accuracy. Finally, we consider the problem of solving a family of FOPs that are related. This occurs, for example, in determining whether force closure occurs, in analyzing the worst case contact force required over a set of external forces and torques, and in the problem of choosing contact points on an object so as to minimize the required contact force. Using dual bounds, and a warm-start version of our FOP method, we show how such families of FOPs can be solved very efficiently.     

Convex optimization algorithms for cooperative RSS-based sensor localization

To obtain a global solution for the source location estimates, the cost function of RSS-based sensor localization is relaxed as convex optimization problem which can be solved by interior point method. Weighted squared least square (WSLS) and weighted least square (WLS) based optimization functions are proposed to locate the source nodes. The corresponding semidefinite programming (SDP), second-order cone program (SOCP) and mixed SOC/SDP algorithms are designed by considering the known or unknown transmit powers. The computational complexity of the proposed algorithms is derived by analyzing the number of variables and equality constraints produced in the relaxation. The simulations show that the mixed SOC/SDP runs faster than the SDP, although the algorithms have the approximately equal accuracy performance. Whether the transmit power is known or not, the accuracy performance of the WLS-SDP is better than that of the WSLS-SDP and WSLS-SOC/SDP algorithms. However the computational complexity of the WLS-SDP is greatly larger than that of WSLS-SOC/SDP and WSLS-SDP due to a large number of variables.     

Infinite horizon indefinite stochastic linear quadratic control for discrete-time systems

This paper discusses discrete-time stochastic linear quadratic (LQ) problem in the infinite horizon with state and control dependent noise, where the weighting matrices in the cost function are assumed to be indefinite. The problem gives rise to a generalized algebraic Riccati equation (GARE) that involves equality and inequality constraints. The well-posedness of the indefinite LQ problem is shown to be equivalent to the feasibility of a linear matrix inequality (LMI). Moreover, the existence of a stabilizing solution to the GARE is equivalent to the attainability of the LQ problem. All the optimal controls are obtained in terms of the solution to the GARE. Finally, we give an LMI -based approach to solve the GARE via a semidefinite programming.     

A primal-dual semi-definite programming approach to linearquadratic control

We study a deterministic linear-quadratic (LQ) control problem over an infinite horizon, without the restriction that the control cost matrix R or the state cost matrix Q be positive-definite. We develop a general approach to the problem based on semi-definite programming (SDP) and related duality analysis. We show that the complementary duality condition of the SDP is necessary and sufficient for the existence of an optimal LQ control under a certain stability condition (which is satisfied automatically when Q is positive-definite). When the complementary duality does hold, an optimal state feedback control is constructed explicitly in terms of the solution to the primal SDP     

Linear convex stochastic control problems over an infinite horizon

A stochastic control problem over an infinite horizon which involves a linear system and a convex cost functional is analyzed. We prove the convergence of the dynamic programming algorithm associated with the problem, and we show the existence of a stationary Borel measurable optimal control law. The approach used illustrates how results on infinite time reachability [1] can be used for the analysis of dynamic programming algorithms over an infinite horizon subject to state constraints.     

An SDP approach for multiperiod mixed 0–1 linear programming models with stochastic dominance constraints for risk management

In this paper we consider multiperiod mixed 0–1 linear programming models under uncertainty. We propose a risk averse strategy using stochastic dominance constraints (SDC) induced by mixed-integer linear recourse as the risk measure. The SDC strategy extends the existing literature to the multistage case and includes both the first-order and second-order constraints. We propose a stochastic dynamic programming (SDP) solution approach, where one has to overcome the negative impact of the cross-scenario constraints on the decomposability of the model. In our computational experience we compare our SDP approach against a commercial optimization package, in terms of solution accuracy and elapsed time. We use supply chain planning instances, where procurement, production, inventory, and distribution decisions need to be made under demand uncertainty. We confirm the hardness of the testbed, where the benchmark cannot find a feasible solution for half of the test instances while we always find one, and show the appealing tradeoff of SDP, in terms of solution accuracy and elapsed time, when solving medium-to-large instances.     

Linear matrix inequalities, Riccati equations, and indefinitestochastic linear quadratic controls

This paper deals with an optimal stochastic linear-quadratic (LQ) control problem in infinite time horizon, where the diffusion term in dynamics depends on both the state and the control variables. In contrast to the deterministic case, we allow the control and state weighting matrices in the cost functional to be indefinite. This leads to an indefinite LQ problem, which may still be well posed due to the deep nature of uncertainty involved. The problem gives rise to a stochastic algebraic Riccati equation (SARE), which is, however, fundamentally different from the classical algebraic Riccati equation as a result of the indefinite nature of the LQ problem. To analyze the SARE, we introduce linear matrix inequalities (LMIs) whose feasibility is shown to be equivalent to the solvability of the SARE. Moreover, we develop a computational approach to the SARE via a semi-definite programming associated with the LMIs. Finally, numerical experiments are reported to illustrate the proposed approach     

An Optimal Approach to Collaborative Target Tracking with Performance Guarantees

In this paper, we present a discrete-time optimization framework for target tracking with multi-agent systems. The “target tracking” problem is formulated as a generic semidefinite program (SDP) that when paired with an appropriate objective yields an optimal robot configuration over a given time step. The framework affords impressive performance guarantees to include full target coverage (i.e. each target is tracked by at least a single team member) as well as maintenance of network connectivity across the formation. Key to this work is the result from spectral graph theory that states the second-smallest eigenvalue—λ ₂—of a weighted graph’s Laplacian (i.e. its inter-connectivity matrix) is a measure of connectivity for the associated graph. Our approach allows us to articulate agent-target coverage and inter-agent communication constraints as linear-matrix inequalities (LMIs). Additionally, we present two key extensions to the framework by considering alternate tracking problem formulations. The first allows us to guarantee k-coverage of targets, where each target is tracked by k or more agents. In the second, we consider a relaxed formulation for the case when network connectivity constraints are superfluous. The problem is modeled as a second-order cone program (SOCP) that can be solved significantly more efficiently than its SDP counterpart—making it suitable for large-scale teams (e.g. 100’s of nodes in real-time). Methods for enforcing inter-agent proximity constraints for collision avoidance are also presented as well as simulation results for multi-agent systems tracking mobile targets in both ?² and ?³.     

Efficient hyperkernel learning using second-order cone programming

The kernel function plays a central role in kernel methods. Most existing methods can only adapt the kernel parameters or the kernel matrix based on empirical data. Recently, Ong et al. introduced the method of hyperkernels which can be used to learn the kernel function directly in an inductive setting. However, the associated optimization problem is a semidefinite program (SDP), which is very computationally expensive, even with the recent advances in interior point methods. In this paper, we show that this learning problem can be equivalently reformulated as a second-order cone program (SOCP), which can then be solved more efficiently than SDPs. Comparison is also made with the kernel matrix learning method proposed by Lanckriet et al. Experimental results on both classification and regression problems, with toy and real-world data sets, show that our proposed SOCP formulation has significant speedup over the original SDP formulation. Moreover, it yields better generalization than Lanckriet et al.'s method, with a speed that is comparable, or sometimes even faster, than their quadratically constrained quadratic program (QCQP) formulation.     

Well-posedness and attainability of indefinite stochastic linear quadratic control in infinite time horizon

This paper is concerned with a stochastic linear-quadratic (LQ) problem in an infinite time horizon with multiplicative noises both in the state and the control. A distinctive feature of the problem under consideration is that the cost weighting matrices for the state and the control are allowed to be indefinite. A new type of algebraic Riccati equation – called a generalized algebraic Riccati equation (GARE) – is introduced which involves a matrix pseudo-inverse and two additional algebraic equality/inequality constraints. It is then shown that the well-posedness of the indefinite LQ problem is equivalent to a linear matrix inequality (LMI) condition, whereas the attainability of the LQ problem is equivalent to the existence of a “stabilizing solution” to the GARE. Moreover, all possible optimal controls are identified via the solution to the GARE. Finally, it is proved that the solution to the GARE can be obtained via solving a convex optimization problem called semidefinite programming.     

不确定线性时滞随机系统的最优保性能控制

对一类具有状态时滞的不确定线性随机系统,研究了保性能状态反馈控制律的设计问题。采用线性矩阵不等式方法和伊藤公式,导出了保性能控制律的存在条件。进而,通过求解一个线性矩阵不等式约束的凸优化问题,提出了最优保性能控制律设计方法。最后用数值例子说明了该方法的有效性。     

Characterizing all optimal controls for an indefinite stochasticlinear quadratic control problem

This paper is concerned with a stochastic linear quadratic (LQ) control problem in the infinite-time horizon, with indefinite state and control weighting matrices in the cost function. It is shown that the solvability of this problem is equivalent to the existence of a so-called static stabilizing solution to a generalized algebraic Riccati equation. Moreover, another algebraic Riccati equation is introduced and all the possible optimal controls, including the ones in state feedback form, of the underlying LQ problem are explicitly obtained in terms of the two Riccati equations     

Finite Horizon Minimax Optimal Control of Stochastic Partially Observed Time Varying Uncertain Systems

We consider a linear-quadratic problem of minimax optimal control for stochastic uncertain control systems with output measurement. The uncertainty in the system satisfies a stochastic integral quadratic constraint. To convert the constrained optimization problem into an unconstrained one, a special S-procedure is applied. The resulting unconstrained game-type optimization problem is then converted into a risk-sensitive stochastic control problem with an exponential-of-integral cost functional. This is achieved via a certain duality relation between stochastic dynamic games and risk-sensitive stochastic control. The solution of the risk-sensitive stochastic control problem in terms of a pair of differential matrix Riccati equations is then used to establish a minimax optimal control law for the original uncertain system with uncertainty subject to the stochastic integral quadratic constraint. Date received: May 13, 1997. Date revised: March 18, 1998.     

Stochastic linear quadratic regulation for discrete-time linear systems with input delay

This paper considers the stochastic LQR problem for systems with input delay and stochastic parameter uncertainties in the state and input matrices. The problem is known to be difficult due to the presence of interactions among the delayed input channels and the stochastic parameter uncertainties in the channels. The key to our approach is to convert the LQR control problem into an optimization one in a Hilbert space for an associated backward stochastic model and then obtain the optimal solution to the stochastic LQR problem by exploiting the dynamic programming approach. Our solution is given in terms of two generalized Riccati difference equations (RDEs) of the same dimension as that of the plant.     

Dynamic pricing of durable products with heterogeneous customers and demand interactions over time

In this study, we analyze a dynamic pricing problem in which the demand is interdependent over time and the customers are heterogeneous in their purchasing decisions. The customers are grouped into different classes depending on their purchase probabilities and the customer classes evolve over time depending on the demand realizations at every period, which are a function of the prices set by the company. To decide on the optimal prices at every period, we model this problem using a stochastic dynamic program (SDP) and we develop several approximation algorithms to solve this SDP since the size of the state space of the SDP makes the optimal solution almost impossible to find. We present the efficiencies of the heuristics and provide managerial insights through a computational study in which we compare the revenues obtained with each heuristic with an upper bound value that we find on the optimal revenues.     

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.     

On control of discrete-time state-dependent jump linear systems with probabilistic constraints: A receding horizon approach

In this article, we consider a receding horizon control of discrete-time state-dependent jump linear systems, a particular kind of stochastic switching systems, subject to possibly unbounded random disturbances and probabilistic state constraints. Due to the nature of the dynamical system and the constraints, we consider a one-step receding horizon. Using inverse cumulative distribution function, we convert the probabilistic state constraints to deterministic constraints, and obtain a tractable deterministic receding horizon control problem. We consider the receding horizon control law to have a linear state-feedback and an admissible offset term. We ensure mean square boundedness of the state variable via solving linear matrix inequalities off-line, and solve the receding horizon control problem on-line with control offset terms. We illustrate the overall approach applied on a macroeconomic system.     

Uplink scheduling for joint wireless orthogonal frequency and time division multiple access networks

In this paper, we present a deterministic resource allocation model for a hybrid uplink wireless orthogonal frequency and time division multiple access network. Since the input data of the model may be affected by uncertainty, we further consider a stochastic formulation of the problem which we transform into an equivalent deterministic binary second-order conic program (SOCP). Subsequently, we use this binary SOCP to derive an equivalent integer linear programming formulation. The proposed models are aimed at maximizing the total bandwidth channel capacity subject to user power and sub-carrier assignment constraints while simultaneously scheduling users in time. As such, the models are best suited for non-real-time applications where sub-channel multiuser diversity can be further exploited simultaneously in frequency and time domains. Finally, in view of the large execution times required by CPLEX to solve the proposed models, we propose a variable neighborhood search metaheuristic procedure. Our numerical results show tight bounds and near optimal solutions for most of the instances when compared to the optimal solution of the problem. Moreover, we obtain better feasible solutions than CPLEX in the stochastic case. Finally, these bounds are obtained at a very low computational cost.     

LQ终端控制的生成函数法与Riccati变换法的等价性

通过定义线性哈密顿系统新形式的第3类生成函数, 建立了求解线性二次终端控制问题的生成函数方法与Riccati变换方法的直接联系, 并证明两种方法导出的最优控制律是等价的. 生成函数方法的优势在于可以灵活地处理边界约束条件. 本文根据Riccati变换方法沿时间逆向求解问题的特点, 定义了适于逆向正则变换的第3类生成函数, 用于求解哈密顿两点边值问题, 可得到用生成函数表示的最优控制律. 并通过验证生成函数方法所得最优控制律的各部分与Riccati变换法所得的结果相对应, 证明了两种方法所得控制律的等价性.