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.展开更多
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.展开更多
In this paper, an Improved Affine-Scaling Interior Point Algorithm for Linear Programming has been proposed. Computational results of selected practical problems affirming the proposed algorithm have been provided. Th...In this paper, an Improved Affine-Scaling Interior Point Algorithm for Linear Programming has been proposed. Computational results of selected practical problems affirming the proposed algorithm have been provided. The proposed algorithm is accurate, faster and therefore reduces the number of iterations required to obtain an optimal solution of a given Linear Programming problem as compared to the already existing Affine-Scaling Interior Point Algorithm. The algorithm can be very useful for development of faster software packages for solving linear programming problems using the interior-point methods.展开更多
By attacking the linear programming problems from their dual side,a new general algorithm for linear programming is developed.At each iteration,the algorithm finds a feasible descent search direction by handling a lea...By attacking the linear programming problems from their dual side,a new general algorithm for linear programming is developed.At each iteration,the algorithm finds a feasible descent search direction by handling a least square problem associated with the dual system,using QR decomposition technique.The new method is a combination of pivot method and interior-point method.It in fact not only reduces the possibility of difficulty arising from degeneracy,but also has the same advantages as pivot method in warm-start to resolve linear programming problems.Numerical results of a group of randomly constructed problems are very encouraging.展开更多
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.展开更多
The discrete complex cubic Ginzburg-Landau equation is an important model to describe a number of physical systems such as Taylor and frustrated vortices in hydrodynamics and semiconductor laser arrays in optics. In t...The discrete complex cubic Ginzburg-Landau equation is an important model to describe a number of physical systems such as Taylor and frustrated vortices in hydrodynamics and semiconductor laser arrays in optics. In this paper, the exact solutions of the discrete complex cubic Ginzburg-Landau equation are derived using homogeneous balance principle and the GI/G-expansion method, and the linear stability of exact solutions is discussed.展开更多
We establish polynomial complexity corrector algorithms for linear programming over bounds of the Mehrotra-type predictor- symmetric cones. We first slightly modify the maximum step size in the predictor step of the s...We establish polynomial complexity corrector algorithms for linear programming over bounds of the Mehrotra-type predictor- symmetric cones. We first slightly modify the maximum step size in the predictor step of the safeguard based Mehrotra-type algorithm for linear programming, that was proposed by Salahi et al. Then, using the machinery of Euclidean Jordan algebras, we extend the modified algorithm to symmetric cones. Based on the Nesterov-Todd direction, we obtain O（r log ε1） iteration complexity bound of this algorithm, where r is the rank of the Jordan algebras and ε is the required precision. We also present a new variant of Mehrotra-type algorithm using a new adaptive updating scheme of centering parameter and show that this algorithm enjoys the same order of complexity bound as the safeguard algorithm. We illustrate the numerical behaviour of the methods on some small examples.展开更多
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.展开更多
In this paper,a class of polynomial interior-point algorithms for P_(∗)(κ)-horizontal linear complementarity problems based on a newparametric kernel function is presented.The new parametric kernel function is used b...In this paper,a class of polynomial interior-point algorithms for P_(∗)(κ)-horizontal linear complementarity problems based on a newparametric kernel function is presented.The new parametric kernel function is used both for determining the search directions and for measuring the distance between the given iterate and theμ-center of the problem.We derive the complexity analysis for the algorithm,both with large and small updates.展开更多
单一线性锥规划方法求解最优潮流(optimal power flow,OPF)问题时,锥变量仅局限于某个单一锥集合,使得锥规划模型的构造缺乏灵活性,建模难度较大。为此,基于混合线性锥规划(mixed cone linear programming,MCLP)方法,提出了求解OPF问题...单一线性锥规划方法求解最优潮流(optimal power flow,OPF)问题时,锥变量仅局限于某个单一锥集合,使得锥规划模型的构造缺乏灵活性,建模难度较大。为此,基于混合线性锥规划(mixed cone linear programming,MCLP)方法,提出了求解OPF问题的3种MCLP模型—MCLP-OPF。该模型采用不同的锥变量来构建原始OPF问题的锥松弛模型,锥变量可同时取自半正定锥、二阶锥和非负多面体锥。引入MCLP-OPF问题的可行域"厚度",并根据该"厚度"大小选择直接内点法或齐次自对偶(homogeneous self-dual,HSD)内点法求解。从C-703节点等6个测试系统的仿真结果可以看到,相较于半定规划法,MCLP-OPF提高了锥规划方法的建模效率、求解效率和存储效率,更适于求解大规模电力系统问题。展开更多
文摘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.
基金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.
文摘In this paper, an Improved Affine-Scaling Interior Point Algorithm for Linear Programming has been proposed. Computational results of selected practical problems affirming the proposed algorithm have been provided. The proposed algorithm is accurate, faster and therefore reduces the number of iterations required to obtain an optimal solution of a given Linear Programming problem as compared to the already existing Affine-Scaling Interior Point Algorithm. The algorithm can be very useful for development of faster software packages for solving linear programming problems using the interior-point methods.
文摘By attacking the linear programming problems from their dual side,a new general algorithm for linear programming is developed.At each iteration,the algorithm finds a feasible descent search direction by handling a least square problem associated with the dual system,using QR decomposition technique.The new method is a combination of pivot method and interior-point method.It in fact not only reduces the possibility of difficulty arising from degeneracy,but also has the same advantages as pivot method in warm-start to resolve linear programming problems.Numerical results of a group of randomly constructed problems are very encouraging.
基金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 in part by the Basic Science and the Front Technology Research Foundation of Henan Province of China under Grant No.092300410179the Doctoral Scientific Research Foundation of Henan University of Science and Technology under Grant No.09001204
文摘The discrete complex cubic Ginzburg-Landau equation is an important model to describe a number of physical systems such as Taylor and frustrated vortices in hydrodynamics and semiconductor laser arrays in optics. In this paper, the exact solutions of the discrete complex cubic Ginzburg-Landau equation are derived using homogeneous balance principle and the GI/G-expansion method, and the linear stability of exact solutions is discussed.
基金Supported by the National Natural Science Foundation of China(11471102,61301229)Supported by the Natural Science Foundation of Henan University of Science and Technology(2014QN039)
文摘We establish polynomial complexity corrector algorithms for linear programming over bounds of the Mehrotra-type predictor- symmetric cones. We first slightly modify the maximum step size in the predictor step of the safeguard based Mehrotra-type algorithm for linear programming, that was proposed by Salahi et al. Then, using the machinery of Euclidean Jordan algebras, we extend the modified algorithm to symmetric cones. Based on the Nesterov-Todd direction, we obtain O（r log ε1） iteration complexity bound of this algorithm, where r is the rank of the Jordan algebras and ε is the required precision. We also present a new variant of Mehrotra-type algorithm using a new adaptive updating scheme of centering parameter and show that this algorithm enjoys the same order of complexity bound as the safeguard algorithm. We illustrate the numerical behaviour of the methods on some small examples.
基金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.
文摘In this paper,a class of polynomial interior-point algorithms for P_(∗)(κ)-horizontal linear complementarity problems based on a newparametric kernel function is presented.The new parametric kernel function is used both for determining the search directions and for measuring the distance between the given iterate and theμ-center of the problem.We derive the complexity analysis for the algorithm,both with large and small updates.
文摘单一线性锥规划方法求解最优潮流(optimal power flow,OPF)问题时,锥变量仅局限于某个单一锥集合,使得锥规划模型的构造缺乏灵活性,建模难度较大。为此,基于混合线性锥规划(mixed cone linear programming,MCLP)方法,提出了求解OPF问题的3种MCLP模型—MCLP-OPF。该模型采用不同的锥变量来构建原始OPF问题的锥松弛模型,锥变量可同时取自半正定锥、二阶锥和非负多面体锥。引入MCLP-OPF问题的可行域"厚度",并根据该"厚度"大小选择直接内点法或齐次自对偶(homogeneous self-dual,HSD)内点法求解。从C-703节点等6个测试系统的仿真结果可以看到,相较于半定规划法,MCLP-OPF提高了锥规划方法的建模效率、求解效率和存储效率,更适于求解大规模电力系统问题。
