An outcome space algorithm for optimization over the weakly efficient set of a multiple objective nonlinear programming problem

This article presents for the first time an algorithm specifically designed for globally minimizing a finite, convex function over the weakly efficient set of a multiple objective nonlinear programming problem (V1) that has both nonlinear objective functions and a convex, nonpolyhedral feasible region. The algorithm uses a branch and bound search in the outcome space of problem (V1), rather than in the decision space of the problem, to find a global optimal solution. Since the dimension of the outcome space is usually much smaller than the dimension of the decision space, often by one or more orders of magnitude, this approach can be expected to considerably shorten the search. In addition, the algorithm can be easily modified to obtain an approximate global optimal weakly efficient solution after a finite number of iterations. Furthermore, all of the subproblems that the algorithm must solve can be easily solved, since they are all convex programming problems. The key, and sometimes quite interesting, convergence properties of the algorithm are proven, and an example problem is solved.     

Iterative linear programming solution of convex programs

An iterative linear programming algorithm for the solution of the convex programming problem is proposed. The algorithm partially solves a sequence of linear programming subproblems whose solution is shown to converge quadratically, superlinearly, or linearly to the solution of the convex program, depending on the accuracy to which the subproblems are solved. The given algorithm is related to inexact Newton methods for the nonlinear complementarity problem. Preliminary results for an implementation of the algorithm are given.This material is based on research supported by the National Science Foundation, Grants DCR-8521228 and CCR-8723091, and by the Air Force Office of Scientific Research, Grant AFOSR-86-0172. The author would like to thank Professor O. L. Mangasarian for stimulating discussions during the preparation of this paper.     

Extensions of Dinkelbach's algorithm for solving non-linear fractional programming problems

Dinkelbach's algorithm was developed to solve convex fractinal programming. This method achieves the optimal solution of the optimisation problem by means of solving a sequence of non-linear convex programming subproblems defined by a parameter. In this paper it is shown that Dinkelbach's algorithm can be used to solve general fractional programming. The applicability of the algorithm will depend on the possibility of solving the subproblems. Dinkelbach's extended algorithm is a framework to describe several algorithms which have been proposed to solve linear fractional programming, integer linear fractional programming, convex fractional programming and to generate new algorithms. The applicability of new cases as nondifferentiable fractional programming and quadratic fractional programming has been studied. We have proposed two modifications to improve the speed-up of Dinkelbachs algorithm. One is to use interpolation formulae to update the parameter which defined the subproblem and another truncates the solution of the suproblem. We give sufficient conditions for the convergence of these modifications. Computational experiments in linear fractional programming, integer linear fractional programming and non-linear fractional programming to evaluate the efficiency of these methods have been carried out.     

Solving generalized convex multiobjective programming problems by a normal direction method

We use normal directions of the outcome set to develop a method of outer approximation for solving generalized convex multiobjective programming problems. We prove the convergence of the method and report some computational experiments. As an application, we obtain an algorithm to solve an associated multiplicative problem over a convex constraint set.     

Column enumeration based decomposition techniques for a class of non-convex MINLP problems

We propose a decomposition algorithm for a special class of nonconvex mixed integer nonlinear programming problems which have an assignment constraint. If the assignment decisions are decoupled from the remaining constraints of the optimization problem, we propose to use a column enumeration approach. The master problem is a partitioning problem whose objective function coefficients are computed via subproblems. These problems can be linear, mixed integer linear, (non-)convex nonlinear, or mixed integer nonlinear. However, the important property of the subproblems is that we can compute their exact global optimum quickly. The proposed technique will be illustrated solving a cutting problem with optimum nonlinear programming subproblems.     

The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming

A new deterministic algorithm for solving convex mixed-integer nonlinear programming (MINLP) problems is presented in this paper: The extended supporting hyperplane (ESH) algorithm uses supporting hyperplanes to generate a tight overestimated polyhedral set of the feasible set defined by linear and nonlinear constraints. A sequence of linear or quadratic integer-relaxed subproblems are first solved to rapidly generate a tight linear relaxation of the original MINLP problem. After an initial overestimated set has been obtained the algorithm solves a sequence of mixed-integer linear programming or mixed-integer quadratic programming subproblems and refines the overestimated set by generating more supporting hyperplanes in each iteration. Compared to the extended cutting plane algorithm ESH generates a tighter overestimated set and unlike outer approximation the generation point for the supporting hyperplanes is found by a simple line search procedure. In this paper it is proven that the ESH algorithm converges to a global optimum for convex MINLP problems. The ESH algorithm is implemented as the supporting hyperplane optimization toolkit (SHOT) solver, and an extensive numerical comparison of its performance against other state-of-the-art MINLP solvers is presented.     

