5.7.2. SDP Modeling and Optimization in C¶
In this chapter, we will use MindOpt C API to model and solve the problem in Examples of semidefinite programming.
5.7.2.1. SDP Example I¶
Include the header file:
26#include "Mindopt.h"
Step I: Create an optimization model
Create an empty optimization model:
68 /* Create an empty model. */
69 CHECK_RESULT(MDOemptyenv(&env));
70 CHECK_RESULT(MDOstartenv(env));
71 CHECK_RESULT(MDOnewmodel(env, &m, MODEL_NAME, 0, NULL, NULL, NULL, NULL, NULL));
Step II: SDP model input
We set the optimization sense to maximize
77 /* Change to maximization problem. */
78 CHECK_RESULT(MDOsetintattr(m, MODEL_SENSE, MDO_MAXIMIZE));
We utilize MDOaddpsdvar() to create one semidefinite matrix variable and can simultaneously set their corresponding coefficient matrix in the objective function:
The first argument is the model,
The second argument is the dimension of the matrix variable \(\mathbf{X}\) (in this case, 3),
The third argument represents the number of nonzero elements in the coefficient matrix \(\mathbf{C}\),
The fourth and fifth arguments represent vectorized indices and values of the nonzero elements in \(\mathbf{X}\), respectively.
79 /* Add matrix variable and corresponding objective coefficients. */
80 CHECK_RESULT(MDOaddpsdvar(m, dim_mat, C_size, C_nnz_indices, C_nnz_values, NULL));
Next, we input the constraints. We use MDOaddpsdconstr() to create constraints with semidefinite matrix variables:
The 1st argument is the model.
The 2nd argument is the number of linear terms in the constraint. In this case, there is no linear term and the argument is 0.
The 3rd argument is the number of matrix terms in the constraint. In this case, there is one matrix term \(\langle \mathbf{A},\mathbf{X} \rangle\) in the constraint, so this argument is 1.
The 4th argument represents the total number of nonzero elements in all constraint coefficient matrix. In this case, given the matrix \(\mathbf{A}\) has 5 nonzeros and, owing to its symmetry, only its upper triangular part is considered, this argument becomes 4.
The 5th and 6th arguments represent the indices and values of the linear terms in the constraint. In this case, they are both
NULL.The 7th argument represents the index of the matrix variable in the constraint. In this case, there is only one matrix variable \(\mathbf{X}\), so its index is 0, making this argument
{0}.The 8th argument is an array recording the starting indices of all coefficient matrices in this constraint. Again, in this case, there is only one matrix term so this argument should be
{0}. (If there were n matrix terms \(\{\mathbf{A}_i\}_{i=0}^{n-1}\), all matrices should be vectorized and concatenated into a long vector, and this argument should record the starting positions of the n matrices in that long vector.)The 9th and 10th arguments represent the vectorized indices and values of all nonzero elements in all coefficient matrices. Here, we vectorize matrix \(\mathbf{A}\) and use these two arguments to define its non-zero positions and values.
The 11th argument represents the type of the constraint, and currently, we only support MDO_EQUAL (‘=’), which represents an equality constraint.
The 12th argument represents the right-hand side value of the constraint. In this case, it is 1.
The last argument represents the name of the constraint.
82 /* Add Constraints. */
83 CHECK_RESULT(MDOaddpsdconstr(m, 0, num_psd_var, A_size, NULL, NULL, psd_var_indices, psd_coeff_start_indices, A_nnz_indices, A_nnz_values, MDO_EQUAL, 1.0, NULL));
Step III: Solve SDP model
Solve the optimization problem via MDOoptimize().
88 /* Solve the problem. */
89 CHECK_RESULT(MDOoptimize(m));
Step IV: Obtain the solution of SDP problem
We use MDOgetintattr() to obtain the solution status, i.e., the Status attribute; and we use the generic function MDOgetdblattr() to retrieve the optimal objective function value, i.e., the PrimalObjVal attribute.
90 CHECK_RESULT(MDOgetintattr(m, STATUS, &status));
91 if (status == MDO_OPTIMAL)
92 {
93 CHECK_RESULT(MDOgetdblattr(m, OBJ_VAL, &obj));
94 printf("The objective value is %f\n", obj);
95 }
96 else
97 {
98 printf("No feasible solution exists\n");
99 }
Step V: Release model
We use MDOfreemodel() and MDOfreeenv() to release the model.
30#define RELEASE_MEMORY \ 31 MDOfreemodel(m); \ 32 MDOfreeenv(env);105 RELEASE_MEMORY;
The complete example code is provided in mdo_sdo_ex1.c :
1/**
2 * Description
3 * -----------
4 *
5 * Semidefinite optimization (row-wise input).
6 *
7 * Formulation
8 * -----------
9 *
10 * Maximize
11 * obj: tr(C X)
12 * Subject To
13 * c0 : tr(A X) = 1
14 * Bounds
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
24#include <stdio.h>
25#include <stdlib.h>
26#include "Mindopt.h"
27
28/* Macro to check the return code. */
29#define CHECK_RESULT(code) { int res = code; if (res != 0) { fprintf(stderr, "Bad code: %d\n", res); exit(res); } }
30#define RELEASE_MEMORY \
31 MDOfreemodel(m); \
32 MDOfreeenv(env);
33#define MODEL_NAME "SDP_01"
34#define MODEL_SENSE "ModelSense"
35#define STATUS "Status"
36#define OBJ_VAL "PrimalObjVal"
37
38int main(void)
39{
40 /* Variables. */
41 MDOenv *env;
42 MDOmodel *m;
43 double obj;
44 int status;
45
46 /* Model data. */
47 // Variable dims.
48 int num_mats = 1;
49 int dim_mat = 3 ;
50
51 // Objective coefficients. (Only the right upper part in row-major sparse format)
52 int C_size = 4;
53 int C_nnz_indices[] = { 0, 2, 4, 8 };
54 double C_nnz_values[] = { -3.0, 1.0, -2.0, -3.0 };
55
56 // Constraint coefficients. (Only the right upper part in row-major sparse format)
57 int num_psd_var = 1;
58 int psd_var_indices[] = { 0 };
59 int psd_coeff_start_indices[] = { 0 };
60
61 int A_size = 4;
62 int A_nnz_indices[] = { 0, 2, 4, 8 };
63 double A_nnz_values[] = { 3.0, 1.0, 4.0, 5.0 };
64
65 /*------------------------------------------------------------------*/
66 /* Step 1. Create a model and change the parameters. */
67 /*------------------------------------------------------------------*/
68 /* Create an empty model. */
69 CHECK_RESULT(MDOemptyenv(&env));
70 CHECK_RESULT(MDOstartenv(env));
71 CHECK_RESULT(MDOnewmodel(env, &m, MODEL_NAME, 0, NULL, NULL, NULL, NULL, NULL));
72
73 /*------------------------------------------------------------------*/
74 /* Step 2. Input model. */
75 /*------------------------------------------------------------------*/
76 /* Change to maximization problem. */
77 CHECK_RESULT(MDOsetintattr(m, MODEL_SENSE, MDO_MAXIMIZE));
78
79 /* Add matrix variable and corresponding objective coefficients. */
80 CHECK_RESULT(MDOaddpsdvar(m, dim_mat, C_size, C_nnz_indices, C_nnz_values, NULL));
81
82 /* Add Constraints. */
83 CHECK_RESULT(MDOaddpsdconstr(m, 0, num_psd_var, A_size, NULL, NULL, psd_var_indices, psd_coeff_start_indices, A_nnz_indices, A_nnz_values, MDO_EQUAL, 1.0, NULL));
84
85 /*------------------------------------------------------------------*/
86 /* Step 3. Solve the problem and populate the result. */
87 /*------------------------------------------------------------------*/
88 /* Solve the problem. */
89 CHECK_RESULT(MDOoptimize(m));
90 CHECK_RESULT(MDOgetintattr(m, STATUS, &status));
91 if (status == MDO_OPTIMAL)
92 {
93 CHECK_RESULT(MDOgetdblattr(m, OBJ_VAL, &obj));
94 printf("The objective value is %f\n", obj);
95 }
96 else
97 {
98 printf("No feasible solution exists\n");
99 }
100
101 /*------------------------------------------------------------------*/
102 /* Step 4. Free the model. */
103 /*------------------------------------------------------------------*/
104 /* Free the model. */
105 RELEASE_MEMORY;
106
107 return 0;
108}
5.7.2.2. SDP Example II¶
Include the header file:
32#include "Mindopt.h"
Step I: Create an optimization model
Create an empty optimization model:
94 /* Create an empty model. */
95 CHECK_RESULT(MDOemptyenv(&env));
96 CHECK_RESULT(MDOstartenv(env));
97 CHECK_RESULT(MDOnewmodel(env, &m, MODEL_NAME, 0, NULL, NULL, NULL, NULL, NULL));
Step II: SDP model input
we set the optimization sense to maximize
102 /* Change to maximization problem. */
103 CHECK_RESULT(MDOsetintattr(m, MODEL_SENSE, MDO_MAXIMIZE));
We use MDOaddvar() to create two linear variables \(x_0,x_1\) and set their bounds and coefficients in the objective function.
105 /* Add linear variable and corresponding objective coefficients. */
106 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 0.0, 0.0, MDO_INFINITY, MDO_CONTINUOUS, NULL));
107 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 0.0, 0.0, MDO_INFINITY, MDO_CONTINUOUS, NULL));
We utilize MDOaddpsdvar() to create two semidefinite matrix variables \(\mathbf{X}_0, \mathbf{X}_1\) and can simultaneously set their corresponding coefficient matrix \(\mathbf{C}_0, \mathbf{C}_1\) in the objective function:
The first argument is the model,
The second argument is the dimension of the matrix variable,
The third element represents the number of nonzero elements in the coefficient matrix,
The fourth and fifth arguments represent vectorized indices and values of the nonzero elements in the coefficient matrix, respectively.
109 /* Add psd variable and corresponding objective coefficients. */
110 CHECK_RESULT(MDOaddpsdvar(m, dim_mats[0], C0_size, C0_nnz_indices, C0_nnz_values, NULL));
111 CHECK_RESULT(MDOaddpsdvar(m, dim_mats[1], C1_size, C1_nnz_indices, C1_nnz_values, NULL));
Next, we input the constraints. We use MDOaddpsdconstr() to create constraints with semidefinite matrix variables. The arguments of MDOaddpsdconstr() have been explained in SDP Example I. The distinctions in this context are:
There are two constraints in Example II.
In each constraint, there is a matrix term and a linear term.
The constraints can be added as:
113 /* Add constraints coefficients. */
114 CHECK_RESULT(MDOaddpsdconstr(m, row0_size, num_psd_var[0], A0_size, row0_idx, row0_val, A0_psd_var_indices, A0_psd_coeff_start_indices, A0_nnz_indices, A0_nnz_values, MDO_EQUAL, 1.0, NULL));
115 CHECK_RESULT(MDOaddpsdconstr(m, row1_size, num_psd_var[1], A1_size, row1_idx, row1_val, A1_psd_var_indices, A1_psd_coeff_start_indices, A1_nnz_indices, A1_nnz_values, MDO_EQUAL, 2.0, NULL));
Step III: Solve SDP model
Solve the optimization problem via MDOoptimize().
120 /* Solve the problem. */
121 CHECK_RESULT(MDOoptimize(m));
Step IV: Obtain the solution of SDP problem
We use MDOgetintattr() to obtain the solution status, i.e., the Status attribute; and we use the generic function MDOgetdblattr() to retrieve the optimal objective function value, i.e., the PrimalObjVal attribute.
122 CHECK_RESULT(MDOgetintattr(m, STATUS, &status));
123 if (status == MDO_OPTIMAL)
124 {
125 CHECK_RESULT(MDOgetdblattr(m, OBJ_VAL, &obj));
126 printf("The objective value is %f\n", obj);
127 }
128 else
129 {
130 printf("No feasible solution exists\n");
131 }
Step V: Release model
We use MDOfreemodel() and MDOfreeenv() to release the model.
36#define RELEASE_MEMORY \ 37 MDOfreemodel(m); \ 38 MDOfreeenv(env);137 RELEASE_MEMORY;
The complete example code is provided in mdo_sdo_ex2.c :
1/**
2 * Description
3 * -----------
4 *
5 * Semidefinite optimization (row-wise input).
6 *
7 * Formulation
8 * -----------
9 *
10 * Maximize
11 * obj: tr(C0 X0) + tr(C1 X1) + 0 x0 + 0 x1
12 * Subject To
13 * c0 : tr(A00 X0) + 1 x0 = 1
14 * c1 : tr(A11 X1) + 1 x1 = 2
15 * Bounds
16 * 0 <= x0
17 * 0 <= x1
18 * X0, X1 are p.s.d.
19 *
20 * Matrix
21 * C0 = [ 2 1 ] A00 = [ 3 1 ]
22 * [ 1 2 ] [ 1 3 ]
23 *
24 * C1 = [ 3 0 1 ] A11 = [ 3 0 1 ]
25 * [ 0 2 0 ] [ 0 4 0 ]
26 * [ 1 0 3 ] [ 1 0 5 ]
27 * End
28 */
29
30#include <stdio.h>
31#include <stdlib.h>
32#include "Mindopt.h"
33
34/* Macro to check the return code. */
35#define CHECK_RESULT(code) { int res = code; if (res != 0) { fprintf(stderr, "Bad code: %d\n", res); exit(res); } }
36#define RELEASE_MEMORY \
37 MDOfreemodel(m); \
38 MDOfreeenv(env);
39#define MODEL_NAME "SDP_02"
40#define MODEL_SENSE "ModelSense"
41#define STATUS "Status"
42#define OBJ_VAL "PrimalObjVal"
43
44int main(void)
45{
46 /* Variables. */
47 MDOenv *env;
48 MDOmodel *m;
49 double obj;
50 int status;
51
52 /* Model data. */
53 // linear variables.
54 int num_cols = 2;
55
56 // psd variables.
57 int num_mats = 2;
58 int dim_mats[] = { 2, 3 };
59
60 // Objective coefficients. (Only the right upper part in row-major sparse format)
61 int C0_size = 3;
62 int C0_nnz_indices[] = { 0, 1, 3 };
63 double C0_nnz_values[] = { 2.0, 1.0, 2.0 };
64
65 int C1_size = 4;
66 int C1_nnz_indices[] = { 0, 2, 4, 8 };
67 double C1_nnz_values[] = { 3.0, 1.0, 2.0, 3.0 };
68
69 // Constraints (linear).
70 int row0_size = 1;
71 int row0_idx[] = { 0 };
72 double row0_val[] = { 1.0 };
73 int row1_size = 1;
74 int row1_idx[] = { 1 };
75 double row1_val[] = { 1.0 };
76
77 // Constraints (psd). (Only the right upper part in row-major sparse format)
78 int num_psd_var[] = { 1, 1 };
79 int A0_psd_var_indices[] = { 0 };
80 int A0_psd_coeff_start_indices[] = { 0 };
81 int A0_size = 3;
82 int A0_nnz_indices[] = { 0, 1, 3 };
83 double A0_nnz_values[] = { 3.0, 1.0, 3.0 };
84
85 int A1_psd_var_indices[] = { 1 };
86 int A1_psd_coeff_start_indices[] = { 0 };
87 int A1_size = 4;
88 int A1_nnz_indices[] = { 0, 2, 4, 8 };
89 double A1_nnz_values[] = { 3.0, 1.0, 4.0, 5.0 };
90
91 /*------------------------------------------------------------------*/
92 /* Step 1. Create a model and change the parameters. */
93 /*------------------------------------------------------------------*/
94 /* Create an empty model. */
95 CHECK_RESULT(MDOemptyenv(&env));
96 CHECK_RESULT(MDOstartenv(env));
97 CHECK_RESULT(MDOnewmodel(env, &m, MODEL_NAME, 0, NULL, NULL, NULL, NULL, NULL));
98
99 /*------------------------------------------------------------------*/
100 /* Step 2. Input model. */
101 /*------------------------------------------------------------------*/
102 /* Change to maximization problem. */
103 CHECK_RESULT(MDOsetintattr(m, MODEL_SENSE, MDO_MAXIMIZE));
104
105 /* Add linear variable and corresponding objective coefficients. */
106 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 0.0, 0.0, MDO_INFINITY, MDO_CONTINUOUS, NULL));
107 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 0.0, 0.0, MDO_INFINITY, MDO_CONTINUOUS, NULL));
108
109 /* Add psd variable and corresponding objective coefficients. */
110 CHECK_RESULT(MDOaddpsdvar(m, dim_mats[0], C0_size, C0_nnz_indices, C0_nnz_values, NULL));
111 CHECK_RESULT(MDOaddpsdvar(m, dim_mats[1], C1_size, C1_nnz_indices, C1_nnz_values, NULL));
112
113 /* Add constraints coefficients. */
114 CHECK_RESULT(MDOaddpsdconstr(m, row0_size, num_psd_var[0], A0_size, row0_idx, row0_val, A0_psd_var_indices, A0_psd_coeff_start_indices, A0_nnz_indices, A0_nnz_values, MDO_EQUAL, 1.0, NULL));
115 CHECK_RESULT(MDOaddpsdconstr(m, row1_size, num_psd_var[1], A1_size, row1_idx, row1_val, A1_psd_var_indices, A1_psd_coeff_start_indices, A1_nnz_indices, A1_nnz_values, MDO_EQUAL, 2.0, NULL));
116
117 /*------------------------------------------------------------------*/
118 /* Step 3. Solve the problem and populate the result. */
119 /*------------------------------------------------------------------*/
120 /* Solve the problem. */
121 CHECK_RESULT(MDOoptimize(m));
122 CHECK_RESULT(MDOgetintattr(m, STATUS, &status));
123 if (status == MDO_OPTIMAL)
124 {
125 CHECK_RESULT(MDOgetdblattr(m, OBJ_VAL, &obj));
126 printf("The objective value is %f\n", obj);
127 }
128 else
129 {
130 printf("No feasible solution exists\n");
131 }
132
133 /*------------------------------------------------------------------*/
134 /* Step 4. Free the model. */
135 /*------------------------------------------------------------------*/
136 /* Free the model. */
137 RELEASE_MEMORY;
138
139 return 0;
140}