Search

An algorithm to solve bi-objective quadratic fractional integer programming problems is presented in this paper. The algorithm uses -scalarization technique and a ranking approach of the integer feasible solution to find all nondominated points. In order to avoid solving non-linear integer programming problems during this ranking scheme, the existence of a linear or a linear fractional function is established, which acts as a lower bound on the values of first objective function of the bi-objective problem over the entire feasible set. Numerical examples are also presented in support of the theory.

To globally solve linear multiplicative programming problem (LMP), this paper presents a practicable branch-and-bound method based on the framework of branch-and-bound algorithm. In this method, a new linear relaxation technique is proposed firstly. Then, the branch-and-bound algorithm is developed for solving problem LMP. The proposed algorithm is proven that it is convergent to the global minimum by means of the subsequent solutions of a series of linear programming problems. Some experiments are reported to show the feasibility and efficiency of this algorithm.

The computational complexity of linear and nonlinear programming problems depends on the number of objective functions and constraints involved and solving a large problem often becomes a difficult task. Redundancy detection and elimination provides a suitable tool for reducing this complexity and simplifying a linear or nonlinear programming problem while maintaining the essential properties of the original system. Although a large number of redundancy detection methods have been proposed to simplify linear and nonlinear stochastic programming problems, very little research has been developed for fuzzy stochastic (FS) fractional programming problems. We propose an algorithm that allows to simultaneously detect both redundant objective function(s) and redundant constraint(s) in FS multi-objective linear fractional programming problems. More precisely, our algorithm reduces the number of linear fuzzy fractional objective functions by transforming them in probabilistic-possibilistic constraints characterized by predetermined confidence levels. We present two numerical examples to demonstrate the applicability of the proposed algorithm and exhibit its efficacy.

This paper presents the convergence proof and complexity analysis of an interior-point framework that solves linear programming problems by dynamically selecting and adding relevant inequalities. First, we formulate a new primal–dual interior-point algorithm for solving linear programmes in non-standard form with equality and inequality constraints. The algorithm uses a primal–dual path-following predictor–corrector short-step interior-point method that starts with a reduced problem without any inequalities and selectively adds a given inequality only if it becomes active on the way to optimality. Second, we prove convergence of this algorithm to an optimal solution at which all inequalities are satisfied regardless of whether they have been added by the algorithm or not. We thus provide a theoretical foundation for similar schemes already used in practice. We also establish conditions under which the complexity of such algorithm is polynomial in the problem dimension and address remaining limitations without these conditions for possible further research.

A projection algorithm for positive definite linear complementarity problems is introduced. The algorithm incorporates the basic idea of gradient projection algorithms. A new descent direction, which will be referred to as the vector of centers, is used instead of the negative of the objective function gradient. This descent direction is kept fixed throughout the iterations, thus reducing the computational effort of computing a search direction by per step. The algorithm exploits the ellipsoid algorithm to find an advanced starting point on the boundary of the feasible region. Accordingly, the algorithm is warm-started and the number of iterations required to reach the solution is reduced. Starting from this point, the algorithm generates a series of boundary points that approaches the solution by projecting the proposed descent direction onto the feasible region. A numerical example is solved and a practical example in the simulation of rigid body dynamics is given to demonstrate the usage of the...

Exchange algorithms are popular for finding optimal or efficient designs for linear models, but there are few discussions of this type of algorithm for generalized linear models (GLMs) in literature. A new algorithm, generalized Coordinate Exchange Algorithm (gCEA), is developed in this article to construct efficient designs for GLMs. We compare the performance of the proposed algorithm with other optimization algorithms, including point exchange algorithm, columnwise-pairwise algorithm, simulated annealing and generic algorithm, and demonstrate the superior performance of this new algorithm.

This article proposes a linear integer programming-based algorithm to construct balanced incomplete block designs. Working of the algorithm is illustrated with the help of an example. The algorithm is able to generate balanced incomplete block designs very fast in most of the cases. The performance of the proposed algorithm is compared with other algorithms proposed in the literature. It is demonstrated that the proposed algorithm is competitive with the existing algorithms.

In this paper, we describe three versions of a primal exterior point Simplex type algorithm for solving linear programming problems. Also, these algorithms are not affected mainly by scaling techniques. We compare their practical effectiveness versus the revised primal Simplex algorithm (our implementation) and the MATLAB’s implementations of Simplex and Interior Point Method. A computational study on randomly generated sparse linear programs is presented to establish the practical value of the proposed versions. The results are very encouraging and verify the superiority of the exterior point versions over the other algorithms either using scaling techniques or not.

