The OPTMODEL Procedure

The conic solver supports two types of quadratic cone predicates, SOC and RSOC, which stand for standard and rotated second-order cones, respectively. Conic transformation converts quadratic constraints to the corresponding cone predicates when possible. The body of the quadratic constraint must be a sum of squared linear terms and possibly some linear terms or the product of two linear terms for the left-hand side (LHS) of a rotated cone. Note that the linear terms on the left-hand side of a second-order cone predicate must be nonnegative. The order of terms is flexible, and you can specify constant coefficients for the terms. Constant terms can be treated as squared terms for the right-hand side (RHS) of the cone or as linear terms for the left-hand side, depending on the sign.

The following code demonstrates various ways to specify a second-order cone by using quadratic constraints:

proc optmodel;
   var x{1..4};
   x[1].lb = 0;                                /* cone LHS must be nonnegative */
   x[2].lb = 0;
   con q1: x[1]^2 >= x[3]^2 + x[4]^2;          /* standard SOC */
   con q2: x[3]^2 + x[4]^2 <= x[1]^2;          /* equivalent to q1 */
   con q3: 25 >= x[3]^2 + x[4]^2;              /* constant on cone LHS */
   con q4: x[1]^2 >= x[3]^2 + 25;              /* constant on cone RHS */
   con q5: 2*x[1]*x[2] >= x[3]^2 + x[4]^2;     /* standard RSOC */
   con q6: x[1] + x[2] + 1 >= x[3]^2 + x[4]^2; /* linear LHS for RSOC */
   con q7: x[1]*x[1] >= 4*(x[2]+x[3])^2 + x[4]*x[4]*3; /* term variants */
   expand / conic;

The output in Figure 73 shows that the quadratic constraints are transformed into equivalent cone predicates by using added variables and constraints, if necessary, to represent linear equations or to rescale variables.

Var x[1] >= 0                                                                   
Var x[2] >= 0                                                                   
Var x[3]                                                                        
Var x[4]                                                                        
Fix _ADDED_VAR_[1] = 5                                                          
Fix _ADDED_VAR_[2] = 0.5                                                        
Var _ADDED_VAR_[3]                                                              
Var _ADDED_VAR_[4]                                                              
Var _ADDED_VAR_[5]                                                              
Constraint q1: SOC(x[1], x[3] x[4])                                             
Constraint q2: SOC(x[1], x[3] x[4])                                             
Constraint q3: SOC(_ADDED_VAR_[1], x[3] x[4])                                   
Constraint q4: SOC(x[1], x[3] _ADDED_VAR_[1])                                   
Constraint q5: RSOC(x[1], x[2], x[3] x[4])                                      
Constraint q6: RSOC(_ADDED_VAR_[3], _ADDED_VAR_[2], x[3] x[4])                  
Constraint q7: SOC(x[1], _ADDED_VAR_[4] _ADDED_VAR_[5])                         
Constraint _ADDED_CON_[1]: - _ADDED_VAR_[3] + x[1] + x[2] = -1                  
Constraint _ADDED_CON_[2]: - _ADDED_VAR_[4] + 2*x[2] + 2*x[3] = 0               
Constraint _ADDED_CON_[3]: - _ADDED_VAR_[5] + 1.7320508076*x[4] = 0             

A constraint whose body is the ratio of linear expressions can be transformed into one or more linear constraints. The same transformation is provided by the LINEARIZE option. See the description of the linearization transformation for more information.

Subexpressions that call the MIN, MAX, and ABS functions or use the <> (maximum) and >< (minimum) operators can be linearized when the function or operator is a convex term in the containing problem formula. The same transformation is provided by the LINEARIZE option for convex terms. See the description of the linearization transformation for more information.

You can also transform terms that use the MAX function and the <> operator if they have a positive coefficient and are part of a sum of squared linear terms, provided that the operands are also sums of squared linear terms. You can transform terms that use the MIN function and the >< operator when they appear on the left-hand side of a second-order cone that you specify via a quadratic constraint, provided that the operands can also be transformed into the left-hand side of a second-order cone.

The following code demonstrates the transformation of MIN and MAX terms in quadratic constraints:

proc optmodel;
   var x{1..4};
   x[1].lb = 0;                                /* cone LHS must be nonnegative */
   x[2].lb = 0;
   con c1: x[1]^2 >= max(x[3]^2, x[4]^2);      /* MAX result is nonnegative */
   con c2: min(x[1]*x[2], x[1]+x[2]) >= x[3]^2 + x[4]^2;
   expand / conic;

