An outer approximations algorithm for computer-aided design problems

This paper presents an implementable algorithm of the outer approximations type for solving nonlinear programming problems with functional inequality constraints. The algorithm was motivated by engineering design problems in circuit tolerancing, multivariable control, and shock-resistant structures.This research was sponsored by the National Science Foundation, Grant No. ENG73-08214A01, and the National Science Foundation (RANN), Grant No. ENV76-04264.     

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.     

Solving nonlinear inequalities in a finite number of iterations

This paper describes a modified Newton algorithm for solving a finite system of inequalities in a finite number of iterations.This research was supported by NSF Grant No. ENG-73-08214-AO1, by NSF-RANN Grant No. ENV-76-04264, and by the United Kingdom Science Research Council.     

A transformation technique for optimal control problems with partially linear state inequality constraints

This paper considers optimal control problems involving the minimization of a functional subject to differential constraints, terminal constraints, and a state inequality constraint. The state inequality constraint is of a special type, namely, it is linear in some or all of the components of the state vector.A transformation technique is introduced, by means of which the inequality-constrained problem is converted into an equality-constrained problem involving differential constraints, terminal constraints, and a control equality constraint. The transformation technique takes advantage of the partial linearity of the state inequality constraint so as to yield a transformed problem characterized by a new state vector of minimal size. This concept is important computationally, in that the computer time per iteration increases with the square of the dimension of the state vector.In order to illustrate the advantages of the new transformation technique, several numerical examples are solved by means of the sequential gradient-restoration algorithm for optimal control problems involving nondifferential constraints. The examples show the substantial savings in computer time for convergence, which are associated with the new transformation technique.This research was supported by the Office of Scientific Research, Office of Aerospace Research, United States Air Force, Grant No. AF-AFOSR-76-3075, and by the National Science Foundation, Grant No. MCS-76-21657.     

On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method

Interest in linear programming has been intensified recently by Karmarkar’s publication in 1984 of an algorithm that is claimed to be much faster than the simplex method for practical problems. We review classical barrier-function methods for nonlinear programming based on applying a logarithmic transformation to inequality constraints. For the special case of linear programming, the transformed problem can be solved by a “projected Newton barrier” method. This method is shown to be equivalent to Karmarkar’s projective method for a particular choice of the barrier parameter. We then present details of a specific barrier algorithm and its practical implementation. Numerical results are given for several non-trivial test problems, and the implications for future developments in linear programming are discussed. The research of the Stanford authors was supported by the U.S. Department of Energy Contract DE-AA03-76SF00326, PA No. DE-AS03-76ER72018; National Science Foundation Grants DCR-8413211 and ECS-8312142; the Office of Naval Research Contract N00014-85-K-0343; and the U.S. Army Research Office Contract DAAG29-84-K-0156. The research of J.A. Tomlin was supported by Ketron, Inc. and the Office of Naval Research Contract N00014-85-C-0338.     

Algorithmic equivalence in quadratic programming,I: A least-distance programming problem

It is demonstrated that Wolfe's algorithm for finding the point of smallest Euclidean norm in a given convex polytope generates the same sequence of feasible points as does the van de Panne-Whinstonsymmetric algorithm applied to the associated quadratic programming problem. Furthermore, it is shown how the latter algorithm may be simplified for application to problems of this type.This work was supported by the National Science Foundation, Grant No. MCS-71-03341-AO4, and by the Office of Naval Research, Contract No. N00014-75-C-0267.     

An algorithm for minimizing a differentiable function subject to box constraints and errors

We consider the problem of minimizing a differentiable function ofn parameters, with upper and lower bounds on the parameters. The motivation for this work comes from the optimization of the design of transient electrical circuits. In such optimization, the parameters are circuit elements, the bound constraints keep these parameters physically meaningful, and both the function and gradient evaluations contain errors. We describe a quasi-Newton algorithm for such problems. This algorithm handles the box constraints directly and approximates the given function locally by nonsingular quadratic functions. Numerical tests indicate that the algorithm can tolerate the errors, if the errors in the function and gradient are of the same relative size.This paper was presented at the SIAM National Meeting, Chicago, Illinois, 1976.This research was sponsored in part by the Air Force Office of Scientific Research (AFSC), United States Air Force, under Contract No. F44620-76-C-0022.     

An algorithm for optimizing network flow capacity under economies of scale