An optimality criteria (OC)-based algorithm for optimization of a general class of nonlinear programming (NLP) problems is presented. The algorithm is only applicable to problems where the objective and constraint functions satisfy certain monotonicity properties. For multiply constrained problems which satisfy these assumptions, the algorithm is attractive compared with existing NLP methods as well as prevalent OC methods, as the latter involve computationally expensive active set and step-size control strategies. The fixed point algorithm presented here is applicable not only to structural optimization problems but also to certain problems as occur in resource allocation and inventory models. Convergence aspects are discussed. The fixed point update or resizing formula is given physical significance, which brings out a strength and trim feature. The number of function evaluations remains independent of the number of variables, allowing the efficient solution of problems with large number of variables.

In this paper we suggest a new ascent direction for the adaptive method developed by Gabasov et al. (A method of solving general linear programming problems, Doklady AN BSSR 23(3) (1979), pp. 197–200 (in Russian)) for solving linear programs with bounded variables. A quantity called optimality estimate is defined, necessary and sufficient conditions of optimality based on this estimate are derived. An algorithm called the adaptive method with hybrid direction (AMHD) is suggested and a numerical example is given for illustration purpose. In order to compare the suggested algorithm with the classical primal simplex algorithm employing Dantzig's rule (PSA), we have developed a numerical implementation under the MATLAB programming language. The experimental study involves the CPU time and the iterations number of the two algorithms applied to solve randomly generated test problems of different dimensions. It has been shown that when the problem dimension increases, the superiority of AMHD over primal simplex ...

The aim of this paper is to present an experimental investigation of a Primal–Dual Exterior Point Simplex Algorithm (PDEPSA) for Linear Programming problems (LPs). There was a huge gap between the theoretical worst-case complexity and practical performance of simplex type algorithms. PDEPSA traverses across the interior of the feasible region in an attempt to avoid combinatorial complexities of vertex following algorithms. In order to gain an insight into the practical behaviour of the proposed algorithm, we have performed some computational experiments. Our computational results demonstrate that PDEPSA is faster comparable with simplex algorithm and the primal exterior point algorithm. A clear advantage is obtained by PDEPSA in number of iterations and CPU time.

Most algorithms for solving linear program require a phase-1 procedure to find a feasible solution. Recently, a dual–primal algorithm for linear optimization has been proposed by Li [Dual–primal algorithm for linear optimization, Optimiz. Methods Softw. 28 2013, pp. 327–338]. In the process of implementing the dual–primal algorithms, we found an interesting phenomenon that the phase-1 algorithm developed in [Li 2013] always terminates in one iteration. This fact does not come by chance. A rigorous proof is given in this paper.

Problems involving estimation and inference under linear inequality constraints arise often in statistical modeling. In this article, we propose an algorithm to solve the quadratic programming problem of minimizing for positive definite Q, where is constrained to be in a closed polyhedral convex cone , and the m × n matrix is not necessarily full row rank. The three-step algorithm is intuitive and easy to code. Code is provided in the R programming language.

The problem of finding a deepest point (a ball centre) of a polyhedron is studied. A finite combinatorial interior point method is presented for this problem which yields an algorithm for linear programming. We conjecture that this is a strongly polynomial algorithm. Meanwhile developing the algorithm, several auxiliary results were found; among others, Gorokh and Werner’s algorithm for linear inequalities is slightly extended. Our numerical experiments with the problem detected bugs in a linear interior point solver used in MATLAB 6 Optimization Toolbox.

Nonlinear programming problem is the general case of mathematical programming problem such that both the objective and constraint functions are nonlinear and is the most difficult case of smooth optimization problem to solve. In this article, we suggest a stochastic search method to general nonlinear programming problems which is not an iterative algorithm but it is an interior point method. The proposed method finds the near-optimal solution to the problem. The results of a few numerical studies are reported. The efficiency of the new method is compared and is found to be reasonable.

In this paper, we propose a new Mehrotra-type predictor–corrector interior-point algorithm for semidefinite programming. This algorithm is an extension of the variant of Mehrotra-type algorithm that was proposed by Salahi et al. [On Mehrotra-type predictor–corrector algorithms, SIAM J. Optim. 18 2007, pp. 1377–1397] for linear programming problems. We modify the step sizes lightly in the predictor step of Koulaei and Terlaky [On the complexity analysis of a Mehrotra-type primal–dual feasible algorithm for semidefinite optimization, Optim. Methods Softw. 25 2010, pp. 467–485]. In such a way, we obtain OnlogTrX0S0/ϵ iteration complexity of the algorithm, where X0, y0, S0 is the initial feasible point and ϵ is the required precision.

In this article, several cascading multilevel finite-element algorithms are considered to discretize nonlinear parabolic problems, of which the nonlinearity has either local or nonlocal form. Algorithm I solves only a stationary linear system of equations at each level of P1 finite element spaces, while Algorithm II works on the coupling of a stationary linear system of equations with a linear parabolic equation. The convergence orders of Algorithms I and II are both O(h J ) in the energy norm; in Algorithm I the estimation depends on the number of grids, while Algorithm II does not. Algorithm III is based on Picard linearization techniques and Algorithm IV on Newton iteration. Both algorithms have convergence order—O(h J ).

This paper describes an active-set algorithm for nonlinear programming that solves a parametric linear programming subproblem at each iteration to generate an estimate of the active set. A step is then computed by solving an equality constrained quadratic program based on this active-set estimate. This approach represents an extension to standard sequential linear-quadratic programming (SLQP) algorithms. It can also be viewed as an attempt to implement a generalization of the gradient projection algorithm for nonlinear programming. To this effect, we explore the relation between the parametric method and the gradient projection method in the bound-constrained case. Numerical results compare the performance of this algorithm with SLQP and gradient projection, and indicate good performance and marked improvement on bound-constrained problems and quadratic programs.

In this article, the standard primal and dual linear semi-infinite programming (DLSIP) problems are reformulated as linear programming (LP) problems over cones. Therefore, the dual formulation via the minimal cone approach, which results in zero duality gap for the primal–dual pair for LP problems over cones, can be applied to linear semi-infinite programming (LSIP) problems. Results on the geometry of the set of the feasible solutions for the primal LSIP problem and the optimality criteria for the DLSIP problem are also discussed.

It has been shown in various papers that most interior-point algorithms and their analysis can be generalized to semidefinite optimization. This paper presents an extension of the recent variant of Mehrotra's predictor-corrector algorithm that was proposed by Salahi et al. [M. Salahi, J. Peng, and T. Terlaky, On Mehrotra-type predictor-corrector algorithms, SIAM J. Optim. 18 (2007), pp. 1377-1397] for linear optimization (LO) problems. Based on the NT [Y.E. Nesterov and M.J. Todd, Self-scaled barriers and interior-point methods for convex programming, Math. Oper. Res. 22 (1997), pp. 1-42] directions which are Newton search directions, we show that the iteration-complexity bound of the algorithm is of the same order as that of the corresponding algorithm for LO.

This article studies linear programming problems in which all minors of maximal order of the coefficient matrix have the same sign. We analyse the relationship between a special structure of the non-degenerate dual feasible bases of a linear programming problem and the structure of its associated matrix. In the particular case in which the matrix has all minors of each order k with the same strict sign ϵ k , we provide a dual simplex revised method with good stability properties. In particular, this method can be applied to the totally positive linear programming problems, of great interest in many applications.

In this article, we present a family of algorithms for linear programming based on an algorithm proposed by von Neumann. The von Neumann algorithm is very attractive due to its simplicity, but is not practical for solving most linear programs to optimality due to its slow convergence. Our algorithms were developed with the objective of improving the practical convergence of the von Neumann algorithm while maintaining its attractive features. We present results from computational experiments on a set of linear programming problems that show significant improvements over the von Neumann algorithm.

We present an algorithm for solving a class of nonlinear complementarity problems called the almost linear complementarity problem (ALCP), which can be used to simulate free boundary problems. The algorithm makes use of a procedure for identifying an active index subset of an ALCP by bounding its solution with an interval vector. It is shown that an acceptable solution of the given ALCP can be obtained by solving at most n systems of equations. Numerical results are reported to illustrate the efficiency of the algorithm for large-scale problems.

An exterior point algorithm for positive definite (PD) and positive semidefinite (PSD) linear complementarity problems (LCPs) is introduced. The algorithm exploits the ellipsoid method to find a starting point in the case of positive definite linear complementarity problems (PDLCPs) and to check for the problem feasibility in case of positive semidefinite linear complementarity problems (PSDLCPs). The algorithm starts from a point on the boundary on which the complementarity condition is satisfied and generates a sequence of points on that same boundary. These points converge to the solution. The algorithm is modified to speed up the convergence for some PDLCPs and PSDLCPs that arise in certain mechanical models. A numerical example and a practical example in robotics are solved to test the algorithm.

