2
$\begingroup$

I'll start by formulating my problem. I am given a point and a plane. I am allowed to apply gains to the point such that it touches the plane, and is closest in 2 norm to the original point. The gains have restrictions on them. The addition of a norm constraint yields a nonconvex problem.

Formally, let $p \in \mathbb{R}^{n}$, $x \in \mathbb{R}^{n}$, and $w \in \mathbb{R}^{n}$, such that $\vert \vert w \vert \vert = 1$. The optimization problem is:

$\textrm{min}_{x} \vert \vert \textrm{diag}(p)x-p \vert \vert $,

subject to:

$a_{i} \leq x_{i} \leq b_{i},$ (Some bounds on $x$)

$w^{\rm T}\textrm{diag}(p)x = \alpha,$ (The plane constraint)

$x^{\rm T}\textrm{diag}(p)\textrm{diag}(p)x = 1$. (Norm constraint)

Ignoring the last constraint, the problem is convex. This is illustrated below for 2 dimensions, where the square is the optimal solution:

enter image description here

With the norm constraint, the problem (or rather the case that brought me here in the first place) looks like this:

enter image description here

My approach to solving the norm constrained problem was to start with the point $p$, linearize the constraint, solve the resulting convex problem, and repeat until convergence. However, the case I drew in the above image fails because the intersection of the linearized norm constraint with the plane constraint lies outside the box constraint.

One way is to just do Monte Carlo simulations, but I want to solve this in a smarter way. I thought about doing away with the bound constraints to start with but that has the disadvantage of converging to a closer infeasible solution than the farther feasible solution, as is again illustrated by the image above.

$\endgroup$
  • $\begingroup$ You said that $\operatorname{diag}(p)x$ should be close to the original point $p$, but in the optimization wrote close to $x$. What is right? $\endgroup$ – A.Γ. Jun 2 '17 at 21:27
  • $\begingroup$ Fixed. Thank you for catching that. $\endgroup$ – Mr. Fegur Jun 2 '17 at 21:29
  • $\begingroup$ With $q=\operatorname{diag}(p)x$, to minimize $\|q-p\|^2=\|q\|^2-2q^Tp+\|p\|^2=1+\|p\|^2-2q^Tp$ is the same as to maximize $q^Tp$. The intersection of the $n-1$ sphere (norm constraint) and the hyperplain is a $n-2$ sphere. It seems doable to maximize the linear function on the sphere subject to extra linear inequality constraints. $\endgroup$ – A.Γ. Jun 2 '17 at 22:14
  • $\begingroup$ That is an interesting insight. I'm not sure what the cost function contours look like for $q^{\rm T}p$, but right now I'm not sure how that addresses the problem of the algorithm either converging to the wrong solution or declaring the problem infeasible because the user happened to start with the wrong point to linearize the norm constraint. I showed this in the last image above. $\endgroup$ – Mr. Fegur Jun 2 '17 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.