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: 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.
