Duality-based regularization in a linear convex mathematical programming problem

For a linear convex mathematical programming (MP) problem with equality and inequality constraints in a Hilbert space, a dual-type algorithm is constructed that is stable with respect to input data errors. In the algorithm, the dual of the original optimization problem is solved directly on the basis of Tikhonov regularization. It is shown that the necessary optimality conditions in the original MP problem are derived in a natural manner by using dual regularization in conjunction with the constructive generation of a minimizing sequence. An iterative regularization of the dual algorithm is considered. A stopping rule for the iteration process is presented in the case of a finite fixed error in the input data.     

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.     

A modified reduced gradient method for dual posynomial programming

In this paper, we present a method for solving the dual of a posynomial geometric program based on modifications of the reduced gradient method. The modifications are necessary because of the numerical difficulties associated with the nondifferentiability of the dual objective function. Some preliminary numerical results are included that compare the proposed method with the modified concave simplex method of Beck and Ecker of Ref. 1.This research was supported in part by the National Science Foundation, Grant No. MCS75-09443-A01.The authors sincerely thank P. Vandeputte for his computing assistance. We also wish to thank T. Magnanti and unknown referees for helpful criticism.     

A stable approach to Newton's method for general mathematical programming problems inR n

The usual approach to Newton's method for mathematical programming problems with equality constraints leads to the solution of linear systems ofn +m equations inn +m unknowns, wheren is the dimension of the space andm is the number of constraints. Moreover, these linear systems are never positive definite. It is our feeling that this approach is somewhat artificial, since in the unconstrained case the linear systems are very often positive definite. With this in mind, we present an alternate Newton-like approach for the constrained problem in which all the linear systems are of order less than or equal ton. Furthermore, when the Hessian of the Lagrangian at the solution is positive definite (a situation frequently occurring), all our systems will be positive definite. Hence, in all cases, our Newton-like method offers greater numerical stability. We demonstrate that the convergence properties of this Newton-like method are superior to those of the standard approach to Newton's method. The operation count for the new method using Gaussian elimination is of the same order as the operation count for the standard method. However, if the Hessian of the Lagrangian at the solution is positive definite and we use Cholesky decomposition, then the order of the operation count for the new method is half that for the standard approach to Newton's method. This theory is generalized to problems with both equality and inequality constraints.     

On various duality theorems in nonlinear programming

Recently, Gulati and Craven and Mond and Egudo established strict converse duality theorems for some of Mond-Weir duals for nonlinear programming problems. Here, we establish various duality theorems under weaker convexity conditions that are different from those of Gulati and Craven, Mond and Weir, and Mond and Egudo.The first author is thankful to the Natural Science and Engineering Research Council of Canada for financial support through Grant A-5319.     

Mixed symmetric duality in non-differentiable multiobjective mathematical programming

Two mixed symmetric dual models for a class of non-differentiable multiobjective nonlinear programming problems with multiple arguments are introduced in this paper. These two mixed symmetric dual models unify the four existing multiobjective symmetric dual models in the literature. Weak and strong duality theorems are established for these models under some mild assumptions of generalized convexity. Several special cases are also obtained.     

An interactive method for multiple-objective mathematical programming problems

An interactive method is developed for solving the general nonlinear multiple objective mathematical programming problems. The method asks the decision maker to provide partial information (local tradeoff ratios) about his utility (preference) function at each iteration. Using the information, the method generates an efficient solution and presents it to the decision maker. In so doing, the best compromise solution is sought in a finite number of iterations. This method differs from the existing feasible direction methods in that (i) it allows the decision maker to consider only efficient solutions throughout, (ii) the requirement of line search is optional, and (iii) it solves the problems with linear objective functions and linear utility function in one iteration. Using various problems selected from the literature, five line search variations of the method are tested and compared to one another. The nonexisting decision maker is simulated using three different recognition levels, and their impact on the method is also investigated.     

Computing exact solution to nonlinear integer programming: Convergent Lagrangian and objective level cut method

In this paper, we propose a convergent Lagrangian and objective level cut method for computing exact solution to two classes of nonlinear integer programming problems: separable nonlinear integer programming and polynomial zero-one programming. The method exposes an optimal solution to the convex hull of a revised perturbation function by successively reshaping or re-confining the perturbation function. The objective level cut is used to eliminate the duality gap and thus to guarantee the convergence of the Lagrangian method on a revised domain. Computational results are reported for a variety of nonlinear integer programming problems and demonstrate that the proposed method is promising in solving medium-size nonlinear integer programming problems.     

Test examples for nonlinear programming codes

The increasing importance of nonlinear programming software requires an enlarged set of test examples. The purpose of this note is to point out how an interested mathematical programmer could obtain computer programs of more than 120 constrained nonlinear programming problems which have been used in the past to test and compare optimization codes.     

正定二次规划的一个对偶算法

