Nonlinear programming and nonsmooth optimization by successive linear programming

Methods are considered for solving nonlinear programming problems using an exactl ₁ penalty function. LP-like subproblems incorporating a trust region constraint are solved successively both to estimate the active set and to provide a foundation for proving global convergence. In one particular method, second order information is represented by approximating the reduced Hessian matrix, and Coleman-Conn steps are taken. A criterion for accepting these steps is given which enables the superlinear convergence properties of the Coleman-Conn method to be retained whilst preserving global convergence and avoiding the Maratos effect. The methods generalize to solve a wide range of composite nonsmooth optimization problems and the theory is presented in this general setting. A range of numerical experiments on small test problems is described.     

New results on the equivalence between zero-one programming and continuous concave programming

In this work, we study continuous reformulations of zero-one concave programming problems. We introduce new concave penalty functions and we prove, using general equivalence results here derived, that the obtained continuous problems are equivalent to the original combinatorial problem.     

Multicriterion reliability-oriented optimization of structural systems by stochastic programming

Papers deals with multicriterion reliability-oriented optimization of truss structures by stochastic programming. Deterministic approach to structural optimization appears to be insufficient when loads acting upon a structure and material properties of the structure elements have a random nature. The aim of this paper is to show importance of random modelling of the structure and influence of random parameters on an optimal solution. Usually, quality of engineering structure design is considered in terms of displacements, total cost and reliability. Therefore, optimization problem has been formulated and then solved in order to show interaction between displacement and a total cost objective function. The examples of 4-bar and 25-bar truss structures illustrate our considerations. The results of optimization are presented in the form of diagrams.     

Global optimization of mixed-integer bilevel programming problems

Two approaches that solve the mixed-integer nonlinear bilevel programming problem to global optimality are introduced. The first addresses problems mixed-integer nonlinear in outer variables and C²-nonlinear in inner variables. The second adresses problems with general mixed-integer nonlinear functions in outer level. Inner level functions may be mixed-integer nonlinear in outer variables, linear, polynomial, or multilinear in inner integer variables, and linear in inner continuous variables. This second approach is based on reformulating the mixed-integer inner problem as continuous via its vertex polyheral convex hull representation and solving the resulting nonlinear bilevel optimization problem by a novel deterministic global optimization framework. Computational studies illustrate proposed approaches.     

Free material optimization via mathematical programming

This paper deals with a central question of structural optimization which is formulated as the problem of finding the stiffest structure which can be made when both the distribution of material as well as the material itself can be freely varied. We consider a general multi-load formulation and include the possibility of unilateral contact. The emphasis of the presentation is on numerical procedures for this type of problem, and we show that the problems after discretization can be rewritten as mathematical programming problems of special form. We propose iterative optimization algorithms based on penalty-barrier methods and interior-point methods and show a broad range of numerical examples that demonstrates the efficiency of our approach. Supported by the project 03ZO7BAY of BMBF (Germany) and the GIF-contract 10455-214.06/95.     

Convergence of a continuous approach for zero-one programming problems

In this paper a new continuous formulation for the zero-one programming problem is presented, followed by an investigation of the algorithm for it. This paper first reformulates the zero-one programming problem as an equivalent mathematical programs with complementarity constraints, then as a smooth ordinary nonlinear programming problem with the help of the Fischer-Burmeister function. After that the augmented Lagrangian method is introduced to solve the resulting continuous problem, with optimality conditions for the non-smooth augmented Lagrangian problem derived on the basis of approximate smooth variational principle, and with convergence properties established. To our benefit, the sequence of solutions generated converges to feasible solutions of the original problem, which provides a necessary basis for the convergence results.     

Quadratic programming for portfolio optimization

Portfolio optimization is a procedure for generating a portfolio composition which yields the highest return for a given level of risk or a minimum risk for given level of return. The problem can be formulated as a quadratic programming problem. We shall present a new and efficient optimization procedure taking advantage of the special structure of the portfolio selection problem. An example of its application to the traditional mean-variance method will be shown. Formulation of the procedure shows that the solution of the problem is vector intensive and fits well with the advanced architecture of recent computers, namely the vector processor.     

An evolutionary programming approach to mixed-variable optimization problems

