We treat some duality assertions regarding multiobjective convex semi-definite programming problems. Having a vector minimization problem with convex entries in the objective vector function, we establish a dual for i...
详细信息
We treat some duality assertions regarding multiobjective convex semi-definite programming problems. Having a vector minimization problem with convex entries in the objective vector function, we establish a dual for it using the so-called conjugacy approach. In order to deal with the duality assertions between these problems we need to study the duality properties and the optimality conditions of the scalarized problem associated to the initial one. Using these results we present the weak, strong and converse duality assertions regarding the primal problem and the dual we obtained for it.
An indefinite stochastic linear-quadratic(LQ) optimal control problem with cross term over an infinite time horizon is studied, allowing the weighting matrices to be indefinite. A systematic approach to the problem ba...
详细信息
An indefinite stochastic linear-quadratic(LQ) optimal control problem with cross term over an infinite time horizon is studied, allowing the weighting matrices to be indefinite. A systematic approach to the problem based on semidefinite programming (SDP) and related duality analysis is developed. Several implication relations among the SDP complementary duality, the existence of the solution to the generalized Riccati equation and the optimality of LQ problem are discussed. Based on these relations, a numerical procedure that provides a thorough treatment of the LQ problem via primal-dual SDP is given: it identifies a stabilizing optimal feedback control or determines the problem has no optimal solution. An example is provided to illustrate the results obtained.
A controller redesign is considered for a class of nonlinear plants. A locally stabilizing state feedback and the corresponding Lyapunov function are assumed to be given. Then, the Lyapunov function is fixed for ensur...
详细信息
ISBN:
(纸本)9788995003848
A controller redesign is considered for a class of nonlinear plants. A locally stabilizing state feedback and the corresponding Lyapunov function are assumed to be given. Then, the Lyapunov function is fixed for ensuring a performance, while the state feedback is redesigned for enlarging the asymptotic stability region of the origin. This redesign can be done efficiently by using sum of squares programming if the plant and the controller are characterized by polynomial functions of the state and/or the control input.
We consider the 2-Catalog Segmentation problem (2-CatSP) introduced by Kleinberg et al. [J. Kleinberg, C. Papadimitriou and P. Raghavan (1998). Segmentation problems. In Proceedings of the 30th Symposium on Theory of ...
详细信息
We consider the 2-Catalog Segmentation problem (2-CatSP) introduced by Kleinberg et al. [J. Kleinberg, C. Papadimitriou and P. Raghavan (1998). Segmentation problems. In Proceedings of the 30th Symposium on Theory of Computation , pp. 473-482.], where we are given a ground set I of n items, a family {S-1, S-2,...,S-m } of subsets of I and an integer 1 less than or equal to k less than or equal to n . The objective is to find subsets A(1), A(2) subset of I such that \A(1)\ = \A(2)\ = k and Sigma(i=1)(m) max {\S-i boolean AND A(1)\, \S-i boolean AND A(2)\} is maximized. It is known that a simple and elegant greedy algorithm has a performance guarantee 1/2. Furthermore, using a semidefinite programming (SDP) relaxation Doids et al. [Y. Doids, V. Guruswami and S. Khanna (1999). The 2-catalog segmentation problem. In Proceedings of SODA , pp. 378-380.] showed that 2-CatSP can be approximated by a factor of 0.56 when k = n/2. Motivated by these results, we develop improved approximation algorithms for 2-CatSP on a range of k in this paper. The performance guarantee of our algorithm is 1/2 for general k , and is strictly greater than 1/2 when k greater than or equal to n /3. In particular, we obtain a ratio of 0.67 for 2-CatSP when k = n/2. Unlike the relaxation used by Doids et al. , our extended and direct SDP relaxation deals with general k , which enables us to obtain better approximation for 2-CatSP. Another contribution of this paper is a new variation of the random hyperplane rounding technique, which allows us to explore the structure of 2-CatSP. This rounding technique might be of independent interest. It can be also used to obtain improved approximation for several other graph partitioning problems considered in Feige and Langberg [U. Fiege and M. Langberg (2002). Approximation algorithms for maximization problems arising in graph partitioning. Journal of Algorithm .], Ye and Zhang [Y. Ye and J. Zhang (2003). Approximation for dense-n/2-subgraph and the complemen
We present an approach to uncertainty propagation in dynamic systems, exploiting information provided by related experimental results along with their models. The approach relies on a solution mapping technique to app...
详细信息
We present an approach to uncertainty propagation in dynamic systems, exploiting information provided by related experimental results along with their models. The approach relies on a solution mapping technique to approximate mathematical models by polynomial surrogate models. We use these surrogate models to formulate prediction bounds in terms of polynomial optimizations. Recent results on polynomial optimizations are then applied to solve the prediction problem. Two examples which illustrate the key aspects of the proposed algorithm are given. The proposed algorithm offers a framework for collaborative data processing among researchers.
In this paper, we survey the most recent methods that have been developed for the solution of semidefinite programs. We first concentrate on the methods that have been primarily motivated by the interior point (IP) al...
详细信息
In this paper, we survey the most recent methods that have been developed for the solution of semidefinite programs. We first concentrate on the methods that have been primarily motivated by the interior point (IP) algorithms for linear programming, putting special emphasis in the class of primal-dual path-following algorithms. We also survey methods that have been developed for solving large-scale SDP problems. These include first-order nonlinear programming (NLP) methods and more specialized path-following IP methods which use the (preconditioned) conjugate gradient or residual scheme to compute the Newton direction and the notion of matrix completion to exploit data sparsity.
We consider a polynomial programming problem P on a compact basic semialgebraic set K subset of R-n, described by m polynomial inequalities g(j) (X) >= 0, and with criterion f is an element of R[X]. We propose a hi...
详细信息
We consider a polynomial programming problem P on a compact basic semialgebraic set K subset of R-n, described by m polynomial inequalities g(j) (X) >= 0, and with criterion f is an element of R[X]. We propose a hierarchy of semidefinite relaxations in the spirit of those of Waki et al. [SIAM J. Optim., 17 ( 2006), pp. 218-242]. In particular, the SDP-relaxation of order r has the following two features: (a) The number of variables is O(K-2r), where K = max[K-1, K-2] with K-1 ( resp., K-2) being the maximum number of variables appearing in the monomials of f (resp., appearing in a single constraint g(j) (X) >= 0). (b) The largest size of the linear matrix inequalities (LMIs) is O(K-r). This is to compare with the respective number of variables O(n(2r)) and LMI size O(n(r)) in the original SDP-relaxations defined in [J. B. Lasserre, SIAM J. Optim., 11 (2001), pp. 796-817]. Therefore, great computational savings are expected in case of sparsity in the data {g(j), f}, i.e, when K is small, a frequent case in practical applications of interest. The novelty with respect to [H. Waki, S. Kim, M. Kojima, and M. Maramatsu, SIAM J. Optim., 17 (2006), pp. 218-242] is that we prove convergence to the global optimum of P when the sparsity pattern satisfies a condition often encountered in large size problems of practical applications, and known as the running intersection property in graph theory. In such cases, and as a by-product, we also obtain a new representation result for polynomials positive on a compact basic semialgebraic set, a sparse version of Putinar's Positivstellensatz [ M. Putinar, Indiana Univ. Math. J., 42 ( 1993), pp. 969-984].
This paper provides algorithms for numerical solution of convex matrix inequalities in which the variables naturally appear as matrices. This includes, for instance, many systems and control problems. To use these alg...
详细信息
This paper provides algorithms for numerical solution of convex matrix inequalities in which the variables naturally appear as matrices. This includes, for instance, many systems and control problems. To use these algorithms, no knowledge of linear matrix inequalities is required. However, as tools, they preserve many advantages of the linear matrix inequality framework. Our method has two components: ( 1) a numerical algorithm that solves a large class of matrix optimization problems and ( 2) a symbolic "convexity checker" that automatically provides a region which, if convex, guarantees that the solution from ( 1) is a global optimum on that region. The algorithms are partly numerical and partly symbolic and since they aim at exploiting the matrix structure of the unknowns, the symbolic part requires the development of new computer techniques for treating noncommutative algebra.
We consider the problem of computing the minimum value pm taken by a polynomial p(x) of degree d over the standard simplex Delta. This is an NP-hard problem already for degree d = 2. For any integer k >= 1, by mini...
详细信息
We consider the problem of computing the minimum value pm taken by a polynomial p(x) of degree d over the standard simplex Delta. This is an NP-hard problem already for degree d = 2. For any integer k >= 1, by minimizing p(x) over the set of rational points in Delta with denominator k, one obtains a hierarchy of upper bounds p(Delta)(k) converging to p(min) as k --> infinity. These upper approximations are intimately linked to a hierarchy of lower bounds for p(min) constructed via polya's theorem about representations of positive forms on the simplex. Revisiting the proof of Polya's theorem allows us to give estimates on the quality of these upper and lower approximations for p(min). Moreover, we show that the bounds p(Delta)(k) yield a polynomial time approximation scheme for the minimization of polynomials of fixed degree d on the simplex, extending an earlier result of Bomze and De Klerk for degree d = 2. (C) 2006 Elsevier B.V. All rights reserved.
An exact condition for uniform stabilization and disturbance attenuation for switched linear systems is given in the discrete-time domain via the union of an increasing family of linear matrix inequality conditions. A...
详细信息
An exact condition for uniform stabilization and disturbance attenuation for switched linear systems is given in the discrete-time domain via the union of an increasing family of linear matrix inequality conditions. Associated with each Markovian jump linear system is a switched linear system, so we obtain a necessary and sufficient condition for almost sure uniform stabilization and disturbance attenuation for Markovian jump linear systems as well. The results lead to semidefinite programming-based controller synthesis techniques, from which optimal finite-path-dependent linear dynamic output feedback controllers arise naturally. In particular, under the notion of path-by-path optimal disturbance attenuation, finite-path-dependent controllers can outperform the usual mode-dependent ones.
暂无评论