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) Dual variablesThe dual (dual in the sense that it is the dual related to a user defined constraint) 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 often 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 form representation, corresponding to 471 equality constraint, 2 semidefinite cones and 3 free variables in the primal form. If we instead would have solved this directly in the stated primal form, we have 3 equality constraints, 2 semidefinite cones and no free variables, corresponding to a dual form with 3 variables and two semidefinite constraints. The computational effort is mainly affected by the number of variables in the dual form and the size of the semidefinite cones. Moreover, many solvers have robustness problems with free variables in the primal form (equalities in the dual form). Hence, in this case, this problem can probably be solved much more efficiently if we could use an alternative model. 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)
Variables are actually automatically updated, so the second line in the code above is not needed (but can be useful to understand what is happening). Hence, the following code is equivalent.
The procedure 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 4th output, and can be recovered from the dual to the equality constraints (this is also done automatically by YALMIP in practice, see above).
To simplify things even further, you can tell YALMIP to dualize, solve the dual, and recover the primal variables, by using the associated option.
Mixed problems can be dualized also, i.e. problems involving constraints of both dual and primal form. Constraint in dual form S(y)≥0 are automatically changed to S(y)-X=0, X≥0, and the dualization algorithm is applied to this new problem. Note that problems involving dual form semidefinite constraints typically not gain from being dualized, unless the dual form constraints are few and small compared to the primal form constraints. A problem involving translated cones X≥C where C is a constant is automatically converted to a problem in standard primal form, with no additional slacks variables. Hence, a lower bound on a variable will typically reduce the size of a dualized problem, since no free variables or slacks will be needed to model this cone. Practice has shown that simple bound constraints of the type x≥L where L is a large negative number can lead to problems if one tries to perform the associated variable change in order to write it as a simple LP cone. Essentially, the dual cost will contain large numbers. With a primal problem {min cTx, Ax=b, x≥-L}) will be converted to {min cTz, Az=b+AL, z≥0}) with the dual {min (b+AL)Ty, ATy≤c}. If you want to avoid detection of translated LP cones (and thus treat the involved variables as free variables), set the 4th argument in dualize.
Problems
involving second order cone constraints can also be dualized. A constraint
of the type Your solver has to be able to return both primal and dual variables for the reconstruction of variables to work. All SDP solvers support this, except LMILAB.
Primal matrices (X and Y in the examples above) must
be defined in one simple call in order to enable detection of the primal
structure. In other words, a constraint 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 no 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 1276 equality constraints and 1326 variables is obtained. This means that the effective number of variables is low (the degree of freedom).
For comparison, let us first solve the original problem.
The primalized takes approximately the same time to solve (this can differ between problem instances though).
So why would we want to perform the primalization? We let YALMIP remove the equalities constraints first!
The drastic reduction in actual solution-time of the semidefinite program comes at a price. Removing the equality constraints and deriving a reduced basis with a smaller number of variables requires computation of a QR factorization of a matrix of dimension 1326 by 1276. The cost of doing this is roughly 2 seconds. The total saving in computation time is however still high enough to motivate the primalization. |