DualityProblems in YALMIP are internally written in the following format (this will be referred to the dual form, or dual type representation) The dual to this problem is (called the primal form) ![]() Some solvers are capable of treating an extension with equality constraints in the dual form, corresponding to free (unconstrained) variables in the primal form. The dual (in our notation) variable X can be obtained using YALMIP. Consider the following version of the Lyapunov stability example (of-course, dual variables in LP, QP and SOCP problems can also be extracted)
The dual variables related to the constraints P>I and ATP+PA< 0 can be obtained by using the command dual and indexing of lmi-objects.
Standard indexing can also be used.
Complementary slackness can easily be checked since double is overloaded on lmi-objects..
Notice, DualizeImportant to note is that problems in YALMIP are modeled internally in the dual format (your primal problem is in dual form). In control theory and many other fields, this is the natural representation (we have a number of variables on which we have inequality constraints), but in some fields (combinatorial optimization), the primal form is more natural. Due to the choice to work in the dual form, some problems are treated very inefficiently in YALMIP. Consider the following problem in YALMIP.
YALMIP will explicitly parameterize the variable X with free 465 variables, Y with 6 free variables, create two semidefinite constraints and introduce 3 equality constraints in the dual representation, corresponding to 471 equality constraint, 2 semidefinite cones and 3 free variables in the primal of this dual. If we instead would have solved this directly in the stated primal form, we would have had 3 equality constraints, 2 semidefinite cones and no free variables, corresponding to a dual problem with 3 variables and two semidefinite constraints. The computational effort is mainly affected by the number of dual variables and the size of the semidefinite cones. Moreover, many solvers have robustness problems with free variables in the primal (equalities in the dual). Hence, in this case, this problem can probably be solved much more efficiently in the alternative form instead. The command dualize can be used to extract the primal form, and return the dual of this problem in YALMIPs preferred dual form.
If we solve this problem in dual form, the duals to the constraints in Fd will correspond to the original variables X and Y. The optimal values of these variables can be reconstructed easily (note that the dual problem is a maximization problem)
The function can be applied also to problems with free variables in the primal form, corresponding to equality constraints in the dual form.
The detected free variables are returned as the 5th output. These variables can be recovered from the dual of the equality constraints in the solved problem.
PrimalizeFor completeness, a functionality called primalize is available. This function takes an optimization problem in dual form and returns a YALMIP model in primal form. Consider the following SDP with 3 free variables, 1 equality constraint, and 1 SDP constraint of dimension 2.
A model in primal form is (note the negation of the objective function, primalize assumes the objective function should be maximized)
The problem can now be solved in the primal form, and the original variables are reconstructed from the duals of the equality constraints (placed last). Note that the primalize function returns an objective function that should be minimized.
Why not dualize the primalized model!
The model obtained from the primalization is most often more complex than the original model, so there is typically not any reason to primalize a model. There are however some cases where it may make sense. Consider the problem in the KYP example
The original problem has 466 variables and one semidefinite constraint. If we primalize this problem, a new problem with 466 equality constraints and 496 variables is obtained.
For comparison, let us first solve the original problem.
The primalized problem is solved roughly twice as fast here (this can differ a lot between problem instances though).
Although we see some improvement here in terms of computational effort needed, the majority of solvers perform bad on this problem due to the equality constraints. However, if we let YALMIP remove the equalities constraints first, most solvers perform very well.
The drastic reduction in actual solution-time of the semidefinite program of-course comes at a price. Removing the equality constraints and deriving a reduced basis with a smaller number of variables requires the computation of a sparse QR factorization of a matrix of dimension 496 by 466. |