이 페이지의 최신 내용은 아직 번역되지 않았습니다. 최신 내용은 영문으로 볼 수 있습니다.

solve

최적화 문제 풀기

구문

sol = solve(prob)
sol = solve(prob,x0)
sol = solve(___,Name,Value)
[sol,fval] = solve(___)
[sol,fval,exitflag,output,lambda] = solve(___)

설명

예제

sol = solve(prob)는 최적화 문제 prob를 풉니다.

예제

sol = solve(prob,x0)은 점 x0에서 시작하여 prob를 풉니다.

예제

sol = solve(___,Name,Value)는 위에 열거된 구문의 입력 인수 외에 하나 이상의 이름-값 쌍 인수를 사용하여 옵션을 지정합니다.

[sol,fval] = solve(___)는 위에 열거된 구문에 나와 있는 입력 인수를 사용하여 해에서 계산된 목적 함수 값을 반환합니다.

예제

[sol,fval,exitflag,output,lambda] = solve(___)는 종료 상태를 설명하는 종료 플래그, 풀이 과정에 대한 추가 정보 output 구조체, 그리고 정수가 아닌 문제에 대한 라그랑주 승수 구조체를 반환합니다.

예제

모두 축소

최적화 문제로 정의된 선형 계획법 문제를 풉니다.

x = optimvar('x');
y = optimvar('y');
prob = optimproblem;
prob.Objective = -x - y/3;
prob.Constraints.cons1 = x + y <= 2;
prob.Constraints.cons2 = x + y/4 <= 1;
prob.Constraints.cons3 = x - y <= 2;
prob.Constraints.cons4 = x/4 + y >= -1;
prob.Constraints.cons5 = x + y >= 1;
prob.Constraints.cons6 = -x + y <= 2;

sol = solve(prob)
Optimal solution found.
sol = struct with fields:
    x: 0.6667
    y: 1.3333

초기 실현가능점을 사용하는 경우와 사용하지 않는 경우에 정수 계획법 문제를 푸는 데 실행되는 스텝의 개수를 비교합니다. 이 문제에는 8개의 정수 변수와 4개의 선형 등식 제약 조건이 있고, 모든 변수가 양수로 제한됩니다.

prob = optimproblem;
x = optimvar('x',8,1,'LowerBound',0,'Type','integer');

4개의 선형 등식 제약 조건을 만들어 문제에 포함합니다.

Aeq = [22    13    26    33    21     3    14    26
    39    16    22    28    26    30    23    24
    18    14    29    27    30    38    26    26
    41    26    28    36    18    38    16    26];
beq = [ 7872
       10466
       11322
       12058];
cons = Aeq*x == beq;
prob.Constraints.cons = cons;

목적 함수를 만들어 문제에 포함합니다.

f = [2    10    13    17     7     5     7     3];
prob.Objective = f*x;

초기점을 사용하지 않고 문제를 푼 후 표시 내용을 검토하여 분기한정 노드의 개수를 확인합니다.

[x1,fval1,exitflag1,output1] = solve(prob);
LP:                Optimal objective value is 1554.047531.                                          

Cut Generation:    Applied 8 strong CG cuts.                                                        
                   Lower bound is 1590.479592.                                                      

Branch and Bound:

   nodes     total   num int        integer       relative                                          
explored  time (s)  solution           fval        gap (%)                                         
   10000      0.77         0              -              -                                          
   10947      0.83         1   2.481000e+03   3.585818e+01                                          
   14148      1.07         2   2.073000e+03   2.319190e+01                                          
   17131      1.31         3   1.854000e+03   1.180593e+01                                          
   17777      1.36         3   1.854000e+03   0.000000e+00                                          

Optimal solution found.

Intlinprog stopped because the objective value is within a gap tolerance of the
optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon
variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the
default value).

비교를 위해 초기 실현가능점을 사용하여 해를 구합니다.

x0.x = [8 62 23 103 53 84 46 34]';
[x2,fval2,exitflag2,output2] = solve(prob,x0);
LP:                Optimal objective value is 1554.047531.                                          

