Continuous-Time Generalized Fractional Programming Problems, Part II: An Interval-Type Computational Procedure

The theory presented in Part I (Wen in J. Optim. Theory Appl. 2012) of this study led to a theoretical parametric procedure for continuous-time generalized fractional programming problems. In this paper (Part II), an interval-type computational procedure by combining the parametric method and discretization approach is proposed. The proposed method is promising particularly when it is acceptable to find an effective, but near-optimal value in an efficient manner. Once the error tolerance is predetermined, we can determine the size of discretization in advance such that the accuracy of the corresponding approximate solution can be controlled within the predefined error tolerance. Hence, the trade-off between the quality of the results and the simplification of the problem can be controlled by the decision maker. Finally, we provide some numerical examples to implement our proposed method.     

Using the parametric approach to solve the continuous-time linear fractional max–min problems

A numerical algorithm based on parametric approach is proposed in this paper to solve a class of continuous-time linear fractional max-min programming problems. We shall transform this original problem into a continuous-time non-fractional programming problem, which unfortunately happens to be a continuous-time nonlinear programming problem. In order to tackle this nonlinear problem, we propose the auxiliary problem that will be formulated as a parametric continuous-time linear programming problem. We also introduce a dual problem of this parametric continuous-time linear programming problem in which the weak duality theorem also holds true. We introduce the discrete approximation method to solve the primal and dual pair of parametric continuous-time linear programming problems by using the recurrence method. Finally, we provide two numerical examples to demonstrate the usefulness of this algorithm.     

Using the Dinkelbach-type algorithm to solve the continuous-time linear fractional programming problems

A Dinkelbach-type algorithm is proposed in this paper to solve a class of continuous-time linear fractional programming problems. We shall transform this original problem into a continuous-time non-fractional programming problem, which unfortunately happens to be a continuous-time nonlinear programming problem. In order to tackle this nonlinear problem, we propose the auxiliary problem that will be formulated as parametric continuous-time linear programming problem. We also introduce a dual problem of this parametric continuous-time linear programming problem in which the weak duality theorem also holds true. We introduce the discrete approximation method to solve the primal and dual pair of parametric continuous-time linear programming problems by using the recurrence method. Finally, we provide two numerical examples to demonstrate the usefulness of this practical algorithm.     

OPTIMALITY CONDITIONS AND DUALITY MODELS FOR A CLASS OF NONSMOOTH CONTINUOUS-TIME GENERALIZED FRACTIONAL PROGRAMMING PROBLEMS

Abstract

Both parametric and parameter-free stationary-point-type and saddle-point-type necessary and sufficient optimality conditions are established for a class of nonsmooth continuous-time generalized fractional programming problems with Volterra-type integral inequality and nonnegativity constraints. These optimality criteria are then utilized for constructing ten parametric and parameter-free Wolfe-type and Lagrangian-type dual problems and for proving weak, strong, and strict converse duality theorems. Furthermore, it is briefly pointed out how similar optimality and duality results can be obtained for two important special cases of the main problem containing arbitrary norms and square roots of positive semidefinite quadratic forms. All the results developed here are also applicable to continuous-time programming problems with fractional, discrete max, and conventional objective functions, which are special cases of the main problem studied in this paper.     

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.      

Method of Centers for Generalized Fractional Programming

We propose an algorithm to solve generalized fractional programming problems. The proposed algorithm combines the parametric approach and the Huard method of centers. A minimum of the problem is obtained by solving a sequence of unconstrained optimization problems.     

Parametric simplex algorithms for solving a special class of nonconvex minimization problems

It is shown that parametric linear programming algorithms work efficiently for a class of nonconvex quadratic programming problems called generalized linear multiplicative programming problems, whose objective function is the sum of a linear function and a product of two linear functions. Also, it is shown that the global minimum of the sum of the two linear fractional functions over a polytope can be obtained by a similar algorithm. Our numerical experiments reveal that these problems can be solved in much the same computational time as that of solving associated linear programs. Furthermore, we will show that the same approach can be extended to a more general class of nonconvex quadratic programming problems.     

