主要内容

이번역페이지는최신내용을담고있지않습니다。최신내용을영문으로보려면여기를클릭하십시오。

국소최적해와전역최적해

솔버가가장작은최솟값을찾지못하는이유

일반적으로,솔버는국소최솟값(또는최적해)을반환합니다。그결과는전역최솟값(또는최적)해일수있지만반드시그렇다는보장은없습니다。

  • 함수의국소최솟값이란함수값이인근점에서보다는더작지만멀리있는점에서보다는더클수있는점을말합니다。

  • 전역최솟값이란함수값이다른모든실현가능점에서보다작은점을말합니다。

优化工具箱™솔버는일반적으로국소최솟값을구합니다。(이국소최솟값이전역최솟값일수있습니다。)솔버는시작점의끌개유역(盆地的吸引力)에서최솟값을구합니다。끌개유역에대한자세한내용은끌개유역항목을참조하십시오。

다음은이일반적인규칙의몇가지예외입니다。

  • 선형계획법문제와양의정부호2차계획법문제는볼록실현가능영역을갖는볼록문제이므로오직하나의끌개유역만있습니다。지정된옵션에따라linprog는사용자가제공한시작점을무시하며,quadprog는시작점을필요로하지않지만시작점을제공하면최소화속도가빨라지기도합니다。

  • 全局优化工具箱함수(예:simulannealbnd)는둘이상의끌개유역을탐색하려고시도합니다。

더작은최솟값찾기

전역최솟값이필요하다면전역최솟값의끌개유역에서솔버의초기값을찾아야합니다。

전역최솟값을찾기위해다음과같은방법으로초기값을설정할수있습니다。

  • 초기점의정규그리드를사용합니다。

  • 문제의모든좌표가유계인경우균등분포에서추출한임의의점을사용합니다。일부성분이비유계인경우정규분,포지수분포또는기타확률분포에서추출한점을사용합니다。전역최솟값의위치에대한정보가적을수록확률분포는넓게퍼져야합니다。예를들어,정규분포는평균에서3표준편차를초과하여떨어져있는값을추출하는일이거의없지만코시(柯西)분포(밀도는1 /(π(1 + x2))임)는상당히많이다른표본을만듭니다。

  • 유계좌표,정규좌,표지수좌표등각좌표에임의섭동을추가한상태로동일한초기점을사용합니다。

  • 全局优化工具箱라이선스가있으면GlobalSearch(全局优化工具箱)솔버또는MultiStart(全局优化工具箱)솔버를사용합니다。이러한솔버는범위내에서임의시작점을자동으로생성합니다。

가능한초기점에대해많이알수록탐색이더욱집중적이고성공할확률이높아집니다。

끌개유역

목적함수f (x)가매끄러우면벡터——∇f (x)f (x)가가장빠르게줄어드는방향을향합니다。최속강하법의방정식,즉다음방정식은

d d t x t f x t

t가커질수록국소최솟값으로이동하는경로x (t)를생성합니다。일반적으로,서로가까운초기값x (0)은동일한최솟값점으로향하는최속강하법경로를제공합니다。최속강하법의끌개유역은동일한국소최솟값에이르는초기값의집합입니다。

다음그림은두개의1차원최솟값을보여줍니다。이그림에서는서로다른선스타일로다른끌개유역을표시하며화살표로최속강하법의방향을나타냅니다。이그림과그다음그림에서검은색점은국소최솟값을나타냅니다。모든최속강하법경로는점x (0)에서시작하여x (0)을포함하는끌개유역의검은색점으로이동합니다。

1차원유역

다음그림은차원이많아질수록최속강하법경로가더복잡해질수있다는것을보여줍니다。

다양한시작점에서의최속강하법경로를보여주는하나의끌개유역

다음그림에서는더욱복잡한경로와끌개유역을보여줍니다。

여러끌개유역

제약조건은하나의끌개유역을여러조각으로나눌수있습니다。예를들어,다음과같은조건으로를y최소화한다고가정하겠습니다。

x y≥| |

Y≥5 - 4(x-2)2

다음그림에서는최종점을갖는두개의끌개유역을보여줍니다。

图생성에사용된코드

최속강하법경로는제약조건경계로내려가는직선입니다。제약조건경계에서최속강하법경로는경계를따라아래로이동합니다。최종점은초기x값2이보다크거나작은지에따라(0,0)이거나(11/4 11/4)이됩니다。

관련항목