An approach for solving nonlinear programming problems

In this paper we use measure theory to solve a wide range of the nonlinear programming problems. First, we transform a nonlinear programming problem to a classical optimal control problem with no restriction on states and controls. The new problem is modified into one consisting of the minimization of a special linear functional over a set of Radon measures; then we obtain an optimal measure corresponding to functional problem which is then approximated by a finite combination of atomic measures and the problem converted approximately to a finite-dimensional linear programming. Then by the solution of the linear programming problem we obtain the approximate optimal control and then, by the solution of the latter problem we obtain an approximate solution for the original problem. Furthermore, we obtain the path from the initial point to the admissible solution.     

Interior-point methods: An old and new approach to nonlinear programming

In this paper we discuss the main concepts of structural optimization, a field of nonlinear programming, which was formed by the intensive development of modern interior-point schemes.     

A differential equation approach to nonlinear programming

A new method is presented for finding a local optimum of the equality constrained nonlinear programming problem. A nonlinear autonomous system is introduced as the base of the theory instead of usual approaches. The relation between critical points and local optima of the original optimization problem is proved. Asymptotic stability of the critical points is also proved. A numerical algorithm which is capable of finding local optima systematically at the quadratic rate of convergence is developed from a detailed analysis of the nature of trajectories and critical points. Some numerical results are given to show the efficiency of the method.     

A novel approach to Bilevel nonlinear programming

Recently developed methods of monotonic optimization have been applied successfully for studying a wide class of nonconvex optimization problems, that includes, among others, generalized polynomial programming, generalized multiplicative and fractional programming, discrete programming, optimization over the efficient set, complementarity problems. In the present paper the monotonic approach is extended to the General Bilevel Programming GBP Problem. It is shown that (GBP) can be transformed into a monotonic optimization problem which can then be solved by “polyblock” approximation or, more efficiently, by a branch-reduce-and-bound method using monotonicity cuts. The method is particularly suitable for Bilevel Convex Programming and Bilevel Linear Programming.      

A relaxed interior approach to nonlinear programming

Summary This paper contains the mathematical validation of a new approach to mathematical programming problems based on a penalty function method. The given problem is replaced by a second auxiliary problem which, in many cases may be solved by standard methods since it involves the maximization of a concave function of a single variable over an interval. The auxiliary problem is defined implicitly in therms of the constituents of the original problem. Examples are presented in order to illustrate the theoretical results.     

An exact penalty function approach for nonlinear integer programming problems

Nonlinear integer programming problems with bounded feasible sets are considered. It is shown how the number of constraints in such problems can be reduced with the aid of an exact penalty function approach. This approach can be used to construct an equivalent unconstrained problem, or a problem with a constraint set which makes it easier to solve. The application of this approach to various nonlinear integer programming problems is discussed.     

An interactive dynamic programming approach to multicriteria discrete programming

Several interactive schemes for solving multicriteria discrete programming problems are developed under a dynamic programming framework. It is assumed that the decision maker's preference structure satisfies the conditions of transitivity, monotonicity, and nonsatiation. Hybrid procedures are also structured by including branch and bound ideas into the recursions. Initial computational results are offered.     

An integer programming approach to b-coloring

In the b-coloring problem, we aim to assign colors from a set $C$ to the vertices of a graph $G$ in such a way that adjacent vertices do not receive the same color, and for every $c\in C$ we have a $c$-colored vertex $v$ in $G$ such that every color in $C\setminus \left\{c\right\}$ is assigned to at least one of $v$’s neighbors. It has been shown that b-coloring is NP-complete, so we propose in this article an approach for the problem under integer programming techniques. To this end, we give an integer programming formulation and study the associated polytope. We provide several families of valid inequalities, and analyze facetness conditions for them. Finally, we show computational evidence suggesting that the given inequalities may be useful in a branch-and-cut environment.     

A nonlinear programming approach to space shuttle trajectory optimization

Journal of Optimization Theory and Applications - Space shuttle trajectory design requires the optimization of highly-constrained, branched, atmospheric trajectories. This paper presents a general...     

An augmented Lagrangian approach with a variable transformation in nonlinear programming

