The Conic Optimization Solver
Example 11.3 Euclidean Distance between Sets
This example demonstrates how to solve a quadratically constrained quadratic programming (QCQP) problem. Let and
be two closed convex sets in
. The Euclidean distance between them is defined as the smallest distance between one point in
and another point in
. You can find the Euclidean distance between these two sets by solving the following optimization problem:
Consider the following Euclidean distance problem. Set is an ellipse in two-dimensional space. A point in set
is denoted as
. Set
is a polyhedron that is defined by two linear inequalities. A point in set
is denoted as
. The QCQP problem is as follows:
Use the following SAS statements to solve the problem:
/* example 3: Euclidean distance between sets */
proc optmodel;
/* let (x, y) be a point in two-dimensional space */
var x{1..2}, y{1..2};
/* minimize the distance between two points in different sets */
minimize f = (x[1] - x[2])^2 + (y[1] - y[2])^2;
/* set A is an ellipse */
con ellipse: 3*(x[1] - 2)^2 + (y[1] - 3)^2 + 2*(x[1] - 2)*(y[1] - 3) <= 5;
/* set B is a polyhedron defined by two linear inequalities */
con line1: x[2] + y[2] <= 1;
con line2: 2*x[2] + y[2] <= 0;
solve with conic;
/* print the optimal solution */
print x y;
quit;
The output and optimal solution are displayed in Output 11.3.1.
Output 11.3.1: Euclidean Distance between Sets
| Problem Summary | |
|---|---|
| Objective Sense | Minimization |
| Objective Function | f |
| Objective Type | Quadratic |
| Number of Variables | 4 |
| Bounded Above | 0 |
| Bounded Below | 0 |
| Bounded Below and Above | 0 |
| Free | 4 |
| Fixed | 0 |
| Number of Constraints | 3 |
| Linear LE (<=) | 2 |
| Linear EQ (=) | 0 |
| Linear GE (>=) | 0 |
| Linear Range | 0 |
| Nonlinear LE (<=) | 1 |
| Nonlinear EQ (=) | 0 |
| Nonlinear GE (>=) | 0 |
| Nonlinear Range | 0 |
| Solution Summary | |
|---|---|
| Solver | Conic |
| Algorithm | Interior Point |
| Objective Function | f |
| Solution Status | Optimal |
| Objective Value | 3.631884584 |
| Primal Infeasibility | 1.1715218E-7 |
| Dual Infeasibility | 3.4277832E-7 |
| Bound Infeasibility | 0 |
| Duality Gap | 2.9966075E-8 |
| Complementarity | 4.8755354E-7 |
| Iterations | 8 |
| Presolve Time | 0.00 |
| Solution Time | 0.00 |
| [1] | x | y |
|---|---|---|
| 1 | 1.08658 | 2.0882 |
| 2 | -0.61798 | 1.2360 |