We construct a class of path-following algorithms for solving semidefinite problems with linear-quadratic functionals. Complexity estimates similar to the best known for the case of the standard convex quadratic progr...
详细信息
We construct a class of path-following algorithms for solving semidefinite problems with linear-quadratic functionals. Complexity estimates similar to the best known for the case of the standard convex quadratic programming problem are obtained. Complete proofs of all results are included.
We propose a new interior-point-based method to minimize a linear function of a matrix variable subject to linear equality and inequality constraints over the set of positive semidefinite matrices. We show that the ap...
详细信息
We propose a new interior-point-based method to minimize a linear function of a matrix variable subject to linear equality and inequality constraints over the set of positive semidefinite matrices. We show that the approach is very efficient for graph bisection problems such as max-cut. Other applications include max-min eigenvalue problems and relaxations for the stable set problem.
In a second-order cone program (SOCP) a linear function is minimized over the intersection of an affine set and the product of second-order (quadratic) cones. SOCPs are nonlinear convex problems that include linear an...
详细信息
In a second-order cone program (SOCP) a linear function is minimized over the intersection of an affine set and the product of second-order (quadratic) cones. SOCPs are nonlinear convex problems that include linear and (convex) quadratic programs as special cases, but are less general than semidefinite programs (SDPs). Several efficient primal-dual interior-point methods for SOCP have been developed in the last few years. After reviewing the basic theory of SOCPs, we describe general families of problems that can be recast as SOCPs. These include robust linear programming and robust least-squares problems, problems involving sums or maxima of norms, or with convex hyperbolic constraints. We discuss a variety of engineering applications, such as filter design, antenna array weight design, truss design, and grasping force optimization in robotics. We describe an efficient primal-dual interior-point method for solving SOCPs, which shares many of the features of primal-dual interior-point methods for linear program-ming (LP): Worst-case theoretical analysis shows that the number of iterations required to solve a problem grows at most as the square root of the problem size, while numerical experiments indicate that the typical number of iterations ranges between 5 and 50, almost independent of the problem size. (C) 1998 Elsevier Science Inc. All rights reserved.
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 in...
详细信息
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. (C) 1998 Elsevier Science Ltd. All rights reserved.
We derive some basic results on the geometry of semidefinite programming (SDP) and eigenvalue-optimization, i.e., the minimization of the sum of the k largest eigenvalues of a smooth matrix-valued function. We provide...
详细信息
We derive some basic results on the geometry of semidefinite programming (SDP) and eigenvalue-optimization, i.e., the minimization of the sum of the k largest eigenvalues of a smooth matrix-valued function. We provide upper bounds on the rank of extreme matrices in SDPs, and the first theoretically solid explanation of a phenomenon of intrinsic interest in eigenvalue-optimization. In the spectrum of an optimal matrix, the kth and (k + 1)st largest eigenvalues tend to be equal and frequently have multiplicity greater than two. This clustering is intuitively plausible and has been observed as early as 1975. When the matrix-valued function is affine, we prove that clustering must occur at extreme points of the set of optimal solutions, if the number of variables is sufficiently large. We also give a lower bound on the multiplicity of the critical eigenvalue. These results generalize to the case of a general matrix-valued function under appropriate conditions.
Conventional methods for optimal sizing of wires and transistors use linear resistor-capacitor (RC) circuit models and the Elmore delay as a measure of signal delay. If the RC circuit has a tree topology, the sizing p...
详细信息
Conventional methods for optimal sizing of wires and transistors use linear resistor-capacitor (RC) circuit models and the Elmore delay as a measure of signal delay. If the RC circuit has a tree topology, the sizing problem reduces to a convex optimization problem that can be solved using geometric programming. The tree topology restriction precludes the use of these methods in several sizing problems of significant importance to high-performance deep submicron design, including for example, circuits with loops of resistors, e.g., clock distribution meshes and circuits with coupling capacitors, e.g., buses with crosstalk between the wires. In this paper, we propose a new optimization method that can be used to address these problems. The method is based on the dominant time constant as a measure of signal propagation delay in an RC circuit instead of Elmore delay. Using this measure, sizing of any RC circuit can be cast as a convex optimization problem and solved using recently developed efficient interior-point methods for semidefinite programming. The method is applied to three important sizing problems: clock mesh sizing and topology design, sizing of tristate buses, and sizing of bus line widths and spacings taking crosstalk into account.
In this work, we formulate a new approach to simultaneous constrained model predictive control and identification (MPCI). The proposed approach relies on the development of a persistent excitation (PE) criterion for p...
详细信息
In this work, we formulate a new approach to simultaneous constrained model predictive control and identification (MPCI). The proposed approach relies on the development of a persistent excitation (PE) criterion for processes described by DARX models. That PE criterion is used as an additional constraint in the standard on-line optimization of MPC. The resulting on-line optimization problem of MPCI is handled by successively solving a series of semi-definite programming problems. Advantages of MPCI in comparison to other closed-loop identification methods are (a) Constraints on process inputs and outputs are handled explicitly, (b) Deterioration of output regulation is kept to a minimum, while closed-loop identification is performed. The applicability of the method is illustrated by a number of simulation studies. Theoretical and computational issues for further investigation are suggested. (C) 1998 Elsevier Science Ltd. All rights reserved.
We study convex optimization problems for which the data is not specified exactly and it is only known to belong to a given uncertainty set U, yet the constraints must hold for all possible values of the data from U. ...
详细信息
We study convex optimization problems for which the data is not specified exactly and it is only known to belong to a given uncertainty set U, yet the constraints must hold for all possible values of the data from U. The ensuing optimization problem is called robust optimization. In this paper we lay the foundation of robust convex optimization. In the main part of the paper we show that if U is an ellipsoidal uncertainty set, then for some of the most important generic convex optimization problems (linear programming, quadratically constrained programming, semidefinite programming and others) the corresponding robust convex program is either exactly, or approximately, a tractable problem which lends itself to efficient algorithms such as polynomial time interior point methods.
We develop a long-step polynomial time version of the Method of Analytic Centers for non-linear convex problems. The method traces a multi-parameter surface of analytic centers rather than the usual path, which allows...
详细信息
We develop a long-step polynomial time version of the Method of Analytic Centers for non-linear convex problems. The method traces a multi-parameter surface of analytic centers rather than the usual path, which allows to handle cases with noncentered and possibly infeasible starting point.
Given a nonnegative, symmetric matrix of weights, H, we study the problem of finding an Hermitian, positive semidefinite matrix which is closest to a given Hermitian matrix, A, with respect to the weighting H. This ex...
详细信息
Given a nonnegative, symmetric matrix of weights, H, we study the problem of finding an Hermitian, positive semidefinite matrix which is closest to a given Hermitian matrix, A, with respect to the weighting H. This extends the notion of exact matrix completion problems in that, H-ij = 0 corresponds to the element A(ij) being unspecified (free), white H-ij large in absolute value corresponds to the element A(ij) being approximately specified (fixed). We present optimality conditions, duality theory, and two primal-dual interior-point algorithms. Because of sparsity considerations, the dual-step-first algorithm is more efficient for a large number of free elements, while the primal-step-first algorithm is more efficient for a large number of fixed elements. Included are numerical tests that illustrate the efficiency and robustness of the algorithms.
暂无评论