A nonlinear Lagrangian for constrained optimization problems

A novel nonlinear Lagrangian is presented for constrained optimization problems with both inequality and equality constraints, which is nonlinear with respect to both functions in problem and Lagrange multipliers. The nonlinear Lagrangian inherits the smoothness of the objective and constraint functions and has positive properties. The algorithm on the nonlinear Lagrangian is demonstrated to possess local and linear convergence when the penalty parameter is less than a threshold (the penalty parameter in the penalty method has to approximate zero) under a set of suitable conditions, and be super-linearly convergent when the penalty parameter is decreased following Lagrange multiplier update. Furthermore, the dual problem based on the nonlinear Lagrangian is discussed and some important properties are proposed, which fail to hold for the dual problem based on the classical Lagrangian. At last, the preliminary and comparing numerical results for several typical test problems by using the new nonlinear Lagrangian algorithm and the other two related nonlinear Lagrangian algorithms, are reported, which show that the given nonlinear Lagrangian is promising.     

A nonlinear augmented Lagrangian for constrained minimax problems

A novel smooth nonlinear augmented Lagrangian for solving minimax problems with inequality constraints, is proposed in this paper, which has the positive properties that the classical Lagrangian and the penalty function fail to possess. The corresponding algorithm mainly consists of minimizing the nonlinear augmented Lagrangian function and updating the Lagrange multipliers and controlling parameter. It is demonstrated that the algorithm converges Q-superlinearly when the controlling parameter is less than a threshold under the mild conditions. Furthermore, the condition number of the Hessian of the nonlinear augmented Lagrangian function is studied, which is very important for the efficiency of the algorithm. The theoretical results are validated further by the preliminary numerical experiments for several testing problems reported at last, which show that the nonlinear augmented Lagrangian is promising.     

A Lagrangian relaxation approach to large-scale flow interception problems

The paper presents a tight Lagrangian bound and an efficient dual heuristic for the flow interception problem. The proposed Lagrangian relaxation decomposes the problem into two subproblems that are easy to solve. Information from one of the subproblems is used within a dual heuristic to construct feasible solutions and is used to generate valid cuts that strengthen the relaxation. Both the heuristic and the relaxation are integrated into a cutting plane method where the Lagrangian bound is calculated using a subgradient algorithm. In the course of the algorithm, a valid cut is added and integrated efficiently in the second subproblem and is updated whenever the heuristic solution improves. The algorithm is tested on randomly generated test problems with up to 500 vertices, 12,483 paths, and 43 facilities. The algorithm finds a proven optimal solution in more than 75% of the cases, while the feasible solution is on average within 0.06% from the upper bound.     

Augmented Lagrangian functions for constrained optimization problems

In this paper, in order to obtain some existence results about solutions of the augmented Lagrangian problem for a constrained problem in which the objective function and constraint functions are noncoercive, we construct a new augmented Lagrangian function by using an auxiliary function. We establish a zero duality gap result and a sufficient condition of an exact penalization representation for the constrained problem without the coercive or level-bounded assumption on the objective function and constraint functions. By assuming that the sequence of multipliers is bounded, we obtain the existence of a global minimum and an asymptotically minimizing sequence for the constrained optimization problem.     

A heuristic approach to hard constrained shortest path problems

Constrained shortest path problems have many applications in areas like network routing, investments planning and project evaluation as well as in some classical combinatorial problems with high duality gaps where even obtaining feasible solutions is a difficult task in general.We present in this paper a systematic method for obtaining good feasible solutions to hard (doubly constrained) shortest path problems. The algorithm is based essentially on the concept of efficient solutions which can be obtained via parametric shortest path calculations. The computational results obtained show that the approach proposed here leads to optimal or very good near optimal solutions for all the problems studied.From a theoretical point of view, the most important contribution of the paper is the statement of a pseudopolynomial algorithm for generating the efficient solutions and, more generally, for solving the parametric shortest path problem.     

An intrinsic approach to manifold constrained variational problems

