GeometricOptimization

GeometricOptimization[f,cons,vars]

finds positive values of variables vars that minimize the posynomial objective subject to posynomial constraints cons.

GeometricOptimization[{a0,b0},{{a1,b1},},{aeq,beq}]

finds the positive vector x=y that minimizes subject to inequality constraints and linear equality constraints .

GeometricOptimization[,"prop"]

specifies what solution property "prop" should be returned.

Details and Options

  • Geometric optimization is also known as geometric programming (GP).
  • Geometric optimization is often used when minimizing quantities like area, volume or power.
  • Geometric optimization finds that solves the primal problem:
  • minimize
    subject to constraints
    where
  • A monomial is a product of powers with . A posynomial is a positive sum of monomials with .
  • A generalized posynomial is a posynomial or a combination of generalized posynomials:
  • posynomial
    sum of generalized posynomials
    product of generalized posynomials
    maximum of generalized posynomials
    positive real power of a generalized posynomial
  • With the transformation , a posynomial corresponds to a matrix with and a -vector with as follows:
  • An equivalent formulation of the problem is to find where solves the problem:
  • minimize
    subject to constraints
    where
  • In GeometricOptimization[{a0,b0},{{a1,b1},},{aeq,beq}], the ai should be matrices, the bi should be vectors, aeq should be an matrix and b_(eq) should be an vector. If there are no equality constraints, the {aeq,beq} can be given as {} or omitted.
  • The primal minimization problem has a related maximization problem that is the Lagrangian dual problem. The dual maximum value is always less than or equal to the primal minimum value, so it provides a lower bound. The dual maximizer provides information about the primal problem, including sensitivity of the minimum value to changes in the constraints.
  • The geometric optimization problem has a dual problem:
  • maximize
    subject to constraints
    where
  • For conic optimization, strong duality always holds, meaning that if there is a solution to the primal minimization problem, then there is a solution to the dual maximization problem, and the dual maximum value is equal to the primal minimum value.
  • The possible solution properties "prop" include:
  • "PrimalMinimizer"a list of the values of vars={v1,} that minimize f
    "PrimalMinimizerRules"rules for the minimizing values of vars={v1,}
    "PrimalMinimizerVector"the vector that minimizes
    "PrimalMinimumValue"the minimum value
    "DualMaximizer"the list of vectors that maximize
    "DualMaximumValue"the dual maximum value
    "DualityGap"the difference between the dual and primal optimal values
    "Slack"vectors that give the values for each monomial for the posynomial terms
    "ConstraintSensitivity"
    sensitivity of to constraint perturbations
    "ConstraintMatrices"The matrices for terms
    "ObjectiveFunction"the objective function
    "GeometricConstraints" the list of geometric constraints
    {"prop1","prop2",} several solution properties
  • The following options may be given:
  • MaxIterationsAutomaticmaximum number of iterations to use
    MethodAutomaticthe method to use
    PerformanceGoal$PerformanceGoalaspects of performance to try to optimize
    ToleranceAutomaticthe tolerance to use for internal comparisons
  • Computations are limited to MachinePrecision.

Examples

open allclose all

Basic Examples  (1)

Maximize the area of a rectangle such that the perimeter is at most 1 and the height is at most half the width:

Scope  (12)

Basic Uses  (4)

Specify a geometric problem using a matrix specification:

Show the equivalent objective function and geometric constraints for the problem:

Solve a geometric problem with an equality constraint given in standard form:

Solve a geometric problem given with generalized posynomials:

Extra variables are added automatically by the algorithm to get an intermediate posynomial form:

Solve a geometric problem given in terms of vector variables:

Primal Model Properties  (3)

Solve a geometric problem in standard posynomial form:

Get the minimum value and the minimizing vector:

Show the matrix representation for the problem:

Solve a geometric problem given with generalized posynomials:

Get the transformed constraints including intermediate variables that were introduced:

These correspond to the matrix representation:

Solve a geometric problem given in matrix form:

Get a symbolic form of the geometric problem in terms formal variables:

