Hyperspheric Integer Programming

This paper develops an efficient method for finding the optimal solution to linear mathematical programs on 0–1 variables. It is shown that the lattice (0–1) points satisfying some linear constraint of dimension n can equally be represented by those lying in a hypersphere of the same dimension. The lattice points satisfying two linear constraints can be represented by a hypersphere which contains the intersection of the hyperspheres of the two constraints. The method for finding the optimal solution consists of enumerating lattice points which are close to the center of the hypersphere corresponding to the constraints. As soon as a better value of the objective function has been found, than some lower bound, we find a new hypersphere which contains the lattice points of the constraints at which the objective function remains higher than the best known value. We continue in this manner until we have at some stage enumerated all lattice points within a given hypersphere and found none which give a better value.     

A dual extremum principle for a population equation

A dual extremum principle for the Verhulst-Pearl population equation is constructed using a complementary variational technique. The dual formulation utilizes a minimum principle recently developed by Leitmann to convert the functional optimization problem into a parameter optimization problem.This research was supported in part by NASA Grant No. NGR-36-010-024. The first author would like to thank Dr. W. Stadler, Department of Mechanical Engineering, University of California, Berkeley, for his valuable suggestions.     

Interior-point methods for nonconvex nonlinear programming: regularization and warmstarts

In this paper, we investigate the use of an exact primal-dual penalty approach within the framework of an interior-point method for nonconvex nonlinear programming. This approach provides regularization and relaxation, which can aid in solving ill-behaved problems and in warmstarting the algorithm. We present details of our implementation within the loqo algorithm and provide extensive numerical results on the CUTEr test set and on warmstarting in the context of quadratic, nonlinear, mixed integer nonlinear, and goal programming. Research of the first author is sponsored by ONR grant N00014-04-1-0145. Research of the second author is supported by NSF grant DMS-0107450.     

A class of generalized variable penalty methods for nonlinear programming

A class of generalized variable penalty formulations for solving nonlinear programming problems is presented. The method poses a sequence of unconstrained optimization problems with mechanisms to control the quality of the approximation for the Hessian matrix, which is expressed in terms of the constraint functions and their first derivatives. The unconstrained problems are solved using a modified Newton's algorithm. The method is particularly applicable to solution techniques where an approximate analysis step has to be used (e.g., constraint approximations, etc.), which often results in the violation of the constraints. The generalized penalty formulation contains two floating parameters, which are used to meet the penalty requirements and to control the errors in the approximation of the Hessian matrix. A third parameter is used to vary the class of standard barrier or quasibarrier functions, forming a branch of the variable penalty formulation. Several possibilities for choosing such floating parameters are discussed. The numerical effectiveness of this algorithm is demonstrated on a relatively large set of test examples.The author is thankful for the constructive suggestions of the referees.     

Solving some optimal control problems using the barrier penalty function method

In this paper we present a new approach to solve a two-level optimization problem arising from an approximation by means of the finite element method of optimal control problems governed by unilateral boundary-value problems. The problem considered is to find a minimum of a functional with respect to the control variablesu. The minimized functional depends on control variables and state variablesx. The latter are the optimal solution of an auxiliary quadratic programming problem, whose parameters depend onu.Our main idea is to replace this QP problem by its dual and then apply the barrier penalty method to this dual QP problem or to the primal one if it is in an appropriate form. As a result we obtain a problem approximating the original one. Its good property is the differentiable dependence of state variables with respect to the control variables. Furthermore, we propose a method for finding an approximate solution of a penalized lower-level problem if the optimal solution of the original QP problem is known. We apply the result obtained to some optimal shape design problems governed by the Dirichlet-Signorini boundary-value problem.This research was supported by the Academy of Finland and the Systems Research Institute of the Polish Academy of Sciences.     

A Globally Convergent Lagrangian Barrier Algorithm for Optimization with General Inequality Constraints and Simple Bounds

We consider the global and local convergence properties of a class of Lagrangian barrier methods for solving nonlinear programming problems. In such methods, simple bound constraints may be treated separately from more general constraints. The objective and general constraint functions are combined in a Lagrangian barrier function. A sequence of such functions are approximately minimized within the domain defined by the simple bounds. Global convergence of the sequence of generated iterates to a first-order stationary point for the original problem is established. Furthermore, possible numerical difficulties associated with barrier function methods are avoided as it is shown that a potentially troublesome penalty parameter is bounded away from zero. This paper is a companion to previous work of ours on augmented Lagrangian methods.

     

On isoperimetric problems for domains with partly known boundaries

In the present paper, we discuss the isoperimetric problems for domains with partly known boundaries, i.e., the problem of determining a domain that minimizes the capacity functional in the class of plain double-connected domains having the same fixed area and outer boundary. The formulas for capacity variations obtained in this paper allows us to formulate necessary conditions.It is proved that the convexity of the fixed outer boundary implies the convexity of the inner boundary corresponding to an optimal domain. Then, we discuss the case where the fixed part of the boundary is a square.Further, we consider similar problems with more complicated functionals. We introduce the concept of a minimal function in the class of equimeasurable functions. This concept allows us to unify the approach to all of these problems. At the end, we produce a hypothesis that, if proved, would enable us to characterize the shape of the optimal domains in the isoperimetric problems mentioned above.The author wishes to express his appreciation to Dr. K. A. Lurie for his help and unceasing attention.     

An exact primal–dual penalty method approach to warmstarting interior-point methods for linear programming

One perceived deficiency of interior-point methods in comparison to active set methods is their inability to efficiently re-optimize by solving closely related problems after a warmstart. In this paper, we investigate the use of a primal–dual penalty approach to overcome this problem. We prove exactness and convergence and show encouraging numerical results on a set of linear and mixed integer programming problems. Research of the first author is sponsored by ONR grant N00014-04-1-0145. Research of the second author is supported by NSF grant DMS-0107450.     

Lower-Order Penalization Approach to Nonlinear Semidefinite Programming

In this paper, we reformulate a nonlinear semidefinite programming problem into an optimization problem with a matrix equality constraint. We apply a lower-order penalization approach to the reformulated problem. Necessary and sufficient conditions that guarantee the global (local) exactness of the lower-order penalty functions are derived. Convergence results of the optimal values and optimal solutions of the penalty problems to those of the original semidefinite program are established. Since the penalty functions may not be smooth or even locally Lipschitz, we invoke the Ekeland variational principle to derive necessary optimality conditions for the penalty problems. Under certain conditions, we show that any limit point of a sequence of stationary points of the penalty problems is a KKT stationary point of the original semidefinite program. Communicated by Y. Zhang This work was supported by a Postdoctoral Fellowship of Hong Kong Polytechnic University and by the Research Grants Council of Hong Kong.     

Penalty and Barrier Methods for Convex Semidefinite Programming

In this paper we present penalty and barrier methods for solving general convex semidefinite programming problems. More precisely, the constraint set is described by a convex operator that takes its values in the cone of negative semidefinite symmetric matrices. This class of methods is an extension of penalty and barrier methods for convex optimization to this setting. We provide implementable stopping rules and prove the convergence of the primal and dual paths obtained by these methods under minimal assumptions. The two parameters approach for penalty methods is also extended. As for usual convex programming, we prove that after a finite number of steps all iterates will be feasible.     

A gradient projection-multiplier method for nonlinear programming

This paper describes a gradient projection-multiplier method for solving the general nonlinear programming problem. The algorithm poses a sequence of unconstrained optimization problems which are solved using a new projection-like formula to define the search directions. The unconstrained minimization of the augmented objective function determines points where the gradient of the Lagrangian function is zero. Points satisfying the constraints are located by applying an unconstrained algorithm to a penalty function. New estimates of the Lagrange multipliers and basis constraints are made at points satisfying either a Lagrangian condition or a constraint satisfaction condition. The penalty weight is increased only to prevent cycling. The numerical effectiveness of the algorithm is demonstrated on a set of test problems.The author gratefully acknowledges the helpful suggestions of W. H. Ailor, J. L. Searcy, and D. A. Schermerhorn during the preparation of this paper. The author would also like to thank D. M. Himmelblau for supplying a number of interesting test problems.     

