GloptiPoly is a Matlab/SeDuMi add-on to build and solve convex linear matrix inequality relaxations of the ( generally nonconvex) global optimization problem of minimizing a multivariable polynomial function subject t...
详细信息
GloptiPoly is a Matlab/SeDuMi add-on to build and solve convex linear matrix inequality relaxations of the ( generally nonconvex) global optimization problem of minimizing a multivariable polynomial function subject to polynomial inequality, equality, or integer constraints. It generates a series of lower bounds monotonically converging to the global optimum without any problem splitting. Global optimality is detected and isolated optimal solutions are extracted automatically. Numerical experiments show that for most of the small-scale problems described in the literature, the global optimum is reached at low computational cost.
Condition numbers based on the "distance to ill-posedness" rho(d) have been shown to play a crucial role in the theoretical complexity of solving convex optimization models. In this paper, we present two alg...
详细信息
Condition numbers based on the "distance to ill-posedness" rho(d) have been shown to play a crucial role in the theoretical complexity of solving convex optimization models. In this paper, we present two algorithms and corresponding complexity analysis for computing estimates of rho(d) for a finite-dimensional convex feasibility problem P(d) in standard primal form: find x that satisfies Ax=b, x is an element of C-X, where d=(A,b) is the data for the problem P(d). Under one choice of norms for the m- and n-dimensional spaces, the problem of estimating rho(d) is hard (co-NP complete even when C-X=r(+)(N)). However, when the norms are suitably chosen, the problem becomes much easier: We can estimate rho(d) to within a constant factor of its true value with complexity bounds that are linear in ln(C(d)) (where C(d) is the condition number of the data d for P(d)), plus other quantities that arise naturally in consideration of the problem P(d). The first algorithm is an interior-point algorithm, and the second algorithm is a variant of the ellipsoid algorithm. The main conclusion of this work is that when the norms are suitably chosen, computing an estimate of the condition measures of P(d) is essentially not much harder than computing a solution of P(d) itself.
We present a polynomial-time interior-point algorithm for a class of nonlinear saddle-point problems that involve semidefiniteness constraints on matrix variables. These problems originate from robust optimization for...
详细信息
We present a polynomial-time interior-point algorithm for a class of nonlinear saddle-point problems that involve semidefiniteness constraints on matrix variables. These problems originate from robust optimization formulations of convex quadratic programming problems with uncertain input parameters. As an application of our approach, we discuss a robust formulation of the Markowitz portfolio selection model.
Using outward rotations, we obtain an approximation algorithm for Max-Bisection problem, i.e., partitioning the vertices of an undirected graph into two blocks of equal cardinality so as to maximize the weights of cro...
详细信息
Using outward rotations, we obtain an approximation algorithm for Max-Bisection problem, i.e., partitioning the vertices of an undirected graph into two blocks of equal cardinality so as to maximize the weights of crossing edges. In many interesting cases, the algorithm performs better than the algorithms of Ye and of Halperin and Zwick. The main tool used to obtain this result is semidefinite programming.
Abstract Given a directed graph G and an edge weight function w : A(G) M R^+ the maximum directed cut problem (MAX DICUT) is that of finding a directed cut '(S) with maximum total weight. We consider a version of ...
详细信息
Abstract Given a directed graph G and an edge weight function w : A(G) M R^+ the maximum directed cut problem (MAX DICUT) is that of finding a directed cut '(S) with maximum total weight. We consider a version of MAX DICUT -- MAX DICUT with given sizes of parts or MAX DICUT WITH GSP -- whose instance is that of MAX DICUT plus a positive integer k, and it is required to find a directed cut '(S) having maximum weight over all cuts '(S) with |S|=k. We present an approximation algorithm for this problem which is based on semidefinite programming (SDP) relaxation. The algorithm achieves the presently best performance guarantee for a range of k.
This paper studies a stochastic linear quadratic (LQ) control problem in the infinite time horizon with Markovian jumps in parameter values. In contrast to the deterministic case, the cost weighting matrices of the st...
详细信息
This paper studies a stochastic linear quadratic (LQ) control problem in the infinite time horizon with Markovian jumps in parameter values. In contrast to the deterministic case, the cost weighting matrices of the state and control are allowed to be indinifite here. When the generator matrix of the jump process - which is assumed to be a Markov chain - is known and time-invariant, the well-posedness of the indefinite stochastic LQ problem is shown to be equivalent to the solvability of a system of coupled generalized algebraic Riccati equations (CGAREs) that involves equality and inequality constraints. To analyze the CGAREs, linear matrix inequalities (LMIs) are utilized, and the equivalence between the feasibility of the LMIs and the solvability of the CGAREs is established. Finally, an LMI-based algorithm is devised to slove the CGAREs via a semidefinite programming, and numerical results are presented to illustrate the proposed algorithm.
We study the lift-and-project procedures for solving combinatorial optimization problems, as described by Lovaasz and Schrijver, in the context of the stable set problem on graphs. We investigate how the procedures...
详细信息
We study the lift-and-project procedures for solving combinatorial optimization problems, as described by Lovaasz and Schrijver, in the context of the stable set problem on graphs. We investigate how the procedures' performances change as we apply fundamental graph operations. We show that the odd subdivision of an edge and the subdivision of a star operations (as well as their common generalization, the stretching of a vertex operation) cannot decrease the N-0-, N-, or N+-rank of the graph. We also provide graph classes (which contain the complete graphs) where these operations do not increase the N-0- or the N-rank. Hence we obtain the ranks for these graphs, and we also present some graph-minor like characterizations for them. Despite these properties we give examples showing that in general most of these operations can increase these ranks. Finally, we provide improved bounds for N+-ranks of graphs in terms of the number of nodes in the graph and prove that the subdivision of an edge or cloning a vertex can increase the N+-rank of a graph.
作者：
Uhlmann, Jeffrey K.201 EBW
Department of Computer Engineering University of Missouri - Columbia Columbia MO 65211 United States
This paper presents a general, rigorous, and fault-tolerant framework for maintaining consistent mean and covariance estimates in an arbitrary, dynamic, distributed network of information processing nodes. In particul...
详细信息
We study the lift-and-project procedures for solving combinatorial optimization problems, as described by Lovaasz and Schrijver, in the context of the stable set problem on graphs. We investigate how the procedures...
详细信息
We study the lift-and-project procedures for solving combinatorial optimization problems, as described by Lovaasz and Schrijver, in the context of the stable set problem on graphs. We investigate how the procedures' performances change as we apply fundamental graph operations. We show that the odd subdivision of an edge and the subdivision of a star operations (as well as their common generalization, the stretching of a vertex operation) cannot decrease the N-0-, N-, or N+-rank of the graph. We also provide graph classes (which contain the complete graphs) where these operations do not increase the N-0- or the N-rank. Hence we obtain the ranks for these graphs, and we also present some graph-minor like characterizations for them. Despite these properties we give examples showing that in general most of these operations can increase these ranks. Finally, we provide improved bounds for N+-ranks of graphs in terms of the number of nodes in the graph and prove that the subdivision of an edge or cloning a vertex can increase the N+-rank of a graph.
This paper studies a stochastic linear quadratic (LQ) control problem in the infinite time horizon with Markovian jumps in parameter values. In contrast to the deterministic case, the cost weighting matrices of the st...
详细信息
This paper studies a stochastic linear quadratic (LQ) control problem in the infinite time horizon with Markovian jumps in parameter values. In contrast to the deterministic case, the cost weighting matrices of the state and control are allowed to be indinifite here. When the generator matrix of the jump process - which is assumed to be a Markov chain - is known and time-invariant, the well-posedness of the indefinite stochastic LQ problem is shown to be equivalent to the solvability of a system of coupled generalized algebraic Riccati equations (CGAREs) that involves equality and inequality constraints. To analyze the CGAREs, linear matrix inequalities (LMIs) are utilized, and the equivalence between the feasibility of the LMIs and the solvability of the CGAREs is established. Finally, an LMI-based algorithm is devised to slove the CGAREs via a semidefinite programming, and numerical results are presented to illustrate the proposed algorithm.
暂无评论