Finite-frequency output feedback MPC for Markov jump systems

This paper investigates a general design framework of dynamic output feedback model predictive control (DOFMPC) for Markov jump systems within both time and frequency domain. Such a design with guaranteed H_∞ and quadratic performance is formulated by a standard semi-definite programming (SDP), and it is achieved by employing a special congruence transformation. The SDP condition greatly reduces the computational effort by eliminating bilinear matrix inequalities or equation constraints reported in existing references. Specifically, the H_∞ norm of the transfer function is optimized within three types of frequency ranges on account of generalized Kalman–Yakubovic–Popov (GKYP) lemma. The quadratic index is optimized online via SDP. Finally, we verify the feasibility and effectiveness of the proposed method from both theoretical and practical point of view.     

Dinkelbach NCUT: An Efficient Framework for Solving Normalized Cuts Problems with Priors and Convex Constraints

In this paper, we propose a novel framework, called Dinkelbach NCUT (DNCUT), which efficiently solves the normalized graph cut (NCUT) problem under general, convex constraints, as well as, under given priors on the nodes of the graph. Current NCUT methods use generalized eigen-decomposition, which poses computational issues especially for large graphs, and can only handle linear equality constraints. By using an augmented graph and the iterative Dinkelbach method for fractional programming (FP), we formulate the DNCUT framework to efficiently solve the NCUT problem under general convex constraints and given data priors. In this framework, the initial problem is converted into a sequence of simpler sub-problems (i.e. convex, quadratic programs (QP’s) subject to convex constraints). The complexity of finding a global solution for each sub-problem depends on the complexity of the constraints, the convexity of the cost function, and the chosen initialization. However, we derive an initialization, which guarantees that each sub-problem is a convex QP that can be solved by available convex programming techniques. We apply this framework to the special case of linear constraints, where the solution is obtained by solving a sequence of sparse linear systems using the conjugate gradient method. We validate DNCUT by performing binary segmentation on real images both with and without linear/nonlinear constraints, as well as, multi-class segmentation. When possible, we compare DNCUT to other NCUT methods, in terms of segmentation performance and computational efficiency. Even though the new formulation is applied to the problem of spectral graph-based, low-level image segmentation, it can be directly applied to other applications (e.g. clustering).     

Constrained Stochastic LQC: A Tractable Approach

Despite the celebrated success of dynamic programming for optimizing quadratic cost functions over linear systems, such an approach is limited by its inability to tractably deal with even simple constraints. In this paper, we present an alternative approach based on results from robust optimization to solve the stochastic linear-quadratic control (SLQC) problem. In the unconstrained case, the problem may be formulated as a semidefinite optimization problem (SDP). We show that we can reduce this SDP to optimization of a convex function over a scalar variable followed by matrix multiplication in the current state, thus yielding an approach that is amenable to closed-loop control and analogous to the Riccati equation in our framework. We also consider a tight, second-order cone (SOCP) approximation to the SDP that can be solved much more efficiently when the problem has additional constraints. Both the SDP and SOCP are tractable in the presence of control and state space constraints; moreover, compared to the Riccati approach, they provide much greater control over the stochastic behavior of the cost function when the noise in the system is distributed normally.     

A simple effective heuristic for embedded mixed-integer quadratic programming

ABSTRACT

In this paper, we propose a fast optimisation algorithm for approximately minimising convex quadratic functions over the intersection of affine and separable constraints (i.e. the Cartesian product of possibly nonconvex real sets). This problem class contains many NP-hard problems such as mixed-integer quadratic programming. Our heuristic is based on a variation of the alternating direction method of multipliers (ADMM), an algorithm for solving convex optimisation problems. We discuss the favourable computational aspects of our algorithm, which allow it to run quickly even on very modest computational platforms such as embedded processors. We give several examples for which an approximate solution should be found very quickly, such as management of a hybrid-electric vehicle drivetrain and control of switched-mode power converters. Our numerical experiments suggest that our method is very effective in finding a feasible point with small objective value; indeed, we see that in many cases, it finds the global solution.     

Symmetricity of the solution of semidefinite programming

Symmetricity of an optimal solution of Semi-Definite Programming (SDP) is discussed based on the symmetry property of the central path that is traced by a primal-dual interior-point method. A symmetric SDP is defined by operators for rearranging elements of matrices and vectors, and the solution on the central path is proved to be symmetric. Therefore, it is theoretically guaranteed that a symmetric optimal solution is always obtained by using a primal-dual interior-point method even if there exist other asymmetric optimal solutions. The optimization problem of symmetric trusses under eigenvalue constraints is shown to be formulated as a symmetric SDP. Numerical experiments illustrate convergence to strictly symmetric optimal solutions.     

