2
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Yes, you can replace 1 by any constant. This is called a feasibility problem. $\endgroup$ – littleO May 27 '15 at 10:05
  • $\begingroup$ @littleO Any idea how does it work? I mean how Maltab proceeds to solve this? thank you! $\endgroup$ – tam May 27 '15 at 12:28
  • $\begingroup$ 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. $\endgroup$ – Willem Hagemann May 27 '15 at 12:39
  • $\begingroup$ 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. $\endgroup$ – littleO May 27 '15 at 12:52
0
$\begingroup$

You're trying to find if there's a convex combination of the columns of $A$ that will yield $b$.

Any feasible solution to your problem produces such a combination.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

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.