Cut Generation:    Applied 8 strong CG cuts.                                                        
                   Lower bound is 1590.479592.                                                      
                   Relative gap is 59.21%.                                                         

Branch and Bound:

   nodes     total   num int        integer       relative                                          
explored  time (s)  solution           fval        gap (%)                                         
    4535      0.56         2   2.262000e+03   2.965091e+01                                          
    6516      0.73         3   1.854000e+03   1.412399e+01                                          
    7795      0.83         3   1.854000e+03   2.695418e-01                                          
    7825      0.83         3   1.854000e+03   0.000000e+00                                          

Optimal solution found.

Intlinprog stopped because the objective value is within a gap tolerance of the
optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon
variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the
default value).
fprintf('Without an initial point, solve took %d steps.\nWith an initial point, solve took %d steps.',output1.numnodes,output2.numnodes)
Without an initial point, solve took 17777 steps.
With an initial point, solve took 7825 steps.

초기점을 제공한다고 해서 항상 문제가 개선되는 것은 아닙니다. 이 문제에서는 초기점을 사용함으로써 시간과 계산 스텝을 절약할 수 있습니다. 그러나, 일부 문제에서는 초기점으로 인해 solve가 더 많은 스텝을 실행하게 될 수 있습니다.

다음 문제를 풀어 보겠습니다.

이때 반복 과정은 표시하지 않습니다.

x = optimvar('x',2,1,'LowerBound',0);
x3 = optimvar('x3','Type','integer','LowerBound',0,'UpperBound',1);
prob = optimproblem;
prob.Objective = -3*x(1) - 2*x(2) - x3;
prob.Constraints.cons1 = x(1) + x(2) + x3 <= 7;
prob.Constraints.cons2 = 4*x(1) + 2*x(2) + x3 == 12;

options = optimoptions('intlinprog','Display','off');

sol = solve(prob,'Options',options)
sol = struct with fields:
     x: [2x1 double]
    x3: 1

해를 검토합니다.

sol.x
ans = 2×1

         0
    5.5000

sol.x3
ans = 1

solve가 선형 계획법 문제에 대한 솔버로 intlinprog를 사용하도록 강제 설정합니다.

x = optimvar('x');
y = optimvar('y');
prob = optimproblem;
prob.Objective = -x - y/3;
prob.Constraints.cons1 = x + y <= 2;
prob.Constraints.cons2 = x + y/4 <= 1;
prob.Constraints.cons3 = x - y <= 2;
prob.Constraints.cons4 = x/4 + y >= -1;
prob.Constraints.cons5 = x + y >= 1;
prob.Constraints.cons6 = -x + y <= 2;

sol = solve(prob,'Solver', 'intlinprog')
LP:                Optimal objective value is -1.111111.                                            


Optimal solution found.

No integer variables specified. Intlinprog solved the linear problem.
sol = struct with fields:
    x: 0.6667
    y: 1.3333

디폴트가 아닌 옵션으로 정수 계획법 문제 풀기에 설명되어 있는 혼합 정수 선형 계획법 문제를 풀고 모든 출력 데이터를 검토합니다.

x = optimvar('x',2,1,'LowerBound',0);
x3 = optimvar('x3','Type','integer','LowerBound',0,'UpperBound',1);
prob = optimproblem;
prob.Objective = -3*x(1) - 2*x(2) - x3;
prob.Constraints.cons1 = x(1) + x(2) + x3 <= 7;
prob.Constraints.cons2 = 4*x(1) + 2*x(2) + x3 == 12;

[sol,fval,exitflag,output] = solve(prob)
LP:                Optimal objective value is -12.000000.                                           


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap
tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default
value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).
sol = struct with fields:
     x: [2x1 double]
    x3: 1

fval = -12
exitflag = 
    OptimalSolution

output = struct with fields:
        relativegap: 0
        absolutegap: 0
      numfeaspoints: 1
           numnodes: 0
    constrviolation: 0
            message: 'Optimal solution found....'
             solver: 'intlinprog'

