Composite geometric programming

Geometric programming is based on functions called posynomials, the terms of which are log-linear. This class of programs is extended from the composition of an exponential and a linear function to an exponential and a convex function. The resulting duality theory for composite geometric programs retains many of the qualities of geometric programming duality, while at the same time encompassing new areas of application. As an application, composite geometric programming is applied to exponential geometric programming. A pure dual is developed for the first time and used to solve a problem from the literature.This research was supported by the Air Force Office of Scientific Research, Grant No. AFOSR-83-0234.     

Linearly constrained convex programming as unconstrained differentiable concave programming

Recently, Fang proposed approximating a linear program in Karmarkar's standard form by adding an entropic barrier function to the objective function and using a certain geometric inequality to transform the resulting problem into an unconstrained differentiable concave program. We show that, by using standard duality theory for convex programming, the results of Fang and his coworkers can be strengthened and extended to linearly constrained convex programs and more general barrier functions.This research was supported by the National Science Foundation, Grant No. CCR-91-03804.     

Stable zero duality gaps in convex programming: Complete dual characterisations with applications to semidefinite programs

The zero duality gap that underpins the duality theory is one of the central ingredients in optimisation. In convex programming, it means that the optimal values of a given convex program and its associated dual program are equal. It allows, in particular, the development of efficient numerical schemes. However, the zero duality gap property does not always hold even for finite-dimensional problems and it frequently fails for problems with non-polyhedral constraints such as the ones in semidefinite programming problems. Over the years, various criteria have been developed ensuring zero duality gaps for convex programming problems. In the present work, we take a broader view of the zero duality gap property by allowing it to hold for each choice of linear perturbation of the objective function of the given problem. Globalising the property in this way permits us to obtain complete geometric dual characterisations of a stable zero duality gap in terms of epigraphs and conjugate functions. For convex semidefinite programs, we establish necessary and sufficient dual conditions for stable zero duality gaps, as well as for a universal zero duality gap in the sense that the zero duality gap property holds for each choice of constraint right-hand side and convex objective function. Zero duality gap results for second-order cone programming problems are also given. Our approach makes use of elegant conjugate analysis and Fenchel's duality.     

On geometric programming and complementary slackness

When the terms in a convex primal geometric programming (GP) problem are multiplied by slack variables whose values must be at least unity, the invariance conditions may be solved as constraints in a linear programming (LP) problem in logarithmically transformed variables. The number of transformed slack variables included in the optimal LP basis equals the degree of difficulty of the GP problem, and complementary slackness conditions indicate required changes in associated GP dual variables. A simple, efficient search procedure is used to generate a sequence of improving primal feasible solutions without requiring the use of the GP dual objective function. The solution procedure appears particularly advantageous when solving very large geometric programming problems, because only the right-hand constants in a system of linear equations change at each iteration.The influence of J. G. Ecker, the writer's teacher, is present throughout this paper. Two anonymous referees and the Associate Editor made very helpful suggestions. Dean Richard W. Barsness provided generous support for this work.     

Convex analysis treated by linear programming

The theme of this paper is the application of linear analysis to simplify and extend convex analysis. The central problem treated is the standard convex program — minimize a convex function subject to inequality constraints on other convex functions. The present approach uses the support planes of the constraint region to transform the convex program into an equivalent linear program. Then the duality theory of infinite linear programming shows how to construct a new dual program of bilinear type. When this dual program is transformed back into the convex function formulation it concerns the minimax of an unconstrained Lagrange function. This result is somewhat similar to the Kuhn—Tucker theorem. However, no constraint qualifications are needed and yet perfect duality maintains between the primal and dual programs.Work prepared under Research Grant DA-AROD-31-124-71-G17, Army Research Office (Durham).     

Nonlinear Proximal Decomposition Method for Convex Programming