Parallel machine scheduling with a common due window

In this paper, we consider a machine scheduling problem where jobs should be completed at times as close as possible to their respective due dates, and hence both earliness and tardiness should be penalized. Specifically, we consider the problem with a set of independent jobs to be processed on several identical parallel machines. All the jobs have a given common due window. If a job is completed within the due window, then there is no penalty. Otherwise, there is either a job-dependent earliness penalty or a job-dependent tardiness penalty depending on whether the job is completed before or after the due window. The objective is to find an optimal schedule with minimum total earliness–tardiness penalty. The problem is known to be NP-hard. We propose a branch and bound algorithm for finding an optimal schedule of the problem. The algorithm is based on the column generation approach in which the problem is first formulated as a set partitioning type formulation and then in each branch and bound iteration the linear relaxation of this formulation is solved by the standard column generation procedure. Our computational experiments show that this algorithm is capable of solving problems with up to 40 jobs and any number of machines within a reasonable computational time.     

Cauchy system for Fredholm resolvents with composite displacement kernels

In recent years, the invariant imbedding approach to initial-value solutions of Fredholm integral equations with degenerate or semidegenerate kernels has been discussed with emphasis. In the present paper, with the aid of invariant imbedding, the Cauchy problem for Fredholm resolvents with composite displacement kernels is reduced to that for generalized Chandrasekhar'sX-functions andY-functions. In other words, it is shown how to convert the initial-value solution of the resolvent into a system of simultaneous nonlinear integrodifferential equations ofX-functions andY-functions of a single argument. From the computational aspect, the result seems to be more tractable than the original ones.Dedicated to R. BellmanThis work was partially supported by the Ministry of Education of Japan, Grant No. 503540. The author is indebted to Professor R. E. Kalaba, University of Southern California, and Dr. H. H. Kagiwada, Hughes Aircraft Company, for their helpful comments and kind interest in the present paper.     

An Interior Point Algorithm for Computing Saddle Points of Constrained Continuous Minimax

The aim of this paper is to present an algorithm for finding a saddle point to the constrained minimax problem. The initial problem is transformed into an equivalent equality constrained problem, and then the interior point approach is used. To satisfy the original inequality constraints a logarithmic barrier function is used and special care is given to step size parameter to keep the variables within permitted boundaries. Numerical results illustrating the method are given.     

On the complexity of an optimal routing tree problem

A routing tree for a set of tasks is a decision tree which assigns the tasks to their destinations according to the features of the tasks. A weighted routing tree is one with costs attached to each link of the tree. Links of the same feature have the same cost. It is proved that the problem of finding a routing tree of the minimum cost for a given set of tasks of two features is NP-complete.This research was supported in part by theNSF grantsDCR-8501226 andDCR-8696135. Part of this work was done while the first author was at the Mathematical Sciences Research Institute, Berkeley, California, and while the second author was at the Department of Mathematics, University of California, Santa Barbara, California.     

Penalty methods for minimal surfaces with obstacles

Summary In this paper, we discuss an approach to the obstacle problem for minimal boundaries via penalty techniques. After investigating some classes of penalized problems, a general method is introduced, based on the minimization of a suitable functional containing an extra term related to the mean curvature of the given obstacle.     

Testing of a large-scale network optimization program

This paper describes the experimental results of testing a large-scale program for solving minimum-cost network flow problems. With this program, general structure transshipment problems with over ten thousand nodes and thirty thousand arcs have been easily solved without resorting to auxiliary storage. The algorithm is a variant of the primal revised simplex method; the computer code is called LPNET illustrating the close connection between linear programming and network graphs. This approach substantially improves computer processing timeand core storage, especially for relatively large network problems. The results of these experiments are provided. It is emphasized that an organized experimental design and a detailed series of empirical tests are crucial for an efficient implementation.Research supported in part by TRW Systems Group and Harvard Business School.     

