Optimal objective function approximation for separable convex quadratic programming

We present an optimal piecewise-linear approximation method for the objective function of separable convex quadratic programs. The method provides guidelines on how many grid points to use and how to position them for a piecewise-linear approximation if the error induced by the approximation is to be bounded a priori.Corresponding author.     

A polynomially bounded algorithm for a singly constrained quadratic program

This paper presents a characterization of the solutions of a singly constrained quadratic program. This characterization is then used in the development of a polynomially bounded algorithm for this class of problems.     

Quadratic geometric programming with application to machining economics

Geometric Programming is extended to include convex quadratic functions. Generalized Geometric Programming is applied to this class of programs to obtain a convex dual program. Machining economics problems fall into this class. Such problems are studied by applying this duality to a nested set of three problems. One problem is zero degree of difficulty and the solution is obtained by solving a simple system of equations. The inclusion of a constraint restricting the force on the tool to be less than or equal to the breaking force provides a more realistic solution. This model is solved as a program with one degree of difficulty. Finally the behavior of the machining cost per part is studied parametrically as a function of axial depth. This research was supported by the Air Force Office of Scientific Research Grant AFOSR-83-0234     

The complementary unboundedness of dual feasible solution sets in convex programming

F.E. Clark has shown that if at least one of the feasible solution sets for a pair of dual linear programming problems is nonempty then at least one of them is both nonempty and unbounded. Subsequently, M. Avriel and A.C. Williams have obtained the same result in the more general context of (prototype posynomial) geometric programming. In this paper we show that the same result is actually false in the even more general context of convex programming — unless a certain regularity condition is satisfied.We also show that the regularity condition is so weak that it is automatically satisfied in linear programming (prototype posynomial) geometric programming, quadratic programming (with either linear or quadratic constraints),l _p -regression analysis, optimal location, roadway network analysis, and chemical equilibrium analysis. Moreover, we develop an equivalent regularity condition for each of the usual formulations of duality.Research sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR-73-2516.     

Analytical solutions to the optimization of a quadratic cost function subject to linear and quadratic equality constraints

In the area of broad-band antenna array signal processing, the global minimum of a quadratic equality constrained quadratic cost minimization problem is often required. The problem posed is usually characterized by a large optimization space (around 50–90 tuples), a large number of linear equality constraints, and a few quadratic equality constraints each having very low rank quadratic constraint matrices. Two main difficulties arise in this class of problem. Firstly, the feasibility region is nonconvex and multiple local minima abound. This makes conventional numerical search techniques unattractive as they are unable to locate the global optimum consistently (unless a finite search area is specified). Secondly, the large optimization space makes the use of decision-method algorithms for the theory of the reals unattractive. This is because these algorithms involve the solution of the roots of univariate polynomials of order to the square of the optimization space. In this paper we present a new algorithm which exploits the structure of the constraints to reduce the optimization space to a more manageable size. The new algorithm relies on linear-algebra concepts, basic optimization theory, and a multivariate polynomial root-solving tool often used by decision-method algorithms.This research was supported by the Australian Research Council and the Corporative Research Centre for Broadband Telecommunications and Networking.     

A quadratic assignment formulation of the molecular conformation problem

The molecular conformation problem is discussed, and a concave quadratic global minimization approach for solving it is described. This approach is based on a quadratic assignment formulation of a discrete approximation to the original problem.     

An infeasible-interior-point predictor-corrector algorithm for theP *-geometric LCP

AP _*-geometric linear complementarity problem (P _*GP) as a generalization of the monotone geometric linear complementarity problem is introduced. In particular, it contains the monotone standard linear complementarity problem and the horizontal linear complementarity problem. Linear and quadratic programming problems can be expressed in a “natural” way (i.e., without any change of variables) asP _*GP. It is shown that the algorithm of Mizunoet al. [6] can be extended to solve theP _*GP. The extended algorithm is globally convergent and its computational complexity depends on the quality of the starting points. The algorithm is quadratically convergent for problems having a strictly complementary solution. The work of F. A. Potra was supported in part by NSF Grant DMS 9305760     

A quadratic network optimization model for equilibrium single commodity trade flows

When supply and demand curves for a single commodity are approximately linear in each ofN regions and interregional transportation costs are linear, then equilibrium trade flows can be computed by solving a quadratic program of special structure. An equilibrium trade flow exists in which the routes carrying positive flow form a forest, and this solution can be efficiently computed by a tree growing algorithm.     

Computation of efficient compromise arcs in Convex Quadratic Multicriteria Optimization

Given a Convex Quadratic Multicriteria Optimization Problem, we show the stability of the Domination Problem. By modifying Benson’s single parametric method, which is based on the Domination Problem, we are able to show the existence of an efficient compromise arc connecting any two efficient points. Moreover, we deduce an algorithm which realizes the modification in polynomial time.Part of the article is taken from the author’s doctoral dissertation at the University of Eichstätt-Ingolstadt     

Nonlinear programming via an exact penalty function: Global analysis

In this paper we motivate and describe an algorithm to solve the nonlinear programming problem. The method is based on an exact penalty function and possesses both global and superlinear convergence properties. We establish the global qualities here (the superlinear nature is proven in [7]). The numerical implementation techniques are briefly discussed and preliminary numerical results are given.This work is supported in part by NSERC Grant No. A8639 and the U.S. Dept. of Energy.