Some remarks on computer-aided design of optical lens systems

Computer-aided design of optical lens systems implies the solution of an optimization problem of large dimension. To apply a local algorithm, we want to know a starting point within a small neighborhood of the desired system. For a given task, the designer is not able to define a suitable starting point. In this paper, we describe a global optimization algorithm which uses the principles of biological evolution with the aim of locating an adequate starting point for a local correction routine.This work was supported by the Department of Mathematics, Friedrich Schiller University, Jena, GDR, in cooperation with the research center of VEB Kombinat Carl Zeiss, Jena, GDR. The authors are indebted to Dr. L. C. W. Dixon for discussions of the topic.     

A sparse sequential quadratic programming algorithm

Described here is the structure and theory for a sequential quadratic programming algorithm for solving sparse nonlinear optimization problems. Also provided are the details of a computer implementation of the algorithm along with test results. The algorithm maintains a sparse approximation to the Cholesky factor of the Hessian of the Lagrangian. The solution to the quadratic program generated at each step is obtained by solving a dual quadratic program using a projected conjugate gradient algorithm. An updating procedure is employed that does not destroy sparsity.     

A new sequential systems of linear equations algorithm of feasible descent for inequality constrained optimization

Based on a new efficient identification technique of active constraints introduced in this paper, a new sequential systems of linear equations （SSLE） algorithm generating feasible iterates is proposed for solving nonlinear optimization problems with inequality constraints. In this paper, we introduce a new technique for constructing the system of linear equations, which recurs to a perturbation for the gradients of the constraint functions. At each iteration of the new algorithm, a feasible descent direction is obtained by solving only one system of linear equations without doing convex combination. To ensure the global convergence and avoid the Maratos effect, the algorithm needs to solve two additional reduced systems of linear equations with the same coefficient matrix after finite iterations. The proposed algorithm is proved to be globally and superlinearly convergent under some mild conditions. What distinguishes this algorithm from the previous feasible SSLE algorithms is that an improving direction is obtained easily and the computation cost of generating a new iterate is reduced. Finally, a preliminary implementation has been tested.     

MCS—A new algorithm for multicriteria optimisation in constraint programming

In this paper we propose a new algorithm called MCS for the search for solutions to multicriteria combinatorial optimisation problems. To quickly produce a solution that offers a good trade-off between criteria, the MCS algorithm alternates several Branch & Bound searches following diversified search strategies. It is implemented in CP in a dedicated framework and can be specialised for either complete or partial search.     

Analysis and simulation of a distribution system for flowers

One of the largest flower auctions in the world is located in the Netherlands. Because of an expected expansion of the auction, the capacity of its distribution system was investigated. Discrete event simulation was applied to study the complex system. The simulation results show that the present system cannot handle the expected expansion. However, the analysis also shows ways for improving the system's efficiency, thereby enlarging its capacity.     

An explicit linear solution for the quadratic dynamic programming problem

For a given vectorx ₀, the sequence {x _t} which optimizes the sum of discounted rewardsr(x _t, x_t+1), wherer is a quadratic function, is shown to be generated by a linear decision rulex _t+1=Sx _t +R. Moreover, the coefficientsR,S are given by explicit formulas in terms of the coefficients of the reward functionr. A unique steady-state is shown to exist (except for a degenerate case), and its stability is discussed.     

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 optimal sequential procedure for a multiple selling problem with independent observations

We consider a sequential problem of selling K identical assets over the finite time horizon with a fixed number of offers per time period and no recall of past offers. The objective is to find an optimal sequential procedure which maximizes the total expected revenue. In this paper, we derive an effective number of stoppings for an optimal sequential procedure for the selling problem with independent observations.     

A tolerant algorithm for linearly constrained optimization calculations

