A predictor-corrector interior-point algorithm for P ∗ ( κ ) -horizontal linear complementarity problem

We present a predictor-corrector path-following interior-point algorithm for \(P_*(\kappa )\) horizontal linear complementarity problem based on new search directions. In each iteration, the algorithm performs two kinds of steps: a predictor (damped Newton) step and a corrector (full Newton) step. The full Newton-step is generated from an algebraic reformulation of the centering equation, which defines the central path and seeks directions in a small neighborhood of the central path. While the damped Newton step is used to move in the direction of optimal solution and reduce the duality gap. We derive the complexity for the algorithm, which coincides with the best known iteration bound for \(P_*(\kappa )\) -horizontal linear complementarity problems.     

LMI优化的一种原对偶中心路径算法

系统和控制理论中许多重要的问题,都可转化为具有线性目标函数、线性矩阵不等式约束的LMI优化问题,从而使其在数值上易于求解.本文给出一种求解LMI优化问题的原对偶中心路径算法,该算法利用牛顿方法求解中心路径方程得到牛顿系统,并将该牛顿系统对称化以避免得到非对称化的搜索方向.文章详细分析了算法的计算复杂性.     

A full-Newton step interior-point algorithm based on modified Newton direction

The central path plays a very important role in interior-point methods. By an equivalent reformulation of the central path, we obtain a new search direction which targets at a small neighborhood of the central path. For a full-Newton step interior-point algorithm based on this search direction, the complexity bound of the algorithm is the best known for linear optimization.     

A full-Newton step infeasible interior-point algorithm for monotone LCP based on a locally-kernel function

We propose a new full-Newton step infeasible interior-point algorithm for monotone linear complementarity problems based on a simple locally-kernel function. The algorithm uses the simple locally-kernel function to determine the search directions and define the neighborhood of central path. Two types of full-Newton steps are used, feasibility step and centering step. The algorithm starts from strictly feasible iterates of a perturbed problem, on its central path, and feasibility steps find strictly feasible iterates for the next perturbed problem. By using centering steps for the new perturbed problem, we obtain strictly feasible iterates close enough to the central path of the new perturbed problem. The procedure is repeated until an ?-approximate solution is found. We analyze the algorithm and obtain the complexity bound, which coincides with the best-known result for monotone linear complementarity problems.     

Complexity analysis of a full-Newton step interior-point method for linear optimization

This paper concerns a short-update primal-dual interior-point method for linear optimization based on a new search direction. We apply a vector-valued function generated by a univariate function on the nonlinear equation of the system which defines the central path. The common way to obtain the equivalent form of the central path is using the square root function. In this paper we consider a new function formed by the difference of the identity map and the square root function. We apply Newton’s method in order to get the new directions. In spite of the fact that the analysis is more difficult in this case, we prove that the complexity of the algorithm is identical with the one of the best known methods for linear optimization.     

水平线性互补问题的广义中心路径跟踪算法

对水平线性互补问题提出了一种广义中心路径跟踪算法.任意的原始-对偶可行内点均可作为算法的初始点.每步迭代选择“仿射步”与“中心步”的凸组合为新的迭代方向,采用使对偶间隙尽可能减小的最大步长.算法的迭代复杂性为O(√nL).     

二阶锥规划的基于自协调指数核函数的原始-对偶内点算法

基于一个自协调指数核函数, 设计求解二阶锥规划的原始-对偶内点算法. 根据自协调指数核函数的二阶导数与三阶导数的特殊关系, 在求解问题的中心路径时, 用牛顿方向代替了负梯度方向来确定搜索方向. 由于自协调指数核函数不具有``Eligible'性质, 在分析算法的迭代界时, 利用牛顿方法求解目标函数满足自协调性质的无约束优化问题的技术, 估计算法内迭代中自协调指数核函数确定的障碍函数的下降量, 得到原始-对偶内点算法大步校正的迭代界O(2N\frac{\log2N}{\varepsilon}), 这里N是二阶锥的个数. 这个迭代界与线性规划情形下的迭代界一致. 最后, 通过数值算例验证了算法的有效性.     

A Full-Newton Step Infeasible Interior-Point Algorithm Based on Darvay Directions for Linear Optimization