On the Continuity of the Optimal Value in Parametric Linear Optimization: Stable Discretization of the Lagrangian Dual of Nonlinear Problems

This paper is focused on the stability of the optimal value, and its immediate repercussion on the stability of the optimal set, for a general parametric family of linear optimization problems in ⁿ. In our approach, the parameter ranges over an arbitrary metric space, and each parameter determines directly a set of coefficient vectors describing the linear system of constraints. Thus, systems associated with different parameters are not required to have the same number (cardinality) of inequalities. In this way, discretization techniques for solving a nominal linear semi-infinite optimization problem may be modeled in terms of suitable parametrized problems. The stability results given in the paper are applied to the stability analysis of the Lagrangian dual associated with a parametric family of nonlinear programming problems. This dual problem is translated into a linear (semi-infinite) programming problem and, then, we prove that the lower semicontinuity of the corresponding feasible set mapping, the continuity of the optimal value function, and the upper semicontinuity of the optimal set mapping are satisfied. Then, the paper shows how these stability properties for the dual problem entail a nice behavior of parametric approximation and discretization strategies (in which an ordinary linear programming problem may be considered in each step). This approximation–discretization process is formalized by means of considering a double parameter: the original one and the finite subset of indices (grid) itself. Finally, the convex case is analyzed, showing that the referred process also allows us to approach the primal problem.Mathematics Subject Classifications (2000) Primary 90C34, 90C31; secondary 90C25, 90C05.     

Approximate Solutions and Duality Theorems for Continuous-Time Linear Fractional Programming Problems

This article proposes a practical computational procedure to solve a class of continuous-time linear fractional programming problems by designing a discretized problem. Using the optimal solutions of proposed discretized problems, we construct a sequence of feasible solutions of continuous-time linear fractional programming problem and show that there exists a subsequence that converges weakly to a desired optimal solution. We also establish an estimate of the error bound. Finally, we provide two numerical examples to demonstrate the usefulness of this practical algorithm.     

Solving Fractional Multicriteria Optimization Problems with Sum of Squares Convex Polynomial Data

This paper focuses on the study of finding efficient solutions in fractional multicriteria optimization problems with sum of squares convex polynomial data. We first relax the fractional multicriteria optimization problems to fractional scalar ones. Then, using the parametric approach, we transform the fractional scalar problems into non-fractional problems. Consequently, we prove that, under a suitable regularity condition, the optimal solution of each non-fractional scalar problem can be found by solving its associated single semidefinite programming problem. Finally, we show that finding efficient solutions in the fractional multicriteria optimization problems is tractable by employing the epsilon constraint method. In particular, if the denominators of each component of the objective functions are same, then we observe that efficient solutions in such a problem can be effectively found by using the hybrid method. Some numerical examples are given to illustrate our results.     

一类广义分式规划问题的ε-近似算法

 本文针对一类广义分式规划问题提出一种求其全局最优解的ε-近似算法,并从理论上证明该算法的收敛性和计算复杂性, 数值结果表明算法是有效可行的.     

具有(F,α,ρ,d)—凸的分式规划问题的最优性条件和对偶性

给出了一类非线性分式规划问题的参数形式和非参数形式的最优性条件,在此基础上,构造出了一个参数对偶模型和一个非参数对偶模型,并分别证明了其相应的对偶定理,这些结果是建立在次线性函数和广义凸函数的基础上的.     

Generalized fractional programming and cutting plane algorithms

In this paper, we introduce a variant of a cutting plane algorithm and show that this algorithm reduces to the well-known Dinkelbach-type procedure of Crouzeix, Ferland, and Schaible if the optimization problem is a generalized fractional program. By this observation, an easy geometrical interpretation of one of the most important algorithms in generalized fractional programming is obtained. Moreover, it is shown that the convergence of the Dinkelbach-type procedure is a direct consequence of the properties of this cutting plane method. Finally, a class of generalized fractional programs is considered where the standard positivity assumption on the denominators of the ratios of the objective function has to be imposed explicitly. It is also shown that, when using a Dinkelbach-type approach for this class of programs, the constraints ensuring the positivity on the denominators can be dropped.The authors like to thank the anonymous referees and Frank Plastria for their constructive remarks on an earlier version of this paper.This research was carried out at Erasmus University, Rotterdam, The Netherlands and was supported by JNICT, Lisboa, Portugal, under Contract BD/707/90-RM.     

