On the basis of the formulations of the logarithmic barrier function and the idea of following the path of minimizers for the logarithmic barrier family of problems the so called "centralpath" for linear pro...On the basis of the formulations of the logarithmic barrier function and the idea of following the path of minimizers for the logarithmic barrier family of problems the so called "centralpath" for linear programming, we propose a new framework of primal-dual infeasible interiorpoint method for linear programming problems. Without the strict convexity of the logarithmic barrier function, we get the following results: (a) if the homotopy parameterμcan not reach to zero,then the feasible set of these programming problems is empty; (b) if the strictly feasible set is nonempty and the solution set is bounded, then for any initial point x, we can obtain a solution of the problems by this method; (c) if the strictly feasible set is nonempty and the solution set is unbounded, then for any initial point x, we can obtain a (?)-solution; and(d) if the strictly feasible set is nonempty and the solution set is empty, then we can get the curve x(μ), which towards to the generalized solutions.展开更多
In this paper, primal-dual interior-point algorithm with dynamic step size is implemented for linear programming （LP） problems. The algorithms are based on a few kernel functions, including both serf-regular functio...In this paper, primal-dual interior-point algorithm with dynamic step size is implemented for linear programming （LP） problems. The algorithms are based on a few kernel functions, including both serf-regular functions and non-serf-regular ones. The dynamic step size is compared with fixed step size for the algorithms in inner iteration of Newton step. Numerical tests show that the algorithms with dynaraic step size are more efficient than those with fixed step size.展开更多
In this paper, we design a primal-dual interior-point algorithm for linear optimization. Search directions and proximity function are proposed based on a new kernel function which includes neither growth term nor barr...In this paper, we design a primal-dual interior-point algorithm for linear optimization. Search directions and proximity function are proposed based on a new kernel function which includes neither growth term nor barrier term. Iteration bounds both for large-and small-update methods are derived, namely, O（nlog（n/c）） and O（√nlog（n/ε））. This new kernel function has simple algebraic expression and the proximity function has not been used before. Analogous to the classical logarithmic kernel function, our complexity analysis is easier than the other pri- mal-dual interior-point methods based on logarithmic barrier functions and recent kernel functions.展开更多
Optimal adjustment algorithm for p coordinates is a generalization of the optimal pair adjustment algorithm for linear programming, which in turn is based on von Neumann’s algorithm. Its main advantages are simplicit...Optimal adjustment algorithm for p coordinates is a generalization of the optimal pair adjustment algorithm for linear programming, which in turn is based on von Neumann’s algorithm. Its main advantages are simplicity and quick progress in the early iterations. In this work, to accelerate the convergence of the interior point method, few iterations of this generalized algorithm are applied to the Mehrotra’s heuristic, which determines the starting point for the interior point method in the PCx software. Computational experiments in a set of linear programming problems have shown that this approach reduces the total number of iterations and the running time for many of them, including large-scale ones.展开更多
A polynomial interior-point algorithm is presented for monotone linear complementarity problem （MLCP） based on a class of kernel functions with the general barrier term, which are called general kernel functions. Un...A polynomial interior-point algorithm is presented for monotone linear complementarity problem （MLCP） based on a class of kernel functions with the general barrier term, which are called general kernel functions. Under the mild conditions for the barrier term, the complexity bound of algorithm in terms of such kernel function and its derivatives is obtained. The approach is actually an extension of the existing work which only used the specific kernel functions for the MLCP.展开更多
The choice of self-concordant functions is the key to efficient algorithms for linear and quadratic convex optimizations, which provide a method with polynomial-time iterations to solve linear and quadratic convex opt...The choice of self-concordant functions is the key to efficient algorithms for linear and quadratic convex optimizations, which provide a method with polynomial-time iterations to solve linear and quadratic convex optimization problems. The parameters of a self-concordant barrier function can be used to compute the complexity bound of the proposed algorithm. In this paper, it is proved that the finite barrier function is a local self-concordant barrier function. By deriving the local values of parameters of this barrier function, the desired complexity bound of an interior-point algorithm based on this local self-concordant function for linear optimization problem is obtained. The bound matches the best known bound for small-update methods.展开更多
In this paper, motivated by the complexity results of Interior Point Methods （IPMs） for Linear Optimization （LO） based on kernel functions, we present a polynomial time IPM for solving P.（a）-linear complementari...In this paper, motivated by the complexity results of Interior Point Methods （IPMs） for Linear Optimization （LO） based on kernel functions, we present a polynomial time IPM for solving P.（a）-linear complementarity problem, using a new class of kernel functions. The special case of our new class was considered earlier for LO by Y. Q. Bai et al. in 2004. Using some appealing properties of the new class, we show that the iteration bound for IPMs matches the so far best known theoretical iteration bound for both large and small updates by choosing special values for the parameters of the new class.展开更多
This work presents a new methodology based on Linear Programming (LP) to tune Proportional-Integral-Derivative (PID) control parameters. From a specification of a desired output time domain of the plant, a linear opti...This work presents a new methodology based on Linear Programming (LP) to tune Proportional-Integral-Derivative (PID) control parameters. From a specification of a desired output time domain of the plant, a linear optimization system is proposed to adjust the PID controller leading the output signal to stable operation condition with minimum oscillations. The constraint set used in the optimization process is defined by using numerical integration approach. The generated optimization problem is convex and easily solved using an interior point algorithm. Results obtained using familiar plants from literature have shown that the proposed linear programming problem is very effective for tuning PID controllers.展开更多
1 Introduction Many linear programming models represent large, complex systems consisting of independent subsystems coupled by a common constraint. Such problems arise in industrial and economic planning involved deci...1 Introduction Many linear programming models represent large, complex systems consisting of independent subsystems coupled by a common constraint. Such problems arise in industrial and economic planning involved decision making, resources assignment, production and operation management, and so on. Many’ methods have been proposed for solving the problems with special structure. The decomposition principle of Dantzig-Wolfe leads展开更多
In this paper we present an infeasible-interior-point algorithm, based on a new wide neighbourhood N（ t1, t2, η）, for linear programming over symmetric cones. We treat the classical Newton direction as the sum of t...In this paper we present an infeasible-interior-point algorithm, based on a new wide neighbourhood N（ t1, t2, η）, for linear programming over symmetric cones. We treat the classical Newton direction as the sum of two other directions. We prove that if these two directions are equipped with different and appropriate step sizes, then the new algorithm has a polynomial convergence for the commutative class of search directions. In particular, the complexity bound is O（r1.5 log ε-1） for the Nesterov-Todd （NT） direction, and O（r2 log ε-1） for the xs and sx directions, where r is the rank of the associated Euclidean Jordan algebra and ε 〉 0 is the required precision. If starting with a feasible point （x0, y0, s0） in N（t1, t2, η）, the complexity bound is O（ √ r log ε-1） for the NT direction, and O（r log ε-1） for the xs and sx directions. When the NT search direction is used, we get the best complexity bound of wide neighborhood interior-point algorithm for linear programming over symmetric cones.展开更多
文摘On the basis of the formulations of the logarithmic barrier function and the idea of following the path of minimizers for the logarithmic barrier family of problems the so called "centralpath" for linear programming, we propose a new framework of primal-dual infeasible interiorpoint method for linear programming problems. Without the strict convexity of the logarithmic barrier function, we get the following results: (a) if the homotopy parameterμcan not reach to zero,then the feasible set of these programming problems is empty; (b) if the strictly feasible set is nonempty and the solution set is bounded, then for any initial point x, we can obtain a solution of the problems by this method; (c) if the strictly feasible set is nonempty and the solution set is unbounded, then for any initial point x, we can obtain a (?)-solution; and(d) if the strictly feasible set is nonempty and the solution set is empty, then we can get the curve x(μ), which towards to the generalized solutions.
基金Project supported by Dutch Organization for Scientific Research(Grant No .613 .000 .010)
文摘In this paper, primal-dual interior-point algorithm with dynamic step size is implemented for linear programming （LP） problems. The algorithms are based on a few kernel functions, including both serf-regular functions and non-serf-regular ones. The dynamic step size is compared with fixed step size for the algorithms in inner iteration of Newton step. Numerical tests show that the algorithms with dynaraic step size are more efficient than those with fixed step size.
基金Supported by the Natural Science Foundation of Hubei Province (2008CDZD47)
文摘In this paper, we design a primal-dual interior-point algorithm for linear optimization. Search directions and proximity function are proposed based on a new kernel function which includes neither growth term nor barrier term. Iteration bounds both for large-and small-update methods are derived, namely, O（nlog（n/c）） and O（√nlog（n/ε））. This new kernel function has simple algebraic expression and the proximity function has not been used before. Analogous to the classical logarithmic kernel function, our complexity analysis is easier than the other pri- mal-dual interior-point methods based on logarithmic barrier functions and recent kernel functions.
文摘Optimal adjustment algorithm for p coordinates is a generalization of the optimal pair adjustment algorithm for linear programming, which in turn is based on von Neumann’s algorithm. Its main advantages are simplicity and quick progress in the early iterations. In this work, to accelerate the convergence of the interior point method, few iterations of this generalized algorithm are applied to the Mehrotra’s heuristic, which determines the starting point for the interior point method in the PCx software. Computational experiments in a set of linear programming problems have shown that this approach reduces the total number of iterations and the running time for many of them, including large-scale ones.
基金supported by the National Natural Science Foundation of China (Grant No.10771133)the Shanghai Pujiang Program (Grant No.06PJ14039)
文摘A polynomial interior-point algorithm is presented for monotone linear complementarity problem （MLCP） based on a class of kernel functions with the general barrier term, which are called general kernel functions. Under the mild conditions for the barrier term, the complexity bound of algorithm in terms of such kernel function and its derivatives is obtained. The approach is actually an extension of the existing work which only used the specific kernel functions for the MLCP.
基金supported by the National Natural Science Foundation of China (Grant No.10771133)the Shanghai Leading Academic Discipline Project (Grant No.S30101)the Research Foundation for the Doctoral Program of Higher Education (Grant No.200802800010)
文摘The choice of self-concordant functions is the key to efficient algorithms for linear and quadratic convex optimizations, which provide a method with polynomial-time iterations to solve linear and quadratic convex optimization problems. The parameters of a self-concordant barrier function can be used to compute the complexity bound of the proposed algorithm. In this paper, it is proved that the finite barrier function is a local self-concordant barrier function. By deriving the local values of parameters of this barrier function, the desired complexity bound of an interior-point algorithm based on this local self-concordant function for linear optimization problem is obtained. The bound matches the best known bound for small-update methods.
基金Supported by a grant from IPM (Grant No. 8890027)
文摘In this paper, motivated by the complexity results of Interior Point Methods （IPMs） for Linear Optimization （LO） based on kernel functions, we present a polynomial time IPM for solving P.（a）-linear complementarity problem, using a new class of kernel functions. The special case of our new class was considered earlier for LO by Y. Q. Bai et al. in 2004. Using some appealing properties of the new class, we show that the iteration bound for IPMs matches the so far best known theoretical iteration bound for both large and small updates by choosing special values for the parameters of the new class.
文摘This work presents a new methodology based on Linear Programming (LP) to tune Proportional-Integral-Derivative (PID) control parameters. From a specification of a desired output time domain of the plant, a linear optimization system is proposed to adjust the PID controller leading the output signal to stable operation condition with minimum oscillations. The constraint set used in the optimization process is defined by using numerical integration approach. The generated optimization problem is convex and easily solved using an interior point algorithm. Results obtained using familiar plants from literature have shown that the proposed linear programming problem is very effective for tuning PID controllers.
基金Project supported in part by the National Natural Science Foundation of China
文摘1 Introduction Many linear programming models represent large, complex systems consisting of independent subsystems coupled by a common constraint. Such problems arise in industrial and economic planning involved decision making, resources assignment, production and operation management, and so on. Many’ methods have been proposed for solving the problems with special structure. The decomposition principle of Dantzig-Wolfe leads
基金Supported by the National Natural Science Foundation of China(No.11471102)the Key Basic Research Foundation of the Higher Education Institutions of Henan Province(No.16A110012)
文摘In this paper we present an infeasible-interior-point algorithm, based on a new wide neighbourhood N（ t1, t2, η）, for linear programming over symmetric cones. We treat the classical Newton direction as the sum of two other directions. We prove that if these two directions are equipped with different and appropriate step sizes, then the new algorithm has a polynomial convergence for the commutative class of search directions. In particular, the complexity bound is O（r1.5 log ε-1） for the Nesterov-Todd （NT） direction, and O（r2 log ε-1） for the xs and sx directions, where r is the rank of the associated Euclidean Jordan algebra and ε 〉 0 is the required precision. If starting with a feasible point （x0, y0, s0） in N（t1, t2, η）, the complexity bound is O（ √ r log ε-1） for the NT direction, and O（r log ε-1） for the xs and sx directions. When the NT search direction is used, we get the best complexity bound of wide neighborhood interior-point algorithm for linear programming over symmetric cones.