We present a full-Newton step primal-dual infeasible interior-point algorithm based on Darvay’s search directions. These directions are obtained by an equivalent algebraic transformation of the centering equation. The algorithm decreases the duality gap and the feasibility residuals at the same rate. During this algorithm we construct strictly feasible iterates for a sequence of perturbations of the given problem and its dual problem. Each main iteration of the algorithm consists of a feasibility step and some centering steps. The starting point in the first iteration of the algorithm depends on a positive number ξ and it is strictly feasible for a perturbed pair, and feasibility steps find strictly feasible iterate for the next perturbed pair. By using centering steps for the new perturbed pair, we obtain strictly feasible iterate close to the central path of the new perturbed pair. The algorithm finds an ?-optimal solution or detects infeasibility of the given problem. The iteration bound coincides with the best known iteration bound for linear optimization problems.     

Local path-following property of inexact interior methods in nonlinear programming

We study the local behavior of a primal-dual inexact interior point methods for solving nonlinear systems arising from the solution of nonlinear optimization problems or more generally from nonlinear complementarity problems. The algorithm is based on the Newton method applied to a sequence of perturbed systems that follows by perturbation of the complementarity equations of the original system. In case of an exact solution of the Newton system, it has been shown that the sequence of iterates is asymptotically tangent to the central path (Armand and Benoist in Math. Program. 115:199?C222, 2008). The purpose of the present paper is to extend this result to an inexact solution of the Newton system. We give quite general conditions on the different parameters of the algorithm, so that this asymptotic property is satisfied. Some numerical tests are reported to illustrate our theoretical results.     

The Nesterov–Todd Direction and Its Relation to Weighted Analytic Centers

The subject of this paper concerns differential-geometric properties of the Nesterov–Todd search direction for linear optimization over symmetric cones. In particular, we investigate the rescaled asymptotics of the associated flow near the central path. Our results imply that the Nesterov–Todd direction arises as the solution of a Newton system defined in terms of a certain transformation of the primal-dual feasible domain. This transformation has especially appealing properties which generalize the notion of weighted analytic centers for linear programming.     

A New Complexity Analysis for Full-Newton Step Infeasible Interior-Point Algorithm for Horizontal Linear Complementarity Problems

In this paper, we first present a full-Newton step feasible interior-point algorithm for solving horizontal linear complementarity problems. We prove that the full-Newton step to the central path is quadratically convergent. Then, we generalize an infeasible interior-point method for linear optimization to horizontal linear complementarity problems based on new search directions. This algorithm starts from strictly feasible iterates on the central path of a perturbed problem that is produced by a suitable perturbation in the horizontal linear complementarity problem. We use the so-called feasibility steps that find strictly feasible iterates for the next perturbed problem. By using centering steps for the new perturbed problem, we obtain a strictly feasible iterate close enough to the central path of the new perturbed problem. The complexity of the algorithm coincides with the best known iteration bound for infeasible interior-point methods.     

Approximation of low rank solutions for linear quadratic control of partial differential equations

Algebraic Riccati equations (ARE) of large dimension arise when using approximations to design controllers for systems modeled by partial differential equations. We use a modified Newton method to solve the ARE that takes advantage of several special features of these problems. The modified Newton method leads to a right-hand side of rank equal to the number of inputs regardless of the weights. Thus, the resulting Lyapunov equation can be more efficiently solved. The Cholesky-ADI algorithm is used to solve the Lyapunov equation resulting at each step. The algorithm is straightforward to code. Performance is illustrated with a number of standard examples. An example on controlling the deflection of the Euler-Bernoulli beam indicates that for weakly damped problems a low rank solution to the ARE may not exist. Further analysis supports this point.     

A nonsmooth Newton method for variational inequalities,I: Theory

This paper presents a modified damped Newton algorithm for solving variational inequality problems based on formulating this problem as a system of equations using the Minty map. The proposed modified damped-Newton method insures convergence and locally quadratic convergence under the assumption of regularity. Under the assumption ofweak regularity and some mild conditions, the modified algorithm is shown to always create a descent direction and converge to the solution. Hence, this new algorithm is often suitable for many applications where regularity does not hold. Part II of this paper presents the results of extensive computational testing of this new method.Corresponding author.     

A new class of polynomial primal–dual methods for linear and semidefinite optimization

