Geometric programming problems with negative degrees of difficulty

This paper proposes two methods to solve posynomial geometric programs with negative degrees of difficulty of lower integral values. Such a case arises when a primal program has a number of variables equal or slightly greater than the number of terms. In this specific case the normality and the orthogonality conditions of the dual geometric program give a system of linear equations, where the number of linear equations is greater than the number of dual variables. No general solution vector exists for this system of linear equations. Either the least square or linear programming method can be applied to get an approximate solution vector for this system. Then the optimum value of the dual objective function can be obtained from the approximate solution vector.     

Process planning in a fuzzy environment

Mixed-integer optimization models for chemical process planning typically assume that model parameters can be accurately predicted. As precise forecasts are difficult to obtain, process planning usually involves uncertainty and ambiguity in the data. This paper presents an application of fuzzy programming to process planning. The forecast parameters are assumed to be fuzzy with a linear or triangular membership function. The process planning problem is then formulated in terms of decision making in a fuzzy environment with fuzzy constraints and fuzzy net present value goals. The model is transformed to a deterministic mixed-integer linear program or mixed-integer nonlinear program depending on the type of uncertainty involved in the problem. For the nonlinear case, a global optimization algorithm is developed for its solution. This algorithm is applicable to general possibilistic programs and can be used as an alternative to the commonly used bisection method. Illustrative examples and computational results for a petrochemical complex with 38 processes and 24 products illustrate the applicability of the developed models and algorithms.     

Belief linear programming

This paper proposes solution approaches to the belief linear programming (BLP). The BLP problem is an uncertain linear program where uncertainty is expressed by belief functions. The theory of belief function provides an uncertainty measure that takes into account the ignorance about the occurrence of single states of nature. This is the case of many decision situations as in medical diagnosis, mechanical design optimization and investigation problems. We extend stochastic programming approaches, namely the chance constrained approach and the recourse approach to obtain a certainty equivalent program. A generic solution strategy for the resulting certainty equivalent is presented.     

An efficient linear programming solver for optimal filter synthesis

We consider the problem of l_∞ optimal deconvolution arising in high data‐rate communication between integrated circuits. The optimal deconvolver can be found by solving a linear program for which we use Mehrotra's interior‐point approach. The critical step is solving the linear system for the normal equations in each iteration. We show that this linear system has a special block structure that can be exploited to obtain a fast solution technique whose overall computational cost depends mostly on the number of design variables, and only linearly on the number of constraints. Numerical experiments validate our findings and illustrate the merits of our approach. Copyright © 2007 John Wiley & Sons, Ltd.     

Numerical method for solving linear Fredholm fuzzy integral equations of the second kind

In this paper we use parametric form of fuzzy number and convert a linear fuzzy Fredholm integral equation to two linear system of integral equation of the second kind in crisp case. We can use one of the numerical method such as Nystrom and find the approximation solution of the system and hence obtain an approximation for fuzzy solution of the linear fuzzy Fredholm integral equations of the second kind. The proposed method is illustrated by solving some numerical examples.     

Certificates of Primal or Dual Infeasibility in Linear Programming

In general if a linear program has an optimal solution, then a primal and dual optimal solution is a certificate of the solvable status. Furthermore, it is well known that in the solvable case, then the linear program always has an optimal basic solution. Similarly, when a linear program is primal or dual infeasible then by Farkas's Lemma a certificate of the infeasible status exists. However, in the primal or dual infeasible case then there is not an uniform definition of what a suitable basis certificate of the infeasible status is.In this work we present a definition of a basis certificate and develop a strongly polynomial algorithm which given a Farkas type certificate of infeasibility computes a basis certificate of infeasibility. This result is relevant for the recently developed interior-point methods because they do not compute a basis certificate of infeasibility in general. However, our result demonstrates that a basis certificate can be obtained at a moderate computational cost.     

A comparison of analytic and knowledge-based approaches to closed-shop scheduling

This paper compares three different approaches to scheduling in a closed-shop environment, making the case for a knowledge-based approach. A manufacturing example from the food industry is used as a vehicle for the presentation. The first approach attempts to find an optimal solution using a mixed integer linear programming formulation, but the size of the problem renders this approach impractical. The second approach uses a spreadsheet program to obtain feasible solutions, but imbedded assumptions in the heuristics used allow it to be used only for simple demand patterns. The third approach employs expert systems technology. It includes several heuristics and takes all constraints into consideration. The solution obtained may not be optimal, but computational tests suggest that it is far superior to both spreadsheet and manual approaches.     