The output in Figure 74 shows that the quadratic constraints are transformed into equivalent linear or cone constraints, with added variables and constraints to enforce the MIN and MAX logic.

Var x[1] >= 0                                                                   
Var x[2] >= 0                                                                   
Var x[3]                                                                        
Var x[4]                                                                        
Var _ADDED_VAR_[1] >= 0                                                         
Var _ADDED_VAR_[2] >= 0                                                         
Var _ADDED_VAR_[3]                                                              
Fix _ADDED_VAR_[4] = 0.5                                                        
Var _ADDED_VAR_[5]                                                              
Constraint c1: _ADDED_VAR_[1] - x[1] <= 0                                       
Constraint c2: SOC(_ADDED_VAR_[2], x[3] x[4])                                   
Constraint _ADDED_CON_[1]: x[3] - _ADDED_VAR_[1] <= 0                           
Constraint _ADDED_CON_[2]: x[3] + _ADDED_VAR_[1] >= 0                           
Constraint _ADDED_CON_[3]: x[4] - _ADDED_VAR_[1] <= 0                           
Constraint _ADDED_CON_[4]: x[4] + _ADDED_VAR_[1] >= 0                           
Constraint _ADDED_CON_[5]: RSOC(_ADDED_VAR_[3], x[2], _ADDED_VAR_[2])           
Constraint _ADDED_CON_[6]: RSOC(_ADDED_VAR_[5], _ADDED_VAR_[4], _ADDED_VAR_[2]) 
Constraint _ADDED_CON_[7]: - _ADDED_VAR_[3] + 0.5*x[1] = 0                      
Constraint _ADDED_CON_[8]: - _ADDED_VAR_[5] + x[1] + x[2] = 0                   

The Euclidean norm of a vector is defined as

You can express a Euclidean norm term in PROC OPTMODEL by using the SQRT function applied to a sum of positive squared linear terms. The coefficients of the squared terms must be positive. Instead of using SQRT, you could also raise the sum of squares to the 0.5th power. When you apply conic transformation, the Euclidean norm must appear in a minimization context.

The following code demonstrates the transformation of a Euclidean norm:

proc optmodel;
   var x{1..3};
   min obj = sqrt(sum{i in 1..3}(x[i] - i + 1)^2);
   expand / conic;

The output in Figure 75 shows that the norm is replaced by an added variable with an added second-order cone predicate.

Var x[1]                                                                        
Var x[2]                                                                        
Var x[3]                                                                        
Var _ADDED_VAR_[1] >= 0                                                         
Var _ADDED_VAR_[2]                                                              
Var _ADDED_VAR_[3]                                                              
Minimize obj=_ADDED_VAR_[1]                                                     
Constraint _ADDED_CON_[1]: SOC(_ADDED_VAR_[1], x[1] _ADDED_VAR_[2]              
_ADDED_VAR_[3])                                                                 
Constraint _ADDED_CON_[2]: - _ADDED_VAR_[2] + x[2] = 1                          
Constraint _ADDED_CON_[3]: - _ADDED_VAR_[3] + x[3] = 2                          

The ratio of a sum of squares (squared linear terms with positive coefficients) over a nonnegative linear subexpression can be transformed into a linear term when the ratio is minimized. The following code demonstrates the transformation:

proc optmodel;
   var x{1..2};
   x[2].lb = 0;                                /* divisor >= 0 */
   min obj = (x[1]^2 + 4) / x[2];
   expand / conic;

The output in Figure 76 shows that the ratio is replaced by an added variable with an added second-order cone predicate. The positive constant 4 is treated as a squared term.

Var x[1]                                                                        
Var x[2] >= 0                                                                   
Var _ADDED_VAR_[1] >= 0                                                         
Fix _ADDED_VAR_[2] = 2                                                          
Minimize obj=2*_ADDED_VAR_[1]                                                   
Constraint _ADDED_CON_[1]: RSOC(_ADDED_VAR_[1], x[2], x[1] _ADDED_VAR_[2])      

A linear base subexpression, x, that is raised to a rational constant exponent, a, can be transformed into a linear term in some cases. The transformation is related to the generalized geometric mean transformation that is described in Erickson and Fourer (2019). The base value x must be nonnegative unless the exponent is an integer. If the exponent is 1, then no transformation is needed. If the exponent is an even positive integer, then the base term is unrestricted. If the exponent is any other integer, then the base can be nonnegative or nonpositive. A nonpositive base is negated and the sign for the coefficient of the exponentiation is adjusted if necessary.

A subexpression in which a constant c is divided by an exponentiated term, , is transformed in the same way as . An exponentiated term can also be replaced by a product of identical linear terms, such as for .

