A fast Newton method is proposed for solving linear programs with a very large (≈106) number of constraints and a moderate (≈102) number of variables. Such linear programs occur in data mining and machine learning. The proposed method is based on the apparently overlooked fact that the dual of an asymptotic exterior penalty formulation of a linear program provides an exact least 2-norm solution to the dual of the linear program for finite values of the penalty parameter but not for the primal linear program. Solving the dual problem for a finite value of the penalty parameter yields an exact least 2-norm solution to the dual, but not a primal solution unless the parameter approaches zero. However, the exact least 2-norm solution to the dual problem can be used to generate an accurate primal solution if m≥n and the primal solution is unique. Utilizing these facts, a fast globally convergent finitely terminating Newton method is proposed. A simple prototype of the method is given in eleven lines of MATLAB code. Encouraging computational results are presented such as the solution of a linear program with two million constraints that could not be solved by CPLEX 6.5 on the same machine

چکیده

یک روش نیوتن سریع، برای حل برنامه های خطی با تعداد قید بسیار زیاد (≈10⁶) و تعداد متغیر متوسط (≈10²) پیشنهاد می شود. چنین برنامه های خطی ای، در کاوش داده ها و یادگیری ماشینی ظاهر می شوند. روش پیشنهاد شده، بر اساس این حقیقت ظاهراً نادیده گرفته شده است که فرمولبندی دوگان تاوان خارجی مجانبی یک برنامه خطی، یک جواب دقیق نرم – 2 حداقل برای دوگان برنامه خطی، برای مقادیر معین پارامتر تاوان ارائه می کند ، اما برای برنامه خطی اولیه این گونه نیست. حل دوگان برای یک مقدار معین پارامتر تاوان، یک جواب نرم – 2 حداقل دقیق برای دوگان به دست می دهد اما جواب اولیه نیست، مگر این که این پارامتر، به صفر میل کند. با این وجود، جواب نرم – 2 حداقل دقیق برای مسئله دوگان، می تواند برای تولید یک جواب اولیه دقیق به کار رود، اگر m>=n  و جواب اولیه یکتاست. با استفاده از این حقایق، روش نیوتن سریع با توقف همگرایی معین کل پیشنهاد می شود. یک نمونه اولیه ساده از این روش، در هفت خط کد متلب نشان داده شده است. نتایج محاسباتی دلگرم کننده، مانند جواب برنامه خطی با دو میلیون محدودیت ارائه شده اند که نمی توان آنها را با CPLEX 6.5 در همان ماشین حل کرد.

1-مقدمه

روش پیشنهاد شده در اینجا، از تاثیر توقف متناهی روش نیوتن که در [23] برای کمینه کردن غیر محدود توابع درجه دوم تکه ای به شدت کوژ حاصل از برنامه های درجه دوم پیشنهاد شده است و به صورت موفقیت آمیزی برای مسائل طبقه بندی در [10] به کار برده شده است، انگیزه گرفته است. برای اعمال این روش به برنامه های خطی، یک انتخاب معقول، فرمولبندی حداقل نرم - 2 [18، 24، 25، 11] یک برنامه خطی به عنوان یک برنامه درجه دوم به شدت کوژ است، که یک جواب حداقل نرم - 2 دقیق برای مقادیر پارامتری متناهی به دست می دهد. این کار در [14] انجام شده است، که در آن، یک روش نیوتن متناهی اما بدون هر گونه نتایج محاسباتی و بدون دادن یک جواب دقیق برای دوگانه جواب حداقل نرم - 2 پیشنهاد شد. در روش ارائه شده مان در اینجا، ما هیچ فرضی درباره برنامه خطی مان غیر از قابلیت حل و یک شرط یکتایی اعمال شده انجام نداده ایم، که این فرض ها به تفصیل در بخش 2 توضیح داده می شوند. در بخش 3، ما الگوریتم نیوتنی خود را با اندازه گام آرمیجو بیان می کنیم و همگرایی کلی آن را ارائه می دهیم. در بخش 4، ما نتایج آزمون مقایسه ای دلگرم کننده ای را با CPLEX 6.5 [5] در کلاسی از برنامه های خطی پراکنده به صورت مصنوعی تولید شده با قیدهایی به میزان 2 میلیون و نیز در شش مسئله طبقه بندی یادگیری ماشینی در دسترس عموم ارائه می دهیم. ما هم چنین، کدهای متلب خلاصه را برای مولد مسئله آزمون و نیز نسخه ساده ای از حل کننده نیوتن خود را بدون اندازه گام آرمیجو ارائه می دهیم. این کد، برای به دست آوردن همه نتایج عددی مان به کار می رود. از میان هفت مسئله ازمون مصنوعی، در پنج مسئله، روش پیشنهاد شده، با ضریبی در محدوده 2,8 تا 34,2، سریع تر از CPLEX بود. در دو مسئله باقیمانده، CPLEX حافظه را تمام کرد. در شش مسئله طبقه بندی یادگیری ماشینی کوچکتر، CPLEX سریع تر بود، اما LPN صحت طبقه بندی مجموعه آزمون و آموزشی بالاتری به دست داد...