A trust region algorithm for solving bilevel programming problems

In this paper, we present a new trust region algorithm for a nonlinear bilevel programming problem by solving a series of its linear or quadratic approximation subproblems. For the nonlinear bilevel programming problem in which the lower level programming problem is a strongly convex programming problem with linear constraints, we show that each accumulation point of the iterative sequence produced by this algorithm is a stationary point of the bilevel programming problem.     

Parallel bundle-based decomposition for large-scale structured mathematical programming problems

In this paper, we present parallel bundle-based decomposition algorithms to solve a class of structured large-scale convex optimization problems. An example in this class of problems is the block-angular linear programming problem. By dualizing, we transform the original problem to an unconstrained nonsmooth concave optimization problem which is in turn solved by using a modified bundle method. Further, this dual problem consists of a collection of smaller independent subproblems which give rise to the parallel algorithms. We discuss the implementation on the CRYSTAL multi-computer. Finally, we present computational experience with block-angular linear programming problems and observe that more than 70% efficiency can be obtained using up to eleven processors for one group of test problems, and more than 60% efficiency can be obtained for relatively smaller problems using up to five processors for another group of problems.     

基于D.C.分解的一类箱型约束的非凸二次规划的新型分支定界算法

提出了一类求解带有箱约束的非凸二次规划的新型分支定界算法.首先,把原问题目标函数进行D.C.分解(分解为两个凸函数之差),利用次梯度方法,求出其线性下界逼近函数的一个最优值,也即原问题的一个下界.然后,利用全局椭球算法获得原问题的一个上界,并根据分支定界方法把原问题的求解转化为一系列子问题的求解.最后,理论上证明了算法的收敛性,数值算例表明算法是有效可行的.     

An efficient solution method for Weber problems with barriers based on genetic algorithms

In this paper we consider the problem of locating one new facility with respect to a given set of existing facilities in the plane and in the presence of convex polyhedral barriers. It is assumed that a barrier is a region where neither facility location nor travelling are permitted. The resulting non-convex optimization problem can be reduced to a finite series of convex subproblems, which can be solved by the Weiszfeld algorithm in case of the Weber objective function and Euclidean distances. A solution method is presented that, by iteratively executing a genetic algorithm for the selection of subproblems, quickly finds a solution of the global problem. Visibility arguments are used to reduce the number of subproblems that need to be considered, and numerical examples are presented.     

Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming

Decomposition has proved to be one of the more effective tools for the solution of large-scale problems, especially those arising in stochastic programming. A decomposition method with wide applicability is Benders' decomposition, which has been applied to both stochastic programming as well as integer programming problems. However, this method of decomposition relies on convexity of the value function of linear programming subproblems. This paper is devoted to a class of problems in which the second-stage subproblem(s) may impose integer restrictions on some variables. The value function of such integer subproblem(s) is not convex, and new approaches must be designed. In this paper, we discuss alternative decomposition methods in which the second-stage integer subproblems are solved using branch-and-cut methods. One of the main advantages of our decomposition scheme is that Stochastic Mixed-Integer Programming (SMIP) problems can be solved by dividing a large problem into smaller MIP subproblems that can be solved in parallel. This paper lays the foundation for such decomposition methods for two-stage stochastic mixed-integer programs.     

SEQUENTIAL CONVEX PROGRAMMING METHODS FOR SOLVING LARGE TOPOLOGY OPTIMIZATION PROBLEMS： IMPLEMENTATION AND COMPUTATIONAL RESULTS

In this paper, we describe a method to solve large-scale structural optimization problems by sequential convex programming （SCP）. A predictor-corrector interior point method is applied to solve the strictly convex subproblems. The SCP algorithm and the topology optimization approach are introduced. Especially, different strategies to solve certain linear systems of equations are analyzed. Numerical results are presented to show the efficiency of the proposed method for solving topology optimization problems and to compare different variants.     

A distributed Douglas-Rachford splitting method for multi-block convex minimization problems

A customized Douglas-Rachford splitting method (DRSM) was recently proposed to solve two-block separable convex optimization problems with linear constraints and simple abstract constraints. The algorithm has advantage over the well-known alternating direction method of multipliers (ADMM), the dual application of DRSM to the two-block convex minimization problem, in the sense that the subproblems can have larger opportunity of possessing closed-form solutions since they are unconstrained. In this paper, we further study along this way by considering the primal application of DRSM for the general case m≥3, i.e., we consider the multi-block separable convex minimization problem with linear constraints where the objective function is separable into m individual convex functions without coupled variables. The resulting method fully exploits the separable structure and enjoys decoupled subproblems which can be solved simultaneously. Both the exact and inexact versions of the new method are presented in a unified framework. Under mild conditions, we manage to prove the global convergence of the algorithm. Preliminary numerical experiments for extracting the background from corrupted surveillance video verify the encouraging efficiency of the new algorithm.     