Robust Duality for Fractional Programming Problems with Constraint-Wise Data Uncertainty

In this paper, we examine duality for fractional programming problems in the face of data uncertainty within the framework of robust optimization. We establish strong duality between the robust counterpart of an uncertain convex–concave fractional program and the optimistic counterpart of its conventional Wolfe dual program with uncertain parameters. For linear fractional programming problems with constraint-wise interval uncertainty, we show that the dual of the robust counterpart is the optimistic counterpart in the sense that they are equivalent. Our results show that a worst-case solution of an uncertain fractional program (i.e., a solution of its robust counterpart) can be obtained by solving a single deterministic dual program. In the case of a linear fractional programming problem with interval uncertainty, such solutions can be found by solving a simple linear program.     

Lower level duality and the global solution of generalized semi-infinite programs

The reformulation of generalized semi-infinite programs (GSIP) to simpler problems is considered. These reformulations are achieved under the assumption that a duality property holds for the lower level program (LLP). Lagrangian duality is used in the general case to establish the relationship between the GSIP and a related semi-infinite program (SIP). Practical aspects of this reformulation, including how to bound the duality multipliers, are also considered. This SIP reformulation result is then combined with recent advances for the global, feasible solution of SIP to develop a global, feasible point method for the solution of GSIP. Reformulations to finite nonlinear programs, and the practical aspects of solving these reformulations globally, are also discussed. When the LLP is a linear program or second-order cone program, specific duality results can be used that lead to stronger results. Numerical examples demonstrate that the global solution of GSIP is computationally practical via the solution of these duality-based reformulations.     

Application of Fuzzy Linear Programming in Production Planning

In this paper, a new fuzzy linear programming based methodology using a specific membership function, named as modified logistic membership function is proposed. The modified logistic membership function is first formulated and its flexibility in taking up vagueness in parameters is established by an analytical approach. This membership function is tested for its useful performance through an illustrative example by employing fuzzy linear programming. The developed methodology of FLP has provided a confidence in applying to real life industrial production planning problem. This approach of solving industrial production planning problem can have feed back within the decision maker, the implementer and the analyst. In such case this approach can be called as IFLP (Interactive Fuzzy Linear Programming). There is a possibility to design the self organizing of fuzzy system for the mix products selection problem in order to find the satisfactory solution. The decision maker, the analyst and the implementer can incorporate their knowledge and experience to obtain the best outcome.     

A finite algorithm for the least two-norm solution of a linear program 1

By perturbing properly a linear program to a separable quadratic program it is possible to solve the latter in its dual variable space by iterative techniques such as sparsity-preserving SOR (successive overtaxation techniques). In this way large sparse linear programs can be handled.

In this paper we give a new computational criterion to check whether the solution of the perturbed quadratic program provides the least 2-norm solution of the original linear program. This criterion improves on the criterion proposed in an earlier paper.

We also describe an algorithm for solving linear programs which is based on the SOR methods. The main property of this algorithm is that, under mild assumptions, it finds the least 2-norm solution of a linear program in a finite number of iteration.s     

Nonlinear programming and stationary strategies in stochastic games

We show that an undiscounted stochastic game possesses optimal stationary strategies if and only if a global minimum with objective value zero can be found to an appropriate nonlinear program with linear constraints. This nonlinear program arises as a method for solving a certain bilinear system, satisfaction of which is also equivalent to finding a stationary optimal solution for the game. The objective function of the program is a nonnegatively valued quadric polynomial.This research was supported in part by the National Science Foundation under the grant #ECS-8503440. We wish to thank the referee for many helpful comments and in streamlining the presentation.     

Modified geometric programming problem and its applications

In this paper, we propose unconstrained and constrained posynomial Geometric Programming (GP) problem with negative or positive integral degree of difficulty. Conventional GP approach has been modified to solve some special typer of GP problems. In specific case, when the degree of difficulty is negative, the normality and the orthogonality conditions of the dual program give a system of linear equations. No general solution vector exists for this system of linear equations. But an approximate solution can be determined by the least square and also max-min method. Here, modified form of geometric programming method has been demonstrated and for that purpose necessary theorems have been derived. Finally, these are illustrated by numerical examples and applications.     

The logarithmic least squares and the generalized pseudoinverse in estimating ratios

