Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to find the saddle point of a quadratic form: $$f(\mathbf{x})=\mathbf{x}^\mathrm{T} \mathbf{A}\mathbf{x}+\mathbf{x}^T\mathbf{b}+\mathbf{c}$$ using a minimization/maximization-like algorithm. Is there such solution method available somewhere? I want to avoid the $\nabla\cdot f(\mathbf{x})=\mathbf{0}$ approach because I later want to add inequality constraints. The point that I am seeking is a maximum in one direction and a minimum in all other directions.

edit The above problem comes from the following formulation: imagine an externally forced one degree-of-freedom oscillator whose displacement $u(t)$ satisfies the equation of motion: $$m\ddot{u}+ku=f \cos \omega t$$ where $m$ and $k$ are respectively the mass and stiffness of the oscillator; $f$ and $\omega$ defines the forcing term. I would like to use a modified version of Hamilton's principle to find the forced steady state solution (the transient part is ignored). Since I am interested in periodic orbits only, the sought (periodic) solution satisfies: $$\delta\bigl(\int_0^T \frac{1}{2} m \dot{u}^2- \frac{1}{2} k u^2+fu\cos \omega t \,\mathrm{d}t\bigr)=0\quad;\quad u(0)=u(T)\quad;\quad \dot{u}(0)=\dot{u}(T)\qquad(1)$$ where $T=2\pi/\omega$. As the Hamilton's principle says, the solution is an extremum of the underlying functional, not a minimum necessarily.

I now want to find an approximation of $u(t)$, as for instance: $$u(t)=a_1+a_2\cos\omega t + a_3\sin \omega t\qquad (2)$$ where $a_1$, $a_2$, and $a_3$ have to be found. I just have to plug (2) in (1) and find the point $(a_1,a_2,a_3)$ that makes the functional stationary. For reasons that are not given here, I would like to reformulate this in a $\max\min$ problem since I know for this specific case that the solution is a saddle point, ie a maximum along $a_1$ and a minimum along $(a_2,a_3)$. The quadratic form given at the top of the message comes from plugging (2) in (1) with $\mathbf{x}=(a_1,a_2,a_3)$.

share|improve this question
    
How would you define the saddle point of an inequality-constrained problem? –  Rahul Aug 19 '12 at 18:18
    
Let us note $\mathbf{x}=\{x_0,x_1,\dots,x_n\}$ then the problem would be: find $\max_{x_0}\min_{x_1,\dots,x_n}\; f(\mathbf{x})$ under linear inequality constraints $\mathbf{G}\mathbf{x}-\mathbf{q}\leq 0$. Not sure if it makes sense but it would be something like that. –  pluton Aug 19 '12 at 19:04
    
Could you look for local extrema where $\nabla f = 0$ and then also consider the boundary of the constraint region? Compare and choose the point you desire? At a local extreme you can determine the nature of the critical point $p$ ( $\nabla f (p)=0$) by shifting variables at the point to write $f(y) = f(p)+y^TMy$. The eigenvalues of $M$ indicate if the point is min/max or saddle or trough. –  James S. Cook Aug 19 '12 at 19:23
    
It may be doable when $n$ is small but I'd say that it would quickly becomes intractable as $n$ increases. Knowing that the solution of the unconstrained problem is a saddle is no the difficulty. The difficulty is about how to formulate the problem with linear inequalities within a $\max\min$ strategy. The first question is: is the formulation correct? –  pluton Aug 19 '12 at 19:32
add comment

1 Answer 1

The problem you specify, $$\min f(x)=x^TAx+x^Tb$$ subject to $$Gx-q\leq 0$$ is a quadraric programming problem. See the wiki page for solution procedures.

For the saddle point, rather than the minimum, the conjugate residual method is developed to find this point.

share|improve this answer
    
Thanks for the hint on the "conjugate residual method": it looks interesting. The problem I was specifying was not a $\min f$, in the sense of finding a minimum of $f$, but rather a $\min\max f$ (not sure about the relevance of the notation) in the sense of finding saddle points. –  pluton Aug 21 '12 at 13:46
    
By the way, do you know if this conjugate residual method generalizes to cases with inequality constraints? –  pluton Aug 21 '12 at 14:01
    
@pluton I've not studied the algorithm in detail, but I suspect that it may be able to be generalised to use with constraints. Look up null space method, which can be used to effectively remove the constraints. –  Daryl Aug 21 '12 at 21:32
    
I think that the null space method is also called the "active-set" method. Anyway, I'll have a look. I'm surprised that there is nothing available in usual soft packages. I'm suspecting something wrong in the formulation. Thanks –  pluton Aug 22 '12 at 3:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.