How to reformulate this optimization problem as a linear program?

Asked Oct 10 '19 at 06:19

Active Oct 10 '19 at 06:19

Viewed 196 times

Let $Ax \leq b$, $x \geq 0$ define the feasible region. Each constraint defines a hyperplane in $R^n$ and the distance from a point $\hat x$ to a hyperplane is

$d_i(\hat x)$ = $(b_i - A_{i,*} \hat x)$ / $|| A_{i,*} ||$ with $|| A_{i,*} ||$ = ($\Sigma^n_{j=1}$ $A^2_{i,j}$)$^{1/2}$

$|| A_{i,*} ||$ is also known as the L-2 norm.

Let $ \bar b_i$ = ($b_i$ / $|| A_{i,*} ||$) and $\bar A_{i,*}$ = ($A_{i,*} \hat x$ / $|| A_{i,*} ||$) and $d_i(\hat x)$ = $\bar b_i - \bar A_{i,*}$. $d_i(\hat x)$ is both the distance from $\hat x$ to the ith hyperplane as well as the slack in the newly scaled ith constraint.

The center can be determined from the optimization problem

Maximize($Minimum_{i=1,...,m}$ $d_i$)
subject to: $\bar A$x + Id = $\bar b$
$x \geq 0$
$d \geq 0$

How to reformulate this optimization problem as a linear program?

asked Oct 10 '19 at 06:19

Julius Baer

The objective can be written as maximize $t$ such that $t\leq d_i$ for all $i$. – Michal Adamaszek Oct 10 '19 at 06:25
and the constraints? – Julius Baer Oct 10 '19 at 06:29
Well the constraints are already clearly linear. – Michal Adamaszek Oct 10 '19 at 06:36
The standard form is $min_x c^Tx$ with Ax=b and $x \geq 0$. Here there is the $Id$ component and the objective is $maximize()$. What is it in standard form please? – Julius Baer Oct 10 '19 at 06:40
And, for a convex polyhedron, is the center formulated here the same as the center of gravity? Or how should I understand this program? – Julius Baer Oct 10 '19 at 06:43
Your program models something resembling the Chebyshev center. As for rewriting to standard form you will find many questions just about that on this page. – Michal Adamaszek Oct 10 '19 at 07:08
I know, but I think it is more something like understanding the dual and primal forms of an LP and that this is then on or the other. Don't you think? – Julius Baer Oct 10 '19 at 08:02

How to reformulate this optimization problem as a linear program?

0 Answers0