The problem of optimally allocating a fixed budget to the various arcs of a single-source, single-sink network for the purpose of maximizing network flow capacity is considered. The initial vector of arc capacities is given, and the cost function, associated with each arc, for incrementing capacity is concave; therefore, the feasible region is nonconvex. The problem is approached by Benders' decomposition procedure, and a finite algorithm is developed for solving the nonconvex relaxed master problems. A numerical example of optimizing network flow capacity, under economies of scale, is included.This research was supported by the National Science Foundation, Grant No. GK-32791.     

Characterization of optimality in convex programming without a constraint qualification

Necessary and sufficient conditions of optimality are given for convex programming problems with no constraint qualification. The optimality conditions are stated in terms of consistency or inconsistency of a family of systems of linear inequalities and cone relations.This research was supported by Project No. NR-047-021, ONR Contract No. N00014-67-A-0126-0009 with the Center for Cybernetics Studies, The University of Texas; by NSF Grant No. ENG-76-10260 at Northwestern University; and by the National Research Council of Canada.     

A note on a sufficient-decrease criterion for a non-derivative step-length procedure

A step-length algorithm is an essential part of many descent methods for unconstrained and constrained optimization. In this note we present a criterion that defines an acceptable step length when only function values are available at trial step lengths.This research was supported by the U.S. Department of Energy Contract DE-AC03-76SF00326, PA No. DE-AT03-76ER72018; National Science Foundation Grants MCS-7926009 and ECS-8012974; the Office of Naval Research Contract N00014-75-C-0267; and the U.S. Army Research Office Contract DAAG29-79-C-0110.     

Benders Decomposition for multi-stage stochastic mixed complementarity problems – Applied to a global natural gas market model

This paper presents and implements a Benders Decomposition type of algorithm for large-scale, stochastic multi-period mixed complementarity problems. The algorithm is applied to various multi-stage natural gas market models accounting for market power exertion by traders. Due to the non-optimization nature of the natural gas market problem, a straightforward implementation of the traditional Benders Decomposition is not possible. The master and subproblems can be derived from the underlying optimization problems and transformed into complementarity problems. However, to complete the master problems optimality cuts are added using the variational inequality-based method developed in Gabriel and Fuller (2010). In this manner, an alternative derivation of Benders Decomposition for Stochastic MCP is presented, thereby making this approach more applicable to a broader audience. The algorithm can successfully solve problems with up to 256 scenarios and more than 600 thousand variables, and problems with over 117 thousand variables with more than two thousand first-stage capacity expansion variables. The algorithm is efficient for solving two-stage problems. The computational time reduction for other stochastic problems is considerable and would be even larger if a parallel implementation of the algorithm were used. The paper concludes with a discussion of infrastructure expansion results, illustrating the impact of hedging on investment timing and optimal capacity sizes.     

A revised simplex method for linear multiple objective programs

For linear multiple-objective problems, a necessary and sufficient condition for a point to be efficient is employed in the development of a revised simplex algorithm for the enumeration of the set of efficient extreme points. Five options within this algorithm were tested on a variety of problems. Results of these tests provide indications for effective use of the algorithm.This work was partially supported by the Office of Naval Research, Contract No. N00014-67-A-0321-0003 (NR047-095).     

A general sufficiency theorem for minimax control

This paper considers optimal control problems where there is uncertainty in the differential equations describing the system. A minimax optimality criterion is used, and sufficient conditions for a control to be a minimax control are presented. These conditions are more general than those given in Refs. 1 and 2.This research was supported by AFOSR under Grant No. 76-2923.     

An accelerated multiplier method for nonlinear programming

This paper describes an accelerated multiplier method for solving the general nonlinear programming problem. The algorithm poses a sequence of unconstrained optimization problems. The unconstrained problems are solved using a rank-one recursive algorithm described in an earlier paper. Multiplier estimates are obtained by minimizing the error in the Kuhn-Tucker conditions using a quadratic programming algorithm. The convergence of the sequence of unconstrained problems is accelerated by using a Newton-Raphson extrapolation process. The numerical effectiveness of the algorithm is demonstrated on a relatively large set of test problems.This work was supported by the US Air Force under Contract No. F04701-74-C-0075.     

Simplicial Branch-and-Reduce Algorithm for Convex Programs with a Multiplicative Constraint

