# Optimization with constraint on solution of a linear system

I'm facing this optimization problem: $$\text{minimize} \quad a^T x$$ $$\text{s.t. the solution of A(x) z + B(x) = 0 belongs to a convex set S}$$

Here $A(x)$ is a linear matrix function of $x$ and $B(x)$ is a linear vector function of $x$: $$A(x) = A_0 + \sum_{i=1}^n x_i A_i, \quad B(x) = B_0 + \sum_{i=1}^n x_i B_i$$

Assume I can assure that $A(x)$ is non-singular, e.g. by some convex constraint on $x$. The main issue is the above constraint. Generally it is non-linear. I can either formulate it as two constraints $A(x) z + B(x) = 0$ and $z \in S$, or use only the (convex) constraint $z \in S$ and the modified objective function $a^T x + M \|A(x) z + B(x)\|$ with a large $M$.

Certainly I can use a nonlinear solver to solve this, e.g. fmincon in Matlab. However, I'd like to know if there are better ways. Possibly a relaxation to a convex problem and/or an iterative algorithm? Thanks!

-
$A(x)$ and $B(x)$ are not linear functions but affine. –  Pantelis Sopasakis Oct 10 '11 at 15:05

First of all, introducing soft constraints does not guarantee that $\mathbf{A}(\mathbf{x})\mathbf{z}+\mathbf{B}(\mathbf{x})=0$ but it makes things much simpler. Second, if $\mathcal{S}$ is a polytope/polyhedron, then you have linear constraints that are easy to handle by any LP solver with constraints. If $\mathcal{S}$ is an ellipsoid i.e. a set of the form

$$\mathcal{S}=\{\mathbf{z}\in\Re^n | \mathbf{z}'\mathbf{Pz}\leq \gamma\}$$

for some positive definite matrix $\mathbf{P}$ and a $\gamma>0$, use the Schur complement to transform it into a set of linear inequalities. In particular you replace the constraint $\mathbf{z}\in\mathcal{S}$ by:

$$\left[ {\begin{array}{cc} \mathbf{P}^{-1} & \mathbf{z}\\ \mathbf{z}' & 1 \end{array} } \right] > 0$$

You now need to solve the following optimization problem: $$\min_{\mathbf{x},\mathbf{z}\in\Re^n}a'x$$ subject to the equality constraints: $$\mathbf{A}(\mathbf{x})\mathbf{z}+\mathbf{B}(\mathbf{x})=0;\ \mathbf{z}\in\Re^n$$ and the inequality constraints: $$\mathbf{z}\in\mathcal{S}$$ Assume that $\mathcal{S}$ is a polyhedron, i.e. there are $\mathbf{H}\in\Re^{n_P\times n}$ and $\mathbf{K}\in\Re^{n_P}$ so that $$\mathcal{S}=\{\mathbf{y}\in\Re^n,\mathbf{Hy}\leq\mathbf{K}\}$$ (here $\leq$ stands for row-wise comparison). Then the constraints of the optimization problem become (no need to assume that $\mathbf{A}(\mathbf{x})$ is invertible till now): $$\mathbf{A}(\mathbf{x})\mathbf{z}+\mathbf{B}(\mathbf{x})=0$$ $$\mathbf{Hz}\leq\mathbf{K}$$ This is a set of bilinear constraints. If it happens that $\mathbf{B}(\mathbf{x})=\mathbf{0}$ then you can cast your problem as a Linear Complementarity Problem.

-
The formulation with bilinear constraints is exactly what I have been using (and solved with an NLP solver like fmincon). However, I'd like to know if there are convex relaxations of the problem, so that I can approximate the solution faster. FYI, the set S is a polytope (in many cases, just a box: l <= z <= h). –  Truong Oct 10 '11 at 21:04
Bilinear constraints are usually non-convex therefore cannot be transformed into linear ones, even with the introduction of auxiliary variables and stuff like that. You can try using soft constraints, get a solution and use it as a starting point in fmincon unless $A(x)z+B(x)=0$. –  Pantelis Sopasakis Oct 11 '11 at 6:44