5.4.6. C#的SDP建模与优化

在本节中,我们将使用 MindOptC# API 来建模以及求解 半定规划问题示例 中的问题。

5.4.6.1. SDP示例1

第一步:创建优化模型:

先建立一空的MindOpt模型。

44            // Create model
45            MDOEnv env = new MDOEnv(); 
46            MDOModel model = new MDOModel(env); 
47            model.Set(MDO.StringAttr.ModelName, "SDP_01");

第二步:SDP模型输入

我们利用 MDOModel.AddPsdVar 创建一个新的半正定矩阵变量,并同时设定其对应的目标函数中的矩阵系数。其中,第一个参数为 矩阵系数,这里它是通过 MDOMatrix.Coo 方法创建的一个 MDOMatrix 类的实例。注意到该系数矩阵的维度应与矩阵变量相同。第二个参数为该变量的名称。

51                // Add variables.
52                MDOPsdVar psd_var = model.AddPsdVar(MDOMatrix.Coo(dim_mat, dim_mat, C_nz_indices, C_nz_values), "X0");

接着,我们输入第一个约束。我们利用 MDOModel.AddPsdConstr 建立一个带半正定矩阵变量的约束。其中,第一个参数分别为该约束中的 半正定表达式,即 \(\langle \mathbf{A},\mathbf{X} \rangle\)。 我们通过 MDOPsdExpr 类的初始化方法 MDOPsdExpr.MDOPsdExpr 创建。第二个系数为该约束的属性,MDO.EQUAL (‘=’) 代表等式约束。第三个参数为该约束的右侧值 (此处为1.0)。最后一个参数为该约束的名称。

54                /* Add constraints. */
55                MDOPsdExpr psd_expr = new MDOPsdExpr(psd_var, MDOMatrix.Coo(dim_mat, dim_mat, A_nz_indices, A_nz_values));
56                model.AddPsdConstr(psd_expr, MDO.EQUAL, 1.0, "C0");

最后,我们利用 MDOModel.SetObjective 设定优化函数中的其余部分 (此处为0),并将优化方向改为maximization (-1)。

58                /* Set objective function. */
59                MDOLinExpr obj = new MDOLinExpr();
60                model.SetObjective(obj, MDO.MAXIMIZE);

第三步:求解SDP模型

模型输入后,我们接着用 MDOModel.Optimize 来求解问题。

62                // Solve the problem and populate optimization result.
63                model.Optimize();

第四步: 取得SDP模型的解

我们利用泛用函数 MDOModel.Get 来取得最优的的目标函数值,即 ObjVal 属性。

65                if (model.Get(MDO.IntAttr.Status) == MDO.Status.OPTIMAL)
66                {
67                    Console.WriteLine($"Optimal objective value is: {model.Get(MDO.DoubleAttr.ObjVal)}");
68                }
69                else
70                {
71                    Console.WriteLine("No feasible solution.");
72                }