Based on the pivot selection rule [Anstreicher, K.M. and Terlaky, T., 1994, A monotonic build-up simplex algorithm for linear programming. Operations Research, 42, 556-561.] we define a new monotonic build-up (MBU) simplex algorithm for linear feasibility problems. An mK upper bound for the iteration bound of our algorithm is given under a weak non-degeneracy assumption, where K is determined by the input data of the problem and m is the number of constraints. The constant K cannot be bounded in general by a polynomial of the bit length of the input data since it is related to the determinants (of the pivot tableau) with the highest absolute value. An interesting local property of degeneracy led us to construct a new recursive procedure to handle strongly degenerate problems as well. Analogous complexity bounds for the linear programming versions of MBU and the first phase of the simplex method can be proved under our weak non-degeneracy assumption.

The Klee-Minty cube is a well-known worst case example for which the simplex method takes an exponential number of iterations as the algorithm visits all the 2 n vertices of the n-dimensional cube. While such behavior is excluded by polynomial interior point methods, we show that, by adding an exponential number of redundant inequalities, the central path can be bent along the edges of the Klee-Minty cube. More precisely, for an arbitrarily small δ, the central path takes 2 n −2 turns as it passes through the δ-neighborhood of all the vertices of the Klee-Minty cube in the same order as the simplex method does.

The pivot algorithm and interior point algorithm are two diverging and competitive types of algorithms for solving linear programming problems. One of the main disadvantages of pivot algorithms is that they suffer from problems especially stalling, arising from degeneracy. Interior point methods, although not affected by degeneracy, require a purification procedure to obtain an exact optimal solution. This paper derives a new general-purpose solution algorithm, called combined projected gradient algorithm with the proof that it converges successfully. The new algorithm combines pivot and interior point techniques naturally. It in fact not only reduces the possibility of difficulty arising from degeneracy, but also reaches a pair of exact primal and dual optimal solutions. Numerical results on a group of NETLIB problems are encouraging.

We generalize new criss-cross type algorithms for linear complementarity problems (LCPs) given with sufficient matrices. Most LCP solvers require a priori information about the input matrix. The sufficiency of a matrix is hard to be checked (no polynomial time method is known). Our algorithm is similar to Zhang's linear programming and Akkeles¸, Balogh and Illes's criss-cross type algorithm for LCP-QP problems. We modify our basic algorithm in such a way that it can start with any matrix M, without having any information about the properties of the matrix (sufficiency, bisymmetry, positive definiteness, etc.) in advance. Even in this case, our algorithm terminates with one of the following cases in a finite number of steps: it solves the LCP problem, it solves its dual problem or it gives a certificate that the input matrix is not sufficient, thus cycling can occur. Although our algorithm is more general than that of Akkeles¸, Balogh and Illes's, the finiteness proof has been simplified. Furthermore, the ...

A method for solving single- and multi-objective probabilistic linear programming problems with a joint constraint is presented. It is assumed that the parameters in the probabilistic linear programming problems are random variables, and the probabilistic problem is converted to an equivalent deterministic mathematical programming problem. In this paper the parameters are generally considered as normal and log-normal random variables. A non-linear programming method is used to solve the single-objective deterministic problem, and a fuzzy programming method is used to solve the multi-objective deterministic problem. Finally, a numerical example is presented to illustrate the methodology.

The out-of-kilter algorithm finds a minimum cost assignment of flows to a network defined in terms of one-way arcs, each with upper and lower bounds on flow, and a cost. It is a mathematical programming algorithm which exploits the network structure of the data. The objective function, being the sum taken over all the arcs of the products, cost×flow, is linear. The algorithm is applied in a new way to minimise a series of linear functions in a heuristic method to reduce the value of a non-convex quadratic function which is a measure of traffic congestion. The coefficients in these linear functions are chosen in a way which avoids one of the pitfalls occurring when Beale's method is applied to such a quadratic function. The method does not guarantee optimality but has produced optimal results with networks small enough for an integer linear programming method to be feasible.

This paper deals with the problem of stabilizing linear discrete-time systems under state and control linear constraints using linear programming techniques. Linear state constraints describe a polyhedron in the state space so that the problem considered is to make such a polyhedron positively invariant while the control does not violate its constraints. For this, necessary and sufficient conditions are given for the existence of a solution of the problem in terms of polyhedron's vertices and directions. These conditions are described by a set of linear constraints and, following the approach introduced by Vassilaki et al. , they can be solved using linear programming techniques. The objective function proposed here turns out to be a natural one when describing the constraints in terms of polyhedron's vertices and directions.

