Changing to SDP (optimization)

  • Thread starter perplexabot
  • Start date
  • Tags
    Optimization
In summary, the conversation discusses an objective function that is being minimized with the help of CVX. The speaker uses the schur complement to simplify the objective function, which results in a series of equivalent formulations. The final formulation involves two matrices, X and Z, which satisfy certain constraints. The speaker asks for confirmation on the correctness of this formulation and provides links for further reading and discussion.
  • #1
perplexabot
Gold Member
329
5
Hey all. Let me get right to it!

I have the following objective function: [tex]\mathbf{minimize} \ \ trace((G^TG)^{-1})[/tex]
I am trying to minimize it with CVX.

I used schur complement to do the following:
[tex]
\begin{equation*}
\begin{aligned}
& \underset{G}{\text{minimize}}
& & \mathrm{trace}((G^TG)^{-1}) \\
\end{aligned}
\end{equation*}
[/tex]
which is equivalent to
[tex]
\begin{equation*}
\begin{aligned}
& \underset{t, G}{\text{minimize}}
& & \mathrm{t} \\
& \text{subject to}
&& t \geq\mathrm{trace}((G^TG)^{-1})
\end{aligned}
\end{equation*}
[/tex]
which is equivalent to
[tex]
\begin{equation*}
\begin{aligned}
& \underset{t, G, X, Z}{\text{minimize}}
& & \mathrm{t} \\
& \text{subject to}
&& t \geq\mathrm{trace}(Z) \\
&&&\begin{bmatrix} X & G^T \\G & I \end{bmatrix} \succeq 0 \qquad \\
&&&\begin{bmatrix} Z & I \\ I & X \end{bmatrix} \succeq 0 \qquad
\end{aligned}
\end{equation*}
[/tex]

Those two matrices introduced by schur complement achieve the following two inequalities: [tex]X \geq G^TG[/tex] and [tex]Z \geq X^{-1}[/tex]

My question is, is this formulation correct?

Here are some links that may be worth the read if you are interested:
The work I did is based on the following similar example.
I have had some help at the official cvx forums.

Thank you for reading : ) Any comments, pointers or advice is much appreciated!

EDIT: Apologies if this is in the wrong category.
 
Last edited:

Related to Changing to SDP (optimization)

1. What is SDP optimization?

SDP optimization stands for semidefinite programming optimization. It is a mathematical optimization technique used to solve problems in which the objective and constraints are specified in terms of linear matrix inequalities.

2. How does SDP optimization differ from other optimization techniques?

SDP optimization is a type of convex optimization, meaning that the objective function and constraints must be convex. It is also unique in that it involves optimizing over a space of symmetric matrices instead of vectors, as in other optimization techniques.

3. What types of problems can be solved using SDP optimization?

SDP optimization can be used to solve a wide range of problems, including: maximum cut problems, graph partitioning, combinatorial optimization, robust control, and many more. It has applications in various fields such as engineering, computer science, economics, and physics.

4. What are the advantages of using SDP optimization?

SDP optimization is advantageous because it can handle large-scale problems with a high degree of accuracy. It also guarantees global optimality for convex problems, meaning that the solution obtained is the best possible solution. Additionally, it has a wide range of applications and can be used to solve complex problems that other techniques may struggle with.

5. Are there any limitations to using SDP optimization?

One limitation of SDP optimization is that it can be computationally expensive for large problems. It also requires the objective and constraints to be specified as linear matrix inequalities, which may not be possible for all problems. Additionally, it may not be suitable for non-convex problems, as it cannot guarantee global optimality in these cases.

Similar threads

  • Linear and Abstract Algebra
Replies
10
Views
302
  • Linear and Abstract Algebra
Replies
8
Views
957
  • Linear and Abstract Algebra
Replies
16
Views
1K
  • Introductory Physics Homework Help
Replies
6
Views
307
Replies
27
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Linear and Abstract Algebra
Replies
8
Views
1K
Replies
1
Views
562
Replies
1
Views
831
Back
Top