Given a partial symmetric matrix A with only certain elements specified, the Euclidean distance matrix completion problem (EDMCP) is to find the unspecified elements of A that make A a Euclidean distance matrix (EDM)....
详细信息
Given a partial symmetric matrix A with only certain elements specified, the Euclidean distance matrix completion problem (EDMCP) is to find the unspecified elements of A that make A a Euclidean distance matrix (EDM). In this paper, we follow the successful approach in [20] and solve the EDMCP by generalizing the completion problem to allow for approximate completions. In particular, we introduce a primal-dual interior-point algorithm that solves an equivalent (quadratic objective function) semidefinite programming problem (SDP). Numerical results are included which illustrate the efficiency and robustness of our approach. Our randomly generated problems consistently resulted in low dimensional solutions when no completion existed.
This paper considers the problem of minimizing a quadratic cost subject to purely quadratic equality constraints. This problem is tackled by first relating it to a standard semidefinite programming problem. The approa...
详细信息
This paper considers the problem of minimizing a quadratic cost subject to purely quadratic equality constraints. This problem is tackled by first relating it to a standard semidefinite programming problem. The approach taken leads to a dynamical systems analysis of semidefinite programming and the formulation of a gradient descent flow which can be used to solve semidefinite programming problems. Though the reformulation of the initial problem as a semidefinite programming problem does not in general lead directly to a solution of the original problem, the initial problem is solved by using a modified flow incorporating a penalty function.
Monteiro and Tsuchiya [22] have proposed two primal-dual Newton directions for semidefinite programming, referred to as the MT directions, and established polynomial convergence of path-following methods based on them...
详细信息
Monteiro and Tsuchiya [22] have proposed two primal-dual Newton directions for semidefinite programming, referred to as the MT directions, and established polynomial convergence of path-following methods based on them. This paper reports some computational results on the performance of interior-point predictor-corrector methods based on the MT directions and a variant of these directions, called the S-Ch-MT direction. We discuss how to compute these directions efficiently and derive their corresponding computational complexities. A main feature of our analysis is that computational formulae for these directions are derived from a unified point of view which entirely avoids the use of Kronecker product. Using this unified approach, we also present schemes to compute the Alizadeh-Haeberly-Overton (AHO) direction, the Nesterov-Todd direction and the HRVW/KSH/M direction with computational complexities (for dense problems) better than previously reported in the literature. We present some computational results for small dense problems, which are quite promising. We have obtained better performance for the methods based on the AHO, NT and HRVW/KSH/M directions. We have also observed that the method based on the S-Ch-MT direction compares favorably with the new implementation of the methods based on the NT direction and the HRVW/KSH/M direction.
In this paper, we give an example of a semidefinite programming problem in which primal-dual affine-scaling algorithms using the HRVW/KSH/M, MT, and AHO directions fail. We prove that each of these algorithms can gene...
详细信息
In this paper, we give an example of a semidefinite programming problem in which primal-dual affine-scaling algorithms using the HRVW/KSH/M, MT, and AHO directions fail. We prove that each of these algorithms can generate a sequence converging to a non-optimal solution and that, for the AHO direction, even its associated continuous trajectory can converge to a non-optimal point. In contrast with these directions, we show that the primal-dual affine-scaling algorithm using the NT direction for the same semidefinite programming problem always generates a sequence converging to the optimal solution. Both primal and dual problems have interior feasible solutions and unique optimal solutions which satisfy strict complementarity, and are nondegenerate everywhere.
A semidefinite programming problem is a mathematical program in which the objective function is linear in the unknowns and the constraint set is defined by a linear matrix inequality. This problem is nonlinear, nondif...
详细信息
A semidefinite programming problem is a mathematical program in which the objective function is linear in the unknowns and the constraint set is defined by a linear matrix inequality. This problem is nonlinear, nondifferentiable but convex. It covers several standard problems, such as linear and quadratic programming, and has many applications in engineering. In this paper, we introduce the notion of minimal-penalty path, which is defined as the collection of minimizers for a family of convex optimization problems, and propose two methods for solving the problem by following the minimal-penalty path from the exterior of the feasible set. Our first method, which is also a constraint-aggregation method, achieves the solution by solving a sequence of linear programs, but exhibits a zigzagging behavior around the minimal-penalty path. Our second method eliminates the above drawback by following efficiently the minimum-penalty path through the centering and ascending steps. The global convergence of the methods is proved and their performance is illustrated by means of an example.
Two nonsymmetric search directions for semidefinite programming, the XZ and ZX search directions, are proposed. They are derived from a nonsymmetric formulation of the semidefinite programming problem. The XZ directio...
详细信息
Two nonsymmetric search directions for semidefinite programming, the XZ and ZX search directions, are proposed. They are derived from a nonsymmetric formulation of the semidefinite programming problem. The XZ direction corresponds to the direct linearization of the central path equation XZ = nu I;while the ZX direction corresponds to ZX = nu I. The XZ and ZX directions are well defined if both X and Z are positive definite matrices, where X may be nonsymmetric. We present an algorithm using the XZ and ZX directions alternately following the Mehrotra predictor-corrector framework. Numerical results show that the XZ/ZX algorithm, in many cases, requires less CPU time than the XZ+ZX method of Alizadeh, Overton, and Haeberly [SIAM J. Optim., 8 (1998), pp. 746-768] while achieving similar accuracy.
We study the local convergence of a predictor-corrector algorithm for semidefinite programming problems based on the Monteiro-Zhang unified direction whose polynomial convergence was recently established by Monteiro. ...
详细信息
We study the local convergence of a predictor-corrector algorithm for semidefinite programming problems based on the Monteiro-Zhang unified direction whose polynomial convergence was recently established by Monteiro. Under strict complementarity and nondegeneracy assumptions superlinear convergence with Q-order 1.5 is proved if the scaling matrices in the corrector step have bounded condition number. A version of the predictor-corrector algorithm enjoys quadratic convergence if the scaling matrices in both predictor and corrector steps have bounded condition numbers. The latter results apply in particular to algorithms using the Alizadeh-Haeberly-Overton (AHO) direction since there the scaling matrix is the identity matrix.
Free material design deals with the question of finding the stiffest structure with respect to one or more given loads which can be made when both the distribution of material and the material itself can freely vary. ...
详细信息
Free material design deals with the question of finding the stiffest structure with respect to one or more given loads which can be made when both the distribution of material and the material itself can freely vary. The case of one single load has been discussed in several recent papers, and an efficient numerical approach was presented in [M. Kocvara, M. Zibulevsky, and J. Zow, RAIRO Model. Math. Anal. Numer. 32 (1998), pp. 255-281]. We attack here the multiload situation (understood in the worst-case sense), which is of much more interest for applications but also significantly more challenging from both the theoretical and the numerical points of view. After a series of transformation steps we reach a problem formulation for which we can prove existence of a solution;a suitable discretization leads to a semidefinite programming problem for which modern polynomial time algorithms of interior point type are available. A number of numerical examples demonstrates the efficiency of our approach.
This paper establishes the polynomial convergence of a new class of primal-dual interior-point path-following feasible algorithms for semidefinite programming (SDP) whose search directions are obtained by applying New...
详细信息
This paper establishes the polynomial convergence of a new class of primal-dual interior-point path-following feasible algorithms for semidefinite programming (SDP) whose search directions are obtained by applying Newton's method to the symmetric central path equation (PXPT)(1/2)(P-T SP-1)(PXPT)(1/2) - mu I = 0, where P is a nonsingular matrix. Specifically, we show that the short-step path-following algorithm based on the Frobenius norm neighborhood and the semilong-step path-following algorithm based on the operator 2-norm neighborhood have O(root nL) and O(nL) iteration-complexity bounds, respectively. When P = I, this yields the first polynomially convergent semilong-step algorithm based on a pure Newton direction. Restricting the scaling matrix P at each iteration to a certain subset of nonsingular matrices, we are able to establish an O(n(3/2) L) iteration complexity for the long-step path-following method. The resulting subclass of search directions contains both the Nesterov-Todd direction and the Helmberg-Rendl-Vanderbei-Wolkowicz/Kojima-Shindoh-Hara/Monteiro direction.
We discuss several different search directions which can be used in primal-dual interior-point methods for semidefinite programming problems and investigate their theoretical properties, including scale invariance, pr...
详细信息
We discuss several different search directions which can be used in primal-dual interior-point methods for semidefinite programming problems and investigate their theoretical properties, including scale invariance, primal-dual symmetry, and whether they always generate well-defined directions. Among the directions satisfying all but at most two of these desirable properties are the Alizadeh-Haeberly-Overton, Helmberg-Rendl-Vanderbei-Wolkowicz/Kojima-Shindoh-Hara/Monteiro, Nesterov-Todd, Gu, and Toh directions, as well as directions we will call the MTW and Half directions. The first five of these appear to be the best in our limited computational testing also.
暂无评论