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 have a problem:

find $min||\overrightarrow{x}||$ where $A\overrightarrow{x} \leqslant \overrightarrow{b}$

Is it possible to get analytic solution? Or which iteration method should I use?

share|improve this question

2 Answers 2

It depends what norm you are talking about. If you mean the Euclidian norm, your problem is a quadratic program. It is equivalent to $$ \min_x \ \tfrac{1}{2} \|x\|^2 \quad \text{subject to } Ax \leq b. $$ In general, we don't have the analytic solution of inequality-constrained problems. However, as it was mentioned in another answer, if $b \geq 0$, the solution of your problem is $x = 0$. Otherwise, you can equivalently solve $$ \min_x \ \tfrac{1}{2} \|x\|^2 \quad \text{subject to } Ax = b. $$ The optimality conditions are that there exist a vector $y$ such that $$ \begin{bmatrix} I & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 0 \\ b \end{bmatrix}. $$ If your matrix $A$ has full row rank, the latter block matrix is nonsingular and you get a solution in closed form. Here you can use your favorite method for linear systems. You can factorize the coefficient matrix (the recommended factorization here is the so-called $LBL^T$, or Bunch-Parlett-Kaufman, factorization because this matrix is symmetric and indefinite). Or you can use an iterative method for symmetric systems, such as MINRES or SYMMLQ. You can't use the conjugate gradient method here.

You can play the same game for any other elliptic norm, i.e., $\|x\|_M^2 := x^T M x$ where $M = M^T$ is a positive definite matrix. The identity block in the above block matrix should just be changed to $M$.

If you mean to use another norm, e.g., $\|x\|_1$ or $\|x\|_{\infty}$, or any other polyhedral norm, it is possible to convert your problem to a linear program. The latter will have inequality constraints and in general, you won't have a solution in closed form but you can use any algorithm for linear programming to solve it (for instance the Simplex method or an interior-point method). For example, suppose you want to solve $$ \min_x \ \|x\|_{\infty} \quad \text{subject to } Ax \leq b. $$ This problem is equivalent to $$ \min_{x,t} \ t \quad \text{subject to } Ax \leq b, \ -t \leq x_i \leq t, \ i = 1, \ldots, n. $$

share|improve this answer

When the polyedron contains origin $x=(0,0,\ldots,0)$, its obvious solution with optimal value $0$. Whenever its not, one way to approach it is by using Langrange Multipliers, since the minimum of the norm function will be obviously on the boudary of the polyedron, so we care only about equality contraints $Ax=b$.

We wish to find extreme (minimum) value of $\|x\|$ subject to $Ax=b$. We wrote down Langrange's function (assuming L2 norm):

$L(x,\lambda)=\|x\|+\lambda(Ax-b)$

By solving system of equations $\frac{\partial L(x,\lambda)}{\partial x}=0$ and $\frac{\partial L(x,\lambda)}{\partial\lambda}=0$ we find stacionary points where one will state for minimum value of the norm $x$ and second one for the maximum.

share|improve this answer

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.