Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
$A(x)$ and $B(x)$ are not linear functions but affine. –  Pantelis Sopasakis Oct 10 '11 at 15:05
add comment

1 Answer

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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