Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
I need to solve the follwing constrained optimization problem. Is there any MATLAB toolbox which can solve this.
minimize $A_1 x$
subject to $A_2 x = 0$
$A_1$ is an $m\times n$ matrix where $m \lt n$ and $A_2$ is a $(n-m) \times n$ matrix.
Now if $A_1$ were a row vector, this would reduce to the standard linear-programming problem.
But I am not sure how to go about solving the above problem.
You haven't explained what you mean by minimizing the $m$ element column vector $A_{1}x$. There is a large literature devoted to "multicriteria optimization problems" or "vector optimization problems" that addresses this question.
Are you interested in the partial order that $x \succeq y$ if $x_{i} \geq y_{i}$ for $i=1, 2, \ldots, m$? For example, in this ordering,
$\left[ \begin{array}{c} 1 \\ 1 \\ \end{array} \right] \succeq \left[ \begin{array}{c} 0 \\ 0 \\ \end{array} \right] $
but there is no ordering between
$\left[ \begin{array}{c} 1 \\ 0 \\ \end{array} \right] $
and
$\left[ \begin{array}{c} 0 \\ 1 \\ \end{array} \right] $
Since this component by component comparison only provides a partial order, the best that you can do is to find a Pareto optimal solution- that is a feasible vector $x^{*}$ such that for every other feasible vector $x^{'}$, either $x^{'} \succeq x^{*}$, or $x^{'}$ and $x^{*}$ can't be compared.
A standard technqique for finding Pareto optimal solutions to such problems is called "scalarization." In this technique, you multiply the vector objective function by a weight vector and then do conventional scalar minimization of the weighted objective function.
An introduction to vector optimization problems and the scalarization technique can be found in the convex optimization textbook by Stephen Boyd and Lieven Vandenberghe.
This problem is multi-objective linear programming problem. Therefore, you find effective points of this problem. First, you find effective vertexes, and consist of solution set connecting effective vertexes.