Two extreme techniques when choosing a search direction in a linearly constrained optimization calculation are to take account of all the constraints or to use an active set method that satisfies selected constraints as equations, the remaining constraints being ignored. We prefer an intermediate method that treats all inequality constraints with small residuals as inequalities with zero right hand sides and that disregards the other inequality conditions. Thus the step along the search direction is not restricted by any constraints with small residuals, which can help efficiency greatly, particularly when some constraints are nearly degenerate. We study the implementation, convergence properties and performance of an algorithm that employs this idea. The implementation considerations include the choice and automatic adjustment of the tolerance that defines the small residuals, the calculation of the search directions, and the updating of second derivative approximations. The main convergence theorem imposes no conditions on the constraints except for boundedness of the feasible region. The numerical results indicate that a Fortran implementation of our algorithm is much more reliable than the software that was tested by Hock and Schittkowski (1981). Therefore the algorithm seems to be very suitable for general use, and it is particularly appropriate for semi-infinite programming calculations that have many linear constraints that come from discretizations of continua.     

Activity graphs: A language for flexible consultation systems

An intelligent decision system (IDS) uses artificial intelligence principles to deliver automated, interactive decision analysis (DA) consultations. Network methods adapted from operations research underlie two key IDS components: influence diagrams and activity graphs. Influence diagrams, which are familiar to DA researchers and practitioners, represent decision problems inevent space. Activity graphs, which are introduced in this paper, represent processes inaction space. While activity graphs can represent any process, we use them as a knowledge-engineering and programming language to represent the process knowledge of skilled decision analysts in the context of a specific class of decisions. This paper defines activity graphs as an extension of directed AND-OR graphs. Anactivity tree is a directed AND-OR tree consisting of nodes, which may contain activities (small computer programs) and connectors that establish logical relationships among nodes and define logical resolution agendas. Anactivity graph is a directed, multiply connected network of activity trees. Activity graphs may involve recursion. Development of the activity graph language is motivated by our desire to enable professional decision analysts — or other experts — with limited advanced programming experience to design and build consultation systems that combine the guidance offered by protocol systems with the flexibility and generality of transaction systems. This paper defines the activity graph language in detail. A simple example illustrates key concepts. The paper also discusses our experience using a computer system that implements activity graphs for developing commercial IDSs.     

A hybrid immune multiobjective optimization algorithm

In this paper, we develop a hybrid immune multiobjective optimization algorithm (HIMO) based on clonal selection principle. In HIMO, a hybrid mutation operator is proposed with the combination of Gaussian and polynomial mutations (GP-HM operator). The GP-HM operator adopts an adaptive switching parameter to control the mutation process, which uses relative large steps in high probability for boundary individuals and less-crowded individuals. With the generation running, the probability to perform relative large steps is reduced gradually. By this means, the exploratory capabilities are enhanced by keeping a desirable balance between global search and local search, so as to accelerate the convergence speed to the true Pareto-optimal front in the global space with many local Pareto-optimal fronts. When comparing HIMO with various state-of-the-art multiobjective optimization algorithms developed recently, simulation results show that HIMO performs better evidently.     

A new algorithm for generalized fractional programs

A new dual problem for convex generalized fractional programs with no duality gap is presented and it is shown how this dual problem can be efficiently solved using a parametric approach. The resulting algorithm can be seen as “dual” to the Dinkelbach-type algorithm for generalized fractional programs since it approximates the optimal objective value of the dual (primal) problem from below. Convergence results for this algorithm are derived and an easy condition to achieve superlinear convergence is also established. Moreover, under some additional assumptions the algorithm also recovers at the same time an optimal solution of the primal problem. We also consider a variant of this new algorithm, based on scaling the “dual” parametric function. The numerical results, in case of quadratic-linear ratios and linear constraints, show that the performance of the new algorithm and its scaled version is superior to that of the Dinkelbach-type algorithms. From the computational results it also appears that contrary to the primal approach, the “dual” approach is less influenced by scaling. This research was carried out at the Econometric Institute, Erasmus University, Rotterdam, the Netherlands and was supported by J.N.I.C.T. (Portugal) under contract BD/707/90-RM.     

A five facet frame for the design of heuristics —A rejoinder

An argument was put forward by Stainton and Papoulias for an additional category of heuristics to those proposed by Müller-Merbach, which the authors called ‘relational’. In response to the subsequent suggestion by Müller-Merbach of a five facet frame for the design of heuristics, this paper sets out to expand upon and clarify the characteristics of the relational approach, as defined by the authors.     

