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!

  • $\begingroup$ $A(x)$ and $B(x)$ are not linear functions but affine. $\endgroup$ – 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.

  • $\begingroup$ 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). $\endgroup$ – Truong Oct 10 '11 at 21:04
  • $\begingroup$ 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$. $\endgroup$ – Pantelis Sopasakis Oct 11 '11 at 6:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.