宽邻域内点算法是求解线性规划以及线性互补问题的一种行之有效的方法。然而一直以来,实际计算效果好的宽邻域算法在复杂度方面却表现一般。Ai-Zhang宽邻域的提出弥补了这种理论和实践之间的差异。基于该宽邻域的重要性,本论文先对其展开研究,扩大了其中两个邻域参数的取值范围,并进而重新定义了三个相关宽邻域N1(τ,β),V2(τ,β)和N∞(τ,β)。之后针对线性规划和线性互补问题,分别具体研究这三个宽邻域内的原-对偶内点算法,讨论它们的复杂度和局部收敛性。研究首先在宽邻域N1(τ,β)中进行。证明了艾文宝的邻域跟踪算法在更一般情形下,即无需假设线性规划问题非退化的情况下,是二次收敛的。接下来将此算法推广到线性互补问题中,证明了算法的复杂度是O((?)L),这是迄今为止最好的复杂度结果,而且在假设严格互补解存在的条件下,算法是二次收敛的。进一步地,把该算法作为安全步,之前增加一个快速步,得到改进算法。新算法总是优先执行快速步,如果快速步不成功,才执行安全步,所以算法的复杂度仍然是O((?)L)。特别地,成功的快速步是在逐渐增大的宽邻域中进行的,且当迭代次数充分大时,算法将只执行快速步。证明了改进算法是超线性收敛的,而且算法产生的迭代点本身也是收敛的。数值实验表明了该算法的优越性。其次在N2(τ,β)中,根据路径跟踪法的迭代方向的正负分解在内点法设计时所发挥的作用,选择负分解项来确定预估方向,正分解项确定校正方向,针对线性互补问题提出了一个新的Mizuno-Todd-Ye预估校正算法,证明了算法的复杂度为O((?)L)。理论上该算法的对偶间隙在校正步没有下降,数值结果也表明算法有改进的必要,就此提出了第二个算法。保持第一个算法的预估方向不变,把仿射尺度方向嵌入校正方向中进行组合处理。该算法的时间复杂度为O((?)L),且对偶间隙在校正步中得到了充分下降。数值实验表明它优于第一个算法。接下来针对线性规划问题,在第二个算法基础上,基于中心参数自适应变化提出了第三个算法。证明了该算法有最好的时间复杂度,而且是超线性收敛的。最后,通过算法在不同中心参数选择下的数值表现,比较了各自的执行效率。最后,基于宽邻域N∞(τ,β)提出了针对线性规划问题的一阶Mehrotra型预估校正算法和二阶Mehrotra型预估校正算法。两个算法都运用了新的保障策略,使得算法既有实践性又具有多项式复杂度。一般情况下,算法都执行经典Mehrotra型预估校正步,但当预估步长或者实际迭代步长很小时,则执行保障策略,即将Mehrotra的自适应中心参数替换为固定常数,同时执行一个新的二阶校正项。一阶算法的时间复杂度为O(nL),理论结果比单纯只替换中心参数的保障方法要更好。二阶算法的多项式复杂度也是O(nL),其中新的迭代点的构成不同于一般的二阶Mehrotra型预估校正算法,需要预估方向的步长参与。数值实验的结果表明两个算法都是有效的。