We propose a new class of primal–dual methods for linear optimization (LO). By using some new analysis tools, we prove that the large-update method for LO based on the new search direction has a polynomial complexity of O(n^4/(4+ρ)log(n/ε)) iterations, where ρ∈[0,2] is a parameter used in the system defining the search direction. If ρ=0, our results reproduce the well-known complexity of the standard primal–dual Newton method for LO. At each iteration, our algorithm needs only to solve a linear equation system. An extension of the algorithms to semidefinite optimization is also presented.     

A POLYNOMIAL PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING

This article presents a polynomial predictor-corrector interior-point algorithm for convex quadratic programming based on a modified predictor-corrector interior-point algorithm. In this algorithm, there is only one corrector step after each predictor step, where Step 2 is a predictor step and Step 4 is a corrector step in the algorithm. In the algorithm, the predictor step decreases the dual gap as much as possible in a wider neighborhood of the central path and the corrector step draws iteration points back to a narrower neighborhood and make a reduction for the dual gap. It is shown that the algorithm has O(n~(1/2)L) iteration complexity which is the best result for convex quadratic programming so far.     

Properties of the Central Points in Linear Programming Problems

In this paper we list several useful properties of central points in linear programming problems. We study the logarithmic barrier function, the analytic center and the central path, relating the proximity measures and scaled Euclidean distances defined for the primal and primal–dual problems. We study the Newton centering steps, and show how large the short steps used in path following algorithms can actually be, and what variation can be ensured for the barrier function in each iteration of such methods. We relate the primal and primal–dual Newton centering steps and propose a primal-only path following algorithm for linear programming.     

On the fast solution of a linear system arising in numerical conformal mapping

One step of the Newton method for the discretized Theodorsen equation in conformal mapping requires the solution of a certain 2N×2N system. Application of the Gaussian algorithm costs O(N³) arithmetic operations (a.o.). We present an algorithm which reduces the problem to the solution of three N×N linear Toeplitz systems. These systems can be solved in O(N log²N) a.o. This is also the amount of work required by the whole algorithm.     

A PENALTY TECHNIQUE FOR NONLINEAR COMPLEMENTARITY PROBLEMS

1.IntroductionConsiderthefollowingnonlinearcomplementarityproblemsNCP(F)offindinganxER",suchthatwhereFisamappingfromR"intoitself.ItisanimportantformofthefollowingvariationalinequalityVI(F,X)offindinganxEX,suchthatwhereXCReisaclosedconvexset.WhenX=R7,(1.1)…     

A new infeasible interior-point method based on Darvay’s technique for symmetric optimization

We present a full Nesterov and Todd step primal-dual infeasible interior-point algorithm for symmetric optimization based on Darvay’s technique by using Euclidean Jordan algebras. The search directions are obtained by an equivalent algebraic transformation of the centering equation. The algorithm decreases the duality gap and the feasibility residuals at the same rate. During this algorithm we construct strictly feasible iterates for a sequence of perturbations of the given problem and its dual problem. Each main iteration of the algorithm consists of a feasibility step and some centering steps. The starting point in the first iteration of the algorithm depends on a positive number ξ and it is strictly feasible for a perturbed pair. The feasibility steps find strictly feasible iterates for the next perturbed pair. By using centering steps for the new perturbed pair, we obtain strictly feasible iterates close to the central path of the new perturbed pair. The algorithm finds an ?-optimal solution or detects infeasibility of the given problem. Moreover, we derive the currently best known iteration bound for infeasible interior-point methods.     

Solution of Complementarity Problems via Piecewise Linearization

My master thesis concerns the solution linear complementarity problems (LCP). The Lemke algorithm, the most commonly used algorithm for solving a LCP until this day, was compared with the piecewise Newton method (PLN algorithm). The piecewise Newton method is an algorithm to solve a piecewise linear system on the basis of damped Newton methods. The linear complementarity problem is formulated as a piecewise linear system for the applicability of the PLN algorithm. Then, different application examples will be presented, solved with the PLN algorithm. As a result of the findings (of my master thesis) it can be assumed that – under the condition of coherent orientation – the PLN-algorithm requires fewer iterations to solve a linear complementarity problem than the Lemke algorithm. The coherent orientation for piecewise linear problems corresponds for linear complementarity problems to the P-matrix-property. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)