Tangent cone and (regular) normal cone of a closed set under an invertible variable transformation around a given point are investigated, which lead to the concepts of θ⁻¹-tangent cone of a set and θ⁻¹-subderivative of a function. When the notion of θ⁻¹-subderivative is applied to perturbation functions, a class of augmented Lagrangians involving an invertible mapping of perturbation variables are obtained, in which dualizing parameterization and augmenting functions are not necessarily convex in perturbation variables. A necessary and sufficient condition for the exact penalty representation under the proposed augmented Lagrangian scheme is obtained. For an augmenting function with an Euclidean norm, a sufficient condition (resp., a sufficient and necessary condition) for an arbitrary vector (resp., 0) to support an exact penalty representation is given in terms of θ⁻¹-subderivatives. An example of the variable transformation applied to constrained optimization problems is given, which yields several exact penalization results in the literature.     

A sequential quadratic programming with a dual parametrization approach to nonlinear semi-infinite programming

In the sequel of the work reported in Liu et al. (1999), in which a method based on a dual parametrization is used to solve linear-quadratic semi-infinite programming (SIP) problems, a sequential quadratic programming technique is proposed to solve nonlinear SIP problems. A merit function to measure progress toward the solution and a procedure to compute the penalty parameter are also proposed.     

New approach to optimality conditions for degenerate nonlinear programming problems

In the work, a new approach to constructing optimality conditions for degenerate smooth optimization problems with inequality constraints is proposed. The approach is based on the theory of p-regularity. A special case of degeneracy, when the first derivatives of some function-constraints are equal to zero up to some order, is considered. Optimality conditions for the general case of degeneracy with p = 2 are presented. Proposed constructions and optimality conditions are illustrated by an example. A general case of degeneracy is considered and optimality conditions for the case of p ≥ 2 are proposed.     

Parametric nonlinear programming approach to fuzzy queues with bulk service

This paper proposes a procedure to construct the membership functions of the performance measures in bulk service queuing systems with the arrival rate and service rate are fuzzy numbers. The basic idea is to transform a fuzzy queue with bulk service to a family of conventional crisp queues with bulk service by applying the α-cut approach. On the basis of α-cut representation and the extension principle, a pair of parametric nonlinear programs is formulated to describe that family of crisp bulk service queues, via which the membership functions of the performance measures are derived. To demonstrate the validity of the proposed procedure, two fuzzy queues often encountered in transportation management are exemplified. Since the performance measures are expressed by membership functions rather than by crisp values, they completely conserve the fuzziness of input information when some data of bulk-service queuing systems are ambiguous. Thus the proposed approach for vague systems can represent the system more accurately, and more information is provided for designing queuing systems in real life. By extending to fuzzy environment, the bulk service queuing models would have wider applications.     

An alternative approach to nonlinear filtering

The structure of a nonlinear filter with observation process having continuous and discontinuous components is considered. The approach is based on the so-called “Bayes” formula for conditional expectations. “Fubini” type theorems for stochastic integrals are given and used to obtain the representations of an optimal estimate and of the conditional likelihood ratio. A linear unnormalized filtering equation for controlled system process is derived.     

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 efficient sequential quadratic programming algorithm for nonlinear programming

In this paper, a new feasible sequential quadratic programming (FSQP) algorithm is proposed to solve the nonlinear programming, where a feasible descent direction is obtained by solving only one QP subproblem. In order to avoid Maratos effect, a high-order revised direction is computed by solving a linear system with involving some “active” constraints. The theoretical analysis shows that global and superlinear convergence can be deduced.     

A dual approach to solving nonlinear programming problems by unconstrained optimization

Several recent algorithms for solving nonlinear programming problems with equality constraints have made use of an augmented penalty Lagrangian function, where terms involving squares of the constraint functions are added to the ordinary Lagrangian. In this paper, the corresponding penalty Lagrangian for problems with inequality constraints is described, and its relationship with the theory of duality is examined. In the convex case, the modified dual problem consists of maximizing a differentiable concave function (indirectly defined) subject to no constraints at all. It is shown that any maximizing sequence for the dual can be made to yield, in a general way, an asymptotically minimizing sequence for the primal which typically converges at least as rapidly.Supported in part by the Air Force Office of Scientific Research under grant AF-AFOSR-72-2269.     

An ellipsoid algorithm for nonlinear programming

We investigate an ellipsoid algorithm for nonlinear programming. After describing the basic steps of the algorithm, we discuss its computer implementation and present a method for measuring computational efficiency. The computational results obtained from experimenting with the algorithm are discussed and the algorithm's performance is compared with that of a widely used commercial code. This research was supported in part by The National Science Foundation, Grant No. MCS78-02096.