The problems of testing the feasibility of a system of linear inequalities, or strict inequalities, are well-known to be the most fundamental problems in the theory and practice of linearprogramming. From Gordan'...
详细信息
The problems of testing the feasibility of a system of linear inequalities, or strict inequalities, are well-known to be the most fundamental problems in the theory and practice of linearprogramming. From Gordan's Theorem it follows that Ax < b is feasible if and only if the homogeneous problem A(T)y = 0, b(T)y + S = 0, (0, 0) not equal (y, s) >= (0, 0), is infeasible. We prove a stronger result: if Ax < b is feasible, then there is a feasible point satisfying x = A(T)W, for some w < 0. Moreover, there exists a feasible x = ATW satisfying AA(T)w = b + delta w(-1), where 3 is a positive scalar and w(-1) = (1/w(1),..., 1/w(n))(T). The existence of w and its computation is motivated by a procedure suggested by Chvatal for solving linearprogramming as homogeneous problems, as well as results on diagonal matrix scaling of positive semidefinite matrices. Not only these reveal the significance of the homogeneous problem, but also practical and theoretical relevance of Khachiyan and Kalantari's diagonal matrix scaling algorithm, in computing an interiorpoint of a linear system of inequalities, or in solving linearprogramming itself, over the reals or the rationals. (c) 2006 Elsevier Inc. All rights reserved.
We investigate solution of the maximum cut problem using a polyhedral cut and price approach. The dual of the well-known SDP relaxation of maxcut is formulated as a semi-infinite linearprogramming problem, which is s...
详细信息
We investigate solution of the maximum cut problem using a polyhedral cut and price approach. The dual of the well-known SDP relaxation of maxcut is formulated as a semi-infinite linearprogramming problem, which is solved within an interiorpoint cutting plane algorithm in a dual setting;this constitutes the pricing (column generation) phase of the algorithm. Cutting planes based on the polyhedral theory of the maxcut problem are then added to the primal problem in order to improve the SDP relaxation;this is the cutting phase of the algorithm. We provide computational results, and compare these results with a standard SDP cutting plane scheme.
We investigate solution of the maximum cut problem using a polyhedral cut and price approach. The dual of the well-known SDP relaxation of maxcut is formulated as a semi-infinite linearprogramming problem, which is s...
详细信息
We investigate solution of the maximum cut problem using a polyhedral cut and price approach. The dual of the well-known SDP relaxation of maxcut is formulated as a semi-infinite linearprogramming problem, which is solved within an interiorpoint cutting plane algorithm in a dual setting;this constitutes the pricing (column generation) phase of the algorithm. Cutting planes based on the polyhedral theory of the maxcut problem are then added to the primal problem in order to improve the SDP relaxation;this is the cutting phase of the algorithm. We provide computational results, and compare these results with a standard SDP cutting plane scheme.
The classic introduction to engineering optimization theory and practice--now expanded and updated Engineering optimization helps engineers zero in on the most effective, efficient solutions to problems. This text pro...
ISBN:
(数字)9780470117811
ISBN:
(纸本)9780471558149
The classic introduction to engineering optimization theory and practice--now expanded and updated Engineering optimization helps engineers zero in on the most effective, efficient solutions to problems. This text provides a practical, real-world understanding of engineering optimization. Rather than belaboring underlying proofs and mathematical derivations, it emphasizes optimization methodology, focusing on techniques and stratagems relevant to engineering applications in design, operations, and analysis. It surveys diverse optimization methods, ranging from those applicable to the minimization of a single-variable function to those most suitable for large-scale, nonlinear constrained problems. New material covered includes the duality theory, interiorpointmethods for solving LP problems, the generalized Lagrange multiplier method and generalization of convex functions, and goal programming for solving multi-objective optimization problems. A practical, hands-on reference and text, Engineering Optimization, Second Edition covers: * Practical issues, such as model formulation, implementation, starting point generation, and more * Current, state-of-the-art optimization software * Three engineering case studies plus numerous examples from chemical, industrial, and mechanical engineering * Both classical methods and new techniques, such as successive quadratic programming, interiorpointmethods, and goal programming Excellent for self-study and as a reference for engineering professionals, this Second Edition is also ideal for senior and graduate courses on engineering optimization, including television and online instruction, as well as for in-plant training.
Second-order cone programming (SOCP) problems are typically solved by interiorpointmethods. As in linearprogramming (LP), interiorpointmethods can, in theory, solve SOCPs in polynomial time and can, in practice, ...
详细信息
Second-order cone programming (SOCP) problems are typically solved by interiorpointmethods. As in linearprogramming (LP), interiorpointmethods can, in theory, solve SOCPs in polynomial time and can, in practice, exploit sparsity in the problem data. Specifically, when cones of large dimension are present, the density that results in the normal equations that are solved at each iteration can be remedied in a manner similar to the treatment of dense columns in an LP. Here we propose a product-form Cholesky factorization (PFCF) approach, and show that it is more numerically stable than the alternative Sherman-Morrison-Woodbury approach. We derive several PFCF variants and compare their theoretical performance. Finally, we prove that the elements of L in the Cholesky factorizations LDLT that arise in interiorpointmethods for SOCP are uniformly bounded as the duality gap tends to zero as long as the iterates remain is some conic neighborhood of the cental path.
interiorpointmethods are not only the most effective methods for solving optimisation problems in practice but they also have polynomial time complexity. However, there is still a gap between the practical behavior ...
详细信息
interiorpointmethods are not only the most effective methods for solving optimisation problems in practice but they also have polynomial time complexity. However, there is still a gap between the practical behavior of the interiorpoint method algorithms and their theoretical complexity results. In this paper, by focusing on linearprogramming problems, we introduce a new family of kernel functions that have some simple and easy to check properties. We present a simplified analysis to obtain the complexity of generic interiorpointmethods based on the proximity functions induced by these kernel functions. Finally, we prove that this family of kernel functions leads to improved iteration bounds of the large-update interiorpointmethods.
作者:
Wright, MHNYU
Courant Inst Math Sci Dept Comp Sci New York NY 10012 USA
interiormethods are a pervasive feature of the optimization landscape today, but it was not always so. Although interior-point techniques, primarily in the form of barrier methods, were widely used during the 1960s f...
interiormethods are a pervasive feature of the optimization landscape today, but it was not always so. Although interior-point techniques, primarily in the form of barrier methods, were widely used during the 1960s for problems with nonlinear constraints, their use for the fundamental problem of linearprogramming was unthinkable because of the total dominance of the simplex method. During the 1970s, barrier methods were superseded, nearly to the point of oblivion, by newly emerging and seemingly more efficient alternatives such as augmented Lagrangian and sequential quadratic programmingmethods. By the early 1980s, barrier methods were almost universally regarded as a closed chapter in the history of optimization. This picture changed dramatically in 1984, when Narendra Karmarkar announced a fast polynomial-time interior method for linearprogramming;in 1985, a formal connection was established between his method and classical barrier methods. Since then, interiormethods have continued to transform both the theory and practice of constrained optimization. We present a condensed, unavoidably incomplete look at classical material and recent research about interiormethods.
A solution to the single-snapshot non-linear L-1 estimation of the power transmission network is presented. The non-linear L-1 estimation problem is formulated as a non-linear program and solved using a primal-dual in...
详细信息
A solution to the single-snapshot non-linear L-1 estimation of the power transmission network is presented. The non-linear L-1 estimation problem is formulated as a non-linear program and solved using a primal-dual interior-point approach. The efficiency of this approach is dependent on the numerical procedure used to solve the reduced Karush-Kuhn-Tucker (KKT) system of equations. It is shown that two mathematically equivalent formulations of the non-linearprogramming problem can be obtained. These formulations lend themselves to fundamentally different numerical procedures to solve the reduced KKT system. Numerical testing on IEEE systems is used to quantify the performance of the interior-point approach on both formulations. Comparisons are also carried out with a recent implementation of an iteratively reweighted least-squares method for non-linear L-1 regression.
暂无评论