A hybrid ‘dynamic programming/depth-first search’ algorithm has been developed to solve non-linear integer programming problems arising in the reliability optimization of redundancy allocation. Initially, the technique solves the knapsack relaxation of the original mathematical programming problem using dynamic programming. Then, all solutions in some range of the relaxation problem are obtained via an enumerative depth-first search technique. The solutions are ranked and the optimal solution is given by the best one that satisfies the remaining constraints of the given problem. Computational complexity of the algorithm is also discussed. The salient features of our hybrid algorithm are its simplicity and ease of programming. Our algorithm also has an advantage over the traditional Lagrangian and surrogate dual approaches. It does not have to deal with the issue of ‘duality gap’ as in classical dual approaches, which is responsible for the failure to identify optimal solutions to the primal integer optimi...

Evolutionary algorithms are promising candidates for obtaining the global optimum. Hybrid differential evolution is one or the evolutionary algorithms, which has been successfully applied to many real-world nonlinear programming problems. This paper proposes a co-evolutionary hybrid differential evolution to solve mixed-integer nonlinear programming (MINLP) problems. The key ingredients of the algorithm consist of an integer-valued variable evolution and a real-valued variable co-evolution, so that the algorithm can be used to solve MINLP problems or pure integer programming problems. Furthermore, the algorithm combines a local search heuristic (called acceleration) and a widespread search heuristic (called migration) to promote the search for a global optimum. Some numerical examples are tested to illustrate the performance of the proposed algorithm. Numerical examples show that the proposed algorithm converges to better solutions than the conventional MINLP optimization methods

A procedure for solving stochastic two-stage programming problems has been developed. The approach consists of genetic algorithm optimization with point estimate procedures. It has several advantages over traditional methods, such as evaluating function values only, no continuous or gradient requirements and it can solve integer or continuous problems. To improve the performance of the method, a modification of a standard genetic algorithm is suggested and coded. Point estimation methods are used to efficiently evaluate the second stage expected value objective function. Finally, the overall procedure is applied to several linear and nonlinear problems

The efficient set of a multiple objective linear programming problem is usually nonconvex, hence linear optimization over the efficient set problem is classified as a nonlinear optimization problem. This paper presents a modified interior point algorithm for solving linear optimization over the efficient set problems. Using computational experiments, we show that the modified algorithm provides an effective and accurate approach for solving the linear optimization over the efficient set problem.

In this paper, a hybrid, two-stage algorithm, namely, Foraging-directed Adaptive Linear Programming is introduced. The second stage, Adaptive Linear Programming, has been presented in detail elsewhere. Hence, in this paper, the focus is on the first stage which is based on the notion of animals foraging for food in the wild. Two problems are included. In the first, significantly better solutions than previous studies are found and global opti-mality can be proven. In the second, more complex problem, finding a global optimum is difficult, but various solutions that may not be optimal but are as good or better than previous reports can be found. Therefore, depending upon the complexity of a given problem, the algorithm presented is able to find optimal solutions or identify satisficing solutions or regions where good solutions are located.

In this paper we establish an equivalence between the solutions of a generalized linear complementarity problem and efficient points of a related nonlinear (quadratic) multiobjective programming problem. An algorithm based on multiple objective programming approach is presented to solve generalized linear complementarity problem

The authors propose a new algorithm for computing l 1 central estimators of linear parameters. A theorem is given saying that such an estimator can be computed by solving a group of linear programming problems with a common feasible region. An overall simplex algorithm for solving such a group of linear programming problems is suggested, which may avoid repeated search of any vertex of the common feasible region. These results may effectively reduce the computation of l 1 central estimators of linear parameters.

Motivated by the successful application of mathematical programming techniques to difficult machine learning problems, we seek solutions of concave minimization problems over polyhedral sets with minimum number of nonzero components. We that if such problems have a solution, they have a vertex solution with a minimal number of zeros. This includes linear programs and general linear complementarity problems. A smooth concave exponential approximation to a step function solves the minimumsupport problem exactly for a finite value of the smoothing parameter. A fast finite linear-programming-based iterative method terminates at a stationary point, which for many important real world problems provides very useful answers. Utilizing the complementarity property of linear programs and linear complementarity problems, an upper bound on the number of nonzeros can be obtained by solving a single convex minimization problem on a polyhedral set