Branch-and-Bound Outer Approximation Algorithm for Sum-of-Ratios Fractional Programs

In this article, a branch and-bound outer approximation algorithm is presented for globally solving a sum-of-ratios fractional programming problem. To solve this problem, the algorithm instead solves an equivalent problem that involves minimizing an indefinite quadratic function over a nonempty, compact convex set. This problem is globally solved by a branch-and-bound outer approximation approach that can create several closed-form linear inequality cuts per iteration. In contrast to pure outer approximation techniques, the algorithm does not require computing the new vertices that are created as these cuts are added. Computationally, the main work of the algorithm involves solving a sequence of convex programming problems whose feasible regions are identical to one another except for certain linear constraints. As a result, to solve these problems, an optimal solution to one problem can potentially be used to good effect as a starting solution for the next problem.     

一类带反凸约束的非线性比式和问题的全局优化算法

本文针对一类带有反凸约束的非线性比式和分式规划问题,提出一种求其全局最优解的单纯形分支和对偶定界算法.该算法利用Lagrange对偶理论将其中关键的定界问题转化为一系列易于求解的线性规划问题.收敛性分析和数值算例均表明提出的算法是可行的.     

Lower Bound Improvement and Forcing Rule for Quadratic Binary Programming

In this paper several equivalent formulations for the quadratic binary programming problem are presented. Based on these formulations we describe four different kinds of strategies for estimating lower bounds of the objective function, which can be integrated into a branch and bound algorithm for solving the quadratic binary programming problem. We also give a theoretical explanation for forcing rules used to branch the variables efficiently, and explore several properties related to obtained subproblems. From the viewpoint of the number of subproblems solved, new strategies for estimating lower bounds are better than those used before. A variant of a depth-first branch and bound algorithm is described and its numerical performance is presented.     

AnUV-algorithm for semi-infinite multiobjective programming

In this paper, we give an application ofUV-decomposition method of convex programming to multiobjective programming, and offer a new algorithm for solving semi-infinite multiobjective programming. Finally, the superlinear convergence of the algorithm is proved.     

Decomposition methods for a spatial model for long-term energy pricing problem

We consider an energy production network with zones of production and transfer links. Each zone representing an energy market (a country, part of a country or a set of countries) has to satisfy the local demand using its hydro and thermal units and possibly importing and exporting using links connecting the zones. Assuming that we have the appropriate tools to solve a single zonal problem (approximate dynamic programming, dual dynamic programming, etc.), the proposed algorithm allows us to coordinate the productions of all zones. We propose two reformulations of the dynamic model which lead to different decomposition strategies. Both algorithms are adaptations of known monotone operator splitting methods, namely the alternating direction method of multipliers and the proximal decomposition algorithm which have been proved to be useful to solve convex separable optimization problems. Both algorithms present similar performance in theory but our numerical experimentation on real-size dynamic models have shown that proximal decomposition is better suited to the coordination of the zonal subproblems, becoming a natural choice to solve the dynamic optimization of the European electricity market.     

A successive quadratic programming method for a class of constrained nonsmooth optimization problems

In this paper we present an algorithm for solving nonlinear programming problems where the objective function contains a possibly nonsmooth convex term. The algorithm successively solves direction finding subproblems which are quadratic programming problems constructed by exploiting the special feature of the objective function. An exact penalty function is used to determine a step-size, once a search direction thus obtained is judged to yield a sufficient reduction in the penalty function value. The penalty parameter is adjusted to a suitable value automatically. Under appropriate assumptions, the algorithm is shown to produce an approximate optimal solution to the problem with any desirable accuracy in a finite number of iterations.     

Equivalence of some quadratic programming algorithms

We formulate a general algorithm for the solution of a convex (but not strictly convex) quadratic programming problem. Conditions are given under which the iterates of the algorithm are uniquely determined. The quadratic programming algorithms of Fletcher, Gill and Murray, Best and Ritter, and van de Panne and Whinston/Dantzig are shown to be special cases and consequently are equivalent in the sense that they construct identical sequences of points. The various methods are shown to differ only in the manner in which they solve the linear equations expressing the Kuhn-Tucker system for the associated equality constrained subproblems. Equivalence results have been established by Goldfarb and Djang for the positive definite Hessian case. Our analysis extends these results to the positive semi-definite case. This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grant No. A8189.