정수 제약 조건이 없는 문제의 경우 비어 있지 않은 라그랑주 승수 구조체를 5번째 출력값으로 얻을 수도 있습니다.

명명된 인덱스 변수를 사용하여 최적화 문제를 만들고 풉니다. 가중 흐름에 대한 제약 조건을 적용하여 수익에 가중치를 두고서 다양한 공항으로 과일의 유통 흐름을 극대화하는 문제입니다.

rng(0) % For reproducibility
p = optimproblem('ObjectiveSense', 'maximize');
flow = optimvar('flow', ...
    {'apples', 'oranges', 'bananas', 'berries'}, {'NYC', 'BOS', 'LAX'}, ...
    'LowerBound',0,'Type','integer');
p.Objective = sum(sum(rand(4,3).*flow));
p.Constraints.NYC = rand(1,4)*flow(:,'NYC') <= 10;
p.Constraints.BOS = rand(1,4)*flow(:,'BOS') <= 12;
p.Constraints.LAX = rand(1,4)*flow(:,'LAX') <= 35;
sol = solve(p);
LP:                Optimal objective value is -1027.472366.                                         

Heuristics:        Found 1 solution using rounding.                                                 
                   Upper bound is -1027.233133.                                                     
                   Relative gap is 0.02%.                                                          

Cut Generation:    Applied 1 mir cut, and 2 strong CG cuts.                                         
                   Lower bound is -1027.233133.                                                     
                   Relative gap is 0.00%.                                                          


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap
tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default
value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).

뉴욕과 로스앤젤레스로 향하는 오렌지와 베리의 최적 흐름을 구합니다.

[idxFruit,idxAirports] = findindex(flow, {'oranges','berries'}, {'NYC', 'LAX'})
idxFruit = 1×2

     2     4

idxAirports = 1×2

     1     3

orangeBerries = sol.flow(idxFruit, idxAirports)
orangeBerries = 2×2

         0  980.0000
   70.0000         0

위 결과가 의미하는 바는, NYC로 가는 오렌지가 없지만 70개의 베리가 NYC로 가고, 980개의 오렌지가 LAX로 가지만 LAX로 가는 베리는 없다는 것입니다.

다음의 최적 흐름을 나열합니다.

Fruit Airports

----- --------

Berries NYC

Apples BOS

Oranges LAX

idx = findindex(flow, {'berries', 'apples', 'oranges'}, {'NYC', 'BOS', 'LAX'})
idx = 1×3

     4     5    10

optimalFlow = sol.flow(idx)
optimalFlow = 1×3

   70.0000   28.0000  980.0000

위 결과가 의미하는 바는, 베리 70개가 NYC로, 사과 28개가 BOS로, 오렌지 980개가 LAX로 간다는 것입니다.

입력 인수

모두 축소

최적화 문제로, OptimizationProblem 객체로 지정됩니다.

예: prob = optimproblem; prob.Objective = obj; prob.Constraints.cons1 = cons1;

초기점으로, prob의 변수 이름과 같은 필드 이름을 가진 구조체로 지정됩니다.

명명된 인덱스 변수가 있는 x0을 사용하는 예제는 Create Initial Point for Optimization with Named Index Variables 항목을 참조하십시오.

예: probxy라는 변수가 있는 경우: x0.x = [3,2,17]; x0.y = [pi/3,2*pi/3].

데이터형: struct

이름-값 쌍의 인수

선택적으로 Name,Value 인수가 쉼표로 구분되어 지정됩니다. 여기서 Name은 인수 이름이고 Value는 대응값입니다. Name은 따옴표 안에 표시해야 합니다. Name1,Value1,...,NameN,ValueN과 같이 여러 개의 이름-값 쌍의 인수를 어떤 순서로든 지정할 수 있습니다.

예: solve(prob,'options',opts)

