3
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ $A(x)$ and $B(x)$ are not linear functions but affine. $\endgroup$ Commented Oct 10, 2011 at 15:05

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\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
    Commented Oct 10, 2011 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$ Commented Oct 11, 2011 at 6:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .