Bilinear programming: An exact algorithm

The Bilinear Programming Problem is a structured quadratic programming problem whose objective function is, in general, neither convex nor concave. Making use of the formal linearity of a dual formulation of the problem, we give a necessary and sufficient condition for optimality, and an algorithm to find an optimal solution.Research partially supported by the Office of Naval Research under Contract N00014-69-A-0200-1010 with the University of California.     

Complementarity and nondegeneracy in semidefinite programming

Primal and dual nondegeneracy conditions are defined for semidefinite programming. Given the existence of primal and dual solutions, it is shown that primal nondegeneracy implies a unique dual solution and that dual nondegeneracy implies a unique primal solution. The converses hold if strict complementarity is assumed. Primal and dual nondegeneracy assumptions do not imply strict complementarity, as they do in LP. The primal and dual nondegeneracy assumptions imply a range of possible ranks for primal and dual solutionsX andZ. This is in contrast with LP where nondegeneracy assumptions exactly determine the number of variables which are zero. It is shown that primal and dual nondegeneracy and strict complementarity all hold generically. Numerical experiments suggest probability distributions for the ranks ofX andZ which are consistent with the nondegeneracy conditions. Supported in part by the U.S. National Science Foundation grant CCR-9625955. Supported in part by U.S. National Science Foundation grant CCR-9501941 and the U.S. Office of Naval Research grant N00014-96-1-0704. Supported in part by U.S. National Science Foundation grant CCR-9401119.     

The empirical performance of a polynomial algorithm for constrained nonlinear optimization

In [6], a polynomial algorithm based on successive piecewise linear approximation was described. The algorithm is polynomial for constrained nonlinear (convex or concave) optimization, when the constraint matrix has a polynomial size subdeterminant. We propose here a practical adaptation of that algorithm with the idea of successive piecewise linear approximation of the objective on refined grids, and the testing of the gap between lower and upper bounds. The implementation uses the primal affine interior point method at each approximation step. We develop special features to speed up each step and to evaluate the gap. Empirical study of problems of size up to 198 variables and 99 constraints indicates that the procedure is very efficient and all problems tested were terminated after 171 interior point iterations. The procedure used in the implementation is proved to converge when the objective is strongly convex.Supported in part by the Office of Naval Research under Grant No. N00014-88-K-0377 and Grant No. ONR N00014-91-J-1241.     

Superlinear convergence of the affine scaling algorithm

In this paper we show that a variant of the long-step affine scaling algorithm (with variable stepsizes) is two-step superlinearly convergent when applied to general linear programming (LP) problems. Superlinear convergence of the sequence of dual estimates is also established. For homogeneous LP problems having the origin as the unique optimal solution, we also show that 2/3 is a sharp upper bound on the (fixed) stepsize that provably guarantees that the sequence of primal iterates converge to the optimal solution along a unique direction of approach. Since the point to which the sequence of dual estimates converge depend on the direction of approach of the sequence of primal iterates, this result gives a plausible (but not accurate) theoretical explanation for why 2/3 is a sharp upper bound on the (fixed) stepsize that guarantees the convergence of the dual estimates. The work of this author was based on research supported by the Overseas Research Scholars of the Ministry of Education, Science and Culture of Japan, 1992. The work of this author was based on research supported by the National Science Foundation (NSF) under grant DDM-9109404 and the Office of Naval Research (ONR) under grant N00014-93-1-0234. This work was done while the second author was a faculty member of the Systems and Industrial Engineering Department at the University of Arizona.     

Solving combinatorial optimization problems using Karmarkar's algorithm

We describe a cutting plane algorithm for solving combinatorial optimization problems. The primal projective standard-form variant of Karmarkar's algorithm for linear programming is applied to the duals of a sequence of linear programming relaxations of the combinatorial optimization problem.Computational facilities provided by the Cornell Computational Optimization Project supported by NSF Grant DMS-8706133 and by the Cornell National Supercomputer Facility. The Cornell National Supercomputer Facility is a resource of the Center for Theory and Simulation in Science and Engineering at Cornell Unversity, which is funded in part by the National Science Foundation, New York State, and the IBM Corporation. The research of both authors was partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.Research partially supported by ONR Grant N00014-90-J-1714.Research partially supported by NSF Grant ECS-8602534 and by ONR Contract N00014-87-K-0212.     

A convergence proof for an affine-scaling algorithm for convex quadratic programming without nondegeneracy assumptions

This paper presents a theoretical result on convergence of a primal affine-scaling method for convex quadratic programs. It is shown that, as long as the stepsize is less than a threshold value which depends on the input data only, Ye and Tse's interior ellipsoid algorithm for convex quadratic programming is globally convergent without nondegeneracy assumptions. In addition, its local convergence rate is at least linear and the dual iterates have an ergodically convergent property.Research supported in part by the NSF under grant DDM-8721709.     

Solving convex quadratic bilevel programming problems using an enumeration sequential quadratic programming algorithm

In this paper, we present an original method to solve convex bilevel programming problems in an optimistic approach. Both upper and lower level objective functions are convex and the feasible region is a polyhedron. The enumeration sequential linear programming algorithm uses primal and dual monotonicity properties of the primal and dual lower level objective functions and constraints within an enumeration frame work. New optimality conditions are given, expressed in terms of tightness of the constraints of lower level problem. These optimality conditions are used at each step of our algorithm to compute an improving rational solution within some indexes of lower level primal-dual variables and monotonicity networks as well. Some preliminary computational results are reported.     

A Lagrange duality approach for multi-composed optimization problems

In this paper, we consider an optimization problem with geometric and cone constraints, whose objective function is a composition of \(n+1\) functions. For this problem, we calculate its conjugate dual problem, where the functions involved in the objective function of the primal problem will be decomposed. Furthermore, we formulate generalized interior point regularity conditions for strong duality and give necessary and sufficient optimality conditions. As applications of this approach, we determine the formulas of the conjugate as well as the biconjugate of the objective function of the primal problem and discuss an optimization problem having as objective function the sum of reciprocals of concave functions.     

An outer approximation method for minimizing the product of several convex functions on a convex set

This paper addresses the minimization of the product ofp convex functions on a convex set. It is shown that this nonconvex problem can be converted to a concave minimization problem withp variables, whose objective function value is determined by solving a convex minimization problem. An outer approximation method is proposed for obtaining a global minimum of the resulting problem. Computational experiments indicate that this algorithm is reasonable efficient whenp is less than 4.This research was partly supported by Grant-in-Aid for Scientific Research of the Ministry of Education, Science and Culture, Grant No. (C)03832018 and (C)04832010.     

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.