A generalization of the Frank—Wolfe theorem

The Frank—Wolfe theorem states that a quadratic function, bounded below on a nonempty polyhedral convex set, attains its infimum there. This paper gives sufficient conditions under which a function either attains its infimum on a nonempty polyhedral convex set or is unbounded below on some halfline of that set. Quadratic functions are shown to satisfy these sufficient conditions.Research and reproduction of this report were partially supported by the National Science Foundation Grant MCS76-81259; and the Office of Naval Research Contract N00014-75-C-0267.     

Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming

Decomposition has proved to be one of the more effective tools for the solution of large-scale problems, especially those arising in stochastic programming. A decomposition method with wide applicability is Benders' decomposition, which has been applied to both stochastic programming as well as integer programming problems. However, this method of decomposition relies on convexity of the value function of linear programming subproblems. This paper is devoted to a class of problems in which the second-stage subproblem(s) may impose integer restrictions on some variables. The value function of such integer subproblem(s) is not convex, and new approaches must be designed. In this paper, we discuss alternative decomposition methods in which the second-stage integer subproblems are solved using branch-and-cut methods. One of the main advantages of our decomposition scheme is that Stochastic Mixed-Integer Programming (SMIP) problems can be solved by dividing a large problem into smaller MIP subproblems that can be solved in parallel. This paper lays the foundation for such decomposition methods for two-stage stochastic mixed-integer programs.     

线性空间中具有集到集映射的向量极值问题的Lagrange乘子定理

本文在没有任何拓扑结构的条件下，即在非常一般的线性空间中，首先利用Ｍｏｒｒｉｓ序列定义了集到集凸映射的概念，其次证明了集到集映射的Ｆａｒｋａｓ－Ｍｉｎｋｏｗｓｋｉ定理，然后讨论了具有集到集映射的向量极值问题的Ｌａｇｒａｎｇｅ乘子定理。     

Extensions of Dinkelbach's algorithm for solving non-linear fractional programming problems

Dinkelbach's algorithm was developed to solve convex fractinal programming. This method achieves the optimal solution of the optimisation problem by means of solving a sequence of non-linear convex programming subproblems defined by a parameter. In this paper it is shown that Dinkelbach's algorithm can be used to solve general fractional programming. The applicability of the algorithm will depend on the possibility of solving the subproblems. Dinkelbach's extended algorithm is a framework to describe several algorithms which have been proposed to solve linear fractional programming, integer linear fractional programming, convex fractional programming and to generate new algorithms. The applicability of new cases as nondifferentiable fractional programming and quadratic fractional programming has been studied. We have proposed two modifications to improve the speed-up of Dinkelbachs algorithm. One is to use interpolation formulae to update the parameter which defined the subproblem and another truncates the solution of the suproblem. We give sufficient conditions for the convergence of these modifications. Computational experiments in linear fractional programming, integer linear fractional programming and non-linear fractional programming to evaluate the efficiency of these methods have been carried out.     

A method for globally minimizing concave functions over convex sets

A method is described for globally minimizing concave functions over convex sets whose defining constraints may be nonlinear. The algorithm generates linear programs whose solutions minimize the convex envelope of the original function over successively tighter polytopes enclosing the feasible region. The algorithm does not involve cuts of the feasible region, requires only simplex pivot operations and univariate search computations to be performed, allows the objective function to be lower semicontinuous and nonseparable, and is guaranteed to converge to the global solution. Computational aspects of the algorithm are discussed.     

Semidefinite Relaxations of Fractional Programs via Novel Convexification Techniques

In a recent work, we introduced the concept of convex extensions for lower semi-continuous functions and studied their properties. In this work, we present new techniques for constructing convex and concave envelopes of nonlinear functions using the theory of convex extensions. In particular, we develop the convex envelope and concave envelope of z=x/y over a hypercube. We show that the convex envelope is strictly tighter than previously known convex underestimators of x/y. We then propose a new relaxation technique for fractional programs which includes the derived envelopes. The resulting relaxation is shown to be a semidefinite program. Finally, we derive the convex envelope for a class of functions of the type f(x,y) over a hypercube under the assumption that f is concave in x and convex in y.     

A simplex algorithm for piecewise-linear programming I: Derivation and proof

The simplex method for linear programming can be extended to permit the minimization of any convex separable piecewise-linear objective, subject to linear constraints. This three-part paper develops and analyzes a general, computationally practical simplex algorithm for piecewiselinear programming.Part I derives and justifies the essential steps of the algorithm, by extension from the simplex method for linear programming in bounded variables. The proof employs familiar finite-termination arguments and established piecewise-linear duality theory.Part II considers the relaxation of technical assumptions pertaining to finiteness, feasibility and nondegeneracy of piecewise-linear programs. Degeneracy is found to have broader consequences than in the linear case, and the standard techniques for prevention of cycling are extended accordingly.Part III analyzes the computational requirements of piecewise-linear programming. The direct approach embodied in the piecewise-linear simplex algorithm is shown to be inherently more efficient than indirect approaches that rely on transformation of piecewise-linear programs to equivalent linear programs. A concluding section surveys the many applications of piecewise-linear programming in linear programming,l ₁ estimation, goal programming, interval programming, and nonlinear optimization.This research has been supported in part by the National Science Foundation under grant MCS-8217261.     

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.     