You can transform the following cases:

Conic transformation recognizes the floating-point approximations to rational numbers like or that are used as exponents. The complexity of the exponent fractions is limited. You can use fractions with denominators up to 1,414, provided that the numerators are reasonably sized. Some fractions with larger denominators, such as , are also recognized, although the transformed problem could be difficult to solve to sufficient accuracy.

The following example demonstrates solving with the power transformations:

proc optmodel printlevel=0;
   var x{1..5};
   for {i in 1..4} x[i].lb = 0; /* need a lower bound in most cases */
   con c1: x[1]^-2 <= 0.25;     /* minimize with exponent <= 0 */
   con c2: x[2]^(1/3) >= 2;     /* maximize with exponent in [0,1] */
   con c3: sqrt(x[3]) >= 3;     /* maximize square root */
   con c4: x[4]^1.5 <= 8;       /* minimize with exponent >= 1 */
   con c5: x[5]^4 <= 16;        /* minimize with even exponent > 0 */
   min obj = x[1] + x[2] + x[3] - x[4] - x[5];
   solve with conic;
   print x;

Because the conic solver is used and the problem has nonlinear constraints, the SOLVE statement applies conic transformations automatically. The objective ensures that the constraints hold with equality at the optimal solution. The output in Figure 77 shows the resulting values of x.

Conic transformation attempts to rewrite an expression that depends on a single variable when it represents the ratio of two polynomials in that variable. The expression is rewritten into a weighted sum of integer powers of linear terms. The rewritten power terms are then linearized as described in the preceding section. For example, the expression can be rewritten as . These rewritten terms can be linearized when you use them in a maximization context and .

You can specify the rational function as a sequence of polynomial terms that are combined using multiplication and division operators, with exponents optionally applied to the polynomial terms. For example, you can specify the ratio in various ways, as shown in the following code:

var x >= 1;
min z1 = (x + 2) / (x**2 - 2*x + 1);     /* direct */
min z2 = (x**2 - 2*x + 1)**-1 * (x + 2); /* rearranged */
min z3 = (x + 2) / (x - 1)**2;           /* factored */

Conic transformation first performs polynomial division on the numerator and denominator polynomials, producing quotient and remainder polynomials. When the remainder is not zero, the ratio of the remainder and the denominator polynomials is split into a sum of negative powers of linear terms by using partial fraction decomposition. The power terms from the quotient and decomposition can then be linearized if they satisfy the requirements for conic transformation that are described in the preceding section.

Partial fraction decomposition requires the factorization of the denominator into a product of linear terms. Factors for quadratic or higher-degree denominator polynomial terms must be determined numerically by computing the roots. Conic transformation retains the factors of the denominator when they are given explicitly. The transformation fails when the denominator polynomial has complex roots.

When partial fraction decomposition rewrites a ratio, the linear factors of the denominator polynomial provide the linear terms for the rewritten negative powers. For example, the ratio is rewritten as

This expression is convex for maximization when , so the power terms can be transformed in the appropriate contexts when the variable x is restricted to that range.

Even when the denominator can be factored into linear terms, it might not be possible to transform a rational function into a that form that the conic solver accepts. For example, the partial fraction decomposition of is

Because the signs of the terms alternate, there is no range for the variable x where the terms are all convex for either maximization or minimization. On the other hand, the similar ratio decomposes into

All the terms are convex for maximization for , so they can be transformed when x is restricted to that range.

Conic transformation recognizes a generalized form of geometric mean (Erickson and Fourer 2019) that can be described mathematically as

The terms must be linear. The exponents must be rational, like the exponents for the power transformation. You can specify the generalized form by using exponentiation with a power between 0 and 1 applied to a product of linear terms (such as ), as the product of linear terms with exponents (such as ), or as a mixed combination of products and exponentiation (such as ). You can also use the SAS library function GEOMEAN with the terms as arguments. In this case, the required exponent is determined from the number of nonmissing arguments.

You can use geometric mean to model optimization problems that contain the product of nonnegative variables. For example, a problem might have an objective with a product:

To permit conic transformation, you can replace this objective with

The new objective becomes linear after conic transformations. The objective value changes, but the optimal solution is unchanged.

The following code demonstrates the transformation of a geometric mean:

proc optmodel printlevel=0;
   var x{1..4} >= 0;
   max obj = prod{i in 1..4} x[i]^0.25;
   con c: sum{i in 1..4} i*x[i] <= 72;
   solve with conic;
   print x;

The output in Figure 78 shows the resulting values of x.