This paper concerns the pairwise-comparison method used in Analytic Hierarchy Process (AHP). The logarithmic least square method is one of the methods used to rank a finite number of stimuli based on their pairwise-comparison. In the case of one decision-maker the problem can be solved using the geometric mean method. It is then assumed that the solution is geometrically normalized. In the case of multiple decision makers a set of linear equations is obtained and if we have a different number of judgments for each pair of the compared objects the geometric normalization assumption can not be used directly. The aim of this paper is to show that applying the generalized pseudoinverse we obtain the solution that is geometrically normalized and consistent with the case of one decision maker. To define the pseudoinverse the spectral decomposition is used. The structure of the general solution is presented and the existence of the general solution is discussed.     

Linear and nonlinear abstract equations with parameters

This paper focuses on nonlocal boundary value problems for linear and nonlinear abstract elliptic equations in Banach spaces. Here equations and boundary conditions contain certain parameters. The uniform separability of the linear problem and the existence and uniqueness of maximal regular solution of nonlinear problem are obtained in L_p spaces. For linear case the discreteness of spectrum of corresponding parameter dependent differential operator is obtained. The behavior of solution when the parameter approaches zero and its smoothness with respect to the parameter is established. Moreover, we show the estimate for analytic semigroups in terms of interpolation spaces. This fact can be used to obtain maximal regularity properties for abstract boundary value problems.     

The theory of linear programming:skew symmetric self-dual problems and the central path *

The literature in the field of interior point methods for linear programming has been almost exclusively algorithm oriented. Recently Güler, Roos, Terlaky and Vial presented a complete duality theory for linear programming based on the interior point approach. In this paper we present a more simple approach which is based on an embedding of the primal problem and its dual into a skew symmetric self-dual problem. This embedding is essentially due Ye, Todd and Mizuno

First we consider a skew symmetric self-dual linear program. We show that the strong duality theorem trivally holds in this case. Then, using the logarithmic barrier problem and the central path, the existence of a strictly complementary optimal solution is proved. Using the embedding just described, we easily obtain the strong duality theorem and the existence of strictly complementary optimal solutions for general linear programming problems     

确定性需求下的最优保理融资与生产策略

企业为下游买方提供赊销,由于大量的资金被应收账款占用,企业可能因资金不足而无法生产足够的产品。企业可以通过保理(出售应收账款)进行融资,减小需求损失。在离散时间多周期的确定需求下,使用决策变量描述各周期的系统状态及其状态转移方程,将此问题建模为线性规划。通过分析此问题的结构特点,再提出了一种新颖且等价的建模方法,可以有效减少决策变量和约束条件的数量。在连续时间模型和混合模型中,这种建模方法同样适用,将优化问题写为连续线性规划,极大地降低了优化问题的复杂度。此连续线性规划问题可通过适当的区间划分进行离散化,用分片常量函数代替优化模型中的一般函数(无限维)决策变量,通过求解有限维线性规划得到原问题的可行近似解。最后,通过数值例子分析了贴现率对企业利润的影响。     

Asymptotic properties of solutions to two discrete airy equations

We construct two finite difference models for the Airy differential equation. In one model, the form of the complete asymptotic representation of the solution can be found. However, this is not the case for the second model which is based on the use of a nonstandard difference scheme. This scheme leads to a second-order, linear difference equation that is not of a form for which the theorems of Poincaré and Perron can be directly applied to obtain the asymptotic behavior of the solutions.     

On the Minimum Norm Solution of Linear Programs

This paper describes a new technique to find the minimum norm solution of a linear program. The main idea is to reformulate this problem as an unconstrained minimization problem with a convex and smooth objective function. The minimization of this objective function can be carried out by a Newton-type method which is shown to be globally convergent. Furthermore, under certain assumptions, this Newton-type method converges in a finite number of iterations to the minimum norm solution of the underlying linear program.     

Quadratic control for linear periodic systems

We propose a new quadratic control problem for linear periodic systems which can be finite or infinite dimensional. We consider both deterministic and stochastic cases. It is a generalization of average cost criterion, which is usually considered for time-invariant systems. We give sufficient conditions for the existence of periodic solutions.Under stabilizability and detectability conditions we show that the optimal control is given by a periodic feedback which involves the periodic solution of a Riccati equation. The optimal closed-loop system has a unique periodic solution which is globally exponentially asymptotically stable. In the stochastic case we also consider the quadratic problem under partial observation. Under two sets of stabilizability and detectability conditions we obtain the separation principle. The filter equation is not periodic, but we show that it can be effectively replaced by a periodic filter. The theory is illustrated by simple examples.This work was done while this author was a visiting professor at the Scuola Normale Superiore, Pisa.