6.6 Geometric Programming¶
Geometric programs (GP) are a particular class of optimization problems which can be expressed in special polynomial form as positive sums of generalized monomials. More precisely, a geometric problem in canonical form is
where each
with arbitrary real
Under this substitution all constraints in a GP can be reduced to the form
involving a log-sum-exp bound. Moreover, constraints involving only a single monomial in
We refer to the MOSEK Modeling Cookbook and to [BKVH07] for more details on this reformulation. A geometric problem formulated in convex form can be entered into MOSEK with the help of exponential cones.
6.6.1 Example GP1¶
The following problem comes from [BKVH07]. Consider maximizing the volume of a
The decision variables in the problem are
after which (6.19) becomes
Next, we demonstrate how to implement a log-sum-exp constraint (6.18). It can be written as:
This presentation requires one extra variable
As a matter of demonstration we will also add the constraint
as an affine conic constraint. It means that to define the all the ACCs we need to produce the following affine expressions (AFE) and store them:
We implement it by adding all the affine expressions (AFE) and then picking the ones required for each ACC:
{
let afei = task.get_num_afe()?;
let u1 = task.get_num_var()?;
let u2 = u1+1;
let afeidx = &[0, 1, 2, 2, 3, 3, 5, 5];
let varidx = &[u1, u2, x, y, x, z, u1, u2];
let fval = &[1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0];
let gfull = &[0.0, 0.0, (2.0/Aw).ln(), (2.0/Aw).ln(), 1.0, -1.0];
task.append_vars(2)?;
task.append_afes(6)?;
task.put_var_bound_slice_const(u1, u1+2, Boundkey::FR, -INF, INF)?;
// Affine expressions appearing in affine conic constraints
// in this order:
// u1, u2, x+y+log(2/Awall), x+z+log(2/Awall), 1.0, u1+u2-1.0
task.put_afe_f_entry_list(afeidx, varidx, fval)?;
task.put_afe_g_slice(afei, afei+6, gfull)?;
{
let dom = task.append_primal_exp_cone_domain()?;
// (u1, 1, x+y+log(2/Awall)) \in EXP
task.append_acc(dom, &[0, 4, 2], &[0.0,0.0,0.0])?;
// (u2, 1, x+z+log(2/Awall)) \in EXP
task.append_acc(dom, &[1, 4, 3], &[0.0,0.0,0.0])?;
}
{
let dom = task.append_rzero_domain(1)?;
// The constraint u1+u2-1 \in \ZERO is added also as an ACC
task.append_acc(dom, &[5], &[0.0])?;
}
}
We can now use this function to assemble all constraints in the model. The linear part of the problem is entered as in Sec. 6.1 (Linear Optimization).
#[allow(non_snake_case)]
fn max_volume_box(Aw : f64,
Af : f64,
alpha : f64,
beta : f64,
gamma : f64,
delta : f64) -> Result<Vec<f64>,String>
{
let numvar = 3i32; // Variables in original problem
/* Create the optimization task. */
let mut task = match Task::new() {
Some(e) => e,
None => return Err("Failed to create task".to_string()),
}.with_callbacks();
// Directs the log task stream to the user specified
// method task_msg_obj.stream
task.put_stream_callback(Streamtype::LOG, |msg| print!("{}",msg))?;
// Add variables and constraints
task.append_vars(numvar)?;
let x = 0i32;
let y = 1i32;
let z = 2i32;
// Objective is the sum of three first variables
task.put_obj_sense(Objsense::MAXIMIZE)?;
task.put_c_slice(0, numvar, &[1.0,1.0,1.0])?;
task.put_var_bound_slice_const(0, numvar, Boundkey::FR, -INF, INF)?;
task.append_cons(3)?;
// s0+s1 < 1 <=> log(s0+s1) < 0
task.put_aij_list(&[0,0,1,1,2,2],
&[y, z, x, y, z, y],
&[1.0, 1.0, 1.0, -1.0, 1.0, -1.0])?;
task.put_con_bound(0,Boundkey::UP,-INF,Af.ln())?;
task.put_con_bound(1,Boundkey::RA,alpha.ln(),beta.ln())?;
task.put_con_bound(2,Boundkey::RA,gamma.ln(),delta.ln())?;
{
let afei = task.get_num_afe()?;
let u1 = task.get_num_var()?;
let u2 = u1+1;
let afeidx = &[0, 1, 2, 2, 3, 3, 5, 5];
let varidx = &[u1, u2, x, y, x, z, u1, u2];
let fval = &[1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0];
let gfull = &[0.0, 0.0, (2.0/Aw).ln(), (2.0/Aw).ln(), 1.0, -1.0];
task.append_vars(2)?;
task.append_afes(6)?;
task.put_var_bound_slice_const(u1, u1+2, Boundkey::FR, -INF, INF)?;
// Affine expressions appearing in affine conic constraints
// in this order:
// u1, u2, x+y+log(2/Awall), x+z+log(2/Awall), 1.0, u1+u2-1.0
task.put_afe_f_entry_list(afeidx, varidx, fval)?;
task.put_afe_g_slice(afei, afei+6, gfull)?;
{
let dom = task.append_primal_exp_cone_domain()?;
// (u1, 1, x+y+log(2/Awall)) \in EXP
task.append_acc(dom, &[0, 4, 2], &[0.0,0.0,0.0])?;
// (u2, 1, x+z+log(2/Awall)) \in EXP
task.append_acc(dom, &[1, 4, 3], &[0.0,0.0,0.0])?;
}
{
let dom = task.append_rzero_domain(1)?;
// The constraint u1+u2-1 \in \ZERO is added also as an ACC
task.append_acc(dom, &[5], &[0.0])?;
}
}
let _trm = task.optimize()?;
task.write_data("gp1.ptf")?;
let mut xyz = vec![0.0; 3];
task.get_xx_slice(Soltype::ITR, 0i32, numvar, xyz.as_mut_slice())?;
// task.write_data("gp1.ptf")?;
Ok(xyz.iter().map(|v| v.exp()).collect())
}
Given sample data we obtain the solution
#[allow(non_snake_case)]
fn main() -> Result<(),String> {
// maximize h*w*d
// subjecto to 2*(h*w + h*d) <= Awall
// w*d <= Afloor
// alpha <= h/w <= beta
// gamma <= d/w <= delta
//
// Variable substitutions: h = exp(x), w = exp(y), d = exp(z).
//
// maximize x+y+z
// subject log( exp(x+y+log(2/Awall)) + exp(x+z+log(2/Awall)) ) <= 0
// y+z <= log(Afloor)
// log( alpha ) <= x-y <= log( beta )
// log( gamma ) <= z-y <= log( delta )
//
// Finally, the model we will implement:
//
// maximize x+y+z
// subject to s0 > exp(x+y+log(2/Awall); (s0,1,x+y+log(2/Awall)) in PEXP
// s1 > exp(x+z+log(2/Awall); (s1,1,x+z+log(2/Awall)) in PEXP
// s0+s1 < 1
//
// y+z < log Afloor
//
// x-y in [log alpha; log beta]
// z-y in [log gamma; log delta]
//
// (x,y,z) in pexp : x0 > x1 * exp(x2/x1)
let Aw = 200.0;
let Af = 50.0;
let alpha = 2.0;
let beta = 10.0;
let gamma = 2.0;
let delta = 10.0;
let hwd = max_volume_box(Aw, Af, alpha, beta, gamma, delta)?;
println!("h={:.4} w={:.4} d={:.4}\n", hwd[0], hwd[1], hwd[2]);
Ok(())
}