# What is the interpretation of the following optimization problem?

Suppose we have $N$ variables $x_1,\ldots,x_N$. Let $\mathbf{A}$ a $M \times N$ matrix, and $\mathbf{b}$ a $M \times 1$ vector.
I have the following minimization problem: \begin{array}{rl} \min \limits_{\mathbf{x}} & 1 \\ \mbox{s.t.} & \mathbf{Ax}=\mathbf{b}\\ & \mathbf{x}^T \mathbf{1}=1 \\ & x_n >0, \forall n \end{array} What is the interpretation of this kind of optimization problems? can we replace $1$ by another constant?

• Yes, you can replace 1 by any constant. This is called a feasibility problem. – littleO May 27 '15 at 10:05
• @littleO Any idea how does it work? I mean how Maltab proceeds to solve this? thank you! – tam May 27 '15 at 12:28
• See de.mathworks.com/help/optim/ug/linprog.html. You need the Optimization Toolbox. There are also interfaces for GLPK and gurobi (free for academic use) around. – Willem Hagemann May 27 '15 at 12:39
• If we replace the positivity constraint with a non negativity constraint, this feasibility problem is a linear program, and linear programs are often solved using interior point methods, or a simplex method. It could also be solved using proximal algorithms. – littleO May 27 '15 at 12:52

You're trying to find if there's a convex combination of the columns of $A$ that will yield $b$.
It's a feasibility problem which has been formulated in a rather odd way. It's simply asking to a point $x \in \mathbb{R}^N$ s.t $Ax = b$, $\sum_{k}x_k = 1$ and $x_k > 0$ $\forall k$.