A linear program has a unique least 2-norm solution, provided that the linear program has a solution. To locate this solution, most of the existing methods were devised to solve certain equivalent perturbed quadratic ...
详细信息
A linear program has a unique least 2-norm solution, provided that the linear program has a solution. To locate this solution, most of the existing methods were devised to solve certain equivalent perturbed quadratic programs or unconstrained minimization problems. We provide in this paper a new theory which is different from these traditional methods and is an effective numerical method for seeking the least 2-norm solution of a linear program. The essence of this method is a (interior-point-like) path-following algorithm that traces a newly introduced regularized central path that is fairly different from the central path used in interior-point methods. One distinguishing feature of our method is that it imposes no assumption on the problem. The iterates generated by this algorithm converge to the least 2-norm solution whenever the linear program is solvable;otherwise, the iterates converge to a point which gives a minimal KKT residual when the linear program is unsolvable.
This paper proposes a new approach to solve the problem of designing optimal proportional-integral-derivative (PID) controllers that minimize an H 2 -norm associated with the set-point response while subjecting to an...
详细信息
This paper proposes a new approach to solve the problem of designing optimal proportional-integral-derivative (PID) controllers that minimize an H 2 -norm associated with the set-point response while subjecting to an H ∞ -norm on the load disturbance rejection. The proposed design approach consists of constructing the feasible domain in the controller gain space and searching over the domain the optimal gain values of minimizing the H 2 -norm objective. The construction of the feasible domain that satisfies the requirements of closed-loop stability and H ∞ -norm constraint on disturbance-rejection is achieved through analytically characterizing the domain boundary with the notion of principal points associated with the value set of differentiable mapping. The feasible domain boundary construction greatly save the computational effort required to search for the H 2 -optimal controller gain values that satisfy both the stability and disturbance rejection requirements.
Geometric programming (GP) is a class of optimization problems with a nonlinear objective function subject to a set of nonlinear constraints. The problems considered in this paper are posynomial GP problems, whose sol...
详细信息
Geometric programming (GP) is a class of optimization problems with a nonlinear objective function subject to a set of nonlinear constraints. The problems considered in this paper are posynomial GP problems, whose solutions can be obtained by solving a dual linear programing problem. The primary purpose of this paper is to investigate the quality of solutions found by, the application of a path-following algorithm, which is one of interior point methods. Two majorr approches to solve posynomial GP problems are investigated. One is dual GP as Generalized Lmear Programming (GLP) and the other is the traditional dual GP. The test results suggest that dual GP as GLP approach is advantageous over the posynomial one in the event that high a~curacy of the solution is required or critically important.
A large-step infeasible path-following method is proposed for solving general linear complementarity problems with sufficient matrices. If the problem has a solution, the algorithm is superlinearly convergent from any...
详细信息
A large-step infeasible path-following method is proposed for solving general linear complementarity problems with sufficient matrices. If the problem has a solution, the algorithm is superlinearly convergent from any positive starting points, even for degenerate problems. The algorithm generates points in a large neighborhood of the central path. Each iteration requires only one matrix factorization and at most three (asymptotically only two) backsolves. It has been recently proved that any sufficient matrix is a P*(kappa)-matrix for some kappa greater than or equal to 0. The computational complexity of the algorithm depends on kappa as well as on a feasibility measure of the starting point. If the starting point is feasible or close to being feasible, then the iteration complexity is O((1 + kappa)root nL). Otherwise, for arbitrary positive and large enough starting points, the iteration complexity is O((1 + kappa)(2)nL). We note that, while computational complexity depends on kappa, the algorithm itself does not.
This paper considers signomial geometric programming (GP) dual problems, a class of nonconvex nonlinear programming problems possessing multiple locally optimal solutions, The primary purpose of this paper is to inves...
详细信息
This paper considers signomial geometric programming (GP) dual problems, a class of nonconvex nonlinear programming problems possessing multiple locally optimal solutions, The primary purpose of this paper is to investigate the quality of solutions found by use of a path-following algorithm. The path-following method may be applied to either the original nonconvex problem, or to each of a sequence of convex posynomial GP problems approximating the original problem. For each test problem, the algorithms were initiated with thousands of different starting points. It was determined that, when the stopping criterion was relaxed for early posynomial GP problems in the sequence, the ultimate solution tended to be of better quality, and more frequently globally optimal. (C) 1997 Elsevier Science B.V.
The success of interior point algorithms for large-scale linear programming has prompted researchers to extend these algorithms to the semi-definite programming (SDP) case. In this paper, the method of approximate cen...
详细信息
The success of interior point algorithms for large-scale linear programming has prompted researchers to extend these algorithms to the semi-definite programming (SDP) case. In this paper, the method of approximate centers of Roos and Vial [14] is extended to SDP. The algorithm is subsequently extended to a primal-dual infeasible start algorithm, by employing a suitable self-dual embedding of the primal-dual SDP problem pair.
We explain and justify a path-following algorithm for solving the equations A(C)(x) = a, where A is a linear transformation from R(n) to R(n), C is a polyhedral convex subset of R(n), and A(C) is the associated normal...
详细信息
We explain and justify a path-following algorithm for solving the equations A(C)(x) = a, where A is a linear transformation from R(n) to R(n), C is a polyhedral convex subset of R(n), and A(C) is the associated normal map. When A(C) is coherently oriented, we are able to prove that the pathfollowing method terminates at the unique solution of A(C)(x)= a, which is a generalization of the well known fact that Lemke's method terminates at the unique solution of LCP (q, M) when M is a P = matrix. Otherwise, we identify two classes of matrices which are analogues of the class of copositive-plus and L-matrices in the study of the linear complementarity problem. We then prove that our algorithm processes A(C)(x) = a when A is the linear transformation associated with such matrices. That is, when applied to such a problem, the algorithm will find a solution unless the problem is infeasible in a well specified sense.
We consider a primal-scaling path-following algorithm for solving a certain class of monotone variational inequality problems. Included in this class are the convex separable programs considered by Monteiro and Adler ...
详细信息
We consider a primal-scaling path-following algorithm for solving a certain class of monotone variational inequality problems. Included in this class are the convex separable programs considered by Monteiro and Adler and the monotone linear complementarity problem. This algorithm can start from any interior solution and attain a global linear rate of convergence with a convergence ratio of 1 - c/square-root m, where m denotes the dimension of the problem and c is a certain constant. One can also introduce a line search strategy to accelerate the convergence of this algorithm.
An estimation method of region is presented, in which a solution path of the so-called Newton type homotopy equation is guaranteed to exist, when it is applied to a certain class of uniquely solvable nonlinear equatio...
详细信息
An estimation method of region is presented, in which a solution path of the so-called Newton type homotopy equation is guaranteed to exist, when it is applied to a certain class of uniquely solvable nonlinear equations. The region can be estimated a posteriori, and its upper bound also can be estimated a priori.
We describe a new potential function and a sequence of ellipsoids in the path-following algorithm for convex quadratic programming. Each ellipsoid in the sequence contains all of the optimal primal and dual slack vect...
详细信息
We describe a new potential function and a sequence of ellipsoids in the path-following algorithm for convex quadratic programming. Each ellipsoid in the sequence contains all of the optimal primal and dual slack vectors. Furthermore, the volumes of the ellipsoids shrink at the ratio $2^{ - \Omega (\sqrt n )} $ , in comparison to 2?Ω(1) in Karmarkar's algorithm and 2?Ω(1/n) in the ellipsoid method. We also show how to use these ellipsoids to identify the optimal basis in the course of the algorithm for linear programming.
暂无评论