In this paper, we propose a new decomposition method for solving convex programming problems with separable structure. The proposed method is based on the decomposition method proposed by Chen and Teboulle and the nonlinear proximal point algorithm using the Bregman function. An advantage of the proposed method is that, by a suitable choice of the Bregman function, each subproblem becomes essentially the unconstrained minimization of a finite-valued convex function. Under appropriate assumptions, the method is globally convergent to a solution of the problem.     

Posynomial geometric programming as a special case of semi-infinite linear programming

This paper develops a wholly linear formulation of the posynomial geometric programming problem. It is shown that the primal geometric programming problem is equivalent to a semi-infinite linear program, and the dual problem is equivalent to a generalized linear program. Furthermore, the duality results that are available for the traditionally defined primal-dual pair are readily obtained from the duality theory for semi-infinite linear programs. It is also shown that two efficient algorithms (one primal based and the other dual based) for geometric programming actually operate on the semi-infinite linear program and its dual.     

Rough posynomial geometric programming

A rough posynomial geometric programming is put forward by the author. This model is advantageous for us to consider questions not only from the quantity of aspect, but from the quality because it contains more information than a traditional geometric programming one. Here, a rough convex function concept is advanced in rough value sets on foundation of rough sets and rough convex sets. Besides, a knowledge expression model in rough posynomial geometric programming is established and so is a mathematical one. Thirdly, solution properties are studied in mathematical model of rough posynomial geometric programming, and antinomy of the more-for-less paradox is solved with an arithmetic in rough posynomial geometric programming given, which can be changed into a rough linear programming after monomial rough posynomial geometric programming is solved. Finally, validity in model and algorithm is verified by examples.     

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     

A General Alternative Procedure for Solving Negative Degree of Difficulty Problems in Geometric Programming

The degree of difficulty is an important concept in classical geometric programming theory. The dual problem is often infeasible when the degree of difficulty is negative and little has been published on this topic. In this paper, an alternative procedure is developed to find the optimal solution for the posynomial geometric programming problem with a negative degree of difficulty. First an equivalent problem was constructed with a positive degree of difficulty and the general posynomial geometric programming problem was solved using an original method previously developed by the authors. This method avoids the difficulty of non-differentiability of the dual objective function in the classical methods classified as dual. It also avoids the problem that appears when the feasible region for the dual problem is formed by an inconsistent system of linear equations.     

Range reduction techniques for improving computational efficiency in global optimization of signomial geometric programming problems

Many global optimization approaches for solving signomial geometric programming problems are based on transformation techniques and piecewise linear approximations of the inverse transformations. Since using numerous break points in the linearization process leads to a significant increase in the computational burden for solving the reformulated problem, this study integrates the range reduction techniques in a global optimization algorithm for signomial geometric programming to improve computational efficiency. In the proposed algorithm, the non-convex geometric programming problem is first converted into a convex mixed-integer nonlinear programming problem by convexification and piecewise linearization techniques. Then, an optimization-based approach is used to reduce the range of each variable. Tightening variable bounds iteratively allows the proposed method to reach an approximate solution within an acceptable error by using fewer break points in the linearization process, therefore decreasing the required CPU time. Several numerical experiments are presented to demonstrate the advantages of the proposed method in terms of both computational efficiency and solution quality.     

Generalized Newton method for linear optimization problems with inequality constraints

A dual problem of linear programming is reduced to the unconstrained maximization of a concave piecewise quadratic function for sufficiently large values of a certain parameter. An estimate is given for the threshold value of the parameter starting from which the projection of a given point to the set of solutions of the dual linear programming problem in dual and auxiliary variables is easily found by means of a single solution of the unconstrained maximization problem. The unconstrained maximization is carried out by the generalized Newton method, which is globally convergent in an a finite number of steps. The results of numerical experiments are presented for randomly generated large-scale linear programming problems.     

A column generation approach for the unconstrained binary quadratic programming problem

