A fuzzy multiobjective programming algorithm in decision support systems

Multicriteria analysis is one of the analytical functions in the problem processing system of decision support systems (DSS). In this paper, an interactive and iterative fuzzy programming method for solving a quasi-optimization problem in complex decisions under constraints involving a multiple objective function is proposed. Comparing with an adapted gradient search method, a surrogate worth tradeoff method, and a Zionts—Wallenius method, an approximate preference structure is emphasized in the proposed method.     

Interior-point methods for convex programming

This work is concerned with generalized convex programming problems, where the objective function and also the constraints belong to a certain class of convex functions. It examines the relationship of two basic conditions used in interior-point methods for generalized convex programming—self-concordance and a relative Lipschitz condition—and gives a short and simple complexity analysis of an interior-point method for generalized convex programming. In generalizing ellipsoidal approximations for the feasible set, it also allows a geometrical interpretation of the analysis.This work was supported by a research grant from the Deutsche Forschungsgemeinschaft, and in part by the U.S. National Science Foundation Grant DDM-8715153 and the Office of Naval Research Grant N00014-90-J-1242.On leave from the Institut für Angewandte Mathematik, University of Würzburg, Am Hubland, W-8700 Würzburg, Federal Republic of Germany.     

Deletion-by-infeasibility rule for DC-constrained global optimization

In Ref. 1, a general class of branch-and-bound methods was proposed by Horst for solving global optimization problems. One of the main contributions of Ref. 1 was the opportunity of handling partition elements whose feasibility is not known. Deletion-by-infeasibility rules were presented for problems where the feasible set is convex, is defined by finitely many convex and reverse convex constraints, or is defined by Lipschitzian inequalities. In this note, we propose a new deletion-by-infeasibility rule for problems whose feasible set is defined by functions representable as differences of convex functions.This research was supported in part by the Hungarian National Research Foundation, Grant OTKA No. 2568.     

A Sequential Quadratically Constrained Quadratic Programming Method of Feasible Directions

In this paper, a sequential quadratically constrained quadratic programming method of feasible directions is proposed for the optimization problems with nonlinear inequality constraints. At each iteration of the proposed algorithm, a feasible direction of descent is obtained by solving only one subproblem which consist of a convex quadratic objective function and simple quadratic inequality constraints without the second derivatives of the functions of the discussed problems, and such a subproblem can be formulated as a second-order cone programming which can be solved by interior point methods. To overcome the Maratos effect, an efficient higher-order correction direction is obtained by only one explicit computation formula. The algorithm is proved to be globally convergent and superlinearly convergent under some mild conditions without the strict complementarity. Finally, some preliminary numerical results are reported. Project supported by the National Natural Science Foundation (No. 10261001), Guangxi Science Foundation (Nos. 0236001, 064001), and Guangxi University Key Program for Science and Technology Research (No. 2005ZD02) of China.     

Solving multiple criteria problems by interactive decomposition

An interactive decomposition method is developed for solving the multiple criteria (MC) problem. Based on nonlinear programming duality theory, the MC problem is decomposed into a series of subproblems and relaxed master problems. Each subproblem is a bicriterion problem, and each relaxed master problem is a standard linear program. The prime objective of the decomposition is to simplify and facilitate the process of making preference assessments and tradeoffs across many conflicting objectives. Therefore, the decision-maker's preference function is not assumed to be known explicitly; rather, the decision maker is required to make only limited local preference assessments in the context of feasible and nondominated alternatives. Also, the preference assessments are of the form of ordinal paired comparisons, and in most of them only two criteria are allowed to change their values simultaneously, while the remaining (l–2) criteria are held fixed at certain levels.     

Variable Programming: A Generalized Minimax Problem. Part II: Algorithms

In this part of the two-part series of papers, algorithms for solving some variable programming (VP) problems proposed in Part I are investigated. It is demonstrated that the non-differentiability and the discontinuity of the maximum objective function, as well as the summation objective function in the VP problems constitute difficulty in finding their solutions. Based on the principle of statistical mechanics, we derive smooth functions to approximate these non-smooth objective functions with specific activated feasible sets. By transforming the minimax problem and the corresponding variable programming problems into their smooth versions we can solve the resulting problems by some efficient algorithms for smooth functions. Relevant theoretical underpinnings about the smoothing techniques are established. The algorithms, in which the minimization of the smooth functions is carried out by the standard quasi-Newton method with BFGS formula, are tested on some standard minimax and variable programming problems. The numerical results show that the smoothing techniques yield accurate optimal solutions and that the algorithms proposed are feasible and efficient.This work was supported by the RGC grant CUHK 152/96H of the Hong Kong Research Grant Council.     

