5.4.4. Java的SDP建模与优化

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

5.4.4.1. SDP示例1

首先,需要引入头文件:

23import com.alibaba.damo.mindopt.*;

第一步:创建优化模型:

先建立一空的MindOpt模型。

40        // Create model
41        MDOEnv env = new MDOEnv(); 
42        MDOModel model = new MDOModel(env); 
43        model.set(MDO.StringAttr.ModelName, "SDP_01");

第二步:SDP模型输入

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

46            // Add variables.
47            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)。最后一个参数为该约束的名称。

49            /* Add constraints. */
50            MDOPsdExpr psd_expr = new MDOPsdExpr(psd_var, MDOMatrix.coo(dim_mat, dim_mat, A_nz_indices, A_nz_values));
51            model.addPsdConstr(psd_exprs, MDO.EQUAL, 1.0, "C0");

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

53            /* Set objective function. */
54            MDOLinExpr objective = new MDOLinExpr();
55            model.setObjective(objective, MDO.MAXIMIZE); 

第三步:求解SDP模型

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

57            // Step 3. Solve the problem and populate optimization result.
58            model.optimize();

第四步: 取得SDP模型的解

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

60            if (model.get(MDO.IntAttr.Status) == MDO.OPTIMAL) {
61                System.out.println("Optimal objective value is: " + model.get(MDO.DoubleAttr.ObjVal));
62            }
63            else {
64                System.out.println("No feasible solution.");
65            }

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

 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 */
23import com.alibaba.damo.mindopt.*;
24import java.util.*;
25
26public class MdoSdoEx1 { 
27    public static void main(String[] args) throws MDOException {
28        /* Model data. */
29        int    num_mats = 1;
30        int    dim_mat = 3;                                 /* Dimension of the matrix variables. */
31
32        int      C_nnz = 4;
33        int[]    C_nz_indices = new int[]    {  0,   2,    4,    8    }; /* Nonzero vectorized index of obj coeff. */
34        double[] C_nz_values  = new double[] { -3.0, 1.0,  -2.0, -3.0 }; /* Nonzero values of obj coeff. */
35
36        int      A_nnz = 4;
37        int[]    A_nz_indices = new int[]    { 0,    2,    4,    8    }; /* Nonzero vectorized index of constr coeff. */
38        double[] A_nz_values  = new double[] { 3.0,  1.0,  4.0,  5.0  }; /* Nonzero values of constr coeff. */
39
40        // Create model
41        MDOEnv env = new MDOEnv(); 
42        MDOModel model = new MDOModel(env); 
43        model.set(MDO.StringAttr.ModelName, "SDP_01");
44
45        try {
46            // Add variables.
47            MDOPsdVar psd_var = model.addPsdVar(MDOMatrix.coo(dim_mat, dim_mat, C_nz_indices, C_nz_values), "X0");
48        
49            /* Add constraints. */
50            MDOPsdExpr psd_expr = new MDOPsdExpr(psd_var, MDOMatrix.coo(dim_mat, dim_mat, A_nz_indices, A_nz_values));
51            model.addPsdConstr(psd_exprs, MDO.EQUAL, 1.0, "C0");
52            
53            /* Set objective function. */
54            MDOLinExpr objective = new MDOLinExpr();
55            model.setObjective(objective, MDO.MAXIMIZE); 
56
57            // Step 3. Solve the problem and populate optimization result.
58            model.optimize();
59
60            if (model.get(MDO.IntAttr.Status) == MDO.OPTIMAL) {
61                System.out.println("Optimal objective value is: " + model.get(MDO.DoubleAttr.ObjVal));
62            }
63            else {
64                System.out.println("No feasible solution.");
65            }
66        } catch (Exception e) { 
67            System.out.println("Exception during optimization");
68            e.printStackTrace();
69        } finally { 
70            model.dispose();
71            env.dispose();
72        }
73    }
74}

5.4.4.2. SDP示例2

首先,需要引入头文件:

30import com.alibaba.damo.mindopt.*;

第一步:创建MindOpt模型

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

58        // Create model
59        MDOEnv env = new MDOEnv(); 
60        MDOModel model = new MDOModel(env); 
61        model.set(MDO.StringAttr.ModelName, "SDP_02");

第二步:SDP模型输入

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

65            MDOPsdVar psd_var0 = model.addPsdVar(MDOMatrix.coo(dim_mat[0], dim_mat[0], C0_nz_indices, C0_nz_values), "X0");
66            MDOPsdVar psd_var1 = model.addPsdVar(MDOMatrix.coo(dim_mat[1], dim_mat[1], C1_nz_indices, C1_nz_values), "X1");

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

67            MDOVar    var0     = model.addVar(0.0, MDO.INFINITY, 0.0, 'C', "x0");
68            MDOVar    var1     = model.addVar(0.0, MDO.INFINITY, 0.0, 'C', "x1"); 

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

70            /* Add constraints. */
71            MDOPsdExpr psd_expr0 = new MDOPsdExpr(psd_var0, MDOMatrix.coo(dim_mat[0], dim_mat[0], A0_nz_indices, A0_nz_values));
72            MDOVar[] row0_vars = new MDOVar[] { var0 };
73            psd_expr0.addTerms(row0_values, row0_vars);
74            model.addPsdConstr(psd_expr0, MDO.EQUAL, 1.0, "C0");
75
76            MDOPsdExpr psd_expr1 = new MDOPsdExpr(psd_var1, MDOMatrix.coo(dim_mat[0], dim_mat[0], A1_nz_indices, A1_nz_values));
77            MDOVar[] row1_vars = new MDOVar[] { var1 };
78            psd_expr1.addTerms(row1_values, row1_vars);        
79            model.addPsdConstr(psd_expr1, MDO.EQUAL, 2.0, "C1");

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

