Unified steerable phase I-phase II method of feasible directions for semi-infinite optimization

In this paper, we complete a cycle in the construction of methods of feasible directions for solving semi-infinite constrained optimization problems. Earlier phase I-phase II methods of feasible directions used one search direction rule in all of ⁿ with two stepsize rules, one for feasible points and one for infeasible points. The algorithm presented in this paper uses both a single search direction rule and a single stepsize rule in all of ⁿ . In addition, the new algorithm incorporates a steering parameter which can be used to control the speed with which feasibility is achieved. The new algorithm is simpler to analyze and performs somewhat better than existing, first order, phase I-phase II methods. The new algorithm is globally convergent, with linear rate.The research reported herein was sponsored in part by the National Science Foundation Grant ECS-8713334, the Air Force Office of Scientific Research Contract AFOSR-86-0116, and the State of California MICRO Program Grant 532410-19900.The authors would like to thank Dr. J. Higgins for providing the C-code of Algorithm 3.1.     

Properties of the optimal trajectories for coplanar,aeroassisted orbital transfer

We show that the sequences of function values constructed by two versions of a minimax algorithm converge linearly to the minimum values. Both versions use the Pshenichnyi-Pironneau-Polak search direction subprocedure; the first uses an exact line search to determine the stepsize, while the second one uses an Armijo-type stepsize rule. The proofs depend on a second-order sufficiency condition, but not on strict complementary slackness. Minimax problems in which each function appearing in the max is a composition of a twice continuously differentiable function with a linear function typically do not satisfy second-order sufficiency conditions. Nevertheless, we show that, on such minimax problems, the two algorithms do converge linearly when the outer functions are convex and strict complementary slackness holds at the solutions.The research reported herein was sponsored in part by the National Science Foundation Grant ECS-87-13334, the Air Force Office of Scientific Research Contract AFOSR-86-0116, the State of California MICRO Program Grant 532410-19900, and a Howard Hughes Doctoral Fellowship (Hughes Aircraft Company). The authors would like to thank the referees for their helpful suggestions.     

Sequential quadratically constrained quadratic programming norm-relaxed algorithm of strongly sub-feasible directions

In this paper, we present a sequential quadratically constrained quadratic programming (SQCQP) norm-relaxed algorithm of strongly sub-feasible directions for the solution of inequality constrained optimization problems. By introducing a new unified line search and making use of the idea of strongly sub-feasible direction method, the proposed algorithm can well combine the phase of finding a feasible point (by finite iterations) and the phase of a feasible descent norm-relaxed SQCQP algorithm. Moreover, the former phase can preserve the “sub-feasibility” of the current iteration, and control the increase of the objective function. At each iteration, only a consistent convex quadratically constrained quadratic programming problem needs to be solved to obtain a search direction. Without any other correctional directions, the global, superlinear and a certain quadratic convergence (which is between 1-step and 2-step quadratic convergence) properties are proved under reasonable assumptions. Finally, some preliminary numerical results show that the proposed algorithm is also encouraging.     

一般约束优化基于识别函数的模松弛算法

借助于半罚函数和产生工作集的识别函数以及模松弛SQP算法思想, 本文建立了求解带等式及不等式约束优化的一个新算法. 每次迭代中, 算法的搜索方向由一个简化的二次规划子问题及一个简化的线性方程组产生. 算法在不包含严格互补性的温和条件下具有全局收敛性和超线性收敛性. 最后给出了算法初步的数值试验报告.     

An improved sequential quadratic programming algorithm for solving general nonlinear programming problems

In this paper, a class of general nonlinear programming problems with inequality and equality constraints is discussed. Firstly, the original problem is transformed into an associated simpler equivalent problem with only inequality constraints. Then, inspired by the ideals of the sequential quadratic programming (SQP) method and the method of system of linear equations (SLE), a new type of SQP algorithm for solving the original problem is proposed. At each iteration, the search direction is generated by the combination of two directions, which are obtained by solving an always feasible quadratic programming (QP) subproblem and a SLE, respectively. Moreover, in order to overcome the Maratos effect, the higher-order correction direction is obtained by solving another SLE. The two SLEs have the same coefficient matrices, and we only need to solve the one of them after a finite number of iterations. By a new line search technique, the proposed algorithm possesses global and superlinear convergence under some suitable assumptions without the strict complementarity. Finally, some comparative numerical results are reported to show that the proposed algorithm is effective and promising.     

An exact penalty function algorithm for optimal control problems with control and terminal equality constraints,part 1