Minimax and L 1-norm optimization problems are well-known in nonlinear programming. These problems are widely applied in different areas of science, technology and economy. This paper presents a new algorithm for the solution of these problems. The basic constructions of the algorithm are theoretically justified and proved. The results of numerical experiments are also included in the paper

This note is aimed to correct the strong duality theorem of previous paper regarding the continuous-time linear programming problems. The argument presented in the previous paper can only be used to prove the case of piecewise continuous functions in which the discontinuities are the left-continuities.

Multiobjective linear programming algorithms are typically based on value maximization. However, there is a growing body of experimental evidence showing that decision maker behavior is inconsistent with value maximization. Tversky and Simonson provide an alternative model for problems with a discrete set of choices. Their model, called the componential context model, has been shown to capture observed decision maker behavior. In this paper, an interactive multiobjective linear programming algorithm is developed which follows the rationale of Tversky and Simonson. The algorithm is illustrated with an example solved using standard linear programming software. Finally, an interactive decision support system based on this algorithm is developed to field test the usefulness of the algorithm. Results show that this algorithm compares favorably with an established algorithm in the field.

In this paper, we discuss the application of the ABS algorithm to the simplex method, the dual simplex method, the linear complementary problem. We consider the ABS formulation of the stopping criterion, the search direction, the minimal rule to determine the vectors entering and leaving the basis matrix and the updating of the Abaffian matrix after a basis vector exchange. The Lemke algorithm for the LCP problem is reformulated in terms of the ABS procedure

In this paper the ABS algorithm with singular initial matrix is considered and used to construct an active set algorithm for solving the linear programming prbblem. We prove that this active set algorithm is reduced to the simplex algorithm whep it starts from a vertex or it meets a vertex

We present an interior Multiple Objective Linear Programming (MOLP) algorithm based on the path-following primal-dual algorithm. In contrast to the simplex algorithm, which generates a solution path on the exterior of the constraints polytope by following its vertices, the path-following primal-dual algorithm moves through the interior of the polytope. Interior algorithms lend themselves to modifications capable of addressing MOLP problems in a way that is quite different from current solution approaches. In addition, moving through the interior of the polytope results in a solution approach that is less sensitive to problem size than simplex-based MOLP algorithms. The modification of the interior single-objective algorithm to MOLP problems, as presented here, is accomplished by combining the step direction vectors generated by applying the single-objective algorithm to each of the cost vectors into a combined direction vector along which we step from the current iterate to the next iterate.

The partially-linear models can be successfully applied in economics and technology, which increases the interest in them. Every continuous partially-linear function with a finite number of linear parts can be presented by means of linear functions and maximum of the functions. We considear graph interpretation of this optimization problem. Partially-linear problems are commonly not only nondifferentiable but nonconvex, which makes their solution by standard optimization methods difficult. In this work we give the necessary and sufficient conditions for local optimality. An algorithm for solving such problems, based on the constructive optimization methods is suggested

In this paper a method for solving perfect systems of linear inequalities is presented. It is based on selecting and removing inessential constraints. This method is a strongly polynomial one for the class of systems of inequalities with a constant difference between the number of constraints and the number of variables.

An algorithm for addressing multiple objective linear programming (MOLP) problems is presented. The algorithm modifies the path-following primal-dual algorithm to MOLP problems by using the single objective algorithm to generate interior search directions and later combine them to derive a single direction along which to step to the next iterate. Combining the different interior search directions is done by interacting with a Decision Maker (DM) to obtain locally-relevant preference information for the value vectors along these directions. This preference information is then used to derive an approximation to the gradient of an implicity-known utility function, and using a projection of this gradient provides a direction gradient of an implicitly-known utility function, and using a projection of this gradient provides a direction vector along which we step to the next iterate. At each iteration the algorithm also generates boundary points that aid in deriving the combined search direction. We refer to the...

In this paper, we propose an “inexact solution” approach to deal with linear semi-infinite programming problems with finitely many variables and infinitely many constraints over a compact metric space. A general convergence proof with some numerical examples are given and the advantages of using this approach are discussed

In this paper, we study a general path-following model for linear programming. Generalized barrier functions for linear programming are defined to create an ideal interior trajectory for path-following. The key components required for a generic algorithm, including the moving directions and criterion of closeness are discussed. A generic path-following algorithm is proposed and sufficient conditions for convergence and polynomality proofs are derived.