Solving combinatorial optimization problems using Karmarkar's algorithm

We describe a cutting plane algorithm for solving combinatorial optimization problems. The primal projective standard-form variant of Karmarkar's algorithm for linear programming is applied to the duals of a sequence of linear programming relaxations of the combinatorial optimization problem.Computational facilities provided by the Cornell Computational Optimization Project supported by NSF Grant DMS-8706133 and by the Cornell National Supercomputer Facility. The Cornell National Supercomputer Facility is a resource of the Center for Theory and Simulation in Science and Engineering at Cornell Unversity, which is funded in part by the National Science Foundation, New York State, and the IBM Corporation. The research of both authors was partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.Research partially supported by ONR Grant N00014-90-J-1714.Research partially supported by NSF Grant ECS-8602534 and by ONR Contract N00014-87-K-0212.     

Application of sequential quadratic programming software program to an actual problem

We produced a nonlinear optimization software program which is based on a Sequential Quadratic Programming (SQP) method (Schittkowski, 1981a). Our program has several original characteristics: (1) automatic choice between two QP solvers, the Goldfarb—Idnani (GI) method (Goldfarb and Idnani, 1983) and the Least Squares (LS) method (Schittkowski, 1981b); (2) an augmented Lagrange function (Schittkowski, 1981a) as the objective function for line search; (3) adaptive Armijo method for line search; (4) direct definition of upper and lower bounds for variables and constraint functions; and (5) accurate numerical differentials. These characteristics ensure the reliability of our program for solving standard problems. In this paper, point (3) is described in detail. Then, the program is applied to an actual problem, the optimal placement of blocks. A model for this problem has been suggested by Sha and Dutton (1984), but it was unsuited to treatment by the SQP method. Thus we modify it to ensure program applicability.     

Polynomiality of infeasible-interior-point algorithms for linear programming

Kojima, Megiddo, and Mizuno investigate an infeasible-interior-point algorithm for solving a primal—dual pair of linear programming problems and they demonstrate its global convergence. Their algorithm finds approximate optimal solutions of the pair if both problems have interior points, and they detect infeasibility when the sequence of iterates diverges. Zhang proves polynomial-time convergence of an infeasible-interior-point algorithm under the assumption that both primal and dual problems have feasible points. In this paper, we show that a modification of the Kojima—Megiddo—Mizuno algorithm solves the pair of problems in polynomial time without assuming the existence of the LP solution. Furthermore, we develop anO(nL)-iteration complexity result for a variant of the algorithm.The original title was Polynomiality of the Kojima—Megiddo—Mizuno infeasible-interior-point algorithm for linear programming.Research performed while visiting Cornell University (April 1992 – January 1993) as an Overseas Research Scholar of the Ministry of Science, Education and Culture of Japan.     

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.     

New Sequential Quadratically-Constrained Quadratic Programming Method of Feasible Directions and Its Convergence Rate

This paper discusses optimization problems with nonlinear inequality constraints and presents a new sequential quadratically-constrained quadratic programming (NSQCQP) method of feasible directions for solving such problems. At each iteration. the NSQCQP method solves only one subproblem which consists of a convex quadratic objective function, convex quadratic equality constraints, as well as a perturbation variable and yields a feasible direction of descent (improved direction). The following results on the NSQCQP are obtained: the subproblem solved at each iteration is feasible and solvable: the NSQCQP is globally convergent under the Mangasarian-Fromovitz constraint qualification (MFCQ); the improved direction can avoid the Maratos effect without the assumption of strict complementarity; the NSQCQP is superlinearly and quasiquadratically convergent under some weak assumptions without thestrict complementarity assumption and the linear independence constraint qualification (LICQ). Research supported by the National Natural Science Foundation of China Project 10261001 and Guangxi Science Foundation Projects 0236001 and 0249003. The author thanks two anonymous referees for valuable comments and suggestions on the original version of this paper.     

An Interactive Multiple Criteria Approach to Ranking Alternatives

In this paper we are concerned with ranking various orderings of a set of alternatives to a composite order as a multiple criteria problem. The orderings (called preference orderings) can be real preference orderings or any natural orderings. The objective is to find the most preferred order of the decision maker using the preference orderings as criteria.In principle, the problem can be formulated as a multiple objective linear programming problem using the model of Bowman and Colantoni and then solved with the interactive method proposed by Zionts and Wallenius. However, the fact that we are dealing with integer variables prohibits us from applying this approach as such. We discuss the problem formulation and propose a modified approach to that of Zionts and Wallenius for solving the problem.     

