interiormethods for optimization were widely used in the 1960s, primarily in the form of barrier methods. However, they were not seriously applied to linearprogramming because of the dominance of the simplex method....
The nonlinear rescaling principle employs monotone and sufficiently smooth functions to transform the constraints and/or the objective function into an equivalent problem, the classical Lagrangian which has important ...
详细信息
The nonlinear rescaling principle employs monotone and sufficiently smooth functions to transform the constraints and/or the objective function into an equivalent problem, the classical Lagrangian which has important properties on the primal and the dual spaces. The application of the nonlinear rescaling principle to constrained optimization problems leads to a class of modified barrier functions (MBF's) and MBF Method (MBFM's). Being classical Lagrangians (CL's) for an equivalent problem, the MBF's combine the best properties of the CL's and classical barrier functions (CBF's) but at the same time are free of their most essential deficiencies. Due to the excellent MBF properties, new characteristics of the dual pair convex programming problems have been found and the duality theory for nonconvex constrained optimization has been developed. The MBFM have up to a superlinear rate of convergence and are to the classical barrier functions (CBF's) method as the Multipliers Method for Augmented Lagrangians is to the Classical Penalty Function Method. Based on the dual theory associated with MBF, the method for the simultaneous solution of the dual pair convex programming problems with up to quadratic rates of convergence have been developed. The application of the MBF to linear (LP) and quadratic (QP) programming leads to a new type of multipliers methods which have a much better rate of convergence under lower computational complexity at each step as compared to the CBF methods. The numerical realization of the MBFM leads to the Newton Modified Barrier Method (NMBM). The excellent MBF properties allow us to discover that for any nondegenerate constrained optimization problem, there exists a "hot" start, from which the NMBM has a better rate of convergence, a better complexity bound, and is more stable than the interiorpointmethods, which are based on the classical barrier functions.
This paper describes a primal-dual interior paint algorithm for convex nonlinearprogramming problems subject to linear constraints. The algorithm is based on the path following idea. Each iteration updates a penalty ...
详细信息
This paper describes a primal-dual interior paint algorithm for convex nonlinearprogramming problems subject to linear constraints. The algorithm is based on the path following idea. Each iteration updates a penalty parameter and finds a Newton step associated with the simplified Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem for that parameter. It is shown that the duality gap if reduced at each iteration by a factor of (1 - δ / n;), where S is positive and depends on some parameters associated with the objective function.
This paper proposes a procedure for improving the rate of convergence of interiorpointmethods for linearprogramming. If (x(k)) is the sequence generated by an interiorpoint method, the procedure derives an auxilia...
详细信息
This paper proposes a procedure for improving the rate of convergence of interiorpointmethods for linearprogramming. If (x(k)) is the sequence generated by an interiorpoint method, the procedure derives an auxiliary sequence (x(k)BAR). Under the suitable assumptions it is shown that the sequence (x(k)BAR) converges superlinearly faster to the solution than (x(k)). Application of the procedure to the projective and affine scaling algorithms is discussed and some computational illustration is provided.
A basic characteristic of an interiorpoint algorithm for linearprogramming is the search direction. Many papers on interiorpoint algorithms only give an implicit description of the search direction. In this report ...
详细信息
A basic characteristic of an interiorpoint algorithm for linearprogramming is the search direction. Many papers on interiorpoint algorithms only give an implicit description of the search direction. In this report we derive explicit expressions for the search directions used in many well-known algorithms. Comparing these explicit expressions gives a good insight into the similarities and differences between the various algorithms. Moreover, we give a survey of projected gradient and Newton directions for all potential and barrier functions. This is done both for the affine and projective variants.
In the feasible region of a linearprogramming problem, a number of "desirably good" directions have been defined in connexion with various interiorpointmethods. Each of them determines a contravariant vec...
详细信息
In the feasible region of a linearprogramming problem, a number of "desirably good" directions have been defined in connexion with various interiorpointmethods. Each of them determines a contravariant vector field in the region whose only stable critical point is the optimum point. Some interiorpointmethods incorporate a two- or higher-dimensional search, which naturally leads us to the introduction of the corresponding contravariant multivector field. We investigate the integrability of those multivector fields, i.e., whether a contravariant p-vector field is X(p)-forming, is enveloped by a family of X(q)'s (q > p) or envelops a family of X(q)'s (q < p) (in J.A. Schouten's terminology), where X(q) is a q-dimensional manifold. Immediate consequences of known facts are: (1) The directions hitherto proposed are X1-forming with the optimum point of the linearprogramming problem as the stable accumulation point, and (2) there is an X2-forming contravariant bivector field for which the center path is the critical submanifold. Most of the meaningful p-vector fields with p greater-than-or-equal-to 3 are not X(p)-forming in general, though they envelop that bivector field. This observation will add another circumstantial evidence that the bivector field has a kind of invariant significance in the geometry of interiorpointmethods for linearprogramming. For a kind of appendix, it is noted that, if we have several objectives, i.e., in the case of multiobjective linearprogramming extension to higher dimensions is easily obtained.
In this paper we show the global convergence of the affine scaling methods without assuming any condition on degeneracy. The behavior of the method near degenerate faces is analyzed in detail on the basis of the equiv...
详细信息
In this paper we show the global convergence of the affine scaling methods without assuming any condition on degeneracy. The behavior of the method near degenerate faces is analyzed in detail on the basis of the equivalence between the affine scaling methods for homogeneous LP problems and Karmarkar's method. It is shown that the step-size 1/8, where the displacement vector is normalized with respect to the distance in the scaled space, is sufficient to guarantee the global convergence of the affine scaling methods.
We present a procedure for computing lower bounds for the optimal cost in a linearprogramming problem. Whenever the procedure succeeds, it finds a dual feasible slack and the associated duality gap. Although no proje...
详细信息
We present a procedure for computing lower bounds for the optimal cost in a linearprogramming problem. Whenever the procedure succeeds, it finds a dual feasible slack and the associated duality gap. Although no projective transformations or problem restatements are used, the method coincides with the procedures by Todd and Burrell and by de Ghellinck and Vial when these procedures are applicable. The procedure applies directly to affine potential reduction algorithms, and improves on existent techniques for finding lower bounds.
We present an interiorpoint approach to the zero-one integer programming feasibility problem based on the minimization of a nonconvex potential function. Given a polytope defined by a set of linear inequalities, this...
详细信息
We present an interiorpoint approach to the zero-one integer programming feasibility problem based on the minimization of a nonconvex potential function. Given a polytope defined by a set of linear inequalities, this procedure generates a sequence of strict interiorpoints of this polytope, such that each consecutive point reduces the value of the potential function. An integer solution (not necessarily feasible) is generated at each iteration by a rounding scheme. The direction used to determine the new iterate is computed by solving a nonconvex quadratic program on an ellipsoid. We illustrate the approach by considering a class of difficult set covering problems that arise from computing the 1-width of the incidence matrix of Steiner triple systems.
暂无评论