5
$\begingroup$

This is from Boyd & Vandenberghe's Convex Optimization:

Show that $$ \min_{x \in \left\{x : c^T x +d > 0 \right\}} \ \frac{\|Ax-b\|_2^2}{c^T x + d} $$ has a minimizer $x^* = x_1 +t x_2$ where $$ x_1 = \left( A^T A \right)^{-1} A^T b, \qquad x_2=\left( A^T A \right)^{-1} c $$ and $t \in \mathbb{R}$ is obtained by solving a quadratic equation.


From the structure of the solution, it seems like I am supposed to split the problem into two parts, but apart from that I don't really understad how to solve this. I tried to differentiate to find the minimizer, but I didn't get anything of this form. (In the problem before this, we had to show that $f$ is closed, if that is relevant).

$\endgroup$
1
  • $\begingroup$ Which section of the book? $\endgroup$ Commented Mar 29, 2023 at 6:00

1 Answer 1

7
$\begingroup$

Let us rewrite the problem to a convex optimization problem by adding a variable $s$: $$\min \{ s||Ax-b||^2 : s = 1/(c^Tx + d) \}$$ and then substituting $y = xs$: $$\min \{ s||A(y/s)-b||^2 : (c^Ty + ds) = 1 \}$$ Note that the objective function is the perspective of a convex function, and is therefore convex. The KKT stationarity conditions for $y$ and $s$ read: $$2(A^TA(y/s)-A^Tb) + \lambda c = 0$$ $$-2\frac{||Ax||^2}{s^2} + b^T b + \lambda d = 0$$ The first condition can be solved for $y/s$: $$x = \frac{y}{s} = (A^TA)^{-1}A^Tb-\frac{1}{2} \lambda (A^TA)^{-1} c$$ Your $t$ is now $-\lambda/2$. To find $\lambda$, consider the KKT stationarity condition for $s$, and plug in $s = 1/(c^Tx + d)$ to obtain the quadratic equation.

$\endgroup$
7
  • $\begingroup$ It's already a convex optimization problem as written; there's no need to "convert" it to one. Though of course your method works ;-) $\endgroup$ Commented Dec 5, 2016 at 0:29
  • $\begingroup$ @MichaelGrant ahh you are right, it's even a SOCP. $\endgroup$
    – LinAlg
    Commented Dec 5, 2016 at 8:35
  • 1
    $\begingroup$ Well, not quite. It can be converted to an SOCP, but it is not an SOCP in its native form. $\endgroup$ Commented Dec 6, 2016 at 3:46
  • $\begingroup$ @MichaelGrant if we do not have norm-2 (i.e. $\|.\|^2$) and if $A$ is a vector then according to the LinAlg method the objective function will still be convex. But in Convex Optimization book it is written that it a linear fractional program and the objective function is quasiconvex. Doesn't it mean that there is some contradiction. $\endgroup$ Commented Mar 5, 2019 at 8:44
  • $\begingroup$ @LinAlg if we do not have norm-2 (i.e. $\|.\|^2$) and if $A$ is a vector then according to the your method the objective function will still be convex. But in Convex Optimization book it is written that it a linear fractional program and the objective function is quasiconvex. Doesn't it mean that there is some contradiction. $\endgroup$ Commented Mar 5, 2019 at 8:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .