A geometric method in nonlinear programming

A differential geometric approach to the constrained function maximization problem is presented. The continuous analogue of the Newton-Raphson method due to Branin for solving a system of nonlinear equations is extended to the case where the system is under-determined. The method is combined with the continuous analogue of the gradient-projection method to obtain a constrained maximization method with enforced constraint restoration. Detailed analysis of the global behavior of both methods is provided. It is shown that the conjugate-gradient algorithm can take advantage of the sparse structure of the problem in the computation of a vector field, which constitutes the main computational task in the methods.This is part of a paper issued as Stanford University, Computer Science Department Report No. STAN-CS-77-643 (Ref. 45), which was presented at the Gatlinburg VII Conference, Asilomar, California, 1977. This work was supported in part by NSF Grant No. NAT BUR OF ECON RES/PO No. 4369 and by Department of Energy Contract No. EY-76-C-02-0016.The main part of this work was presented at the Japan-France Seminar on Functional Analysis and Numerical Analysis, Tokyo, Japan, 1976. The paper was prepared in part while the author was a visitor at the Department of Mathematics, North Carolina State University, Raleigh, North Carolina, 1976–77, and was completed while he was a visitor at the Computer Science Department, Stanford University, Stanford, California, 1977. He acknowledges the hospitality and stimulating environment provided by Professor G. H. Golub, Stanford University, and Professors N. J. Rose and C. D. Meyer, North Carolina State University.     

Efficient and stereoselective synthesis of novel cis-4-substituted proline analogues

A series of novel cis-4-substituted proline analogues were designed and synthesized. Highly stereoselective alkylations at the γ-position of glutamic ester 2 were achieved, followed by reduction, mesylation, and cyclization to afford the title compounds 1 in good yields and high diastereoselectivity.     

Convex Separable Minimization Subject to Bounded Variables

A minimization problem with convex and separable objective function subject to a separable convex inequality constraint and bounded variables is considered. A necessary and sufficient condition is proved for a feasible solution to be an optimal solution to this problem. Convex minimization problems subject to linear equality/linear inequality constraint, and bounds on the variables are also considered. A necessary and sufficient condition and a sufficient condition, respectively, are proved for a feasible solution to be an optimal solution to these two problems. Algorithms of polynomial complexity for solving the three problems are suggested and their convergence is proved. Some important forms of convex functions and computational results are given in the Appendix.     

On the Geometry of Inner Approximations to the Set of Null Controllability for Constrained Linear Systems

The problem of obtaining inner approximations to the set of null controllability for linear systems is considered, and the geometry of certain sets arising in the approximation of using linear feedback is explored. A two-dimensional example is worked in detail in order to delineate the limitations to the use of linear feedback.     

A Piecewise Line-Search Technique for Maintaining the Positive Definitenes of the Matrices in the SQP Method

A technique for maintaining the positive definiteness of the matrices in the quasi-Newton version of the SQP algorithm is proposed. In our algorithm, matrices approximating the Hessian of the augmented Lagrangian are updated. The positive definiteness of these matrices in the space tangent to the constraint manifold is ensured by a so-called piecewise line-search technique, while their positive definiteness in a complementary subspace is obtained by setting the augmentation parameter. In our experiment, the combination of these two ideas leads to a new algorithm that turns out to be more robust and often improves the results obtained with other approaches.     

Subspace Barzilai-Borwein Gradient Method for Large-Scale Bound Constrained Optimization

An active set subspace Barzilai-Borwein gradient algorithm for large-scale bound constrained optimization is proposed. The active sets are estimated by an identification technique. The search direction consists of two parts: some of the components are simply defined; the other components are determined by the Barzilai-Borwein gradient method. In this work, a nonmonotone line search strategy that guarantees global convergence is used. Preliminary numerical results show that the proposed method is promising, and competitive with the well-known method SPG on a subset of bound constrained problems from CUTEr collection. This work was supported by the 973 project granted 2004CB719402 and the NSF project of China granted 10471036.     

Additional symmetries of constrained CKP and BKP hierarchies

The additional symmetries of the constrained CKP (cCKP) and BKP (cBKP) hierarchies are given by their actions on the Lax operators, and their actions on the eigenfunction and adjoint eigenfunction {Φ i , Ψ i } are presented explicitly. Furthermore, we show that acting on the space of the wave operator, *k forms new centerless W cC 1+∞ and W cB 1+∞ -subalgebra of centerless W 1+∞ respectively. In order to define above symmetry flows *k of the cCKP and cBKP hierarchies, two vital operators Y k are introduce...     

Pre-emption in resource-constrained project scheduling

The Resource-Constrained Project Scheduling Project (RCPSP), together with some of its extensions, has been widely studied. A fundamental assumption in this basic problem is that activities in progress are non-preemptable. Very little effort has been made to uncover the potential benefits of discrete activity pre-emption, and the papers dealing with this issue have reached the conclusion that it has little effect on project length when constant resource availability levels are defined. In this paper we show how three basic elements of many heuristics for the RCPSP – codification, serial SGS and double justification – can be adapted to deal with interruption. The paper is mainly focussed on problem 1_PRCPSP, a generalization of the RCPSP where a maximum of one interruption per activity is allowed. However, it is also shown how these three elements can be further adapted to deal with more general pre-emptive problems. Computational experiments on the standard j30 and j120 sets support the conclusion that pre-emption does help to decrease project length when compared to the no-interruption case. They also prove the usefulness of the justification in the presence of pre-emption. The justification is a RCPS technique that can be easily incorporated into a wide range of algorithms for the RCPSP, increasing their solution quality – maintaining the number of schedules calculated.     

A unified method for a class of convex separable nonlinear knapsack problems

In this paper, a unified algorithm is proposed for solving a class of convex separable nonlinear knapsack problems, which are characterized by positive marginal cost (PMC) and increasing marginal loss–cost ratio (IMLCR). By taking advantage of these two characteristics, the proposed algorithm is applicable to the problem with equality or inequality constraints. In contrast to the methods based on Karush–Kuhn–Tucker (KKT) conditions, our approach has linear computation complexity. Numerical results are reported to demonstrate the efficacy of the proposed algorithm for different problems.