Convex optimization

The convex optimization is a branch of mathematical optimization.

Is to minimize a certain size, the so-called cost function, which on a parameter which is referred to, depending. In addition, certain constraints must be observed, that is, the values ​​that you can choose certain restrictions are subject. These are usually given in the form of equations and inequalities. If a value for all constraints met, it is said, that is permissible. One speaks of a convex optimization problem or a convex program if both the objective function and the set of feasible points is convex. Many practical problems are convex nature. Often, for example, optimized for blocks which are always convex, and the objective function often find using quadratic forms, which are also convex under certain conditions (see definiteness ). Another important special case is the linear optimization wherein a linear objective function is optimized over a convex polyhedron.

An important property of the convex optimization in contrast to the non-convex optimization is that each local optimum is a global optimum. This clearly means that a solution that is at least as good as all other solutions in an environment that also at least as good as all feasible solutions. This allows you to easily search for local optima.

• 5.1 Lagrangian
• 5.2 Lagrange multiplier rule for the convex problem

Introduction

There are many possible formulations of a convex program. At this point a general form as possible be selected. The input parameter is of the one that is, the problem depends on influencing parameters. The objective function is convex. Furthermore, the convex functions and the affine functions are given with. Here is a convex subset of.

Convex program:

Minimize with subject to the constraints

A restriction with is called active. The functions are the so-called inequality constraints and the functions are the so-called equality constraints dar.

History

The discipline of convex optimization arose in part from the convex analysis. The first optimization technique, which is known as the gradient goes back to Gauss. In 1947, the simplex method was introduced by George Dantzig. In addition, interior-point methods have been proposed by Fiacco and McCormick in 1968 for the first time. In the years 1976 and 1977, the ellipsoid method of Yudin and Arkadi Nemirovski David and regardless of Naum Shor has been developed for the solution of convex optimization problems. Narendra Karmarkar described in 1984 for the first time a polynomial potentially be implemented in practice algorithm for nonlinear problems. In 1994, Arkadi Nemirovski developed and Yurii Nesterov interior-point method for convex optimization, which large classes of convex optimization problems could be solved in polynomial time.

The Karush -Kuhn -Tucker conditions, the necessary conditions for the inequality constraint for the first time in 1939 in the Master's thesis ( unpublished) have been performed by William Karush. Known were these, however, only in 1951 after a conference paper by Harold W. Kuhn and Albert W. Tucker.

Prior to 1990, the application of convex optimization was mainly in the operations research and less in the area of ​​engineers. Since 1990, however, more and more applications offered in engineering science. Here can be, inter alia, control and signaling control, communication, and the circuit design call. In addition, new classes of problems such as semidefinite and cone optimization and robust optimization 2nd order originated.

Example

As an example, a one-dimensional problem without equality constraints and with only one inequality condition is considered:

Minimize

Under the constraint:

The allowable range is given by the convex set

For values ​​greater than 1 is not satisfied. The drawing can be seen that assuming for the optimal value.

Optimality conditions

First, necessary optimality conditions are presented. These are criteria that must be met in any case in the optimum. Thereafter, sufficient optimality conditions are formulated. These show that a solution is optimal.

Fritz- John conditions

Be optimal for the above convex program. Then there are multipliers which do not all have the value with the following properties:

• (Complementary slackness condition)
• For all

The Fritz John - conditions are a necessary optimality condition. For they are sufficient. In this case, one may even put. The complementary slackness condition is also called the complementary slackness condition in German. Here, one can prove that if for all, then all multipliers that must be for all. This condition is thus for the construction and design of algorithms of great importance.

Karush -Kuhn -Tucker conditions

The Karush -Kuhn -Tucker conditions ( also known as the KKT ) conditions are necessary for the optimality of a solution in nonlinear optimization. They are the generalization of the Lagrange multipliers of optimization problems under constraints and used in sophisticated neoclassical theory application.

Necessary conditions

Be the objective function and convex functions and the affine functions are the constraint functions. It is a feasible point, ie it applies. Furthermore, it is assumed that the active functions are differentiable at the point, the functions are continuously differentiable at the point. If a local minimum, then there are constants, with and so that

Also, applies

And the complementarity condition is satisfied:

Regularity conditions

For the above necessary condition, the dual scalar may be zero. In such cases, one speaks of degenerate or abnormal. Then, the necessary condition is not important for the characteristics of the feature, only the geometry of the relevant constraints.

There are several conditions which should ensure that the solution is non- degenerate, that is. These are called constraint qualifications.

Sufficient conditions

Be the objective function and convex functions and the affine functions are the constraint functions. It is a feasible point, ie it applies. Furthermore, it is believed that the active gradient and the gradients are linearly independent. If a local minimum, then there are constants, with and so that

Then, the point is a global minimum.

Constraint qualifications

A criterion which ensures that true, it is called qualification constraint. In other words, a condition that ensures that the Fritz - John conditions also satisfy the Karush -Kuhn -Tucker conditions are called constraint qualification.

Examples of constraint qualifications are:

• Slater: It will not occur equality constraints. Furthermore, there is a point, so that for everyone. It should be noted that the qualification constraint Slater is generally regarded as the most important.
• Linear independence - linear independence constraint qualification ( LICQ ): The gradient of the active Ungleichungsbedingungen and the gradients of the equation terms are linearly independent in point.
• Mangasarian - Fromovitz - Mangasarian - Fromovitz constraint qualification ( MFCQ ): The gradient of the active Ungleichungsbedingungen and the gradients of the equation terms are positive - linearly independent in point.
• Constant Rank - Constant rank constraint qualification ( CRCQ ): For each subset of the gradients of the Ungleichungsbedingungen which are active, and the gradient of the equation terms of rank near constant.
• Constant positive linear dependence - Constant positive - linear dependence constraint qualification ( CPLD ): For each subset of the gradients, the Ungleichungsbedingungen which are active, and the gradient of the equation conditions, and if a positive - linear dependence exists at the point, then there is a positive linear relationship near.

One can show that the following two inference strands are

Although MFCQ is not equivalent to CRCQ. In practice, weaker constraint qualifications are preferred since this stronger optimality conditions provide.

Concrete action

Lagrangian

First, the following shorthand notation is introduced:

Where the vector of all multipliers.

Lagrange multiplier rule for the convex problem

Compare also with Lagrange multiplier rule. Concrete action:

• Check if all occurring functions are continuous differentiable. If not, this rule is not applicable.
• Is there a feasible point, for which:? If yes, then is optimal. Otherwise, continue with the next step.
• Determine the gradient of the Lagrangian function.
• Solve the system with no multiplier may be negative. If a restriction is not active, the associated multiplier must be even equal. If one finds a solution, this is optimal.