Large scale portfolio optimization with piecewise linear transaction costs

We consider the fundamental problem of computing an optimal portfolio based on a quadratic mean-variance model for the objective function and a given polyhedral representation of the constraints. The main departure from the classical quadratic programming formulation is the inclusion in the objective function of piecewise linear, separable functions representing the transaction costs. We handle the non-smoothness in the objective function by using spline approximations. The problem is first solved approximately using a primal-dual interior-point method applied to the smoothed problem. Then, we crossover to an active set method applied to the original non-smooth problem to attain a high accuracy solution. Our numerical tests show that we can solve large scale problems efficiently and accurately.     

Global optimization in protein docking using clustering,underestimation and semidefinite programming

The underestimation of data points by a convex quadratic function is a useful tool for approximating the location of the global minima of potential energy functions that arise in protein-ligand docking problems. Determining the parameters that define the underestimator can be formulated as a convex quadratically constrained quadratic program and solved efficiently using algorithms for semidefinite programming (SDP). In this paper, we formulate and solve the underestimation problem using SDP and present numerical results for active site prediction in protein docking.     

Robust ℒ︁2‐gain feedforward control of uncertain systems using dynamic IQCs

We consider the problem of robust ??₂‐gain disturbance feedforward control for uncertain systems described in the standard LFT form. We use integral quadratic constraints (IQCs) for describing the uncertainty blocks in the system. For technical reasons related to the feedforward problem, throughout the paper, we work with the duals of the constraints involved in robustness analysis using IQCs. We obtain a convex solution to the problem using a state‐space characterization of nominal stability that we have developed recently. Specifically, our solution consists of LMI conditions for the existence of a feedforward controller that guarantees a given ??₂‐gain for the closed‐loop system. We demonstrate the effectiveness of using dynamic IQCs in robust feedforward design through a numerical example. Copyright © 2008 John Wiley & Sons, Ltd.     

Output feedback optimal guaranteed cost control of uncertain piecewise linear systems

This paper proposes the output feedback optimal guaranteed cost controller design method for uncertain piecewise linear systems based on the piecewise quadratic Lyapunov functions technique. By constructing piecewise quadratic Lyapunov functions for the closed‐loop augmented systems, the existence of the guaranteed cost controller for closed‐loop uncertain piecewise linear systems is cast as the feasibility of a set of bilinear matrix inequalities (BMIs). Some of the variables in BMIs are set to be searched by genetic algorithm (GA), then for a given chromosome corresponding to the variables in BMIs, the BMIs turn to be linear matrix inequalities (LMIs), and the corresponding non‐convex optimization problem, which minimizes the upper bound on cost function, reduces to a semidefinite programming (SDP) which is convex and can be solved numerically efficiently with the available software. Thus, the output feedback optimal guaranteed cost controller can be obtained by solving the non‐convex optimization problem using the mixed algorithm that combines GA and SDP. Numerical examples show the effectiveness of the proposed method. Copyright © 2008 John Wiley & Sons, Ltd.     

A note on semidefinite relaxation for 0-1 quadratic knapsack problems

We investigate in this note solution properties of semidefinite programming (SDP) relaxation for 0-1 quadratic knapsack problem (QKP). In particular, we focus on the issue of uniqueness of the optimal solution to the SDP relaxation for QKP. We first give a counterexample which shows that the optimal solution to the SDP relaxation for QKP could be non-unique. This is in contrast with the case of unconstrained 0-1 quadratic problems. A necessary and sufficient condition is then derived to ensure the uniqueness of the optimal solution to the SDP relaxation for QKP.     

Solution of the input-constrained LQR problem using dynamic programming

The input-constrained LQR problem is addressed in this paper; i.e., the problem of finding the optimal control law for a linear system such that a quadratic cost functional is minimised over a horizon of length N subject to the satisfaction of input constraints. A global solution (i.e., valid in the entire state space) for this problem, and for arbitrary horizon N, is derived analytically by using dynamic programming. The scalar input case is considered in this paper. Solutions to this problem (and to more general problems: state constraints, multiple inputs) have been reported recently in the literature, for example, approaches that use the geometric structure of the underlying quadratic programming problem and approaches that use multi-parametric quadratic programming techniques. The solution by dynamic programming proposed in the present paper coincides with the ones obtained by the aforementioned approaches. However, being derived using a different approach that exploits the dynamic nature of the constrained optimisation problem to obtain an analytical solution, the present result complements the previous methods and reveals additional insights into the intrinsic structure of the optimal solution.     

Splines in Higher Order TV Regularization