Keplerian Action,Convexity Optimization,and the 4-Body Problem

In this paper we introduce a method to construct periodic solutions for the n-body problem with only boundary and topological constraints. Our approach is based on some novel features of the Keplerian action functional, constraint convex optimization techniques, and variational methods. We demonstrate the strength of this method by constructing relative periodic solutions for the planar four-body problem within a special topological class, and our results hold for an open set of masses.     

ARMA identification

In view of recent results on the asymptotic behavior of the prediction error covariance for a state variable system (see Ref. 1), an identification scheme for autoregressive moving average (ARMA) processes is proposed. The coefficients of thed-step predictor determine asymptotically the system momentsU ₀,...,U _d–1. These moments are also nonlinear functions of the coefficients of the successive 1-step predictors. Here, we estimate the state variable parameters by the following scheme. First, we use the Burg technique (see Ref. 2) to find the estimates of the coefficients of the successive 1-step predictors. Second, we compute the moments by substitution of the estimates provided by the Burg technique for the coefficients in the nonlinear functions relating the moments with the 1-step predictor coefficients. Finally, the Hankel matrix of moment estimates is used to determine the coefficients of the characteristic polynomial of the state transition matrix (see Refs. 3 and 4).A number of examples for the state variable systems corresponding to ARMA(2, 1) processes are given which show the efficiency of this technique when the zeros and poles are separated. Some of these examples are also studied with an alternative technique (see Ref. 5) which exploits the linear dependence between successive 1-step predictors and the coefficients of the transfer function numerator and denominator polynomials.In this paper, the problems of order determination are not considered; we assumed the order of the underlying system. We remark that the Burg algorithm is a robust statistical procedure. With the notable exception of Ref. 6 that uses canonical correlation methods, most identification procedures in control are based on a deterministic analysis and consequently are quite sensitive to errors. In general, spectral identification based on the windowing of data lacks the resolving power of the Burg technique, which is a super resolution method.This work was supported by NATO Research Grant No. 585/83, by University of Nice, by Thomson CSF-DTAS, by Instituto Nacional de Investigação Científica, and by CIRIT (Comissió Interdepartmental de Recerca i Innovació Technológica de Catalunya). The work of the third author was also partially supported by Army Research Office Contract DAAG-29-84-k-005.Simple ARMA(2, 1) Basic language analysis programs to construct random data were written by the second author and Dr. K. D. Senne, MIT Lincoln Laboratory. Lack of stability of the direct estimation was observed at TRW with the help of Dr. G. Butler. Analysis programs in FORTRAN for ARMA(p, q) were written and debugged at CAPS by the fifth author. The research was helped by access to VAXs at Thomson CSF-DTAS, Valbonne, France, at CAPS, Instituto Superior Técnico, and at Universitat Politécnica de Catalunya. In particular, the authors explicitly acknowledge Thomson CSF-DTAS and Dr. H. Gautier for extending the use of their facilities to the authors from September 1983 until June 1984, when the examples presented were simulated.on leave from University of Southern California, Los Angeles, California.formerly visiting at Massachusetts Institute of Technology and Laboratory for Information and Decision Systems, while on leave from Instituto Superior Técnico, Lisbon, Portugal.     

A constraint programming approach for a batch processing problem with non-identical job sizes

This paper presents a constraint programming approach for a batch processing machine on which a finite number of jobs of non-identical sizes must be scheduled. A parallel batch processing machine can process several jobs simultaneously and the objective is to minimize the maximal lateness. The constraint programming formulation proposed relies on the decomposition of the problem into finding an assignment of the jobs to the batches, and then minimizing the lateness of the batches on a single machine. This formulation is enhanced by a new optimization constraint which is based on a relaxed problem and applies cost-based domain filtering techniques. Experimental results demonstrate the efficiency of cost-based domain filtering techniques. Comparisons to other exact approaches clearly show the benefits of the proposed approach: it can optimally solve problems that are one order of magnitude greater than those solved by a mathematical formulation or by a branch-and-price.