Browsing by Author "Zhou, J.L."

Now showing 1 - 6 of 6
  • Thumbnail Image
    Item
    Nonmonotone Line Search for Minimax Problems
    (1991) Zhou, J.L.; Tits, A.L.; ISR
    It was recently shown that, in the solution of smooth constrained optimization problems by sequential programming (SQP), the Maratos effect can be prevented by means of a certain nonmonotone (more precisely, four-step monotone) line search. Using a well known transformation, this scheme can be readily extended to the case of minimax problems. It turns out however that, due to the structure of these problems, one can use a simpler scheme. Such a scheme is proposed and analyzed in this paper. It is also shown that a three-step monotone (rather than four-step monotone) line search, with a relaxed decrease requirement, can be used without losing the theoretical convergence properties. Numerical experiments indicate a significant advantage of the proposed line search over the (monotone) Armijo search.
  • Thumbnail Image
    Item
    A Simple quadratically convergent Interior Point Algorithm for Linear Programming and Convex quadratic Programming
    (1993) Tits, A.L.; Zhou, J.L.; ISR
    An algorithm for linear programming (LP) and convex quadratic programming (CQP) is proposed, based on an interior point iteration introduced more than ten years ago by J. Herskovits for the solution of nonlinear programming problems. Herskovits' iteration can be simplified significantly in the LP/CQP case, and quadratic convergence from any initial point can be achieved. Interestingly the resulting algorithm is closely related to a popular scheme, proposed in 1989 by Kojima et al. independently of Herskovits' work.
  • Thumbnail Image
    Item
    An SQP Algorithm for Finely Discretized Continuous Minimax Problems and Other Minimax Problems with Many Objective Functions
    (1993) Zhou, J.L.; Tits, A.L.; ISR
    A common strategy for achieving global convergence in the solution of semi-infinite programming (SIP) problems, and in particular of continuous minimax problems, is to (approximately) solve a sequence of discretized problems, with a progressively finer discretization mesh. Finely discretized minimax and SIP problems, as well as other problems with many more objectives/constraints than variables, call for algorithms in which successive search directions are computed based on a small but significant subset of the objectives/constraints, with ensuing reduced computing cost per iteration and decreased risk of numerical difficulties. In this paper, an SQP-type algorithm is proposed that incorporates this idea in the particular case of minimax problems. The general case will be considered in a separate paper. The quadratic programming subproblem that yields the search direction involves only a small subset of the objectives functions. This subset is updated at each iteration in such a way that global convergence is insured. Heuristics are suggested that take advantage of a possible close relationship between ﲡdjacent objective functions. Numerical results demonstrate the efficiency of the proposed algorithm.
  • Thumbnail Image
    Item
    An SQP Algorithm for Finely Discretized SIP Problems and Other Problems with Many Constraints
    (1992) Zhou, J.L.; Tits, A.L.; ISR
    A Common strategy for achieving global convergence in the solution of semi-infinite programming (SIP) problems is to (approximately) solve a sequence of discretized problems, with a progressively finer discretization mesh. Finely discretized SIP problems, as well as other problems with many more constraints than variables, call for algorithms in which successive search directions are computed based on a small but significant subset of the constraints, with ensuing reduced computing cost per iteration and decreased risk of numerical difficulties. In this paper, an SQP-type algorithm is proposed that incorporates this idea. The quadratic programming subproblem that yields the search direction involves only a small subset of the constraints. This subset is updated at each iteration in such a way that global convergence is insured. Heuristics are suggested that take advantage of possible close relationship between "adjacent" constraints. Numerical results demonstrate the efficiency of the proposed algorithm.
  • Thumbnail Image
    Item
    User's Guide for CFSQP Version 2.0: A C Code for Solving (Large Scale) Constrained Nonlinear (Minimax) Optimization Problems, Generating Iterates Satisfying All Inequality Constraints
    (1994) Lawrence, Craig T.; Zhou, J.L.; Tits, A.L.; ISR
    CFSQP is a set of C functions for the minimization of the maximum of a set of smooth objective functions (possibly a single one) subject to general smooth constraints. If the initial guess provided by the user is infeasible for some inequality constraint or some linear equality constraint, CFSQP first generates a feasible point for these constraints; subsequently the successive iterates generated by CFSQP all satisfy these constraints. Nonlinear equality constraints are turned into inequality constraints (to be satisfied by all iterates) and the maximum of the objective functions is replaced by an exact penalty function which penalizes nonlinear equality constraint violations only. When solving problems with many sequentially related constraints (or objectives), such as discretized semi- infinite programming (SIP) problems, CFSQP gives the user the option to use an algorithm that efficiently solves these problems, greatly reducing computational effort. The user has the option of either requiring that the objective function (penalty function if nonlinear equality constraints are present) decrease at each iteration after feasibility for nonlinear inequality and linear constraints has been reached (monotone line search), or requiring a decrease within at most four iterations (nonmonotone line search). He/She must provide functions that define the objective functions and constraint functions and may either provide functions to compute the respective gradients or require that CFSQP estimate them by forward finite differences.

    CFSQP is an implementation of two algorithms based on Sequential Quadratic Programming (SQP), modified so as to generate feasible iterates. In the first one (monotone line search), a certain Armijo type arc search is used with the property that the step of one is eventually accepted, a requirement for superlinear convergence. In the second one the same effect is achieved by means of a "nonmonotone" search along a straight line. The merit function used in both searches is the maximum of the objective functions if there is no nonlinear equality constraints, or an exact penalty function if nonlinear equality constraints are present.

  • Thumbnail Image
    Item
    User's Guide for FSQP Version 3.0c: A FORTRAN Code for Solving Constrained Nonlinear (Minimax) Optimization Problems, Generating Iterates Satisfying All Inequality and Linear Constraints
    (1992) Zhou, J.L.; Tits, A.L.; ISR
    FSQP 3.0c is a set of FORTRAN subroutines for the minimization of the maximum of a set of smooth objective functions (possibly a single one) subject to general smooth constraints. If the initial guess provided by the user is infeasible for some inequality constraint or some linear equality constraint, FSQP first generates a feasible point for these constraints; subsequently the successive iterates generated by FSQP all satisfy these constraints. Nonlinear equality constraints are turned into inequality constraints (to be satisfied by all iterates) and the maximum of the objective functions is replaced by an exact penalty function which penalizes nonlinear equality constraint violations only. The user has the option of either requiring that the (modified) objective function decrease at each iteration after feasibility for nonlinear inequality and linear constraints has been reached (monotone line search), or requiring a decrease within at most four iterations (nonmonotone line search). He/She must provide subroutines that define the objective functions and constraint functions and may either provide subroutines to compute the gradients of these functions or require that FSQP estimate them by forward finite differences.

    FSQP 3.0c implements two algorithms based on Sequential Quadratic Programming (SQP), modified so as to generate feasible iterates. In the first one (monotone line search), a certain Armijo type arc search is used with the property that the step of one is eventually accepted, a requirement for superlinear convergence. In the second one the same effect is achieved by means of a (nonmonotone) search along a straight line. The merit function used in both searches is the maximum of the objective functions if there is no nonlinear equality constraint.