The presence of control constraints, because they are nondifferentiable in the space of control functions, makes it difficult to cope with terminal equality constraints in optimal control problems. Gradient-projection algorithms, for example, cannot be employed easily. These difficulties are overcome in this paper by employing an exact penalty function to handle the cost and terminal equality constraints and using the control constraints to define the space of permissible search directions in the search-direction subalgorithm. The search-direction subalgorithm is, therefore, more complex than the usual linear program employed in feasible-directions algorithms. The subalgorithm approximately solves a convex optimal control problem to determine the search direction; in the implementable version of the algorithm, the accuracy of the approximation is automatically increased to ensure convergence.This work was supported by the United Kingdom Science Research Council, by the US Army Research Office, Contract No. DAAG-29-73-C-0025, and by the National Science Foundation, Grant No. ENG-73-08214-A01.     

Convergence of a smoothing algorithm for symmetric cone complementarity problems with a nonmonotone line search

In this paper, we propose a smoothing algorithm for solving the monotone symmetric cone complementarity problems (SCCP for short) with a nonmonotone line search. We show that the nonmonotone algorithm is globally convergent under an assumption that the solution set of the problem concerned is nonempty. Such an assumption is weaker than those given in most existing algorithms for solving optimization problems over symmetric cones. We also prove that the solution obtained by the algorithm is a maximally complementary solution to the monotone SCCP under some assumptions. This work was supported by National Natural Science Foundation of China (Grant Nos. 10571134, 10671010) and Natural Science Foundation of Tianjin (Grant No. 07JCYBJC05200)     

A NEW ADAPTIVE SUBSPACE MINIMIZATION THREE-TERM CONJUGATE GRADIENT ALGORITHM FOR UNCONSTRAINED OPTIMIZATION

A new adaptive subspace minimization three-term conjugate gradient algorithm with nonmonotone line search is introduced and analyzed in this paper.The search directions are computed by minimizing a quadratic approximation of the objective function on special subspaces,and we also proposed an adaptive rule for choosing different searching directions at each iteration.We obtain a significant conclusion that the each choice of the search directions satisfies the sufficient descent condition.With the used nonmonotone line search,we prove that the new algorithm is globally convergent for general nonlinear functions under some mild assumptions.Numerical experiments show that the proposed algorithm is promising for the given test problem set.     

A robust secant method for optimization problems with inequality constraints

This paper presents a secant method, based on R. B. Wilson's formula for the solution of optimization problems with inequality constraints. Global convergence properties are ensured by grafting the secant method onto a phase I - phase II feasible directions method, using a rate of convergence test for crossover control.This research was sponsored by the National Science Foundation, Grant No. ENG-73-08214 and Grant No. (RANN)-ENV-76-04264, and by the Joint Services Electronics Program. Contract No. F44620-76-C-0100.     

A GENERALIZED PROJECTION-SUCCESSIVE LINEAREQUATIONS ALGORITHM FOR NONLINEARLY EQUALITy AND INEQUALITY CONSTRAINED OPTIMIZATION AND ITS RATE OF CONVERGENCE

In this paper, a new superlinearly convergent algorithm is presented for optimization problems with general nonlineer equality and inequality Constraints, Comparing with other methods for these problems, the algorithm has two main advantages. First, it doesn‘t solve anyquadratic programming (QP), and its search directions are determined by the generalized projection technique and the solutions of two systems of linear equations. Second, the sequential points generated by the algoritbh satisfy all inequity constraints and its step-length is computed by the straight line search,The algorithm is proved to possesa global and auperlinear convergence.     

The Global Convergence of Self-Scaling BFGS Algorithm with Nonmonotone Line Search for Unconstrained Nonconvex Optimization Problems

The self-scaling quasi-Newton method solves an unconstrained optimization problem by scaling the Hessian approximation matrix before it is updated at each iteration to avoid the possible large eigenvalues in the Hessian approximation matrices of the objective function. It has been proved in the literature that this method has the global and superlinear convergence when the objective function is convex （or even uniformly convex）. We propose to solve unconstrained nonconvex optimization problems by a self-scaling BFGS algorithm with nonmonotone linear search. Nonmonotone line search has been recognized in numerical practices as a competitive approach for solving large-scale nonlinear problems. We consider two different nonmonotone line search forms and study the global convergence of these nonmonotone self-scale BFGS algorithms. We prove that, under some weaker condition than that in the literature, both forms of the self-scaling BFGS algorithm are globally convergent for unconstrained nonconvex optimization problems.     

On Anstreicher's combined phase I—phase II projective algorithm for linear programming

Anstreicher has proposed a variant of Karmarkar's projective algorithm that handles standard-form linear programming problems nicely. We suggest modifications to his method that we suspect will lead to better search directions and a more useful algorithm. Much of the analysis depends on a two-constraint linear programming problem that is a relaxation of the scaled original problem.Research supported in part by NSF Grant ECS-8602534 and ONR Contract N00014-87-K-0212.     

