چکیده
یک روش نیوتن سریع، برای حل برنامه های خطی با تعداد قید بسیار زیاد (≈106) و تعداد متغیر متوسط (≈102) پیشنهاد می شود. چنین برنامه های خطی ای، در کاوش داده ها و یادگیری ماشینی ظاهر می شوند. روش پیشنهاد شده، بر اساس این حقیقت ظاهراً نادیده گرفته شده است که فرمولبندی دوگان تاوان خارجی مجانبی یک برنامه خطی، یک جواب دقیق نرم – 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 صحت طبقه بندی مجموعه آزمون و آموزشی بالاتری به دست داد...