3,305 research outputs found
Asymptotic behavior of underlying NT paths in interior point methods for monotone semidefinite linear complementarity problems
No full textAn interior point method (IPM) defines a search direction at each interior point of the feasible region. These search directions form a direction field, which in turn gives rise to a system of ordinary differential equations (ODEs). Thus, it is natural to define the underlying paths of the IPM as solutions of the system of ODEs. In Sim and Zhao (Math. Program. Ser. A 110:475–499, 2007), these off-central paths are shown to be well-defined analytic curves and any of their accumulation points is a solution to the given monotone semidefinite linear complementarity problem (SDLCP). In Sim and Zhao (Math. Program. Ser. A 110:475–499, 2007; J. Optim. Theory Appl. 137:11–25, 2008) and Sim (J. Optim. Theory Appl. 141:193–215, 2009), the asymptotic behavior of off-central paths corresponding to the HKM direction is studied. In particular, in Sim and Zhao (Math. Program. Ser. A 110:475–499, 2007), the authors study the asymptotic behavior of these paths for a simple example, while, in Sim and Zhao (J. Optim. Theory Appl. 137:11–25, 2008) and Sim (J. Optim. Theory Appl. 141:193–215, 2009), the asymptotic behavior of these paths for a general SDLCP is studied. In this paper, we study off-central paths corresponding to another well-known direction, the Nesterov-Todd (NT) direction. Again, we give necessary and sufficient conditions for these off-central paths to be analytic w.r.t. √μ and then w.r.t. μ, at solutions of a general SDLCP. Also, as in Sim and Zhao (Math. Program. Ser. A 110:475–499, 2007), we present off-central path examples using the same SDP, whose first derivatives are likely to be unbounded as they approach the solution of the SDP. We work under the assumption that the given SDLCP satisfies a strict complementarity condition.Department of Applied Mathematic
Superlinear convergence of an infeasible predictor-corrector path-following interior point algorithm for a semidefinite linear complementarity problem using the Helmberg-Kojima-Monteiro direction
No full textAn interior point method (IPM) defines a search direction at each interior point of a region. These search directions form a direction field which in turn gives rise to a system of ordinary differential equations (ODEs). The solutions of the system of ODEs can be viewed as underlying paths in the interior of the region. In [C.-K. Sim and G. Zhao, Math. Program. Ser. A, 110 (2007), pp. 475–499], these off-central paths are shown to be well-defined analytic curves, and any of their accumulation points is a solution to a given monotone semidefinite linear complementarity problem (SDLCP). The study of these paths provides a way to understand how iterates generated by an interior point algorithm behave. In this paper, we give a sufficient condition using these off-central paths that guarantees superlinear convergence of a predictor-corrector path-following interior point algorithm for SDLCP using the Helmberg–Kojima–Monteiro (HKM) direction. This sufficient condition is implied by a currently known sufficient condition for superlinear convergence. Using this sufficient condition, we show that for any linear semidefinite feasibility problem, superlinear convergence using the interior point algorithm, with the HKM direction, can be achieved for a suitable starting point. We work under the assumption of strict complementarity.Department of Applied Mathematic
OPTIMUM MATERIAL COMPOSITION FOR CONTACTING INTERFACE IN TESTING OF LEAD-FREE DEVICE
No full textMaster'sMASTER OF SCIENCE IN ADVANCED MATERIALS FOR MICRO- & NANO- SYSTEMSDissertation Advisor: 1. Assoc. Prof. Wong Chee Cheong, SMA Fellow, NTU STATS ChipPAC Ltd Project Supervisors: 1. Mel Goodson, Test R&D Senior Manager 2. Lim Kok Hwa, Test R&D Senior Engineer 3. Sim Yeow Teck, Test R&D Senor Enginee
Superlinear Convergence of an Interior Point Algorithm on Linear Semi-definite Feasibility Problems
No full textIn the literature, besides the assumption of strict complementarity, superlinear convergence of implementable polynomial-time interior point algorithms using known search directions, namely, the HKM direction, its dual or the NT direction, to solve semi-definite programs (SDPs) is shown by (i) assuming that the given SDP is nondegenerate and making modifications to these algorithms [10], or (ii) considering special classes of SDPs, such as the class of linear semi-definite feasibility problems (LSDFPs) and requiring the initial iterate to the algorithm to satisfy certain conditions [26, 27]. Otherwise, these algorithms are not easy to implement even though they are shown to have polynomial iteration complexities and superlinear convergence [14]. The conditions in [26, 27] that the initial iterate to the algorithm is required to satisfy to have superlinear convergence when solving LSDFPs however are not practical. In this paper, we propose a practical initial iterate to an implementable infeasible interior point algorithm that guarantees superlinear convergence when the algorithm is used to solve the homogeneous feasibility model of an LSDFP.This is the latest version of the original submission arXiv2211.08215 with different title and nontrivial change
Interior point method on semi-definite linear complementarity problems using the Nesterov-Todd (NT) search direction: polynomial complexity and local convergence
No full textSolution to a Monotone Inclusion Problem using the Relaxed Peaceman-Rachford Splitting Method: Convergence and its Rates
No full textWe consider the convergence behavior using the relaxed Peaceman-Rachford
splitting method to solve the monotone inclusion problem ,
where are maximal -strongly
monotone operators, and . Under a technical assumption,
convergence of iterates using the method on the problem is proved when either
or is single-valued, and the fixed relaxation parameter lies
in the interval . With this
convergence result, we address an open problem that is not settled in [20] on
the convergence of these iterates for . Pointwise convergence rate results and -linear
convergence rate results when lies in the interval are also provided in the paper. Our analysis
to achieve these results is atypical and hence novel. Numerical experiments are
conducted on the weighted Lasso minimization problem to test the validity of
the assumption .Comment: 23 pages, 1 figure, 1 tabl
On finding a generalized lowest rank solution to a linear semi-definite feasibility problem
No full textOn finding a generalized lowest rank solution to a linear semi-definite feasibility problem
No full text- …
