Semidefiniteohjelmointi

Semidefinite programming (SDP) is a type of optimization problem where the objective function is linear, and the constraints are linear matrix inequalities (LMIs). It is a generalization of linear programming, where the variables are matrices instead of scalars. SDP is widely used in various fields such as control theory, combinatorial optimization, and machine learning.

The standard form of an SDP problem is as follows:

minimize c^T x

subject to F0 + x1F1 + x2F2 + ... + xnFn ≥ 0

where c is a vector of coefficients, x is a vector of variables, and F0, F1, ..., Fn are symmetric matrices. The inequality F ≥ 0 denotes that F is positive semidefinite, meaning all its eigenvalues are non-negative.

SDP problems can be solved using interior-point methods, which are efficient and reliable for solving large-scale problems. The dual of an SDP problem is also an SDP problem, and strong duality holds, meaning the optimal values of the primal and dual problems are equal.

SDP has several applications in practice. For example, it can be used to solve the maximum cut problem in graph theory, which is NP-hard. SDP can also be used in control theory to design robust controllers for uncertain systems. In machine learning, SDP can be used for semisupervised learning and matrix completion.

In summary, semidefinite programming is a powerful tool for solving optimization problems with linear matrix inequality constraints. It has a wide range of applications in various fields and can be solved efficiently using interior-point methods.