최적화 옵션으로, 'options'와 함께 optimoptions에 의해 생성되는 객체 또는 optimset에 의해 생성되는 것과 같은 options 구조체가 쉼표로 구분되어 지정됩니다.

solve 함수는 내부적으로 linprog, intlinprog, quadprog, lsqlin 또는 lsqnonneg를 호출합니다. 디폴트 솔버에 대해서는 'solver'를 참조하십시오.

intlinprog 풀이 또는 풀이 속도를 향상하기 위한 옵션 설정에 관한 팁은 Tuning Integer Linear Programming 항목을 참조하십시오. linprog의 경우 디폴트 'dual-simplex' 알고리즘은 일반적으로 메모리를 효율적으로 사용하고 속도가 빠릅니다. 때로는 Algorithm 옵션이 'interior-point'일 때 linprog가 대규모 문제를 더 빠르게 풉니다.

예: options = optimoptions('intlinprog','Display','none')

최적화 솔버로, 'solver'와 함께 아래 나열된 솔버의 이름이 쉼표로 구분되어 지정됩니다.

문제 유형기본 솔버기타 허용되는 솔버
선형 목적 함수, 선형 제약 조건linprogintlinprog, quadprog
선형 목적 함수, 선형 제약 조건, 정수 제약 조건intlinproglinprog, quadprog(정수 제약 조건이 무시됨)
2차 목적 함수, 선형 제약 조건quadproglsqlin, lsqnonneg(||C*x - d||^2을 최소화하기 위해 목적 함수를 변환할 수 없는 경우에는 solve가 이러한 솔버에 대해 오류를 발생시킴)
선형 제약 조건을 적용하여 ||C*x - d||^2 최소화목적 함수가 상수에 선형 표현식 제곱의 합을 더한 값일 때는 lsqlinquadprog, lsqnonneg(x >= 0 이외의 제약 조건은 lsqnonneg에서 무시됨)
x >= 0을 적용하여 ||C*x - d||^2 최소화lsqlinquadprog, lsqnonneg

주의

최대화 문제의 경우 lsqlinlsqnonneg 솔버를 지정하지 마십시오. 이러한 솔버는 최대화할 수 없으므로 이들을 지정하면 solve가 오류를 발생시킵니다.

예: 'intlinprog'

데이터형: char | string

출력 인수

모두 축소

해로, 구조체로 반환됩니다. 구조체의 필드는 최적화 변수의 이름입니다. optimvar을 참조하십시오.

해에서 계산된 목적 함수 값으로, 실수로 반환됩니다.

깜빡 잊고 fval을 요구하지 않은 경우 다음을 사용하여 계산할 수 있습니다.

fval = evaluate(prob.Objective,sol)

솔버가 중지된 이유로, categorical형 변수로 반환됩니다. 다음 표에서는 intlinprog 솔버에 대한 종료 플래그를 설명합니다.

intlinprog의 종료 플래그상응하는 숫자의미
IntegerFeasible2intlinprog가 중도에 중지되었습니다. 정수 실현가능점을 찾았습니다.
OptimalSolution

1

솔버가 해 x로 수렴되었습니다.

SolverLimitExceeded

0

intlinprog가 다음 허용오차 중 하나를 초과했습니다.

  • LPMaxIterations

  • MaxNodes

  • MaxTime

  • RootLPMaxIterations

허용오차와 중지 조건 항목을 참조하십시오. solve는 또한 루트 노드에서 메모리가 부족할 때 이 종료 플래그를 반환합니다.

OutputFcnStop-1intlinprog가 출력 함수나 플롯 함수에 의해 중지되었습니다.
NoFeasiblePointFound

-2

실현가능점을 찾을 수 없습니다.

Unbounded

-3

문제가 비유계입니다.

FoundNaN

-4

알고리즘 실행 도중 NaN 값이 발견되었습니다.

PrimalDualInfeasible

-5

원문제(Primal)와 쌍대 문제(Dual) 모두 실현 가능하지 않습니다.

DirectionTooSmall

-7

탐색 방향이 너무 작아졌습니다. 더 이상 진행할 수 없습니다.

