A wide variety of nonlinear convex optimization problems can be cast as problems involving Linear matrix inequalities (LMIs), and hence efficiently solved using recently developed interior-point methods. In this paper...
详细信息
A wide variety of nonlinear convex optimization problems can be cast as problems involving Linear matrix inequalities (LMIs), and hence efficiently solved using recently developed interior-point methods. In this paper, we will consider two classes of optimization problems with LMI constraints: (1) The semidefinite programming problem, i.e., the problem of minimizing a linear function subject to a linear matrix inequality. semidefinite programming is an important numerical tool for analysis and synthesis in systems and control theory. It has also been recognized in combinatorial optimization as a valuable technique for obtaining bounds on the solution of NP-hard problems. (2) The problem of maximizing the determinant of a positive definite matrix subject to Linear matrix inequalities. This problem has applications in computational geometry, experiment design, information and communication theory, and other fields. We review some of these applications, including some interesting applications that are less well known and arise in statistics, optimal experiment design and VLSI. (C) 1999 Elsevier Science B.V, and IMACS. All rights reserved.
This paper describes CSDP, a library of routines that implements a predictor corrector variant of the semidefinite programming algorithm of Helmberg, Rendl, Vanderbei, and Wolkowicz. The main advantages of this code a...
详细信息
This paper describes CSDP, a library of routines that implements a predictor corrector variant of the semidefinite programming algorithm of Helmberg, Rendl, Vanderbei, and Wolkowicz. The main advantages of this code are that it can be used as a stand alone solver or as a callable subroutine, that it is written in C for efficiency, that it makes effective use of sparsity in the constraint matrices, and that it includes support for linear inequality constraints in addition to linear equality constraints. We discuss the algorithm used, its computational complexity, and storage requirements. Finally, we present benchmark results for a collection of test problems.
We propose a framework for developing and analyzing primal-dual interior point algorithms for semidefinite programming. This framework is an extension of the v-space approach that was developed by Kojima et al. (1991)...
详细信息
We propose a framework for developing and analyzing primal-dual interior point algorithms for semidefinite programming. This framework is an extension of the v-space approach that was developed by Kojima et al. (1991) for linear complementarity problems. The extension to semidefinite programming allows us to interpret Nesterov-Todd type directions (Nesterov and Todd 1995, 1997) as Newton search directions. Our approach does not involve any barrier function. Several primal-dual path-following algorithms for semidefinite programming are analyzed. The treatment of these algorithms for semidefinite programming in our setting bears great similarity to the linear programming case. (C) 1999 Published by Elsevier Science B.V. and IMACS. All rights reserved.
The paper describes a method for computing a lower bound of the global minimum of an indefinite quadratic form over a simplex. The bound is derived by computing an underestimator of the convex envelope by solving a se...
详细信息
The paper describes a method for computing a lower bound of the global minimum of an indefinite quadratic form over a simplex. The bound is derived by computing an underestimator of the convex envelope by solving a semidefinite program (SDP). This results in a convex quadratic program (QP). It is shown that the optimal value of the QP is a lower bound of the optimal value of the original problem. Since there exist fast (polynomial time) algorithms for solving SDP's and QP's the bound can be computed in reasonable time. Numerical experiments indicate that the relative error of the bound is about 10 percent for problems up to 20 variables, which is much better than a known SDP bound.
Remarkable breakthroughs have been made recently in obtaining approximate solutions to some fundamental NP-hard problems, namely Max-Cut, Max k-Cut, Max-Sat, Max-Dicut, Max-bisection, k-vertex coloring, maximum indepe...
详细信息
Remarkable breakthroughs have been made recently in obtaining approximate solutions to some fundamental NP-hard problems, namely Max-Cut, Max k-Cut, Max-Sat, Max-Dicut, Max-bisection, k-vertex coloring, maximum independent set, etc. All these breakthroughs involve polynomial time randomized algorithms based upon semidefinite programming, a technique pioneered by Goemans and Williamson. In this paper, we give techniques to derandomize the above class of randomized algorithms, thus obtaining polynomial time deterministic algorithms with the same approximation ratios for the above problems. At the heart of our technique is the use of spherical symmetry to convert a nested sequence of n integrations, which cannot be approximated sufficiently well in polynomial time, to a nested sequence of just a constant number of integrations, which can be approximated sufficiently well in polynomial time.
SDPLIB is a collection of semidefinite programming (SDP) test problems. The problems are drawn from a variety of applications, including truss topology design, control systems engineering, and relaxations of combinato...
详细信息
SDPLIB is a collection of semidefinite programming (SDP) test problems. The problems are drawn from a variety of applications, including truss topology design, control systems engineering, and relaxations of combinatorial optimization problems. The current version of the library contains a total of 92 SDP problems encoded in a standard format. It is hoped that SDPLIB will stimulate the development of improved software for the solution of SDP problems.
semidefinite programming problem is an important optimization problem that has been extensively investigated. A real-time solution method for solving such a problem, however, is still not get available. This paper pro...
详细信息
semidefinite programming problem is an important optimization problem that has been extensively investigated. A real-time solution method for solving such a problem, however, is still not get available. This paper proposes a novel recurrent neural network for this purpose. First, an auxiliary cost function is introduced to minimize the duality gap between the admissible points of the primal problem and the corresponding dual problem. Then a dynamical system is constructed to drive the duality gap to zero exponentially along any trajectory by modifying the gradient of the auxiliary cost function. Furthermore, a subsystem is developed to circumvent in the computation of matrix inverse, so that the resulting overall dynamical system can be realized using a recurrent neural network, The architecture of the resulting neural network is discussed. The operating characteristics and performance of the proposed approach are demonstrated by means of simulation results.
Mehrotra type primal-dual predictor-corrector interior-point algorithms for semidefinite programming are implemented, using the homogeneous formulation proposed and analyzed by Potra and Sheng. Several search directio...
详细信息
Mehrotra type primal-dual predictor-corrector interior-point algorithms for semidefinite programming are implemented, using the homogeneous formulation proposed and analyzed by Potra and Sheng. Several search directions, including the AHO, HKM, NT, Toh, and Gu directions, are used. A rank-2 update technique is employed in our MATLAB code so that the computation of homogeneous directions is only slightly more expensive than in the nonhomogeneous case. However, the homogeneous algorithms generally take fewer iterations to compute an approximate solution within a desired accuracy. Numerical results show that the homogeneous algorithms outperform their non-homogeneous counterparts, with improvement of more than 20% in many cases, in terms of total CPU time.
Primal-dual affine-scaling methods have recently been extended from linear programming to semidefinite programming. We show how to analyze these methods in the framework of potential reduction algorithms. The analysis...
详细信息
Primal-dual affine-scaling methods have recently been extended from linear programming to semidefinite programming. We show how to analyze these methods in the framework of potential reduction algorithms. The analysis suggests implementable variants of the methods as 'long step predictor-corrector' algorithms, where the step length is determined by the potential function. A numerical comparison with the potential reduction method of Nesterov and Todd is presented. (C) 1999 Elsevier Science B.V. and IMACS. All rights reserved.
semidefinite programming concerns the problem of optimizing a linear function over a section of the cone of semidefinite matrices. In the cone affine scaling approach, we replace the cone of semidefinite matrices by a...
详细信息
semidefinite programming concerns the problem of optimizing a linear function over a section of the cone of semidefinite matrices. In the cone affine scaling approach, we replace the cone of semidefinite matrices by a certain inscribed cone, in such a way that the resulting optimization problem is analytically solvable. The now easily obtained solution to this modified problem serves as an approximate solution to the semidefinite programming problem. The inscribed cones that we use are affine transformations of second order cones, hence the name 'cone affine scaling'. Compared to other primal-dual affine scaling algorithms for semidefinite programming (see de Klerk, Roos and Terlaky (1997)), our algorithm enjoys the lowest computational complexity, (C) 1999 Published by Elsevier Science B.V. and IMACS. All rights reserved.
暂无评论