Many engineering optimization problems frequently encounter discrete variables as well as continuous variables and the presence of nonlinear discrete variables considerably adds to the solution complexity. Very few of the existing methods can find a globally optimal solution when the objective functions are non-convex and non-differentiable. In this paper, we present a mixed-variable evolutionary programming (MVEP) technique for solving these nonlinear optimization problems which contain integer, discrete, zero-one and continuous variables. The MVEP provides an improvement in global search reliability in a mixed-variable space and converges steadily to a good solution. An approach to handle various kinds of variables and constraints is discussed. Some examples of mixed-variable optimization problems in the literature are tested, which demonstrate that the proposed approach is superior to current methods for finding the best solution, in terms of both solution quality and algorithm robustness.     

Semidefinite programming in combinatorial optimization

We discuss the use of semidefinite programming for combinatorial optimization problems. The main topics covered include (i) the Lovász theta function and its applications to stable sets, perfect graphs, and coding theory, (ii) the automatic generation of strong valid inequalities, (iii) the maximum cut problem and related problems, and (iv) the embedding of finite metric spaces and its relationship to the sparsest cut problem. Part of this work is supported by NSF contract 9623859-CCR, a Sloan Foundation Fellowship, and ARPA Contract N00014-95-1-1246.     

Constrained optimization using multiple objective programming

In practical applications of mathematical programming it is frequently observed that the decision maker prefers apparently suboptimal solutions. A natural explanation for this phenomenon is that the applied mathematical model was not sufficiently realistic and did not fully represent all the decision makers criteria and constraints. Since multicriteria optimization approaches are specifically designed to incorporate such complex preference structures, they gain more and more importance in application areas as, for example, engineering design and capital budgeting. The aim of this paper is to analyze optimization problems both from a constrained programming and a multicriteria programming perspective. It is shown that both formulations share important properties, and that many classical solution approaches have correspondences in the respective models. The analysis naturally leads to a discussion of the applicability of some recent approximation techniques for multicriteria programming problems for the approximation of optimal solutions and of Lagrange multipliers in convex constrained programming. Convergence results are proven for convex and nonconvex problems.     

Satisfying optimization method based on goal programming for fuzzy multiple objective optimization problem

This paper proposes a satisfying optimization method based on goal programming for fuzzy multiple objective optimization problem. The aim of this presented approach is to make the more important objective achieving the higher desirable satisfying degree. For different fuzzy relations and fuzzy importance, the reformulated optimization models based on goal programming is proposed. Not only the satisfying results of all the objectives can be acquired, but also the fuzzy importance requirement can be simultaneously actualized. The balance between optimization and relative importance is realized. We demonstrate the efficiency, flexibility and sensitivity of the proposed method by numerical examples.     

Global optimization of signomial geometric programming problems

This paper presents a global optimization approach for solving signomial geometric programming problems. In most cases nonconvex optimization problems with signomial parts are difficult, NP-hard problems to solve for global optimality. But some transformation and convexification strategies can be used to convert the original signomial geometric programming problem into a series of standard geometric programming problems that can be solved to reach a global solution. The tractability and effectiveness of the proposed successive convexification framework is demonstrated by seven numerical experiments. Some considerations are also presented to investigate the convergence properties of the algorithm and to give a performance comparison of our proposed approach and the current methods in terms of both computational efficiency and solution quality.     

求解多项式规划的一个全局最优化算法

提出一个求解带箱子约束的一般多项式规划问题的全局最优化算法, 该算法包含两个阶段, 在第一个阶段, 利用局部最优化算法找到一个局部最优解. 在第二阶段, 利用一个在单位球上致密的向量序列, 将多元多项式转化为一元多项式, 通过求解一元多项式的根, 找到一个比当前局部最优解更好的点作为初始点, 回到第一个 阶段, 从而得到一个更好的局部最优解, 通过两个阶段的循环最终找到问题的全局最优解, 并给出了算法收敛性分析. 最后, 数值结果表明了算法是有效的.     

Trust-region algorithms for derivative-free optimization and nonlinear bilevel programming

We briefly describe the contents of the authors PhD thesis (see Colson 2003) discussed on July 2003 at the University of Namur (Belgium) and supervised by Philippe L. Toint. The contributions presented in this thesis are the development of trust-region methods for solving two particular classes of mathematical programs, namely derivative-free optimization (DFO) problems and nonlinear bilevel programming problems. The thesis is written in English and is available via the author.Received: July 2003, AMS classification: 65D05, 90C30, 90C56, 90C59     