Strong duality for inexact linear programming

In this paper, we apply the Dubovitskii-Milyutin approach to derive strong duality theorems for inexact linear programming problems. Inexact linear programming deals with the standard linear problem in which the data is not well known and it is supposed to lie in certain given convex sets. The case of parametric dependence of the data is particularly analyzed and relations with semi-infinite and

semi-definite programming are also commented.     

On ranking of feasible solutions of a bottleneck linear programming problem

Summary An algorithm for the ranking of the feasible solutions of a bottleneck linear programming problem in ascending order of values of a concave bottleneck objective function is developed in this paper. The “best” feasible solution for a given value of the bottleneck objective is obtained at each stage. It is established that only the extreme points of a convex polytope need to be examined for the proposed ranking. Another algorithm, involving partitioning of the nodes, to rank the feasible solutions of the bottleneck linear programming problem is proposed, and numerical illustrations for both are provided.     

Convex optimization and lagrange multipliers

The duality theorem of linear programming is used to prove several results on convex optimization. This is done without using separating hyerplane theorems.This work was supported in part by a grant from Investors in Business Education.     

A practicable way for computing the directional derivative of the optimal value function in convex programming

Formulas for computing the directional derivative of the optimal value function or of lower or upper bounds of it are well-known from literature. Because they have as a rule a minmax structure, methods from nondifferentiable optimization are required.

Considering a fully parametrized convex problem, in the paper the mentioned minmax formulas are transformed into usual programming problems. Although they are nonconvex in general, the computational effort is much lower than that for minmax problems. In several special cases, for instance, for linear least squares problems, linear programming problems arise.     

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.     

Equivalence of some quadratic programming algorithms

We formulate a general algorithm for the solution of a convex (but not strictly convex) quadratic programming problem. Conditions are given under which the iterates of the algorithm are uniquely determined. The quadratic programming algorithms of Fletcher, Gill and Murray, Best and Ritter, and van de Panne and Whinston/Dantzig are shown to be special cases and consequently are equivalent in the sense that they construct identical sequences of points. The various methods are shown to differ only in the manner in which they solve the linear equations expressing the Kuhn-Tucker system for the associated equality constrained subproblems. Equivalence results have been established by Goldfarb and Djang for the positive definite Hessian case. Our analysis extends these results to the positive semi-definite case. This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grant No. A8189.     

Error bounds for the aggregated convex programming problem

Applied mathematical programming problems are often approximations of larger, more detailed problems. One criterion to evaluate an approximating program is the magnitude of the difference between the optimal objective values of the original and the approximating program. The approximation we consider is variable aggregation in a convex program. Bounds are derived on the difference between the two optimal objective values. Previous results of Geoffrion and Zipkin are obtained by specializing our results to linear programming. Also, we apply our bounds to a convex transportation problem. Thanks are due to Ron Dembo, Paul Zipkin and the referees for valuable comments. This research was supported by NSF Grant ENG-76-15599.     

An algorithm for a piecewise linear model of trade and production with negative prices and bankruptcy

The general equilibrium model is approximated as a piecewise linear convex model and solved from the point of view of welfare economics using linear programming and fixed point methods.This research was supported in part by Army Research Office-Durham Contract DAAG-29-74-C-0032, NSF Grant MPS-72-04832-A03, and Energy Research and Development Administration Contract E(04-3)-326 PA#18.     

An unconstrained convex programming approach to solving convex quadratic programming problems

In this paper, we derive an unconstrained convex programming approach to solving convex quadratic programming problems in standard form. Related duality theory is established by using two simple inequalities. An ?-optimal solution is obtained by solving an unconstrained dual convex program. A dual-to-primal conversion formula is also provided. Some preliminary computational results of using a curved search method is included     

An unconstrained convex programming view of linear programming

The major interest of this paper is to show that, at least in theory, a pair of primal and dual -optimal solutions to a general linear program in Karmarkar's standard form can be obtained by solving an unconstrained convex program. Hence unconstrained convex optimization methods are suggested to be carefully reviewed for this purpose.     

An operator-valued Lyapunov theorem

We generalize Lyapunov's convexity theorem for classical (scalar-valued) measures to quantum (operator-valued) measures. In particular, we show that the range of a nonatomic quantum probability measure is a weak^?-closed convex set of quantum effects (positive operators bounded above by the identity operator) under a sufficient condition on the non-injectivity of integration. To prove the operator-valued version of Lyapunov's theorem, we must first define the notions of essentially bounded, essential support, and essential range for quantum random variables (Borel measurable functions from a set to the bounded linear operators acting on a Hilbert space).     

A characterization of affine length and asymptotic approximation of convex discs

It is shown that every equi-affine invariant and upper semicontinuous valuation on the space of convex discs is a linear combination of the Euler characteristic, area, and affine length. Asymptotic formulae for approximation of convex discs by polygons are derived, extending results of L. Fejes Tóth from smooth convex discs to general convex discs.