Parametric computation of a fuzzy set solution to a class of fuzzy linear fractional optimization problems

The class of fuzzy linear fractional optimization problems with fuzzy coefficients in the objective function is considered in this paper. We propose a parametric method for computing the membership values of the extreme points in the fuzzy set solution to such problems. We replace the exhaustive computation of the membership values—found in the literature for solving the same class of problems—by a parametric analysis of the efficiency of the feasible basic solutions to the bi-objective linear fractional programming problem through the optimality test in a related linear programming problem, thus simplifying the computation. An illustrative example from the field of production planning is included in the paper to complete the theoretical presentation of the solving approach, but also to emphasize how many real life problems may be modelled mathematically using fuzzy linear fractional optimization.     

Accelerated sample average approximation method for two-stage stochastic programming with binary first-stage variables

This paper proposes an accelerated solution method to solve two-stage stochastic programming problems with binary variables in the first stage and continuous variables in the second stage. To develop the solution method, an accelerated sample average approximation approach is combined with an accelerated Benders’ decomposition algorithm. The accelerated sample average approximation approach improves the main structure of the original technique through the reduction in the number of mixed integer programming problems that need to be solved. Furthermore, the recently accelerated Benders’ decomposition approach is utilized to expedite the solution time of the mixed integer programming problems. In order to examine the performance of the proposed solution method, the computational experiments are performed on developed stochastic supply chain network design problems. The computational results show that the accelerated solution method solves these problems efficiently. The synergy of the two accelerated approaches improves the computational procedure by an average factor of over 42%, and over 12% in comparison with the original and the recently modified methods, respectively. Moreover, the betterment of the computational process increases substantially with the size of the problem.     

Structural Optimization with FEM-based Shakedown Analyses

In this paper, a mathematical programming formulation is presented for the structural optimization with respect to the shakedown analysis of 3-D perfectly plastic structures on basis of a finite element discretization. A new direct algorithm using plastic sensitivities is employed in solving this optimization formulation. The numerical procedure has been applied to carry out the shakedown analysis of pipe junctions under multi-loading systems. The new approach is compared to so-called derivative-free direct search methods. The computational effort of the proposed method is much lower compared to this methods.     

The asymptotic behavior of nonlinear semigroups and invariant means

Various first-order sufficient optimality criteria for continuous-time nonlinear programming problems with nonlinear equality and inequality constraints are established under generalized convexity assumptions, and applications of these criteria to optimal control and continuous-time fractional programming problems are briefly discussed.     

Feasible Method for Generalized Semi-Infinite Programming

In this paper, we analyze the outer approximation property of the algorithm for generalized semi-infinite programming from Stein and Still (SIAM J. Control Optim. 42:769–788, 2003). A simple bound on the regularization error is found and used to formulate a feasible numerical method for generalized semi-infinite programming with convex lower-level problems. That is, all iterates of the numerical method are feasible points of the original optimization problem. The new method has the same computational cost as the original algorithm from Stein and Still (SIAM J. Control Optim. 42:769–788, 2003). We also discuss the merits of this approach for the adaptive convexification algorithm, a feasible point method for standard semi-infinite programming from Floudas and Stein (SIAM J. Optim. 18:1187–1208, 2007).     

Optimizing a General Optimal Replacement Model by Fractional Programming Techniques

In this paper we adapt the well-known parametric approachfrom fractional programming to solvea class of fractional programs with a noncompact feasible region.Such fractional problems belong to an important class ofsingle component preventive maintenance models.Moreover, for a special but important subclass we showthat the subproblems occurring in this parametric approachare easy solvable.To solve the problem directly we also propose for a relatedsubclass a specialized version of the bisection method.Finally, we present some computational results for these twomethods applied to an inspection model and a minimal repair modelhaving both a unimodal failure rate.