# Solving a "generalized" linear programming problem

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.

• I'm still learning this stuff so this might sound wrong, but do you mean minimise $\|A_1 x\|_1$? May 1 '13 at 2:23

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.

• Once you've weighted the objective you can use a conventional linear programming solver to find a Pareto optimal solution. May 1 '13 at 12:09

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.

• Could you elaborate upon this answer? As it stands, it does not give enough information for someone reasonably competent in optimization to follow your reasoning. Jun 22 '13 at 0:37