Optimization problems that involve products of convex functions in the objective function or in the constraints arise in a variety of applications. These problems are difficult global optimization problems. During the past 15 years, however, a number of practical algorithms have been proposed for globally solving these types of problems. In this article, we present and validate a branch-and-reduce algorithm for finding a global optimal solution to a convex program that contains an additional constraint on the product of several convex functions. To globally solve this problem, the algorithm instead globally solves an equivalent master problem. At any stage of the algorithm, a disconnected set consisting of a union of simplices is constructed. This set is guaranteed to contain a portion of the boundary of the feasible region of the master problem where a global optimal solution lies. The algorithm uses a new branch-and-reduce scheme to iteratively reduce the sizes of these sets until a global optimal solution is found. Several potential computational advantages of the algorithm are explained, and a numerical example is solved.     

Improving benders decomposition using a genetic algorithm

We develop and investigate the performance of a hybrid solution framework for solving mixed-integer linear programming problems. Benders decomposition and a genetic algorithm are combined to develop a framework to compute feasible solutions. We decompose the problem into a master problem and a subproblem. A genetic algorithm along with a heuristic are used to obtain feasible solutions to the master problem, whereas the subproblem is solved to optimality using a linear programming solver. Over successive iterations the master problem is refined by adding cutting planes that are implied by the subproblem. We compare the performance of the approach against a standard Benders decomposition approach as well as against a stand-alone solver (Cplex) on MIPLIB test problems.     

A stable method for solving certain constrained least squares problems

This paper presents a feasible descent algorithm for solving certain constrained least squares problems. These problems are specially structured quadratic programming problems with positive semidefinite Hessian matrices that are allowed to be singular. The algorithm generates a finite sequence of subproblems that are solved using the numerically stable technique of orthogonal factorization with reorthogonalization and Given's transformation updating.This material is based upon work supported by the National Science Foundation under Grant No. MCS 78-06716 and by the International Institute for Applied Systems Analysis.     

A matrix generation approach for eigenvalue optimization

We study the extension of a column generation technique to nonpolyhedral models. In particular, we study the problem of minimizing the maximum eigenvalue of an affine combination of symmetric matrices. At each step of the algorithm a restricted master problem in the primal space, corresponding to the relaxed dual (original) problem, is formed. A query point is obtained as an approximate analytic center of a bounded set that contains the optimal solution of the dual problem. The original objective function is evaluated at the query point, and depending on its differentiability a column or a matrix is added to the restricted master problem. We discuss the issues of recovering feasibility after the restricted master problem is updated by a column or a matrix. The computational experience of implementing the algorithm on randomly generated problems are reported and the cpu time of the matrix generation algorithm is compared with that of the primal-dual interior point methods on dense and sparse problems using the software SDPT3. Our numerical results illustrate that the matrix generation algorithm outperforms primal-dual interior point methods on dense problems with no structure and also on a class of sparse problems. This work has been completed with the partial support of a summer grant from the College of Business Administration, California State University San Marcos, and the University Professional Development/Research and Creative Activity Grant     

Optimal scaling of balls and polyhedra

The concern is with solving as linear or convex quadratic programs special cases of the optimal containment and meet problems. The optimal containment or meet problem is that of finding the smallest scale of a set for which some translation contains a set or meets each element in a collection of sets, respectively. These sets are unions or intersections of cells where a cell is either a closed polyhedral convex set or a closed solid ball.This work was supported in part by the Department of Energy Contract DE-AC03-76-SF00326, PA No. DE-AT-03-76ER72018; National Science Foundation Grants MCS79-03145 and SOC78-16811; and the Army Research Office—Durham, Contract DAAG-29-78-G-0026.     

Solving nonlinear multicommodity flow problems by the analytic center cutting plane method

The paper deals with nonlinear multicommodity flow problems with convex costs. A decomposition method is proposed to solve them. The approach applies a potential reduction algorithm to solve the master problem approximately and a column generation technique to define a sequence of primal linear programming problems. Each subproblem consists of finding a minimum cost flow between an origin and a destination node in an uncapacited network. It is thus formulated as a shortest path problem and solved with Dijkstra’s d-heap algorithm. An implementation is described that takes full advantage of the supersparsity of the network in the linear algebra operations. Computational results show the efficiency of this approach on well-known nondifferentiable problems and also large scale randomly generated problems (up to 1000 arcs and 5000 commodities). This research has been supported by the Fonds National de la Recherche Scientifique Suisse, grant #12-34002.92, NSERC-Canada and FCAR-Quebec. This research was supported by an Obermann fellowship at the Center for Advanced Studies at the University of Iowa.