robustlp.gms : SOCP로서의 강력한 선형 프로그래밍

설명

다음 형식의 선형 최적화 문제를 고려하십시오.
min_x c^Tx s.t. a_i^Tx <= b_i, i=1,..,m.

실제로 계수 벡터 a_i는 완벽하게 알 수 없을 수도 있지만,
소음에 취약하기 때문입니다. 우리가 E_i에 있는 a_i만 알고 있다고 가정합니다.
여기서 E_i에는 타원체가 주어집니다. 강력한 최적화에서는 다음을 최소화하려고 합니다.
원래 목표이지만 각 제약 조건이 충족되어야 한다고 주장합니다.
E_i에서 해당 벡터 a_i의 선택과 관계없이.
2차 원뿔 최적화 문제를 얻습니다.
min_x c^Tx s.t. a'_i^Tx + ||R_i^Tx|| <= b_i, i=1,..,m,
여기서 E_i =  a'_i + R_iu | ||유|| <= 1. 위에서 우리는 다음을 관찰합니다.
다음과 관련된 항으로 인해 실행 가능한 세트가 원래 세트보다 작습니다.
l_2-규범.

위의 그림은 특정 상황에서 얻을 수 있는 실현 가능한 집합의 종류를 보여줍니다.
구형 불확실성이 있는 위 문제의 예(즉, 모든
타원체는 구입니다. 일부 rho >0의 경우 R_i = rho I입니다. 우리는 견고하다는 것을 관찰합니다
실행 가능한 집합은 실제로 원래 다면체에 포함되어 있습니다.

이 특정 예에서는 계수 A(i,*)가 타원체에서 변하는 것을 허용합니다.
견고한 LP는 SOCP로 재구성됩니다.

제공: Michael Ferris, 위스콘신 대학교 매디슨

소형 모델 유형 :QCP

카테고리 : 슬롯 나라 모델 라이브러리

메인 파일 : robustlp.gms

$title SOCP로서의 강력한 선형 프로그래밍(ROBUSTLP,SEQ=416)

$onText
다음 형식의 선형 최적화 문제를 고려하십시오.
min_x c^Tx s.t. a_i^Tx <= b_i, i=1,..,m.

실제로 계수 벡터 a_i는 완벽하게 알 수 없을 수도 있지만,
소음에 취약하기 때문입니다. 우리가 E_i에 있는 a_i만 알고 있다고 가정합니다.
여기서 E_i에는 타원체가 주어집니다. 강력한 최적화에서는 다음을 최소화하려고 합니다.
원래 목표이지만 각 제약 조건이 충족되어야 한다고 주장합니다.
E_i에서 해당 벡터 a_i의 선택과 관계없이.
2차 원뿔 최적화 문제를 얻습니다.
min_x c^Tx s.t. a'_i^Tx + ||R_i^Tx|| <= b_i, i=1,..,m,
여기서 E_i =  a'_i + R_iu | ||유|| <= 1. 위에서 우리는 다음을 관찰합니다.
다음과 관련된 항으로 인해 실행 가능한 세트가 원래 세트보다 작습니다.
l_2-규범.

위의 그림은 특정 상황에서 얻을 수 있는 실현 가능한 집합의 종류를 보여줍니다.
구형 불확실성이 있는 위 문제의 예(즉, 모든
타원체는 구입니다. 일부 rho >0의 경우 R_i = rho I입니다. 우리는 견고하다는 것을 관찰합니다
실행 가능한 집합은 실제로 원래 다면체에 포함되어 있습니다.

이 특정 예에서는 계수 A(i,*)가 타원체에서 변하는 것을 허용합니다.
견고한 LP는 SOCP로 재구성됩니다.

제공: Michael Ferris, 위스콘신 대학교 매디슨

Lobo, MS, Vandenberghe, L, Boyd, S 및 Lebret, H, 응용 분야
2차 콘 프로그래밍. 선형대수학과 그 응용,
제어, 신호 및 이미지의 선형대수학 특별호
처리. 284(1998년 11월).

키워드: 선형 프로그래밍, 2차 제약 조건 프로그래밍, 강력한 최적화,
          2차 콘 프로그래밍
$offText

$mu를 설정하지 않은 경우 $set mu 1.0e-2

세트
   나는 / 1*7 /
   j / 1*4 /;

매개변수 b(i), c(j), A(i,j);
b(i) = 1;
c(j) = -1;

옵션 시드 = 0;
A(i,j) = 균일(0,1);

변수 obj, x(j);

방정식 defobj, cons(i);

defobj..obj =e= sum(j, c(j)*x(j));

cons(i).. sum(j, A(i,j)*x(j)) =l= b(i);

모델 lpmod / defobj, 단점 /;

lp min obj를 사용하여 lpmod를 해결합니다.

매개변수 결과(*,*);
결과('lp',j) = x.l(j);
results('lp','obj') = obj.l;

스칼라 mu / %mu% /;

양수 변수 람다(j), 감마(j);

방정식 lpcons(i), defdual(j);

* A(i,*) \in A(i,*) + [-mu(i) 1, mu(i) 1] (infty 표준 공)
* 제약 조건은 mu(i) * norm(x)_1 + Ax <= b (여기서는 1 mu만 사용하세요)
* 람다와 감마를 사용하여 하나의 표준(inf 표준의 이중)을 구현하기만 하면 됩니다.
lpcons(i)..mu*sum(j, 람다(j) + 감마(j)) + sum(j, A(i,j)*x(j)) =l= b(i);

defdual(j)..lambda(j) - 감마(j) =e= x(j);

모델 lproblp / defobj, lpcons, defdual /;

lp min obj를 사용하여 lproblp를 해결합니다.

results('roblp',j) = x.l(j);
results('roblp','obj') = obj.l;

별칭(j,k);

매개변수 P(i,j,k);
P(i,j,j) = %mu%;

변수 y(i), v(i,k);

방정식 defrhs(i), defv(i,k), socpcons(i);

defrhs(i).. y(i) =e= b(i) - sum(j, A(i,j)*x(j));

defv(i,k)..v(i,k) =e= sum(j, P(i,j,k)*x(j));

방정식 socpqcpcons(i);

socpqcpcons(i)..sqr(y(i)) =g= sum(k, sqr(v(i,k)));

모델 roblpqcp / defobj, socpqcpcons, defrhs, defv /;

y.lo(i) = 0;

옵션 qcp = cplex;

qcp min obj를 사용하여 roblpqcp를 해결합니다.

결과('qcp',j) = x.l(j);
results('qcp','obj') = obj.l;

결과 표시;