Dual Model Properties  (2)

Find where minimizes subject :

The dual problem is to maximize subject to :

The formulation in terms of ConicOptimization replaces the convex terms with intermediate variables , adding constraints that are equivalent to the dual exponential cone constraints used earlier; {-TemplateBox[{{(, {lambda, _, 1}, )}, j}, IndexedDefault],TemplateBox[{{(, {t, _, 1}, )}, j}, IndexedDefault]-TemplateBox[{{(, {lambda, _, 1}, )}, j}, IndexedDefault],1^.lambda_1}_(TemplateBox[{}, DualExponentialConeString])0 requires xTemplateBox[{{(, {lambda, _, 1}, )}, j}, IndexedDefault] ⅇ^((TemplateBox[{{TemplateBox[{{(, {t, _, 1}, )}, j}, IndexedDefault], -, {(, {lambda, _, 1}, )}}, j}, IndexedDefault])/(-TemplateBox[{{(, {lambda, _, 1}, )}, j}, IndexedDefault])-1)<=1^.lambda_1 ∧-TemplateBox[{{(, {lambda, _, 1}, )}, j}, IndexedDefault]<=0.

and can be more easily obtained from the "DualMaximizer" property:

The dual maximum value is the same as the primal minimum value because of strong duality:

Minimize subject to constraints and :

Get the solution to the dual problem:

The dual maximum value is the same as the primal minimum value because GeometricOptimization has strong duality. The difference is referred to as the duality gap:

The dual problem is defined in terms of the matrix representation for the problem:

Because all of the terms are monomials, all of the matrices have one row, and the dual vectors have only one element, so . Maximizing is equivalent to minimizing , and since the exponential is a monotone increasing function, this is equivalent to minimizing , so the dual problem can be solved as:

Note that the primal problem is also solved by linear optimization using the monotonicity of the exponential:

Sensitivity Properties  (3)

Maximize the volume of an open box with height , width and depth subject to the constraint that the cost of the box is less than $100. The cost of the bottom is $10 per unit area and the cost of the sides is $1 per unit area:

Estimate the relative change in the box volume if the cost of the bottom decreased by 10%:

The component for the bottom cost is the first part of the second element (the first element corresponds to the objective). The sensitivity is negated since :

Find the relative change in the maximum volume of a box with height , width and depth to changes in constraints on the area of the top and bottom and on the area of the sides. Maximizing the volume is equivalent to minimizing the reciprocal of the volume:

Constrain the the total area of the sides to be less than or equal to and the area of the top and bottom to be less than or equal to :

Additionally, include bounds on the aspect ratios:

Define a function that computes the volume given and :

Find the maximal volume for :

Get the relative sensitivity of the objective to the constraints when :

The ones associated with the area constraints are the second and third (the first is associated with the objective):

The relative change in volume with respect to is :

This means that small changes in do not change the volume around {α,β}={38,47}:

When is small enough, it does affect the volume:

The sensitivity is the slope of the curve on a log-log plot:

The two components of are from the two sets of opposing sides, so the total relative change in volume is:

The predicted change from increasing by .5 is:

The actual change is:

The sensitivities can also be verified with finite differences:

Find the relative change in the minimum value of subject to the constraint with respect to and :

Use finite differences to verify that :

Similarly for and :

The finite difference estimates are within the tolerance of the optimization:

Applications  (16)

Basic Modeling Transformations  (1)

Determine limits on the constraints that allow feasibility:

This problem is feasible:

This one is not:

Geometric Problems  (4)

Minimize the length of the diagonal of a rectangle of area 4 such that the width plus three times the height is less than 7:

Design an ice cream cone for a spherical scoop of ice cream of volume . Assume the radii of the scoop and cone are the same. Minimize the surface area of the cone so that the cone would hold the entire scoop when melted:

Find that maximizes the volume of an ellipsoid with surface area of at most 1:

When are not too different, with the surface area can be approximated by:

Maximize the volume area by minimizing its reciprocal:

Not surprisingly, this is the sphere. Including additional constraints on the axis lengths changes this:

Maximize the volume of a box with height , width , and depth such that no two dimensions differ by more than a factor of 2 and with constraints on the total surface area of the sides, the top and the bottom:

Define a function that returns the volume given the total side area and the sum of top and bottom area :

Compute a table of the values of the volume:

Show the volume as a function of side area and top and bottom area on a logarithmic scale:

Show tradeoff curves for volume versus allowed top/bottom area for different values of the side area:

Matrix Problems  (2)

Given an matrix with non-negative real entries, find a diagonal matrix with positive entries that minimizes the sum of squares (the Frobenius norm squared) of the similar matrix :

Let d={d1,,dn} be the diagonal entries of . Since di is positive, the entries of are {1/d1,,1/dn}, so the entries of the product are :

Compare norms of the original and scaled matrices:

The matrices are similar, so the eigenvalues are equal:

Let be an TemplateBox[{}, Reals]^(n x n) matrix with posynomial elements in some variable x in TemplateBox[{}, Reals]^k. Find that minimizes the spectral radius of . The spectral radius is equal to the maximum of the absolute values of the eigenvalues of , max(TemplateBox[{lambda}, Abs], A.v=lambda:

The spectral radius is also equal to the PerronFrobenius eigenvalue that can be computed as :

Here is the matrix with minimum spectral radius:

Verify the computed is the spectra radius:

Compare with the spectral radius for some random choices of :

Storage Tank Design  (1)

Minimize the construction and operating cost of a cylindrical storage tank given constraints on the radius , the height and the aspect ratio :

The construction cost is the cost of the base plus the cost of the surface:

The filling cost is taken to be proportional to the ratio of the volume to be supplied, , to the capacity of the tank, :

Minimize the total cost:

Floor Planning  (1)

Plan a rectangular floor with minimal overall area that encloses rectangles with specified areas and constraints on the aspect ratio, distance between rectangles and relative placement.

Describe the larger rectangle by Rectangle[{0,0},{H,W}] and each of the smaller ones by ri=Rectangle[{xi,yi},{xi+wi,yi+hi}], i=1 n .

Limit the aspect ratio of each rectangle to be between and for , so that .

The relative placement can be described by two directed graphs, for horizontal placement and for vertical placement. If there is a edge ij, then ri should be to the left of (or below) rj:

Let be the minimal spacing between rectangles. When has the edge ij, rectangle is constrained to be to the left of rectangle , so . When has the edge ij, rectangle is constrained to be below rectangle , so . Traversing the graph and accounting for rectangles that can be at the edges of the floor can be done with the following function:

Given the placement graphs, the areas, and , the rules can be combined in a function that uses GeometricOptimization:

Here are graphs that describe relative placement for 3 rectangles such that the first is to the left of the other two and the second is below the third:

Here is a function to show the plan:

This shows a plan for 10 rectangles with randomly assigned areas:

Structural Optimization Problems  (3)

Find a minimum-weight truss that is subjected to either a vertical load or a horizontal load . The bars of the truss are hollow pipes of inner radius , outer radius and density :

The length of the bar is defined using the height and width of the truss. The cross-sectional area is . The objective is to minimize weight:

When vertical load is applied, the force in each bar is:

When horizontal load is applied, the force in each bar is:

The total forces in the bars must not exceed maximum allowable force , where is the maximum allowable stress:

The truss height and truss width are constrained:

Require that the tube has a minimum wall thickness. This can be done by requiring that with . The relation between bar area and radius is but is not a monomial function. Using and the constraint , the resulting constraints are monomials:

Specify the parameters of the truss:

Solve for to get the optimal truss:

Recover the outer radius of the bar using :

Find a minimum-weight truss subjected to a vertical load . The height and width of the truss are known. The vertical position of joint is not known:

Let be the cross-sectional areas of bar and bar , respectively, and be the density of the bar. The weight of the truss is given by:

Bar undergoes tension. Let be the tensile stress of the material. The force on bar must not exceed the maximum allowable force:

Bar undergoes compression. Let be the compressive stress of the material. The force on bar must not exceed the maximum allowable force:

Specify the parameters:

A specific instance of the geometric optimization problem can be solved for a given value of . Assuming the vertical position of joint must lie between a certain range, solve a range of problems:

Plot the minimum weight:

Find the specific value of that gives the minimum weight:

Find the optimal cross-sectional areas and the truss weight:

Design a minimum-weight cantilever beam subject to a vertical load on the free end. The beam consists of segments of unit length. Each segment has a width and height :

The load causes the beam to deflect and induces stress on each segment of the beam. The stress must be less than the maximum allowable stress :

Let be the deflection at the right end of segment . The deflection at the free end can be found recursively as , where is the Young's modulus and the slope . Since segment is fixed, :

The deflection on the free end of the beam must be less than the maximum allowable deflection :

The width, height and aspect ratios are constrained to be in a certain range:

Specify the parameters:

Find the dimensions of the individual segments by minimizing the weight:

Visualize the cantilever beam:

Circuit Problems  (3)

Digital circuit gate sizing: Find the optimal sizes of the gates in a given circuit subject to power and area constraint such that delay in the circuit is minimized. Consider a seven-gate circuit:

Let be a scaling factor by which each gate must be increased:

The area taken by each gate is assumed to be proportional to the scaling factor, so the total circuit area is:

The energy lost when gate transitions is proportional to the scale factor , the transition frequency of the gate and the energy lost when the gate transitions:

Gate has input capacitance except gates 6 and 7, which have input capacitance of 10:

Gate has a driving resistance :

Gate capacitance is the sum of the input capacitances of the gates its output is connected to, except output gates 6 and 7, whose capacitance is the same as their input capacitance:

The delay of gate is the product of its driving resistance and the gate capacitance:

The objective is to minimize the worst-case delay for all combinations of paths that can be traversed in the circuit:

The circuit area must be less than a specified maximum allowable area:

The power consumed must be less than a specified maximum allowable power:

Find the minimum area for different combinations of maximum allowable area and power:

Plot the optimal tradeoff curves:

Find the widths of wire segments in an interconnected network in a circuit with known capacitance. There are five wire segments in the network below:

For each wire segment, the resistance and capacitances , where , are positive constants depending on the wire properties and is the length of the wire and width :

Using a model, each wire is modeled using a resistor and capacitor. The resulting network becomes a resistor-capacitor network:

The new capacitances of the model are obtained by summing the respective network capacitances with the wire capacitances :

The Elmore delay measures the delay of voltage changing and converging to a new value. The Elmore delay for each capacitor is , where is the set of resistances between capacitors and :

The objective is to minimize the largest Elmore delay:

The wire is constrained to be within a range:

The total area cannot exceed a maximum allowable area:

Specify the parameters:

Find the width of the wires:

Find the optimal doping profile of a transistor such that the base transit time is minimized. Let be the doping profile, where is the base-width. Let be the base transit time. A simplified model as a function of is given by , where is a constant. Let ; then the integral can be discretized using equally spaced points:

The doping gradient constraint can be approximated as:

The doping profile has upper and lower limits and specified initial and final states:

Specify the parameters:

Solve the resulting geometric optimization problem to get the optimal doping profile:

Plot the resulting profile:

Power Control  (1)

Minimize the total power levels that transmitters transmit at to receivers:

The power received by receiver from transmitter is , where represents the path gain from transmitter to receiver :

The signal power at receiver is :

The interference power at receiver is the total power received from all transmitters except , :

The signal-to-interference-and-noise ratio (SINR) of the ^(th) receiver/transmitter pair is given by , where is the noise power at receiver :

The SINR of any receiver/transmitter pair has a minimum threshold. To make this a posynomial constraint, take the inverse of the SINR constraints :

The power levels have a lower and an upper limit:

Specify the parameters:

Find the power levels:

Introduced in 2020
 (12.1)