文件链接 MdoSdoEx1.cs 提供了完整源代码:

 1/**
 2 *  Description
 3 *  -----------
 4 *
 5 *  Semidefinite optimization (row-wise input).
 6 *
 7 *  Formulation
 8 *  -----------
 9 *
10 *  Maximize 
11 *  obj: tr(C X) 
12 * 
13 *  Subject To
14 *    c0 : tr(A X) = 1
15 *         X is p.s.d.
16 *
17 *  Matrix
18 *    C = [ -3  0  1 ]  A = [ 3 0 1 ]
19 *        [  0 -2  0 ]      [ 0 4 0 ]
20 *        [  1  0 -3 ]      [ 1 0 5 ]
21 *  End
22 */
23
24using Mindopt;
25
26namespace Example
27{
28    public class MdoSdoEx1
29    {
30        public static void Main(string[] args)
31        {
32            /* Model data. */
33            int    num_mats = 1;
34            int    dim_mat = 3;                                 /* Dimension of the matrix variables. */
35
36            int      C_nnz = 4;
37            int[]    C_nz_indices = new int[]    {  0,   2,    4,    8    }; /* Nonzero vectorized index of obj coeff. */
38            double[] C_nz_values  = new double[] { -3.0, 1.0,  -2.0, -3.0 }; /* Nonzero values of obj coeff. */
39
40            int      A_nnz = 4;
41            int[]    A_nz_indices = new int[]    { 0,    2,    4,    8    }; /* Nonzero vectorized index of constr coeff. */
42            double[] A_nz_values  = new double[] { 3.0,  1.0,  4.0,  5.0  }; /* Nonzero values of constr coeff. */
43
44            // Create model
45            MDOEnv env = new MDOEnv(); 
46            MDOModel model = new MDOModel(env); 
47            model.Set(MDO.StringAttr.ModelName, "SDP_01");
48
49            try
50            {
51                // Add variables.
52                MDOPsdVar psd_var = model.AddPsdVar(MDOMatrix.Coo(dim_mat, dim_mat, C_nz_indices, C_nz_values), "X0");
53        
54                /* Add constraints. */
55                MDOPsdExpr psd_expr = new MDOPsdExpr(psd_var, MDOMatrix.Coo(dim_mat, dim_mat, A_nz_indices, A_nz_values));
56                model.AddPsdConstr(psd_expr, MDO.EQUAL, 1.0, "C0");
57
58                /* Set objective function. */
59                MDOLinExpr obj = new MDOLinExpr();
60                model.SetObjective(obj, MDO.MAXIMIZE);
61
62                // Solve the problem and populate optimization result.
63                model.Optimize();
64
65                if (model.Get(MDO.IntAttr.Status) == MDO.Status.OPTIMAL)
66                {
67                    Console.WriteLine($"Optimal objective value is: {model.Get(MDO.DoubleAttr.ObjVal)}");
68                }
69                else
70                {
71                    Console.WriteLine("No feasible solution.");
72                }
73            }
74            catch (Exception e)
75            { 
76                Console.WriteLine("Exception during optimization");
77                Console.WriteLine(e.Message);
78            }
79            finally
80            { 
81                model.Dispose();
82                env.Dispose();
83            }
84        }
85    }
86}

5.4.6.2. SDP示例2

第一步:创建MindOpt模型

首先,我们必须先建立一空的MindOpt模型。

61            // Create model
62            MDOEnv env = new MDOEnv(); 
63            MDOModel model = new MDOModel(env); 
64            model.Set(MDO.StringAttr.ModelName, "SDP_02");

第二步:SDP模型输入

接着,我们利用 MDOModel.AddPsdVar 创建两个新的半正定矩阵变量,并同时设定他们对应的目标函数中的矩阵系数。其中,第一个参数为 矩阵系数,这里它是通过 MDOMatrix.Coo 方法创建的一个 MDOMatrix 类的实例。注意到该系数矩阵的维度应与矩阵变量相同。第二个参数为该变量的名称。

69                MDOPsdVar psd_var0 = model.AddPsdVar(MDOMatrix.Coo(dim_mat[0], dim_mat[0], C0_nz_indices, C0_nz_values), "X0");
70                MDOPsdVar psd_var1 = model.AddPsdVar(MDOMatrix.Coo(dim_mat[1], dim_mat[1], C1_nz_indices, C1_nz_values), "X1");

我们再利用 MDOModel.AddVar 创建两个线性变量。其中,第一个和第二个参数为 变量下界与上界。第三个参数为目标函数中该变量对应的系数。第四个参数为该变量的类型,在这里是连续变量类型 (‘C’)。最后一个参数是该变量名称。

71                MDOVar    var0     = model.AddVar(0.0, MDO.INFINITY, 0.0, 'C', "x0");
72                MDOVar    var1     = model.AddVar(0.0, MDO.INFINITY, 0.0, 'C', "x1"); 