Splines play an important role as solutions of various interpolation and approximation problems that minimize special functionals in some smoothness spaces. In this paper, we show in a strictly discrete setting that splines of degree m−1 solve also a minimization problem with quadratic data term and m-th order total variation (TV) regularization term. In contrast to problems with quadratic regularization terms involving m-th order derivatives, the spline knots are not known in advance but depend on the input data and the regularization parameter λ. More precisely, the spline knots are determined by the contact points of the m–th discrete antiderivative of the solution with the tube of width 2λ around the m-th discrete antiderivative of the input data. We point out that the dual formulation of our minimization problem can be considered as support vector regression problem in the discrete counterpart of the Sobolev space W _2,0 ^m . From this point of view, the solution of our minimization problem has a sparse representation in terms of discrete fundamental splines.     

An improved robust model predictive control for linear parameter‐varying input‐output models

This paper describes a new robust model predictive control (MPC) scheme to control the discrete‐time linear parameter‐varying input‐output models subject to input and output constraints. Closed‐loop asymptotic stability is guaranteed by including a quadratic terminal cost and an ellipsoidal terminal set, which are solved offline, for the underlying online MPC optimization problem. The main attractive feature of the proposed scheme in comparison with previously published results is that all offline computations are now based on the convex optimization problem, which significantly reduces conservatism and computational complexity. Moreover, the proposed scheme can handle a wider class of linear parameter‐varying input‐output models than those considered by previous schemes without increasing the complexity. For an illustration, the predictive control of a continuously stirred tank reactor is provided with the proposed method.     

Nonlinear H ∞ output feedback control with integrator for polynomial discrete‐time systems

This paper investigates the problem of designing a nonlinear H _∞ output feedback controller for a class of polynomial discrete‐time systems. In general, this problem is hard to be formulated in a convex form because the relation between the control input and the Lyapunov function is always not jointly convex. Therefore, the problem cannot be solved via semidefinite programming (SDP). On the basis of the sum of squares (SOS) approach and incorporation of an integrator into the controller, sufficient conditions for the existence of a nonlinear H _∞ output feedback controller are given in terms of SOS conditions, which can be solved by an SDP solver. In contrast to the existing methods, a less conservative result is obtained. Finally, numerical examples are used to demonstrate the validity of this integrator approach. Copyright © 2013 John Wiley & Sons, Ltd.     

Quadratic approximate dynamic programming for input‐affine systems

We consider the use of quadratic approximate value functions for stochastic control problems with input‐affine dynamics and convex stage cost and constraints. Evaluating the approximate dynamic programming policy in such cases requires the solution of an explicit convex optimization problem, such as a quadratic program, which can be carried out efficiently. We describe a simple and general method for approximate value iteration that also relies on our ability to solve convex optimization problems, in this case, typically a semidefinite program. Although we have no theoretical guarantee on the performance attained using our method, we observe that very good performance can be obtained in practice.Copyright © 2012 John Wiley & Sons, Ltd.     

On semidefinite programming bounds for graph bandwidth

In this paper, we propose two new lower bounds on graph bandwidth and cyclic bandwidth based on semidefinite programming (SDP) relaxations of the quadratic assignment problem. We compare the new bounds with two other SDP bounds reported in [A. Blum, G. Konjevod, R. Ravi, and S. Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Theoret. Comput. Sci. 235(1) (2000), pp. 25–42; J. Povh and F. Rendl, A copositive programming approach to graph partitioning, SIAM J. Optim. 18(1) (2007), pp. 223–241].     

PID controller optimization for H∞ control by linear programming

The constraints on the PID gains, which are derived from the H_∞ norm performance index by discretization of the frequency, are convex or concave depending on frequencies. This problem is a non‐convex problem, and a new method of approximating these constraints as adequate linear inequalities is proposed. Then, the optimal solution can be efficiently and successfully searched for by applying linear programming iteratively. This method is compared with methods based on barrier function and linear matrix inequality. Copyright © 2000 John Wiley & Sons, Ltd.     

Semidefinite relaxation for linear programs with equilibrium constraints

In this paper, we present a semidefinite programming (SDP) relaxation for linear programs with equilibrium constraints (LPECs) to be used in a branch‐and‐bound (B&B) algorithm. The procedure utilizes the global optimal solution of LPECs and was motivated by the B&B algorithm proposed by Bard and Moore for linear/quadratic bilevel programs, where complementarities are recursively enforced. We propose the use of the SDP relaxation to generate bounds at the nodes of the B&B tree. Computational results compare the quality of the bounds given by the SDP relaxation with the ones given by conventional linear programming relaxations.