给出了一个正定二次规划的对偶算法．算法把原问题分解为一系列子问题,在保持原问题的Wolfe对偶可行的前提下,通过迭代计算,由这一系列子问题的最优解向原问题的最优解逼近．同时给出了算法的有限收敛性．     

A gradient projection-multiplier method for nonlinear programming

This paper describes a gradient projection-multiplier method for solving the general nonlinear programming problem. The algorithm poses a sequence of unconstrained optimization problems which are solved using a new projection-like formula to define the search directions. The unconstrained minimization of the augmented objective function determines points where the gradient of the Lagrangian function is zero. Points satisfying the constraints are located by applying an unconstrained algorithm to a penalty function. New estimates of the Lagrange multipliers and basis constraints are made at points satisfying either a Lagrangian condition or a constraint satisfaction condition. The penalty weight is increased only to prevent cycling. The numerical effectiveness of the algorithm is demonstrated on a set of test problems.The author gratefully acknowledges the helpful suggestions of W. H. Ailor, J. L. Searcy, and D. A. Schermerhorn during the preparation of this paper. The author would also like to thank D. M. Himmelblau for supplying a number of interesting test problems.     

Average shadow prices in mathematical programming

We develop the concept of average shadow price in mathematical programming. This concept measures the value of resources along a direction in an average sense, in contrast to traditional marginal analysis; it serves as a useful standard price for management decisions about resources, particularly when there are nonconvexities. We give it an economic interpretation. We also develop simple computational schemes for obtaining and improving the bounds of the average shadow prices and illustrate them in two important classes of nonconvex programs: convex maximization problems and mixed integer programs.     

A second-order method for the general nonlinear programming problem

This paper presents a multiplier-type method for nonlinear programming problems with both equality and inequality constraints. Slack variables are used for the inequalities. The penalty coefficient is adjusted automatically, and the method converges quadratically to points satisfying second-order conditions.The work of the first author was supported by NSF RANN and JSEP Contract No. F44620-71-C-0087; the work of the second author was supported by the National Science Foundation Grant No. ENG73-08214A01 and US Army Research Office Durham Contract No. DAHC04-73-C-0025.     

A spline smoothing homotopy method for nonconvex nonlinear programming

Homotopy methods are globally convergent under weak conditions and robust; however, the efficiency of a homotopy method is closely related with the construction of the homotopy map and the path tracing algorithm. Different homotopies may behave very different in performance even though they are all theoretically convergent. In this paper, a spline smoothing homotopy method for nonconvex nonlinear programming is developed using cubic spline to smooth the max function of the constraints of nonlinear programming. Some properties of spline smoothing function are discussed and the global convergence of spline smoothing homotopy under the weak normal cone condition is proven. The spline smoothing technique uses a smooth constraint instead of m constraints and acts also as an active set technique. So the spline smoothing homotopy method is more efficient than previous homotopy methods like combined homotopy interior point method, aggregate constraint homotopy method and other probability one homotopy methods. Numerical tests with the comparisons to some other methods show that the new method is very efficient for nonlinear programming with large number of complicated constraints.     

A filter method for nonlinear semidefinite programming with global convergence

In this study, a new filter algorithm is presented for solving the nonlinear semidefinite programming. This algorithm is inspired by the classical sequential quadratic programming method. Unlike the traditional filter methods, the sufficient descent is ensured by changing the step size instead of the trust region radius. Under some suitable conditions, the global convergence is obtained. In the end, some numerical experiments are given to show that the algorithm is effective.     

一类二层凸规划的分解法

研究了一类二层凸规划和与之相应的凸规划问题的等价性．并讨论了这类凸规划的对偶性和鞍点问题,最后给出了求解这类二层凸规划的一个分解法．     

Yet another geometric programming dual algorithm

We describe an algorithm for the geometric programming dual problem which uses an adaptation of the generalized LP algorithm, proposed by Dantzig et al. twenty-five years ago for the chemical equilibrium problem, and show the slack primal constraints pose no numerical difficulties for this algorithm as they do for previous dual-based algorithms.     

Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming

This paper presents a “standard form” variant of Karmarkar's algorithm for linear programming. The tecniques of using duality and cutting objective are combined in this variant to maintain polynomial-time complexity and to bypass the difficulties found in Karmarkar's original algorithm. The variant works with problems in standard form and simultaneously generates sequences of primal and dual feasible solutions whose objective function values converge to the unknown optimal value. Some computational results are also reported.     

A nonlinear Lagrangian dual for integer programming

Nonlinear Lagrangian theory offers a success guarantee for the dual search via construction of a nonlinear support of the perturbation function at the optimal point. In this paper, a new nonlinear dual formulation of an exponential form is proposed for bounded integer programming. This new formulation possesses an asymptotic strong duality property and guarantees a success in identifying a primal optimum solution. No actual dual search is needed in the solution process when the parameter of the nonlinear Lagrangian formulation is set to be large enough.