下一步,我们创建约束。我们利用 MDOModel.AddPsdConstr 建立带半正定矩阵变量的约束。其中,第一个参数分别为该约束中的 半正定表达式。由于在该例子中,约束同时包含半正定变量与线性变量,我们分两步构造其半正定表达式。我们首先通过 MDOPsdExpr 类的初始化方法 MDOPsdExpr.MDOPsdExpr 创建半正定部分,再通过 MDOPsdExpr.AddTerms 添加剩余的线性部分, 得到最终的该约束对应的半正定表达式。第二个系数为该约束的属性,MDO.EQUAL (‘=’),代表等式约束。第三个参数为该约束的右侧值 (此处为1.0)。最后一个参数为该约束的名称。

74                /* Add constraints. */
75                MDOPsdExpr psd_expr0 = new MDOPsdExpr(psd_var0, MDOMatrix.Coo(dim_mat[0], dim_mat[0], A0_nz_indices, A0_nz_values));
76                MDOVar[] row0_vars = new MDOVar[] { var0 };
77                psd_expr0.AddTerms(row0_values, row0_vars);
78                model.AddPsdConstr(psd_expr0, MDO.EQUAL, 1.0, "C0");
79
80                MDOPsdExpr psd_expr1 = new MDOPsdExpr(psd_var1, MDOMatrix.Coo(dim_mat[0], dim_mat[0], A1_nz_indices, A1_nz_values));
81                MDOVar[] row1_vars = new MDOVar[] { var1 };
82                psd_expr1.AddTerms(row1_values, row1_vars);        
83                model.AddPsdConstr(psd_expr1, MDO.EQUAL, 2.0, "C1");

最后,我们利用 MDOModel.SetObjective 设定优化函数中的其余部分 (此处为0),并将优化方向改为maximization (-1)。

85                /* Set objective function. */
86                MDOLinExpr obj = new MDOLinExpr();
87                model.SetObjective(obj, MDO.MAXIMIZE);

第三步:求解SDP模型

模型输入后,我们接着用 MDOModel.Optimize 来求解问题。

89                // Solve the problem and populate optimization result.
90                model.Optimize();

第四步: 取得SDP模型的解

我们利用泛用函数 MDOModel.Get 来取得最优的的目标函数值,即 ObjVal 属性。

92                if (model.Get(MDO.IntAttr.Status) == MDO.Status.OPTIMAL)
93                {
94                    Console.WriteLine($"Optimal objective value is: {model.Get(MDO.DoubleAttr.ObjVal)}");
95                }
96                else
97                {
98                    Console.WriteLine("No feasible solution.");
99                }

