Conic Programming

Conic programming is useful in a wide variety of application areas including engineering and financial management. Conic programming has been used, for example, in antenna array weight design, grasping force optimization, finite impulse response (FIR) filter design, and portfolio optimization.

This section gives an overview of conic programming and how conic constraints are implemented in GAMS.

• Introduction
• Implementation of Conic Constraints in GAMS
• Example
• Modeling Issues Involving Convex Programs

Back to main page.

Introduction

Conic programs can be thought of as generalized linear programs with the additional nonlinear constraint $x \in C$, where $C$ is required to be a convex cone. The resulting class of problems is known as conic optimization and has the following form:

minimize	$c^Tx$
subject to	$Ax$ $\le$ $r^c$,
	$x \in [l^x, u^x]$
	$x \in C$

where $A\in \Re^{m \times n}$ is the constraint matrix, $x \in \Re^n$ the decision variable, and $c \in \Re^n$ the objective function cost coefficients. The vector $r^c \in \Re^m$ represents the right hand side and the vectors $l^x, u^x \in \Re^n$ are lower and upper bounds on the decision variable $x$.

Now partition the set of decision variables $x$ into sets $S^t, t=1,...,k$, such that each decision variables $x$ is a member of at most one set $S^t$. For example, we could have

$$S^1 = \left [ \begin{tabular}{c} $x_1$\ \\ $x_4$\ \\ $x_7$\ \\ \e... ...{tabular}{c} $x_6$\ \\ $x_5$\ \\ $x_3$\ \\ $x_2$\ \\ \end{tabular} \right]. \\$$ (1)

Let $x_{S^t}$ denote the variables $x$ belonging to set $S^t$. Then define

$$C := \left \{ x \in \Re^n : x_{S^t} \in C_t, t=1,...,k \right \}$$ (2)

where $C_t$ must have one of the following forms:

$\bullet$

Quadratic cone: (also referred to as Lorentz or ice cream cone)

$$C_t = \left \{ x \in \Re^{n^t} : x_1 \ge \sqrt{\sum_{j=2}^{n^t}x_j^2} \right \}.$$ (3)

$\bullet$

Rotated quadratic cone: (also referred to as hyperbolic constraints)

$$C_t = \left \{ x \in \Re^{n^t} : 2x_1x_2 \ge \sum_{j=3}^{n^t}x_j^2, ~x_1,x_2 \ge 0 \right \}.$$ (4)

These two types of cones allow the formulation of quadratic, quadratically constrained, and many other classes of nonlinear convex optimization problems.

Implementation of Conic Constraints in GAMS

GAMS handles conic equations using the =C= equation type. The conic cases are written as:

$\bullet$

Quadratic cone:

$${\tt x(\lq 1\lq ) =C= sum(i\$[not ~sameas(i,\lq 1\lq )], x(i)); }$$ (5)

$\bullet$

Rotated quadratic cone:

$${\tt x(\lq 1\lq )+x(\lq 2\lq ) =C= sum(i\$[not ~sameas(i,\lq 1\lq ) ~and ~not ~sameas(i,\lq 2\lq )], x(i)); }$$ (6)

Note that the resulting nonlinear conic constraints result in ``linear'' constraints in GAMS. Thus the original nonlinear formulation is in fact a linear model in GAMS. We remark that we could formulate conic problems as regular NLP using constraints:

$\bullet$

Quadratic cone:

$${\tt x(\lq 1\lq ) =G= sqrt[ sum(i\$[not ~sameas(i,\lq 1\lq )], sqr[x(i)]) ]; }$$ (7)

$\bullet$

Rotated quadratic cone: $x('1')$ and $x('2')$ are positive variables

$${\tt 2*x(\lq 1\lq )*x(\lq 2\lq ) =G= sum(i\$[not ~sameas(i,\lq 1\lq ) ~and ~not ~sameas(i,\lq 2\lq )], sqr[x(i)] );}$$ (8)

The example below illustrates the different formulations for conic programming problems. Note that the conic optimizer in MOSEK usually outperforms a general NLP method for the reformulated (NLP) cone problems.

Example

Consider the following example (cone2.gms) which illustrates the use of rotated conic constraints. We will give reformulations of the original problem in regular NLP form using conic constraints and in conic form.

The original problem is:

$$\begin{tabular}{lccl} minimize & $\sum_i \frac{d_i}{x_i}$\ \\ sub... ... $\in$\ & $[l_i,u_i]$, ~~~$l_i>0$, ~$d_i \ge 0, ~i=1,2,...,n$\ \\ \end{tabular}$$ (9)

where $x \in \Re^n$ is the decision variable, $d, a, l, u \in \Re^n$ parameters, and $b \in \Re$ a scalar parameter. The original model (9) can be written in GAMS using the equations:

   defobj..      sum(n, d(n)/x(n)) =E= obj;
   e1..          sum(n, a(n)*x(n)) =L= b;
   Model orig /defobj, e1/;
   x.lo(n) = l(n);
   x.up(n) = u(n);

We can write an equivalent NLP formulation, replacing the objective function and adding another constraint:

$$\begin{tabular}{lccl} minimize & $\sum_i d_i t_i$\ \\ subject to ... ...1,...,n$\ \\ & $x$\ & $\in$\ & $[l,u]$, ~~$l>0$, ~$d_i \ge 0$\ \\ \end{tabular}$$ (10)

where $t \in \Re^n$ is a new decision variable. The GAMS formulation of this NLP (model cnlp) is:

   defobjc..     sum(n, d(n)*t(n)) =E= obj;
   e1..          sum(n, a(n)*x(n)) =L= b;
   conenlp(n)..  2*t(n)*x(n) =G= 2;
   
   Model cnlp /defobjc, e1, conenlp/;
   x.lo(n) = l(n);
   x.up(n) = u(n);

We can change the equality to an inequality since the parameter $d_i \ge 0$ and we are dealing with a minimization problem. Also, note that the constraint conenlp(n) is almost in rotated conic form. If we introduce a variable $z \in \Re^n, z_i = \sqrt{2}$, then we can reformulate the problem using conic constraints as:

$$\begin{tabular}{lccl} minimize & $\sum_i d_i t_i$\ \\ subject to ... ...1,...,n$\ \\ & $x$\ & $\in$\ & $[l,u]$, ~~$l>0$, ~$d_i \ge 0$\ \\ \end{tabular}$$ (11)

The GAMS formulation using conic equations =C= is:

   defobjc..     sum(n, d(n)*t(n)) =E= obj;
   e1..          sum(n, a(n)*x(n)) =L= b;
   e2(n)..       z(n) =E= sqrt(2);
   cone(n)..     x(n) + t(n) =C= z(n);
   
   Model clp  /defobjc, e1, e2, cone/;
   x.lo(n) = l(n);
   x.up(n) = u(n);

Note that this formulation is a linear program in GAMS, although the constraints cone(n)... represent the nonlinear rotated quadratic cone constraint.

The complete model cone2.gms is listed below:

   Set n / n1*n10 /;
   Parameter d(n), a(n), l(n), u(n);
   Scalar b;
   
   d(n) = uniform(1,2);
   a(n) = uniform (10,50);
   l(n) = uniform(0.1,10);
   u(n) = l(n) + uniform(0,12-l(n));
   
   Variables x(n);
   x.l(n) = uniform(l(n), u(n));
   b = sum(n, x.l(n)*a(n));
   
   Variables t(n), z(n), obj;
   Equations defobjc, defobj, e1, e2(n), cone(n), conenlp(n);
   
   defobjc..     sum(n, d(n)*t(n)) =E= obj;
   defobj..      sum(n, d(n)/x(n)) =E= obj;
   e1..          sum(n, a(n)*x(n)) =L= b;
   e2(n)..       z(n) =E= sqrt(2);
   cone(n)..     x(n) + t(n) =C= z(n);
   conenlp(n)..  2*t(n)*x(n) =G= 2;
   
   Model clp  /defobjc, e1, e2, cone/;
   Model cnlp /defobjc, e1, conenlp/;
   Model orig /defobj, e1/;

   x.lo(n) = l(n);
   x.up(n) = u(n);
   
   Solve clp  min obj using lp;
   Solve cnlp min obj using nlp;
   Solve orig min obj using nlp;

Modeling Issues Involving Convex Programs

It is often preferable to model convex programs in seperable form, if it is possible. Consider the following example of minizing an objective function $f(x)$:

$$f(x) = \log(a'*x)$$

where $a \in \Re^n$ is a parameter and $x \in \Re^n$ the decision variable. The equation implies an implicit constraint of $a'*x > 0$. Unfortunately, domain violations can still occur because no restrictions are set on $a'*x$. A better approach is to introduce an intermediate variable $y$:

$f(x)$	$=$	$\log(y)$
$y$	$=$	$a'*x$
$y$	$\ge$	0

This accomplishes two things. It implies an explicit bound on $a'*x$, thereby reducing the risk of domain violations. Secondly, it speeds up computation since computations of gradients and Hessians in the first (non-seperable) form are more expensive. Finally, it reduces the amount of memory needed (see the section on ``Memory Options'')