Duality in disjunctive programming via vector optimization

In this paper, we develop a new duality theory for families of linear programs with an emphasis on disjunctive linear optimization by proposing a vector optimization problem as dual problem. We establish that the well-known relations between primal and dual problems hold in this context. We show that our method generalizes the duality results of Borwein on families of linear programs, of Balas on disjunctive programs, and of Patkar and Stancu-Minasian on disjunctive linear fractional programs. Moreover, we can derive some duality results for integer and for fractional programs where the denominator is not assumed (as usual) to be greater than zero for each feasible point.     

Demurrage costs optimization in ports using binary mathematical programming models

Summary SODA is a system by which the schedule of ships in a port can be found in order to minimize the demurrage and operating costs associated with shipping operations. SODA constructs and resolves binary programming models using shipping data (arrival dates, demurrage costs, berths to be used, etc.) and available berths in a planning horizon. The model is of an adjustable precision: major accuracy implies greater calculation time. SODA provides an optimal result to a complex problem in a resolution time which is generally better than that needed for a manual solution.     

A linear programming reformulation of the standard quadratic optimization problem

The problem of minimizing a quadratic form over the standard simplex is known as the standard quadratic optimization problem (SQO). It is NP-hard, and contains the maximum stable set problem in graphs as a special case. In this note, we show that the SQO problem may be reformulated as an (exponentially sized) linear program (LP). This reformulation also suggests a hierarchy of polynomial-time solvable LP’s whose optimal values converge finitely to the optimal value of the SQO problem. The hierarchies of LP relaxations from the literature do not share this finite convergence property for SQO, and we review the relevant counterexamples.     

Global optimization of nonconvex factorable programming problems

In this paper, we consider a special class of nonconvex programming problems for which the objective function and constraints are defined in terms of general nonconvex factorable functions. We propose a branch-and-bound approach based on linear programming relaxations generated through various approximation schemes that utilize, for example, the Mean-Value Theorem and Chebyshev interpolation polynomials coordinated with a Reformulation-Linearization Technique (RLT). A suitable partitioning process is proposed that induces convergence to a global optimum. The algorithm has been implemented in C++ and some preliminary computational results are reported on a set of fifteen engineering process control and design test problems from various sources in the literature. The results indicate that the proposed procedure generates tight relaxations, even via the initial node linear program itself. Furthermore, for nine of these fifteen problems, the application of a local search method that is initialized at the LP relaxation solution produced the actual global optimum at the initial node of the enumeration tree. Moreover, for two test cases, the global optimum found improves upon the solutions previously reported in the source literature. Received: January 14, 1998 / Accepted: June 7, 1999?Published online December 15, 2000     

Nonlinear programming and an optimization problem on infinitely differentiable functions

A nonnegative, infinitely differentiable function ø defined on the real line is called a Friedrichs mollifier function if it has support in [0, 1] and ₀ ¹ ø(t)dt=1. In this article the following problem is considered. Determine _k =inf ₀ ¹ vø^(k)(t)dt, k=1,..., where ø^(k) denotes thekth derivative of ø and the infimum is taken over the set of all mollifier functions. This problem has applications to monotone polynomial approximation as shown by this author elsewhere. In this article, the structure of the problem of determining _k is analyzed, and it is shown that the problem is reducible to a nonlinear programming problem involving the minimization of a strictly convex function of [(k–1)/2] variables, subject to a simple ordering restriction on the variables. An optimization problem on the functions of bounded variation, which is equivalent to the nonlinear programming problem, is also developed. The results of this article and those from approximation of functions theory are applied elsewhere to derive numerical values of various mathematical quantities involved in this article, e.g., _k =k~2^2k–1 for allk=1, 2, ..., and to establish certain inequalities of independent interest. This article concentrates on problem reduction and equivalence, and not numerical value.This research was supported in part by the National Science Foundation under Grant No. GK-32712.     

A dynamic programming approach to adjustable robust optimization

In this paper we consider the adjustable robust approach to multistage optimization, for which we derive dynamic programming equations. We also discuss this from the point of view of risk averse stochastic programming. We consider as an example a robust formulation of the classical inventory model and show that, like for the risk neutral case, a basestock policy is optimal.