Motivated by some questions in continuum mechanics and analysis in metric spaces, we give an intrinsic characterization of sequentially weak lower semicontinuous functionals defined on Sobolev maps with values into manifolds without embedding the target into Euclidean spaces.     

A variational inequality approach to constrained control problems for parabolic equations

A distributed optimal control problem for parabolic systems with constraints in state is considered. The problem is transformed to control problem without constraints but for systems governed by parabolic variational inequalities. The new formulation presented enables the efficient use of a standard gradient method for numerically solving the problem in question. Comparison with a standard penalty method as well as numerical examples are given.     

A branch and bound network approach to the canonical constrained entropy problem

In this paper, we present a branch and bound algorithm for solving the constrained entropy mathematical programming problem. Unlike other methods for solving this problem, our method solves more general problems with inequality constraints. The advantage of the proposed technique is that the relaxed problem solved at each node is a singly constrained network problem. The disadvantage is that the relaxed problem has twice as many variables as the original problem. An application to regional planning is given, and an example problem is solved.     

Set covering-based surrogate approach for solving sup-{\mathcal{T}} equation constrained optimization problems

This work considers solving the sup-T{\mathcal{T}} equation constrained optimization problems from the integer programming viewpoint. A set covering-based surrogate approach is proposed to solve the sup-T{\mathcal{T}} equation constrained optimization problem with a separable and monotone objective function in each of the variables. This is our first trial of developing integer programming-based techniques to solve sup-T{\mathcal{T}} equation constrained optimization problems. Our computational results confirm the efficiency of the proposed method and show its potential for solving large scale sup-T{\mathcal{T}} equation constrained optimization problems.     

A neural network approach to facility layout problems

A near-optimum parallel algorithm for solving facility layout problems is presented in this paper where the problem is NP-complete. The facility layout problem is one of the most fundamental quadratic assignment problems in Operations Research. The goal of the problem is to locate N facilities on an N-square (location) array so as to minimize the total cost. The proposed system is composed of N × N neurons based on an artificial two-dimensional maximum neural network for an N-facility layout problem. Our algorithm has given improved solutions for several benchmark problems over the best existing algorithms.     

A robustness approach to uncapacitated network design problems

In this paper, we address uncapacitated network design problems characterised by uncertainty in the input data. Network design choices have a determinant impact on the effectiveness of the system. Design decisions are frequently made with a great degree of uncertainty about the conditions under which the system will be required to operate. Instead of finding optimal designs for a given future scenario, designers often search for network configurations that are “good” for a variety of likely future scenarios. This approach is referred to as the “robustness” approach to system design. We present a formal definition of “robustness” for the uncapacitated network design problem, and develop algorithms aimed at finding robust network designs. These algorithms are adaptations of the Benders decomposition methodology that are tailored so they can efficiently identify robust network designs. We tested the proposed algorithms on a set of randomly generated problems. Our computational experiments showed two important properties. First, robust solutions are abundant in uncapacitated network design problems, and second, the proposed algorithms performance is satisfactory in terms of cost and number of robust network designs obtained.     

An ODE-based approach to nonlinearly constrained minimax problems

We consider the following problem: Choosex ₁, ...,x _n to wherem ₁,m ₂,m ₃ are integers with 0m ₁m ₂m ₃, thef _i are given real numbers, and theg _i are given smooth functions. Constraints of the formg _i (x ₁, ...,x _n )=0 can also be handled without problem. Each iteration of our algorithm involves approximately solving a certain non-linear system of first-order ordinary differential equations to get a search direction for a line search and using a Newton-like approach to correct back into the feasible region when necessary. The algorithm and our Fortran implementation of it will be discussed along with some examples. Our experience to date has been that the program is more robust than any of the library routines we have tried, although it generally requires more computer time. We have found this program to be an extremely useful tool in diverse areas, including polymer rheology, computer vision, and computation of convexity-preserving rational splines.     

Regularized Lagrangian duality for linearly constrained quadratic optimization and trust-region problems

