In this paper, we present a large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function. The proposed function is strongly convex. It is not self-regular functi...In this paper, we present a large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function. The proposed function is strongly convex. It is not self-regular function and also the usual logarithmic function. The goal of this paper is to investigate such a kernel function and show that the algorithm has favorable complexity bound in terms of the elegant analytic properties of the kernel function. The complexity bound is shown to be O(√n(logn)2 log e/n). This bound is better than that by the classical primal-dual interior-point methods based on logarithmic barrier function and in optimization fields. Some computational results recent kernel functions introduced by some authors have been provided.展开更多
In this paper, a new primal-dual interior-point algorithm for convex quadratic optimization (CQO) based on a kernel function is presented. The proposed function has some properties that are easy for checking. These ...In this paper, a new primal-dual interior-point algorithm for convex quadratic optimization (CQO) based on a kernel function is presented. The proposed function has some properties that are easy for checking. These properties enable us to improve the polynomial complexity bound of a large-update interior-point method (IPM) to O(√n log nlog n/e), which is the currently best known polynomial complexity bound for the algorithm with the large-update method. Numerical tests were conducted to investigate the behavior of the algorithm with different parameters p, q and θ, where p is the growth degree parameter, q is the barrier degree of the kernel function and θ is the barrier update parameter.展开更多
A class of polynomial primal-dual interior-point algorithms for second-order cone optimization based on a new parametric kernel function, with parameters p and q, is presented. Its growth term is between linear and qu...A class of polynomial primal-dual interior-point algorithms for second-order cone optimization based on a new parametric kernel function, with parameters p and q, is presented. Its growth term is between linear and quadratic. Some new tools for the analysis of the algorithms are proposed. The complexity bounds of O(√Nlog N log N/ε) for large-update methods and O(√Nlog N/ε) for smallupdate methods match the best known complexity bounds obtained for these methods. Numerical tests demonstrate the behavior of the algorithms for different results of the parameters p and q.展开更多
This article describes numerical simulation of gas pipeline network operation using high-accuracy computational fluid dynamics (CFD) simulators of the modes of gas mixture transmission through long, multi-line pipelin...This article describes numerical simulation of gas pipeline network operation using high-accuracy computational fluid dynamics (CFD) simulators of the modes of gas mixture transmission through long, multi-line pipeline systems (CFD-simulator). The approach used in CFD-simulators for modeling gas mixture transmission through long, branched, multi-section pipelines is based on tailoring the full system of fluid dynamics equations to conditions of unsteady, non-isothermal processes of the gas mixture flow. Identification, in a CFD-simulator, of safe parameters for gas transmission through compressor stations amounts to finding the interior points of admissible sets described by systems of nonlinear algebraic equalities and inequalities. Such systems of equalities and inequalities comprise a formal statement of technological, design, operational and other constraints to which operation of the network equipment is subject. To illustrate the practicability of the method of numerical simulation of a gas transmission network, we compare computation results and gas flow parameters measured on-site at the gas transmission enter-prise.展开更多
Recent experience has shown that interior-point methods using a log barrierapproach are far superior to classical simplex methods for computing solutions to large parametricquantile regression problems. In many large ...Recent experience has shown that interior-point methods using a log barrierapproach are far superior to classical simplex methods for computing solutions to large parametricquantile regression problems. In many large empirical applications, the design matrix has a verysparse structure. A typical example is the classical fixed-effect model for panel data where theparametric dimension of the model can be quite large, but the number of non-zero elements is quitesmall. Adopting recent developments in sparse linear algebra we introduce a modified version of theFrisch-Newton algorithm for quantile regression described in Portnoy and Koenker[28]. The newalgorithm substantially reduces the storage (memory) requirements and increases computational speed.The modified algorithm also facilitates the development of nonparametric quantile regressionmethods. The pseudo design matrices employed in nonparametric quantile regression smoothing areinherently sparse in both the fidelity and roughness penalty components. Exploiting the sparsestructure of these problems opens up a whole range of new possibilities for multivariate smoothingon large data sets via ANOVA-type decomposition and partial linear models.展开更多
Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm for solving linear optimization problems. In this paper we present a new kernel function which yields ...Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm for solving linear optimization problems. In this paper we present a new kernel function which yields an algorithm with the best known complexity bound for both large- and small-update methods.展开更多
In this paper, we establish a theoretical framework of path-following interior point al- gorithms for the linear complementarity problems over symmetric cones (SCLCP) with the Cartesian P*(κ)-property, a weaker condi...In this paper, we establish a theoretical framework of path-following interior point al- gorithms for the linear complementarity problems over symmetric cones (SCLCP) with the Cartesian P*(κ)-property, a weaker condition than the monotonicity. Based on the Nesterov-Todd, xy and yx directions employed as commutative search directions for semidefinite programming, we extend the variants of the short-, semilong-, and long-step path-following algorithms for symmetric conic linear programming proposed by Schmieta and Alizadeh to the Cartesian P*(κ)-SCLCP, and particularly show the global convergence and the iteration complexities of the proposed algorithms.展开更多
In the present paper we present a class of polynomial primal-dual interior-point algorithms for semidefmite optimization based on a kernel function. This kernel function is not a so-called self-regular function due to...In the present paper we present a class of polynomial primal-dual interior-point algorithms for semidefmite optimization based on a kernel function. This kernel function is not a so-called self-regular function due to its growth term increasing linearly. Some new analysis tools were developed which can be used to deal with complexity "analysis of the algorithms which use analogous strategy in [5] to design the search directions for the Newton system. The complexity bounds for the algorithms with large- and small-update methodswere obtained, namely,O(qn^(p+q/q(P+1)log n/ε and O(q^2√n)log n/ε,respectlvely.展开更多
In this paper, we present neighborhood-following algorithms for linear programming. When the neighborhood is a wide neighborhood, our algorithms are wide neighborhood primal-dual interior point algorithms. If the neig...In this paper, we present neighborhood-following algorithms for linear programming. When the neighborhood is a wide neighborhood, our algorithms are wide neighborhood primal-dual interior point algorithms. If the neighborhood degenerates into the central path, our algorithms also degenerate into path-following algorithms. We prove that our algorithms maintain the O9√nL) -iteration complexity still, while the classical wide neighborhood primal-dual interior point algorithms have only the O(nL-iteration complexity. We also proved that the algorithms are quadratic convergence if the optimal vertex is nondegenerate. Finally, we show some computational results of our algorithms.展开更多
基金Supported by Natural Science Foundation of Hubei Province of China (Grant No. 2008CDZ047)
文摘In this paper, we present a large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function. The proposed function is strongly convex. It is not self-regular function and also the usual logarithmic function. The goal of this paper is to investigate such a kernel function and show that the algorithm has favorable complexity bound in terms of the elegant analytic properties of the kernel function. The complexity bound is shown to be O(√n(logn)2 log e/n). This bound is better than that by the classical primal-dual interior-point methods based on logarithmic barrier function and in optimization fields. Some computational results recent kernel functions introduced by some authors have been provided.
基金the Foundation of Scientific Research for Selecting and Cultivating Young Excellent University Teachers in Shanghai (Grant No.06XPYQ52)the Shanghai Pujiang Program (Grant No.06PJ14039)
文摘In this paper, a new primal-dual interior-point algorithm for convex quadratic optimization (CQO) based on a kernel function is presented. The proposed function has some properties that are easy for checking. These properties enable us to improve the polynomial complexity bound of a large-update interior-point method (IPM) to O(√n log nlog n/e), which is the currently best known polynomial complexity bound for the algorithm with the large-update method. Numerical tests were conducted to investigate the behavior of the algorithm with different parameters p, q and θ, where p is the growth degree parameter, q is the barrier degree of the kernel function and θ is the barrier update parameter.
文摘A class of polynomial primal-dual interior-point algorithms for second-order cone optimization based on a new parametric kernel function, with parameters p and q, is presented. Its growth term is between linear and quadratic. Some new tools for the analysis of the algorithms are proposed. The complexity bounds of O(√Nlog N log N/ε) for large-update methods and O(√Nlog N/ε) for smallupdate methods match the best known complexity bounds obtained for these methods. Numerical tests demonstrate the behavior of the algorithms for different results of the parameters p and q.
文摘This article describes numerical simulation of gas pipeline network operation using high-accuracy computational fluid dynamics (CFD) simulators of the modes of gas mixture transmission through long, multi-line pipeline systems (CFD-simulator). The approach used in CFD-simulators for modeling gas mixture transmission through long, branched, multi-section pipelines is based on tailoring the full system of fluid dynamics equations to conditions of unsteady, non-isothermal processes of the gas mixture flow. Identification, in a CFD-simulator, of safe parameters for gas transmission through compressor stations amounts to finding the interior points of admissible sets described by systems of nonlinear algebraic equalities and inequalities. Such systems of equalities and inequalities comprise a formal statement of technological, design, operational and other constraints to which operation of the network equipment is subject. To illustrate the practicability of the method of numerical simulation of a gas transmission network, we compare computation results and gas flow parameters measured on-site at the gas transmission enter-prise.
基金This research was partially supported by NSF grant SES-02-40781.
文摘Recent experience has shown that interior-point methods using a log barrierapproach are far superior to classical simplex methods for computing solutions to large parametricquantile regression problems. In many large empirical applications, the design matrix has a verysparse structure. A typical example is the classical fixed-effect model for panel data where theparametric dimension of the model can be quite large, but the number of non-zero elements is quitesmall. Adopting recent developments in sparse linear algebra we introduce a modified version of theFrisch-Newton algorithm for quantile regression described in Portnoy and Koenker[28]. The newalgorithm substantially reduces the storage (memory) requirements and increases computational speed.The modified algorithm also facilitates the development of nonparametric quantile regressionmethods. The pseudo design matrices employed in nonparametric quantile regression smoothing areinherently sparse in both the fidelity and roughness penalty components. Exploiting the sparsestructure of these problems opens up a whole range of new possibilities for multivariate smoothingon large data sets via ANOVA-type decomposition and partial linear models.
基金Supported by National Natural Science Foundation of China (Grant Nos.10771133 and 70871082)Shanghai Leading Academic Discipline Project (Grant No.S30104)
文摘Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm for solving linear optimization problems. In this paper we present a new kernel function which yields an algorithm with the best known complexity bound for both large- and small-update methods.
基金supported by National Natural Science Foundation of China (Grant Nos. 10671010, 70841008)
文摘In this paper, we establish a theoretical framework of path-following interior point al- gorithms for the linear complementarity problems over symmetric cones (SCLCP) with the Cartesian P*(κ)-property, a weaker condition than the monotonicity. Based on the Nesterov-Todd, xy and yx directions employed as commutative search directions for semidefinite programming, we extend the variants of the short-, semilong-, and long-step path-following algorithms for symmetric conic linear programming proposed by Schmieta and Alizadeh to the Cartesian P*(κ)-SCLCP, and particularly show the global convergence and the iteration complexities of the proposed algorithms.
文摘In the present paper we present a class of polynomial primal-dual interior-point algorithms for semidefmite optimization based on a kernel function. This kernel function is not a so-called self-regular function due to its growth term increasing linearly. Some new analysis tools were developed which can be used to deal with complexity "analysis of the algorithms which use analogous strategy in [5] to design the search directions for the Newton system. The complexity bounds for the algorithms with large- and small-update methodswere obtained, namely,O(qn^(p+q/q(P+1)log n/ε and O(q^2√n)log n/ε,respectlvely.
基金This work is partially supported by the National Natural Science Foundation of China(Grant No.19731010)the Knowledge Innovation Program of the Chinese Academy of Sciences.
文摘In this paper, we present neighborhood-following algorithms for linear programming. When the neighborhood is a wide neighborhood, our algorithms are wide neighborhood primal-dual interior point algorithms. If the neighborhood degenerates into the central path, our algorithms also degenerate into path-following algorithms. We prove that our algorithms maintain the O9√nL) -iteration complexity still, while the classical wide neighborhood primal-dual interior point algorithms have only the O(nL-iteration complexity. We also proved that the algorithms are quadratic convergence if the optimal vertex is nondegenerate. Finally, we show some computational results of our algorithms.