文件链接 MdoSdoEx2.cs 提供了完整源代码:

  1/**
  2 *  Description
  3 *  -----------
  4 *
  5 *  Semidefinite optimization (row-wise input).
  6 *
  7 *  Formulation
  8 *  -----------
  9 *
 10 *  Maximize
 11 *  obj: tr(C0 X0)   + tr(C0 X1)    + 0 x0 + 0 x1
 12 *
 13 *  Subject To
 14 *   c0 : tr(A00 X0)                + 1 x0        = 1
 15 *   c1 :              tr(A00 X1)          + 1 x1 = 2
 16 *  Bounds
 17 *    0 <= x0
 18 *    0 <= x1
 19 *    X1, X2 are p.s.d.
 20 *
 21 *  Matrix
 22 *    C0 =  [ 2 1 ]   A00 = [ 3 1 ]
 23 *          [ 1 2 ]         [ 1 3 ]
 24 *
 25 *    C0 = [ 3 0 1 ]  A00 = [ 3 0 1 ]
 26 *         [ 0 2 0 ]        [ 0 4 0 ]
 27 *         [ 1 0 3 ]        [ 1 0 5 ]
 28 *  End
 29 */
 30using Mindopt;
 31
 32namespace Example
 33{
 34    public class MdoSdoEx2
 35    {
 36        public static void Main(string[] args)
 37        {
 38            /* Model data. */
 39            int    num_mats = 1;
 40            int[]  dim_mat  = new int[] { 2, 3 };                 /* Dimension of the matrix variables. */
 41
 42            int      C0_nnz = 3;
 43            int[]    C0_nz_indices = new int[]    {  0,   1,   3   };  /* Nonzero vectorized index of obj coeff. */
 44            double[] C0_nz_values  = new double[] {  2.0, 1.0, 2.0 };  /* Nonzero values of obj coeff. */
 45            
 46            int      C1_nnz = 4;
 47            int[]    C1_nz_indices = new int[]    {  0,   2,   4,    8   };   /* Nonzero vectorized index of obj coeff. */
 48            double[] C1_nz_values  = new double[] {  3.0, 1.0, 2.0,  3.0 };   /* Nonzero values of obj coeff. */
 49
 50            int      A0_nnz = 3;
 51            int[]    A0_nz_indices = new int[]    {  0,   1,   3   };    /* Nonzero vectorized index of constr coeff. */
 52            double[] A0_nz_values  = new double[] {  3.0, 1.0, 3.0 };    /* Nonzero values of constr coeff. */
 53
 54            int      A1_nnz = 4;
 55            int[]    A1_nz_indices = new int[]    {  0,   2,   4,    8    };  /* Nonzero vectorized index of constr coeff. */
 56            double[] A1_nz_values  = new double[] {  3.0, 1.0, 4.0,  5.0  };  /* Nonzero values of constr coeff. */
 57            
 58            double[] row0_values = new double[] {  1.0 };
 59            double[] row1_values = new double[] {  1.0 };
 60
 61            // Create model
 62            MDOEnv env = new MDOEnv(); 
 63            MDOModel model = new MDOModel(env); 
 64            model.Set(MDO.StringAttr.ModelName, "SDP_02");
 65
 66            try
 67            {
 68                // Add variables.
 69                MDOPsdVar psd_var0 = model.AddPsdVar(MDOMatrix.Coo(dim_mat[0], dim_mat[0], C0_nz_indices, C0_nz_values), "X0");
 70                MDOPsdVar psd_var1 = model.AddPsdVar(MDOMatrix.Coo(dim_mat[1], dim_mat[1], C1_nz_indices, C1_nz_values), "X1");
 71                MDOVar    var0     = model.AddVar(0.0, MDO.INFINITY, 0.0, 'C', "x0");
 72                MDOVar    var1     = model.AddVar(0.0, MDO.INFINITY, 0.0, 'C', "x1"); 
 73
 74                /* Add constraints. */
 75                MDOPsdExpr psd_expr0 = new MDOPsdExpr(psd_var0, MDOMatrix.Coo(dim_mat[0], dim_mat[0], A0_nz_indices, A0_nz_values));
 76                MDOVar[] row0_vars = new MDOVar[] { var0 };
 77                psd_expr0.AddTerms(row0_values, row0_vars);
 78                model.AddPsdConstr(psd_expr0, MDO.EQUAL, 1.0, "C0");
 79
 80                MDOPsdExpr psd_expr1 = new MDOPsdExpr(psd_var1, MDOMatrix.Coo(dim_mat[0], dim_mat[0], A1_nz_indices, A1_nz_values));
 81                MDOVar[] row1_vars = new MDOVar[] { var1 };
 82                psd_expr1.AddTerms(row1_values, row1_vars);        
 83                model.AddPsdConstr(psd_expr1, MDO.EQUAL, 2.0, "C1");
 84
 85                /* Set objective function. */
 86                MDOLinExpr obj = new MDOLinExpr();
 87                model.SetObjective(obj, MDO.MAXIMIZE);
 88        
 89                // Solve the problem and populate optimization result.
 90                model.Optimize();
 91
 92                if (model.Get(MDO.IntAttr.Status) == MDO.Status.OPTIMAL)
 93                {
 94                    Console.WriteLine($"Optimal objective value is: {model.Get(MDO.DoubleAttr.ObjVal)}");
 95                }
 96                else
 97                {
 98                    Console.WriteLine("No feasible solution.");
 99                }
100            }
101            catch (Exception e)
102            { 
103                Console.WriteLine("Exception during optimization");
104                Console.WriteLine(e.Message);
105            }
106            finally
107            { 
108                model.Dispose();
109                env.Dispose();
110            }
111        }
112    }
113}