81            /* Set objective function. */
82            MDOLinExpr objective = new MDOLinExpr();
83            model.setObjective(objective, MDO.MAXIMIZE); 

第三步:求解SDP模型

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

85            // Step 3. Solve the problem and populate optimization result.
86            model.optimize();

第四步: 取得SDP模型的解

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

88            if (model.get(MDO.IntAttr.Status) == MDO.OPTIMAL) {
89                System.out.println("Optimal objective value is: " + model.get(MDO.DoubleAttr.ObjVal));
90            }
91            else {
92                System.out.println("No feasible solution.");
93            }

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

  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 */
 30import com.alibaba.damo.mindopt.*;
 31import java.util.*;
 32
 33public class MdoSdoEx2 { 
 34    public static void main(String[] args) throws MDOException {
 35        /* Model data. */
 36        int    num_mats = 1;
 37        int[]  dim_mat  = new int[] { 2, 3 };                 /* Dimension of the matrix variables. */
 38
 39        int      C0_nnz = 3;
 40        int[]    C0_nz_indices = new int[]    {  0,   1,   3   };  /* Nonzero vectorized index of obj coeff. */
 41        double[] C0_nz_values  = new double[] {  2.0, 1.0, 2.0 };  /* Nonzero values of obj coeff. */
 42        
 43        int      C1_nnz = 4;
 44        int[]    C1_nz_indices = new int[]    {  0,   2,   4,    8   };   /* Nonzero vectorized index of obj coeff. */
 45        double[] C1_nz_values  = new double[] {  3.0, 1.0, 2.0,  3.0 };   /* Nonzero values of obj coeff. */
 46
 47        int      A0_nnz = 3;
 48        int[]    A0_nz_indices = new int[]    {  0,   1,   3   };    /* Nonzero vectorized index of constr coeff. */
 49        double[] A0_nz_values  = new double[] {  3.0, 1.0, 3.0 };    /* Nonzero values of constr coeff. */
 50
 51        int      A1_nnz = 4;
 52        int[]    A1_nz_indices = new int[]    {  0,   2,   4,    8    };  /* Nonzero vectorized index of constr coeff. */
 53        double[] A1_nz_values  = new double[] {  3.0, 1.0, 4.0,  5.0  };  /* Nonzero values of constr coeff. */
 54        
 55        double[] row0_values = new double[] {  1.0 };
 56        double[] row1_values = new double[] {  1.0 };
 57
 58        // Create model
 59        MDOEnv env = new MDOEnv(); 
 60        MDOModel model = new MDOModel(env); 
 61        model.set(MDO.StringAttr.ModelName, "SDP_02");
 62
 63        try {
 64            // Add variables.
 65            MDOPsdVar psd_var0 = model.addPsdVar(MDOMatrix.coo(dim_mat[0], dim_mat[0], C0_nz_indices, C0_nz_values), "X0");
 66            MDOPsdVar psd_var1 = model.addPsdVar(MDOMatrix.coo(dim_mat[1], dim_mat[1], C1_nz_indices, C1_nz_values), "X1");
 67            MDOVar    var0     = model.addVar(0.0, MDO.INFINITY, 0.0, 'C', "x0");
 68            MDOVar    var1     = model.addVar(0.0, MDO.INFINITY, 0.0, 'C', "x1"); 
 69            
 70            /* Add constraints. */
 71            MDOPsdExpr psd_expr0 = new MDOPsdExpr(psd_var0, MDOMatrix.coo(dim_mat[0], dim_mat[0], A0_nz_indices, A0_nz_values));
 72            MDOVar[] row0_vars = new MDOVar[] { var0 };
 73            psd_expr0.addTerms(row0_values, row0_vars);
 74            model.addPsdConstr(psd_expr0, MDO.EQUAL, 1.0, "C0");
 75
 76            MDOPsdExpr psd_expr1 = new MDOPsdExpr(psd_var1, MDOMatrix.coo(dim_mat[0], dim_mat[0], A1_nz_indices, A1_nz_values));
 77            MDOVar[] row1_vars = new MDOVar[] { var1 };
 78            psd_expr1.addTerms(row1_values, row1_vars);        
 79            model.addPsdConstr(psd_expr1, MDO.EQUAL, 2.0, "C1");
 80             
 81            /* Set objective function. */
 82            MDOLinExpr objective = new MDOLinExpr();
 83            model.setObjective(objective, MDO.MAXIMIZE); 
 84
 85            // Step 3. Solve the problem and populate optimization result.
 86            model.optimize();
 87            
 88            if (model.get(MDO.IntAttr.Status) == MDO.OPTIMAL) {
 89                System.out.println("Optimal objective value is: " + model.get(MDO.DoubleAttr.ObjVal));
 90            }
 91            else {
 92                System.out.println("No feasible solution.");
 93            }
 94        } catch (Exception e) { 
 95            System.out.println("Exception during optimization");
 96            e.printStackTrace();
 97        } finally { 
 98            model.dispose();
 99            env.dispose();
100        }
101    }
102}