다음 표에서는 linprog 솔버에 대한 종료 플래그를 설명합니다.

linprog의 종료 플래그상응하는 숫자의미
OptimalSolution1

솔버가 해 x로 수렴되었습니다.

SolverLimitExceeded0

반복 횟수가 options.MaxIterations를 초과했습니다.

NoFeasiblePointFound-2

실현가능점을 찾을 수 없습니다.

Unbounded-3

문제가 비유계입니다.

FoundNaN-4

알고리즘 실행 도중 NaN 값이 발견되었습니다.

PrimalDualInfeasible-5

원문제(Primal)와 쌍대 문제(Dual) 모두 실현 가능하지 않습니다.

DirectionTooSmall-7

탐색 방향이 너무 작아졌습니다. 더 이상 진행할 수 없습니다.

다음 표에서는 lsqlin 솔버에 대한 종료 플래그를 설명합니다.

lsqlin의 종료 플래그상응하는 숫자의미
FunctionChangeBelowTolerance3

잔차의 변화량이 지정된 허용오차 options.FunctionTolerance보다 작습니다. (trust-region-reflective 알고리즘)

StepSizeBelowTolerance

2

스텝 크기가 options.StepTolerance보다 작으며, 제약 조건이 충족되었습니다(interior-point 알고리즘).

OptimalSolution1

솔버가 해 x로 수렴되었습니다.

SolverLimitExceeded0

반복 횟수가 options.MaxIterations를 초과했습니다.

NoFeasiblePointFound-2

문제가 실현 불가능한지 여부. 또는, interior-point 알고리즘의 경우, 스텝 크기가 options.StepTolerance보다 작지만 제약 조건이 충족되지 않았습니다.

IllConditioned-4

조건이 나빠 최적화가 더 이상 진행되지 않습니다.

NoDescentDirectionFound-8

탐색 방향이 너무 작아졌습니다. 더 이상 진행할 수 없습니다. (interior-point 알고리즘)

다음 표에서는 quadprog 솔버에 대한 종료 플래그를 설명합니다.

quadprog의 종료 플래그상응하는 숫자의미
LocalMinimumFound4

국소 최솟값을 찾았거나, 최솟값이 고유하지 않습니다.

FunctionChangeBelowTolerance3

목적 함수 값의 변화량이 지정된 허용오차 options.FunctionTolerance보다 작습니다. (trust-region-reflective 알고리즘)

StepSizeBelowTolerance

2

스텝 크기가 options.StepTolerance보다 작으며, 제약 조건이 충족되었습니다(interior-point-convex 알고리즘).

OptimalSolution1

솔버가 해 x로 수렴되었습니다.

SolverLimitExceeded0

반복 횟수가 options.MaxIterations를 초과했습니다.

NoFeasiblePointFound-2

문제가 실현 불가능한지 여부. 또는, interior-point 알고리즘의 경우, 스텝 크기가 options.StepTolerance보다 작지만 제약 조건이 충족되지 않았습니다.

IllConditioned-4

조건이 나빠 최적화가 더 이상 진행되지 않습니다.

Nonconvex

-6

비볼록 문제가 감지되었습니다. (interior-point-convex 알고리즘)

NoDescentDirectionFound-8

스텝 방향을 계산할 수 없습니다. (interior-point-convex 알고리즘)

최적화 과정에 대한 정보로, 구조체로 반환됩니다. 출력 구조체에는 solve가 호출한 솔버에 따라 관련 기본 솔버 출력 필드에 다음 필드가 포함됩니다.

solve는 사용된 솔버(예: 'intlinprog')를 식별하기 위해 output 구조체에 추가 필드 Solver를 포함합니다.

