YALMIP Example : Geometric programming

Geometric programming

This example requires MOSEK, GPPOSY or fmincon

Nonlinear terms can be defined also with negative and non-integer powers. This can be used to define geometric optimization problems.

Geometric programming solvers are capable of solving a sub-class of geometric problems where c≥0 with the additional constraint t≥0, so called posynomial geometric programming. The following example is taken from the MOSEK manual. (note, the positivity constraint on t will be added automatically)

t1 = sdpvar(1,1);
t2 = sdpvar(1,1);
t3 = sdpvar(1,1);
obj = (40*t1^-1*t2^-0.5*t3^-1)+(20*t1*t3)+(40*t1*t2*t3);
F = set((1/3)*t1^-2*t2^-2+(4/3)*t2^0.5*t3^-1 < 1);
solvesdp(F,obj);

If the geometric program violates the posynomial assumption, an error will be issued.

solvesdp(F + set(t1-t2 < 1),obj)
Warning: Solver not applicable
 ans = 
  yalmiptime: 0.0600
  solvertime: 0
  info: 'Solver not applicable'
  problem: -4

YALMIP will automatically convert some simple violations of the posynomial assumptions, such as lower bounds on monomial terms and maximization of negative monomials. The following small program maximizes the volume of an open box, under constraints on the floor and wall area, and constraints on the relation between the height, width and depth (example from [S. Boyd, S. Kim, L. Vandenberghe, A. Hassibi] ).

sdpvar h w d

Awall  = 1;
Afloor = 1;

F = set(0.5 < h/w < 2) + set(0.5 < d/w < 2);
F = F + set(2*(h*w+h*d) < Awall) + set(w*d < Afloor);

solvesdp(F,-(h*w*d))

The posynomial geometric programming problem is not convex in its standard formulation. Hence, if a general nonlinear solver is applied to the problem, it will typically fail. However, by performing a suitable logarithmic variable transformation, the problem is rendered convex. YALMIP has built-in support for performing this variable change, and solve the problem using the nonlinear solver fmincon. To invoke this module in YALMIP, use the solver tag 'fmincon-geometric'.Note that this feature mainly is intended for the fmincon solver in the MathWorks Optimization Toolbox. It may work in the fmincon solver in TOMLAB, but this has not been tested to any larger extent.

t1 = sdpvar(1,1);
t2 = sdpvar(1,1);
t3 = sdpvar(1,1);
obj = (40*t1^-1*t2^-0.5*t3^-1)+(20*t1*t3)+(40*t1*t2*t3);
F = set((1/3)*t1^-2*t2^-2+(4/3)*t2^0.5*t3^-1 < 1);
solvesdp(F,obj,sdpsettings('solver','fmincon-geometric'));

The current version of YALMIP has a bug that may cause problems if you have convex quadratic constraints. To avoid this problem, use sdpsettings('convertconvexquad',0). To avoid some other known issues, explicitly tell YALMIP that the problem is a geometric problem by specifying the solver to 'gpposy', 'mosek-geometric' or 'fmincon-geometric'.

Never use the commands sqrt and cpower when working with geometric programs, i.e. always use the ^ operator. The reason is implementation issues in YALMIP. The commands sqrt and cpower are meant to be used in optimization problems where a conic model is derived using convexity propagation, see nonlinear operators.

Generalized geometric programming

Some geometric programs, although not given in standard form, can still be solved using a standard geometric programming solver after some some additional variables and constraints have been introduced. YALMIP has built-in support for some of these conversion.

To begin with, nonlinear operators can be used also in geometric programs, as in any other optimization problems (as long as YALMIP is capable of proving convexity, see the nonlinear operator examples)

t1 = sdpvar(1,1);
t2 = sdpvar(1,1);
t3 = sdpvar(1,1);
obj = (40*t1^-1*t2^-0.5*t3^-1)+(20*t1*t3)+(40*t1*t2*t3);

F = set(max((1/3)*t1^-2*t2^-2+(4/3)*t2^0.5*t3^-1,0.25*t1*t2) < min(t1,t2));
solvesdp(F,obj);

Powers of posynomials are allowed in generalized geometric programs. YALMIP will automatically take care of this and convert the problems to a standard geometric programs. Note that the power has to be positive if used on the left-hand side of a <, and negative otherwise.

t1 = sdpvar(1,1);
t2 = sdpvar(1,1);
t3 = sdpvar(1,1);
obj = (40*t1^-1*t2^-0.5*t3^-1)+(20*t1*t3)+(40*t1*t2*t3);

F = set(max((1/3)*t1^-2*t2^-2+(4/3)*t2^0.5*t3^-1,0.25*t1*t2) < min((t1+0.5*t2)^-1,t2));
F = F + set((2*t1+3*t2^-1)^0.5 < 2);

solvesdp(F,obj);

To understand how a generalized geometric program can be converted to a standard geometric program. the reader is referred to [S. Boyd, S. Kim, L. Vandenberghe, A. Hassibi]

Mixed integer geometric programming

The branch and bound solver in YALMIP is built in a modular fashion that makes it possible to solve almost arbitrary convex mixed integer programs. The following example is taken from [S. Boyd, S. Kim, L. Vandenberghe, A. Hassibi]. To begin with, define the data for the example.

a = ones(7,1); alpha = ones(7,1); beta = ones(7,1); gamma = ones(7,1); f = [1 0.8 1 0.7 0.7 0.5 0.5]'; e = [1 2 1 1.5 1.5 1 2]'; Cout6 = 10; Cout7 = 10;

Introduce symbolic expressions used in the model.

x = sdpvar(7,1);

C = alpha+beta.*x;
A = sum(a.*x);
P = sum(f.*e.*x);
R = gamma./x;

D1 = R(1)*(C(4));
D2 = R(2)*(C(4)+C(5));
D3 = R(3)*(C(5)+C(7));
D4 = R(4)*(C(6)+C(7));
D5 = R(5)*(C(7));
D6 = R(6)*Cout6;
D7 = R(7)*Cout7;

The objective function and constraints (notice the use of the nonlinear operator max in the objective).

% Constraints
F = set(x > 1) + set(P < 20) + set(A < 100);

% Objective
D = max((D1+D4+D6),(D1+D4+D7),(D2+D4+D6),(D2+D4+D7),(D2+D5+D7),(D3+D5+D6),(D3+D7));

Solve!

solvesdp(F+set(integer(x)),D)
double(D)
ans =
    8.3333

An alternative model is discussed in the paper, and is just as easy to define.

T1 = D1;
T2 = D2;
T3 = D3;
T4 = max(T1,T2)+D4;
T5 = max(T2,T3) + D5;
T6 = T4 + D6;
T7 = max(T3,T4,T5) + D7;
D = max(T6,T7);
solvesdp(F+set(integer(x)),D)
double(D)
ans =
    8.3333