Downloaded from https://www.everyspec.com AMCP 706-197 I4 Algebraically, a function fAx) is convex if point x, theorem 6 implies that a convex )- ))(x) function is convex along any line. This allows us to test to se whether a given function of n (12-14) variables is noG convex, for if any line in for all x., x 2 in the (convex) domain of defi- n-dimensional space can be found along which nition of f. The function is strictly convex if g(a) is not convex, then (x) is not convex the strict inequality holds. either. A convex programming problem is one of minimizing a convex function over a convex constraint set.
As we mentioned earlier, the main theorem regarding such programs is that Many problems involve both equality and any local minimum of a convex programmig inequality constraints. In such problems, it problem is a global minimum. Furthermore, if has been found that the linear function there ar a number of points at which the g(x) = a T x is the only function for which the global minimum is attained, the set of all such t points is convex. Thus, there can be no sepa- R = {xlg(x) = 0} (12-1 ' ) ted local minima with different functional is convex. values.
Since most procedures can locate only l incemos proeres an le on Nonlinear functions in two dimensions loal inim, tese xoprtie at ver adan- have graphs that are curved surfaces. If x, aand tageous. The theorems of convexity (Refs. 11 and 12) listed in Table 12-2 allow this to b x 2 are on the graph and are, therefore, in the done in some cases. constraint set R, then points on the line seg- dninsecs.ment joining x 1 and x 2 will, in general, not lie As a consequence of convexity theorems on the graph (will not be in R). A hyperplane, 1 and 2, the problem of minimizing a convex being "flat", is an obvious exception.
function f(x), subject to r constrainta g(x) > Consider the problem of minimizing f(x) bl, i=1,.-.,r with all g, convex, is always a Pi, convex programming problem. This is true be- subject to the constraints g(x)> 0, i = 1,... " cause, from theorem 1, each of the sets and hj(x) = 0, j = 1".,o s. Rom the preceding statements, this may not be a convex pro- Ri = {xlg(x)> b,} (12-15) gramming problem if any of the functions is convex. The constraint set R, which is the hj(x) are nonlinear. This, of course, does not intersection of all the sets R, is also convex by preclude efficient solution of such problems, convexity theorem 2.
but it does make it more difficult to guaran- Since all linear functions are convex, a lin- tee the absence of local optima. ear programming problem is always a convex In many cases, the equality constraints programming problem. This establishes more can be used to eliminate some of the vari- firmly the geometrically evident fact that a ables, leaving a problem with only inequality linear program cannot have local optima dis- constiaints and fewer variables. Even if the tinct from the global optimum.
equalities are difficult to solve analytically (for example, if they are highly nonlinear), it Since convex programs can be identified may still be worthwhile to solve them numeri- by determining whether the objective and cally. Such an approach has been used suc- constraint functions of the problem are con- cessfuly for structural design. (Refs. 13 and vex, it is important to characterize convex 14). functions closely. This can be done by using convexity theorems 3 though 6.
Statement b 12-3.4 THE KUHN-TUCKER CONDITIONS in theorem 3 says that the function, evaluated at any point x,, never lies below its tangent The most important theoretical results in plane passed through any other point X 2 . the field of nonlinear programming are the Theorem 4 is a direct consequence of state- conditions of Kuhn and Tucker, which must men codtin of tKeore an3.krwihms ment c in theorem 3. be satisfied at any constrained optimum, local Since f(x + as) is the function evaluated or global, of any linear and of most nonlinem at points along the line s passing through the programming problems (Ref. 15). These con- 12-11