Convex programming problem

In summary, the optimum of a nonlinear programming problem is, in general, not at an extreme point of the feasible region and may not even be on the boundary. Also, the problem may have local optima distinct from the global optimum. These properties are direct consequences of nonlinearity. A class of nonlinear problems can be defined, however, that are guaranteed to be free of distinct local optima. They are called convex programming problems and are considered in the following section. 

An important result in mathematical programming evolves from the concept of convexity. For the nonlinear programming problem called the convex programming problem... 

If possible, reformulate the MINLP as a convex programming problem. 

Shirkalin, LA. (1997). Solution of Convex Programming Problem with Large Scatter cf Variable Values, SEI AS USSR, Irkutsk (in Russian). 

The global optimization method aBB deterministically locates the global minimum solution of (1) based on the refinement of converging lower and upper bounds. The lower bounds are obtained by the solution of (15), which is formulated as a convex programming problem. Upper bounds are based on the solution of (1) using local minimization techniques. 

It can be shown that this can be generalized to the case of more than two variables. The standard solution of a linear programming problem is then to define the comer points of the convex set and to select the one that yields the best value for the objective function. This is called the Simplex method. 

Although convexity is desirable, many real-world problems turn out to be non-convex. In addition, there is no simple way to demonstrate that a nonlinear problem is a convex problem for all feasible points. Why, then is convex programming studied The main reasons are... 

For example, it is usually impossible to prove that a given algorithm will find the global minimum of a nonlinear programming problem unless the problem is convex. For nonconvex problems, however, many such algorithms find at least a local minimum. Convexity thus plays a role much like that of linearity in the study of dynamic systems. For example, many results derived from linear theory are used in the design of nonlinear control systems. 

Branch and bound (BB) is a class of methods for linear and nonlinear mixed-integer programming. If carried to completion, it is guaranteed to find an optimal solution to linear and convex nonlinear problems. It is the most popular approach and is currently used in virtually all commercial MILP software (see Chapter 7). 

The sufficient conditions for obtaining a global solution of the nonlinear programming problem are that both the objective function and the constraint set be convex. If these conditions are not satisfied, there is no guarantee that the local optima will be the global optima. 

The energy and spectral optimization problems are convex programs so when there are multiple solutions the solution sets form a convex set. The following corollary characterizes how these convex sets of solutions relate to solutions of the Euler equation. In the formulation of this corollary we use the notion of optimal gap Ao—the gap achieved by optimal P and S. The optimal gap is a characteristic of the energy problem, depending only on H and S. 

Note that when setting the list x , j = 1 the authors deviate from the classical Gibbs definition, understanding by the system components not individual substances but their quantities contained in a certain phase. For example, if the water in reaction mixture is in gaseous and condensed phases, its corresponding phase concentrations represent different parameters of the studied system. Such expansion of the space of variables of the problem solved facilitates its reduction to the problems of convex programming (CP). 

McCormick, G. P. Computability of Global Solutions to Factorable Nonconvex Programs Part 1. Convex Underestimating Problems, Math. Program. 10, 146-175 (1976). 

The next iteration consists of creating the new convex hull of concentrations, which include the concentrations obtained by this extension, and checking for favorable recycle reactor extensions from this new convex hull. At iteration P, this involves the solution of the following nonlinear programming problem ... 

McCormick G.P. 1976. Computability of global solutions to factorable nonconvex programs part I - convex underestimating problems. Math. Program., 10, 147-175. 

Sherali H.D. and Adams W.P. 1990. A hierarchy of relaxations between the continnous and convex hull representations for zero-one programming problems, SIAM 1. Discrete Math., 3(3), 411 30. 

This formulation is a standard quadratic programming problem for which an analytical solution exists from the corresponding Kuhn—Tucker conditions. Different versions of the objective function are sometimes used, but the quadratic version is appealing theoretically because it allows investor preferences to be convex. 

If H is positive semidefinite, then problem (QP) is a convex program. Thus, the KKT conditions are sufficient in this case, and any solution to this system will yield a global optimal solution to (QP). When H is indefinite, then local optimal solutions which are not global optimal solutions may... 

Except for constraint (90), this is a linear programming problem in the variables Xj p which can be solved by the simplex method provided a restricted basis entry rule is used which enforces (90). However, in the case when each fj is strictly convex and each is convex, constraint (90) can be... 

If X and ffx), i = 1, 2,. . . , q have some special stracture, then more efficient computational techniques are available. For instance, if X is a convex set and each ffx) is concave, then we first have q concave programming and then a convex programming (because r(f(x) p) is convex under the assumptions). If X is a polyhedron defined by a system of Unear inequalities and each ffx) is hnear, then the ideal points y can be found by q simple linear programming problems. Furthermore, the compromise solutions of y and y can be found by a Unear programming problem (the other compromise solutions, y, 1 < p < >, can be found by convex programming) (Yu 1985). 

---