User-model interaction in decision support systems for risk management

This paper describes and evaluates three different approaches to building decision support systems: the Operations Research/Management Science approach, the Decision Analysis/Multiattribute Utility approach, and the Artificial Intelligence/Expert Systems approach. It evaluates the usefulness of the three approaches for risk management. In particular, it defines evaluation objectives of risk analysts, risk managers, and laypeople and provides a subjective assessment how the three approaches stack up against their objectives. The paper concludes that for most risk management applications a combination of the three approaches would be most desirable.This paper was written under contract No. 2709-85-05 ED ISP D of the European Atomic Energy Community, Commission of the European Communities, Joint Research Centre, Ispra Establishment, Ispra, Italy to the Gemeinschaft für Entscheidungs- und Risikoanalyse, Berlin, West Germany. It was prepared for presentation at the Conference on Operations Research and Multiattribute Decision Analysis held in Passau, April 20–26, 1986. The views and opinions expressed in this paper are solely those of the author.     

A trust region SQP algorithm for mixed-integer nonlinear programming

We propose a modified sequential quadratic programming method for solving mixed-integer nonlinear programming problems. Under the assumption that integer variables have a smooth influence on the model functions, i.e., that function values do not change drastically when in- or decrementing an integer value, successive quadratic approximations are applied. The algorithm is stabilized by a trust region method with Yuan’s second order corrections. It is not assumed that the mixed-integer program is relaxable or, in other words, function values are evaluated only at integer points. The Hessian of the Lagrangian function is approximated by a quasi-Newton update formula subject to the continuous and integer variables. Numerical results are presented for a set of 80 mixed-integer test problems taken from the literature. The surprising result is that the number of function evaluations, the most important performance criterion in practice, is less than the number of function calls needed for solving the corresponding relaxed problem without integer variables.     

非线性0-1规划问题的蜂群算法

针对非线性0-1规划,提出采用一种智能优化算法——蜂群算法进行求解.描述了蜂群算法的实现过程,并在计算机上编程予以实现.经大量实例测试,并与其它算法进行比较,获得了满意的结果.说明了蜂群算法在解决非线性0-1规划问题上的可行性与有效性,同时具有良好的优化能力..     

A new technique for inconsistent QP problems in the SQP method

Successful treatment of inconsistent QP problems is of major importance in the SQP method, since such occur quite often even for well behaved nonlinear programming problems. This paper presents a new technique for regularizing inconsistent QP problems, which compromises in its properties between the simple technique of Pantoja and Mayne [36] and the highly successful, but expensive one of Tone [47]. Global convergence of a corresponding algorithm is shown under reasonable weak conditions. Numerical results are reported which show that this technique, combined with a special method for the case of regular subproblems, is quite competitive to highly appreciated established ones.     

A new algorithm for minimizing convex functions over convex sets

Let be a convex set for which there is an oracle with the following property. Given any pointz∈ℝ ⁿ the oracle returns a “Yes” ifz∈S; whereas ifz∉S then the oracle returns a “No” together with a hyperplane that separatesz fromS. The feasibility problem is the problem of finding a point inS; the convex optimization problem is the problem of minimizing a convex function overS. We present a new algorithm for the feasibility problem. The notion of a volumetric center of a polytope and a related ellipsoid of maximum volume inscribable in the polytope are central to the algorithm. Our algorithm has a significantly better global convergence rate and time complexity than the ellipsoid algorithm. The algorithm for the feasibility problem easily adapts to the convex optimization problem.     

A new algorithm for multi-dimensional dynamic programming problems

The new algorithm presented here solves medium size multi-dimensional dynamic programming problems in a relatively short computational time with no fast-memory restraints. The algorithm converges to the global optimal solution under some differentiability and convexity assumptions.The procedure is to solve a succession of dynamic programming problems, the state sets of which are limited to only a very small subset of the original state space. The interrelated definition of state sets for successive subproblems facilitates an algorithmic convergence while moving the subsets to contain the optimal states at the end.