Relaxation techniques for strictly convex network problems

Gauss—Seidel type relaxation techniques are applied in the context of strictly convex pure networks with separable cost functions. The algorithm is an extension of the Bertsekas—Tseng approach for solving the linear network problem and its dual as a pair of monotropic programming problems. The method is extended to cover the class of generalized network problems. Alternative internal tactics for the dual problem are examined. Computational experiments — aimed at the improved efficiency of the algorithm — are presented.This research was supported in part by National Science Foundation Grant No. DCR-8401098-A01.     

A unified approach to global convergence of trust region methods for nonsmooth optimization

This paper investigates the global convergence of trust region (TR) methods for solving nonsmooth minimization problems. For a class of nonsmooth objective functions called regular functions, conditions are found on the TR local models that imply three fundamental convergence properties. These conditions are shown to be satisfied by appropriate forms of Fletcher's TR method for solving constrained optimization problems, Powell and Yuan's TR method for solving nonlinear fitting problems, Zhang, Kim and Lasdon's successive linear programming method for solving constrained problems, Duff, Nocedal and Reid's TR method for solving systems of nonlinear equations, and El Hallabi and Tapia's TR method for solving systems of nonlinear equations. Thus our results can be viewed as a unified convergence theory for TR methods for nonsmooth problems.Research supported by AFOSR 89-0363, DOE DEFG05-86ER25017 and ARO 9DAAL03-90-G-0093.Corresponding author.     

Variable target value subgradient method

Polyak's subgradient algorithm for nondifferentiable optimization problems requires prior knowledge of the optimal value of the objective function to find an optimal solution. In this paper we extend the convergence properties of the Polyak's subgradient algorithm with a fixed target value to a more general case with variable target values. Then a target value updating scheme is provided which finds an optimal solution without prior knowledge of the optimal objective value. The convergence proof of the scheme is provided and computational results of the scheme are reported.Most of this research was performed when the first author was visiting Decision and Information Systems Department, College of Business, Arizona State University.     

A successive quadratic programming algorithm with global and superlinear convergence properties

This paper presents a successive quadratic programming algorithm for solving general nonlinear programming problems. In order to avoid the Maratos effect, direction-finding subproblems are derived by modifying the second-order approximations to both objective and constraint functions of the problem. We prove that the algorithm possesses global and superlinear convergence properties.This work was supported in part by a Scientific Research Grant-in-Aid from the Ministry of Education, Science and Culture, Japan.     

求解多层线性规划的模糊规划法

本文用模糊集理论中的隶属函数描述多层线性规划的各层目标,在第一层给定最小满意水平下,通过求解相应层次的模糊规划来确定各层的最小满意度,从而最终得到问题的一个满意解。提出的方法只需求解一系列线性规划问题,具有较好的计算复杂性和可行性,最后的算例进一步验证了方法的有效性。     

Solving geometric programs using GRG: Results and comparisons

This paper describes the performance of a general-purpose GRG code for nonlinear programming in solving geometric programs. The main conclusions drawn from the experiments reported are: (i) GRG competes well with special-purpose geometric programming codes in solving geometric programs; and (ii) standard time, as defined by Colville, is an inadequate means of compensating for different computing environments while comparing optimization algorithms.This research was partially supported by the Office of Naval Research under Contracts Nos. N00014-75-C-0267 and N00014-75-C-0865, the US Energy Research and Development Administration, Contract No. E(04-3)-326 PA-18, and the National Science Foundation, Grant No. DCR75-04544 at Stanford University; and by the Office of Naval Research under Contract No. N00014-75-C-0240, and the National Science Foundation, Grant No. SOC74-23808, at Case Western Reserve University.     

一类线性约束下不可微最优化问题的可行下降方法

本文给出了一类线性约束下不可微量优化问题的可行下降方法，这类问题的目标函数是凸函数和可微函数的合成函数，算法通过解系列二次规划寻找可行下降方向，新的迭代点由不精确线搜索产生，在较弱的条件下，我们证明了算法的全局收敛性     

一类线性乘积规划问题的分支定界缩减方法

提出了求解一类线性乘积规划问题的分支定界缩减方法, 并证明了算法的收敛性.在这个方法中, 利用两个变量乘积的凸包络技术, 给出了目标函数与约束函数中乘积的下界, 由此确定原问题的一个松弛凸规划, 从而找到原问题全局最优值的下界和可行解. 为了加快所提算法的收敛速度, 使用了超矩形的缩减策略. 数值结果表明所提出的算法是可行的.