S. Boyd, S.-J. Kim, L. Vandenberghe, and A. Hassibi
Optimization and Engineering, 8(1):67-127, 2007
(software for generalized geometric programming)
A geometric program (GP) is a type of mathematical optimization problem characterized by objective and constraint functions that have a special form. Recently developed solution methods can solve even large-scale GPs extremely efficiently and reliably; at the same time a number of practical problems,
particularly in circuit design, have been found to be equivalent to (or well approximated by) GPs. Putting these two together, we get effective solutions for the practical problems. The basic approach in GP modeling is to attempt to express a practical problem, such as an engineering analysis or design problem, in GP format. In the best case, this formulation is exact; when this isn’t possible, we settle for an approximate formulation. This tutorial paper collects together in one place the basic background material needed to do GP modeling. We start with the basic definitions and facts, and some methods used to transform problems into GP format. We show how to recognize functions and problems compatible with GP, and how to approximate functions or data in a form compatible with GP (when this is possible). We give some simple and representative examples, and also describe some common extensions of GP, along with methods for solving (or approximately solving) them.
gp_tutorial.pdf
GGPLAB
Contents
1 The GP modeling approach 4
2 Basic geometric programming 5
2.1 Monomial and posynomial functions . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Standard form geometric program . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Simple extensions of GP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.4 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.5 How GPs are solved . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 Feasibility, trade-o®, and sensitivity analysis 10
3.1 Feasibility analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Trade-o® analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3 Sensitivity analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4 GP examples 15
4.1 Power control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2 Optimal doping pro¯le . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5 Generalized geometric programming 18
5.1 Fractional powers of posynomials . . . . . . . . . . . . . . . . . . . . . . . . 19
5.2 Maximum of posynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.3 Generalized posynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.4 Generalized geometric program . . . . . . . . . . . . . . . . . . . . . . . . . 22
6 GGP examples 23
6.1 Floor planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6.2 Digital circuit gate sizing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
6.3 Truss design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
6.4 Wire sizing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
7 More transformations 34
7.1 Function composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
7.2 Additive log terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
7.3 Mixed linear geometric programming . . . . . . . . . . . . . . . . . . . . . . 36
7.4 Generalized posynomial equality constraints . . . . . . . . . . . . . . . . . . 37
8 Approximation and ¯tting 39
8.1 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
8.2 Local monomial approximation . . . . . . . . . . . . . . . . . . . . . . . . . 42
8.3 Monomial ¯tting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
8.4 Max-monomial ¯tting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
8.5 Posynomial ¯tting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2
9 Extensions 52
9.1 Signomial programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
9.2 Mixed-integer geometric programming . . . . . . . . . . . . . . . . . . . . . 54
10 Notes and references
0 komentar:
Post a Comment