In this paper we first establish a Lagrange multiplier condition characterizing a regularized Lagrangian duality for quadratic minimization problems with finitely many linear equality and quadratic inequality constraints, where the linear constraints are not relaxed in the regularized Lagrangian dual. In particular, in the case of a quadratic optimization problem with a single quadratic inequality constraint such as the linearly constrained trust-region problems, we show that the Slater constraint qualification (SCQ) is necessary and sufficient for the regularized Lagrangian duality in the sense that the regularized duality holds for each quadratic objective function over the constraints if and only if (SCQ) holds. A new theorem of the alternative for systems involving both equality constraints and two quadratic inequality constraints plays a key role. We also provide classes of quadratic programs, including a class of CDT-subproblems with linear equality constraints, where (SCQ) ensures regularized Lagrangian duality.     

Solving singularly constrained generalized network problems

The singularly constrained generalized network problem represents a large class of capacitated linear programming (LP) problems. This class includes any LP problem whose coefficient matrix, ignoring single upper bound constraints, containsm + 1 rows which may be ordered such that each column has at most two non-zero entries in the firstm rows. The paper describes efficient procedures for solving such problems and presents computational results which indicate that, on large problems, these procedures are at least twenty-five times more efficient than the state of the art LP systemapex-iii.This research was partly supported by ONR Contract N00014-76-C-0383 with Decision Analysis and Research Institute and by Project NR047-021, ONR Contracts N00014-75-C-0616 and N00014-75-C-0569 with the Center for Cybernetic Studies, The University of Texas. Reproduction in whole or in part is permitted for any purpose of the United States Government.     

A decomposition-dualization approach for solving constrained convex minimization problems with applications to discretized obstacle problems

Summary In this paper, we shall be concerned with the solution of constrained convex minimization problems. The constrained convex minimization problems are proposed to be transformable into a convex-additively decomposed and almost separable form, e.g. by decomposition of the objective functional and the restrictions. Unconstrained dual problems are generated by using Fenchel-Rockafellar duality. This decomposition-dualization concept has the advantage that the conjugate functionals occuring in the derived dual problem are easily computable. Moreover, the minimum point of the primal constrained convex minimization problem can be obtained from any maximum point of the corresponding dual unconstrained concave problem via explicit return-formulas. In quadratic programming the decomposition-dualization approach considered here becomes applicable if the quadratic part of the objective functional is generated byH-matrices. Numerical tests for solving obstacle problems in ¹ discretized by using piecewise quadratic finite elements and in ² by using the five-point difference approximation are presented.     

A multi-parametric programming approach for constrained dynamic programming problems

In this work, we present a new algorithm for solving complex multi-stage optimization problems involving hard constraints and uncertainties, based on dynamic and multi-parametric programming techniques. Each echelon of the dynamic programming procedure, typically employed in the context of multi-stage optimization models, is interpreted as a multi-parametric optimization problem, with the present states and future decision variables being the parameters, while the present decisions the corresponding optimization variables. This reformulation significantly reduces the dimension of the original problem, essentially to a set of lower dimensional multi-parametric programs, which are sequentially solved. Furthermore, the use of sensitivity analysis circumvents non-convexities that naturally arise in constrained dynamic programming problems. The potential application of the proposed novel framework to robust constrained optimal control is highlighted.     

A hybrid neural network approach to bilevel programming problems

A combined neural network and tabu search hybrid algorithm is proposed for solving the bilevel programming problem. To illustrate the approach, two numerical examples are solved and the results are compared with those in the literature.     

Bayesian approach to global optimization and application to multiobjective and constrained problems

In this paper, the Bayesian methods of global optimization are considered. They provide the minimal expected deviation from the global minimum. It is shown that, using the Bayesian methods, the asymptotic density of calculations of the objective function is much greater around the point of global minimum. The relation of this density to the parameters of the method and to the function is defined.Algorithms are described which apply the Bayesian methods to problems with linear and nonlinear constraints. The Bayesian approach to global multiobjective optimization is defined. Interactive procedures and reduction of multidimensional data in the case of global optimization are discussed.