해에서의 라그랑주 승수로, 구조체로 반환됩니다. intlinprog 솔버의 경우 lambda는 비어 있는 []입니다. 다른 솔버의 경우 lambda는 다음 필드를 가집니다.

  • Variables – 각 문제 변수에 대한 필드를 포함합니다. 각 문제 변수 이름은 다음 2개의 필드를 갖는 구조체입니다.

    • Lower – 변수 LowerBound 속성과 연결된 라그랑주 승수로, 변수와 같은 크기의 배열로 반환됩니다. 0이 아닌 요소는 해가 하한에 있음을 의미합니다. 이러한 승수는 구조체 lambda.Variables.variablename.Lower에 있습니다.

    • Upper – 변수 UpperBound 속성과 연결된 라그랑주 승수로, 변수와 같은 크기의 배열로 반환됩니다. 0이 아닌 요소는 해가 상한에 있음을 의미합니다. 이러한 승수는 구조체 lambda.Variables.variablename.Upper에 있습니다.

  • Constraints – 각 문제 제약 조건에 대한 필드를 포함합니다. 각 문제 제약 조건은 제약 조건의 이름을 구조체의 이름으로 갖고, 제약 조건과 같은 크기의 숫자형 배열을 값으로 갖는 구조체로 구성됩니다. 0이 아닌 요소는 제약 조건이 해에서 활성 상태임을 의미합니다. 이러한 승수는 구조체 lambda.Constraints.constraintname에 있습니다.

알고리즘

solve 함수는 내부적으로 다음과 같은 솔버를 호출하여 최적화 문제를 풉니다.

  • 선형 목적 함수와 선형 제약 조건의 경우 linprog

  • 선형 목적 함수와 선형 제약 조건 및 정수 제약 조건의 경우 intlinprog

  • 2차 목적 함수와 선형 제약 조건의 경우 quadprog

  • 선형 제약 조건이 있는 선형 최소제곱의 경우 lsqlin 또는 lsqnonneg

solve 또는 다른 관련 함수나 객체를 통해 문제를 솔버 형식으로 변환해야 solve가 이러한 함수를 호출할 수 있습니다. 예를 들어, 이 변환에는 최적화 변수 표현식이 아닌 행렬 표현을 가진 선형 제약 조건이 수반됩니다.

알고리즘의 첫 번째 단계는 문제에 최적화 표현식을 적용하는 것입니다. OptimizationProblem 객체에는 표현식에 사용되는 변수의 내부 목록이 있습니다. 각 변수는 표현식에서 선형 인덱스와 크기를 가집니다. 따라서 문제 변수는 자연스럽게 행렬 형식을 갖게 됩니다. prob2struct 함수가 문제 형식에서 솔버 형식으로의 변환을 수행합니다. 예제는 Convert Problem to Structure 항목을 참조하십시오.

문제 목적 함수 및 제약 조건에 따라 solve가 호출하는 디폴트 솔버와 허용되는 솔버가 달라집니다. 자세한 내용은 'solver'를 참조하십시오. solve를 호출할 때 'solver' 이름-값 쌍 인수를 사용하여 디폴트 값을 재정의할 수 있습니다.

intlinprog가 MILP 문제를 푸는 데 사용하는 알고리즘에 대해서는 intlinprog 알고리즘 항목을 참조하십시오. linprog가 선형 계획법 문제를 푸는 데 사용하는 알고리즘에 대해서는 선형 계획법 알고리즘 항목을 참조하십시오. quadprog가 2차 계획법 문제를 푸는 데 사용하는 알고리즘에 대해서는 2차 계획법 알고리즘 항목을 참조하십시오. lsqlin이 선형 최소제곱 문제를 푸는 데 사용하는 알고리즘에 대해서는 최소제곱(모델 피팅) 알고리즘 항목을 참조하십시오.

참고

목적 함수가 제곱의 합이고 이를 그렇게 인식하도록 solve에 전달하려면 목적 함수를 expr'*expr이 아니라 sum(expr.^2)으로 쓰십시오. 내장 구문 분석기는 명시적인 제곱 합만 인식합니다. 예제는 Nonnegative Least-Squares, Problem-Based 항목을 참조하십시오.

호환성 고려 사항

모두 확장

R2018b부터 오류 발생

R2017b에 개발됨