An affine scaling method with an infeasible starting point: Convergence analysis under nondegeneracy assumption

In this paper, we propose an infeasible-interior-point algorithm for linear programning based on the affine scaling algorithm by Dikin. The search direction of the algorithm is composed of two directions, one for satisfying feasibility and the other for aiming at optimality. Both directions are affine scaling directions of certain linear programming problems. Global convergence of the algorithm is proved under a reasonable nondegeneracy assumption. A summary of analogous global convergence results without any nondegeneracy assumption obtained in [17] is also given.     

非线性约束最优化一族超线性收敛的可行方法

本文建立求解非线性不等式约束最优化一族含参数的可行方法．算法每次迭代仅需解一个规模较小的二次规划．在一定的假设条件下,证明了算法族的全局收敛性和超线性收敛性．     

A superlinearly and quadratically convergent SQP type feasible method for constrained optimization

A new SQP type feasible method for inequality constrained optimization is presented, it is a combination of a master algorithm and an auxiliary algorithm which is taken only in finite iterations. The directions of the master algorithm are generated by only one quadratic programming, and its step-size is always one, the directions of the auxiliary algorithm are new “secondorder“ feasible descent. Under suitable assumptions, the algorithm is proved to possess global and strong convergence, superlinear and quadratic convergence.     

Convergence Analysis of an Inexact Infeasible Interior Point Method for Semidefinite Programming

In this paper we present an extension to SDP of the well known infeasible Interior Point method for linear programming of Kojima, Megiddo and Mizuno (A primal-dual infeasible-interior-point algorithm for Linear Programming, Math. Progr., 1993). The extension developed here allows the use of inexact search directions; i.e., the linear systems defining the search directions can be solved with an accuracy that increases as the solution is approached. A convergence analysis is carried out and the global convergence of the method is proved.     

An algorithm for generalized fractional programs

An algorithm is suggested that finds the constrained minimum of the maximum of finitely many ratios. The method involves a sequence of linear (convex) subproblems if the ratios are linear (convex-concave). Convergence results as well as rate of convergence results are derived. Special consideration is given to the case of (a) compact feasible regions and (b) linear ratios.The research of S. Schaible was supported by Grant Nos. A4534 and A5408 from NSERC. The authors thank two anonymous referees for their helpful remarks.     

A Lagrangian Dual Method with Self-Concordant Barriers for Multi-Stage Stochastic Convex Programming

This paper presents an algorithm for solving multi-stage stochastic convex nonlinear programs. The algorithm is based on the Lagrangian dual method which relaxes the nonanticipativity constraints, and the barrier function method which enhances the smoothness of the dual objective function so that the Newton search directions can be used. The algorithm is shown to be of global convergence and of polynomial-time complexity.Mathematics Subject Classification (2000): 90C15, 90C51, 90C06, 90C25, 90C60Research is partially supported by NUS Academic Research Grant R-146-000-006-112     

Quadratically convergent algorithms and one-dimensional search schemes

In this paper, the performances of three quadratically convergent algorithms coupled with four one-dimensional search schemes are studied through several nonquadratic examples. The algorithms are the rank-one algorithm (Algorithm I), the projection algorithm (Algorithm II), and the Fletcher-Reeves algorithm (Algorithm III). The search schemes are the exact quadratic search (EQS), the exact cubic search (ECS), the approximate quadratic search (AQS), and the approximate cubic search (ACS). The performances are analyzed in terms of number of iterations and number of equivalent function evaluations for convergence. From the numerical experiments, the following conclusions are found: (a) while the number of iterations generally increases by relaxing the search stopping condition, the number of equivalent function evaluations decreases; therefore, approximate searches should be preferred to exact searches; (b) the numbers of iterations for ACS, ECS, and EQS are about the same; therefore, the use of more sophisticated, higher order search schemes is not called for; the present ACS scheme, modified so that only the function, instead of the gradient, is used in bracketing the minimal point, could prove to be most desirable in terms of the number of equivalent function evaluations; (c) for Algorithm I, ACS and AQS yield almost identical results; it is believed that further improvements in efficiency are possible if one uses a fixed stepsize approach, thus bypassing the one-dimensional search completely; (d) the combination of Algorithm II and ACS exhibits high efficiency in treating functions whose order is higher than two and whose Hessian at the minimal point is singular; and (f) Algorithm III, even with the best search scheme, is inefficient in treating functions with flat bottoms; it is doubtful that the simplicity of its update will compensate for its inefficiency in such pathological cases.This research was supported by the National Science Foundation, Grant No. 32453.