Semidefinite relaxations of quadratic 0-1 programming or graph partitioning problems are well known to be of high quality. However, solving them by primal-dual interiorpointmethods can take much time even for proble...
详细信息
Semidefinite relaxations of quadratic 0-1 programming or graph partitioning problems are well known to be of high quality. However, solving them by primal-dual interiorpointmethods can take much time even for problems of moderate size. The recent spectral bundle method of Helmberg and Rendl can solve quite efficiently large structured equality-constrained semidefinite programs if the trace of the primal matrix variable is fixed, as happens in many applications. We extend the method so that it can handle inequality constraints without seriously increasing computation time. In addition, we introduce inexact null steps. This abolishes the need of computing exact eigenvectors for subgradients, which brings along significant advantages in theory and in practice. Encouraging preliminary computational results are reported.
A finite element formulation of the limit analysis of perfectly plastic slabs is given. An element with linear moment fields for which equilibrium is satisfied exactly is used in connection with an optimization algori...
详细信息
A finite element formulation of the limit analysis of perfectly plastic slabs is given. An element with linear moment fields for which equilibrium is satisfied exactly is used in connection with an optimization algorithm taking into account the full nonlinearity of the yield criteria. Both load and material optimization problems are formulated and by means of the duality theory of linearprogramming the displacements are extracted from the dual variables. Numerical examples demonstrating the capabilities of the method and the effects of using a more refined representation of the yield criteria are given. (C) 2002 Civil-Comp Ltd. and Elsevier Science Ltd. All rights reserved.
The new concepts of repelling inequalities. repelling paths, and prime analytic centers are introduced, A repelling path is a generalization of the analytic central path for linearprogramming. and we show that this p...
详细信息
The new concepts of repelling inequalities. repelling paths, and prime analytic centers are introduced, A repelling path is a generalization of the analytic central path for linearprogramming. and we show that this path has a unique limit. Furthermore, this limit is the prime analytic center if the set of repelling inequalities contains only those constraints that "shape" the polytope. Because we allow lower dimensional polytopes. the proof techniques are nonstandard and follow from data perturbation analysis. This analysis overcomes the difficulty that analytic centers of lower dimensional polytopes are not necessarily continuous with respect to the polytope's data representation. A second concept introduced here is that of the "prime analytic center". in which we establish its uniqueness in the absence of redundant inequalities. Again. this is well known for full dimensional polytopes, but it is not immediate for lower dimensional polytopes because there are many different data representations of the same polytope. each without any redundant inequalities. These two concepts combine when we introduce ways in which repelling inequalities can interact. (C) 2002 Elsevier Science B.V. All rights reserved.
Research on interior-pointmethods (IPMs) has dominated the field of mathematical programming for the last two decades. Two contrasting approaches in the analysis and implementation of IPMs are the so-called small-upd...
详细信息
ISBN:
(数字)9781400825134
ISBN:
(纸本)9780691091938
Research on interior-pointmethods (IPMs) has dominated the field of mathematical programming for the last two decades. Two contrasting approaches in the analysis and implementation of IPMs are the so-called small-update and large-update methods, although, until now, there has been a notorious gap between the theory and practical performance of these two strategies. This book comes close to bridging that gap, presenting a new framework for the theory of primal-dual IPMs based on the notion of the self-regularity of a function. The authors deal with linear optimization, nonlinear complementarity problems, semidefinite optimization, and second-order conic optimization problems. The framework also covers large classes of linear complementarity problems and convex optimization. The algorithm considered can be interpreted as a path-following method or a potential reduction method. Starting from a primal-dual strictly feasible point, the algorithm chooses a search direction defined by some Newton-type system derived from the self-regular proximity. The iterate is then updated, with the iterates staying in a certain neighborhood of the central path until an approximate solution to the problem is found. By extensively exploring some intriguing properties of self-regular functions, the authors establish that the complexity of large-update IPMs can come arbitrarily close to the best known iteration bounds of IPMs. Researchers and postgraduate students in all areas of linear and nonlinear optimization will find this book an important and invaluable aid to their work.
This paper concerns the use of iterative solvers in interior-pointmethods for linear and quadratic programming problems. We state an adaptive termination rule for the inner iterative scheme and we prove the global co...
详细信息
This paper concerns the use of iterative solvers in interior-pointmethods for linear and quadratic programming problems. We state an adaptive termination rule for the inner iterative scheme and we prove the global convergence of the obtained algorithm, exploiting the theory developed for inexact Newton methods. This approach is promising for problems with special structure on parallel computers. We present an application on Cray T3E/256 and SGI Origin 2000/64 arising in stochastic linearprogramming and robust optimization, where the constraint matrix is block-angular and extremely large.
In this paper, we introduce two direct methods for solving some classes of linearprogramming problems. The first method produces the extreme vertex or a neighboring vertex with respect to the extreme point. The secon...
详细信息
In this paper, we introduce two direct methods for solving some classes of linearprogramming problems. The first method produces the extreme vertex or a neighboring vertex with respect to the extreme point. The second method is based on the game theory. Both these methods can be used in the preparation of the starting point for the simplex method. The efficiency of the improved simplex method, whose starting point is constructed by these introduced methods, is compared with the original simplex method and the interiorpointmethods, and illustrated by examples, Also, we investigate the elimination of excessive constraints. (C) 2001 Elsevier Science B,V. All rights reserved.
作者：
Tunçel, LUniv Waterloo
Fac Math Dept Combinatories & Optimizat Waterloo ON N2L 3G1 Canada
We generalize primal-dual interior-pointmethods for linearprogramming (LP) problems to the convex optimization problems in conic form. Previously, the most comprehensive theory of symmetric primal-dual interior-poin...
详细信息
We generalize primal-dual interior-pointmethods for linearprogramming (LP) problems to the convex optimization problems in conic form. Previously, the most comprehensive theory of symmetric primal-dual interior-point algorithms was given by Nesterov and Todd for feasible regions expressed as the intersection of a symmetric cone with an affine subspace, In our setting, we allow an arbitrary convex cone in place of the symmetric cone. Even though some of the impressive properties attained by Nesterov-Todd algorithms are impossible in this general setting of convex optimization problems, we show that essentially all primal-dual interior-point algorithms for LP can be extended easily to the general setting. We provide three frameworks for primal-dual algorithms, each framework corresponding to a different level of sophistication in the algorithms. As the level of sophistication increases, we demand better formulations of the feasible solution sets. Our algorithms, in return, attain provably better theoretical properties. We also make a very strong connection to quasi-Newton methods by expressing the square of the symmetric primal-dual linear transformation (the so-called scaling) as a quasi-Newton update in the case of the least sophisticated framework.
The optimization problem with the Bilinear Matrix Inequality (BMI) is one of the problems which have greatly interested researchers of system and control theory in the last few years. This inequality permits to reduce...
详细信息
The optimization problem with the Bilinear Matrix Inequality (BMI) is one of the problems which have greatly interested researchers of system and control theory in the last few years. This inequality permits to reduce in an elegant way various problems of robust control into its form. However, in contrast to the linear Matrix Inequality (LMI), which can be solved by interior-point-methods, the BMI is a computationally difficult object in theory and in practice. This article improves the branch-and-bound algorithm of Goh, Safonov and Papavassilopoulos (Journal of Global Optimization, vol. 7, pp. 365-380, 1995) by applying a better convex relaxation of the BMI Eigenvalue Problem (BMIEP), and proposes new Branch-and-Bound and Branch-and-Cut Algorithms. Numerical experiments were conducted in a systematic way over randomly generated problems, and they show the robustness and the efficiency of the proposed algorithms.
暂无评论