This paper proposes a column generation approach based on the Lagrangean relaxation with clusters to solve the unconstrained binary quadratic programming problem that consists of maximizing a quadratic objective function by the choice of suitable values for binary decision variables. The proposed method treats a mixed binary linear model for the quadratic problem with constraints represented by a graph. This graph is partitioned in clusters of vertices forming sub-problems whose solutions use the dual variables obtained by a coordinator problem. The column generation process presents alternative ways to find upper and lower bounds for the quadratic problem. Computational experiments were performed using hard instances and the proposed method was compared against other methods presenting improved results for most of these instances.     

Linear multiplicative programming

An algorithm for solving a linear multiplicative programming problem (referred to as LMP) is proposed. LMP minimizes the product of two linear functions subject to general linear constraints. The product of two linear functions is a typical non-convex function, so that it can have multiple local minima. It is shown, however, that LMP can be solved efficiently by the combination of the parametric simplex method and any standard convex minimization procedure. The computational results indicate that the amount of computation is not much different from that of solving linear programs of the same size. In addition, the method proposed for LMP can be extended to a convex multiplicative programming problem (CMP), which minimizes the product of two convex functions under convex constraints.     

Perturbing the Dual Feasible Region for Solving Convex Quadratic Programs

A dual l _p-norm perturbation approach is introduced for solving convex quadratic programming problems. The feasible region of the Lagrangian dual program is approximated by a proper subset that is defined by a single smooth convex constraint involving the l _p-norm of a vector measure of constraint violation. It is shown that the perturbed dual program becomes the dual program as p and, under some standard conditions, the optimal solution of the perturbed dual program converges to a dual optimal solution. A closed-form formula that converts an optimal solution of the perturbed dual program into a feasible solution of the primal convex quadratic program is also provided. Such primal feasible solutions converge to an optimal primal solution as p. The proposed approach generalizes the previously proposed primal perturbation approach with an entropic barrier function. Its theory specializes easily for linear programming.     

Lagrangian duality and saddle points for sparse linear programming

The sparse linear programming(SLP) is a linear programming problem equipped with a sparsity constraint, which is nonconvex, discontinuous and generally NP-hard due to the combinatorial property involved.In this paper, by rewriting the sparsity constraint into a disjunctive form, we present an explicit formula of the Lagrangian dual problem for the SLP, in terms of an unconstrained piecewise-linear convex programming problem which admits a strong duality under bi-dual sparsity consistency. Furthermore, we show a saddle point theorem based on the strong duality and analyze two classes of stationary points for the saddle point problem. At last,we extend these results to SLP with the lower bound zero replaced by a certain negative constant.     

An Exterior Newton Method for Strictly Convex Quadratic Programming

We propose an exterior Newton method for strictly convex quadratic programming (QP) problems. This method is based on a dual formulation: a sequence of points is generated which monotonically decreases the dual objective function. We show that the generated sequence converges globally and quadratically to the solution (if the QP is feasible and certain nondegeneracy assumptions are satisfied). Measures for detecting infeasibility are provided. The major computation in each iteration is to solve a KKT-like system. Therefore, given an effective symmetric sparse linear solver, the proposed method is suitable for large sparse problems. Preliminary numerical results are reported.     

A generalized Lagrangian function and multiplier method

As is well known, a saddle point for the Lagrangian function, if it exists, provides a solution to a convex programming problem; then, the values of the optimal primal and dual objective functions are equal. However, these results are not valid for nonconvex problems.In this paper, several results are presented on the theory of the generalized Lagrangian function, extended from the classical Lagrangian and the generalized duality program. Theoretical results for convex problems also hold for nonconvex problems by extension of the Lagrangian function. The concept of supporting hypersurfaces is useful to add a geometric interpretation to computational algorithms. This provides a basis to develop a new algorithm.     

求解随机凸规划概率约束问题的对偶算法

1引言随机规划中的概率约束问题在工程和管理中有广泛的应用.因为问题中包含非线性的概率约束,它们的求解非常困难.如果目标函数是线性的,问题的求解就比较容易.给出了一个求解随机线性规划概率约束问题的综述.原-对偶算法和切平面算法是比较有效的.在本文中,我们讨论随机凸规划概率约束问题: