Optimization with constraint on solution of a linear system

Question

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!

Answer 1

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.