Helo, every one. May I ask for help about how to solve this problem?

\[\begin{align} max_{x_i} \quad |\sum_{i=1}^{4} a_i x_i | \\ s.t. \quad \sum_{i=1}^4 x_i^2=1\end{align}\]

The goal is to find the optimal \(x_i\), the \(a_i\) is known.

Thank you very much.

asked 26 Sep '14, 06:30

Lee's gravatar image

accept rate: 0%

edited 26 Sep '14, 06:43

Intuitively, the optimal \(x\) will be proportional to \(a\). A hint to get you started, in case this is homework: first ignore the absolute value and use the method of Lagrange multipliers to show that \(x_i = a_i / \sqrt(\sum_j a_j^2)\). By the way, there is nothing special about 4 here; you can replace it with arbitrary \(n\).


answered 27 Sep '14, 12:36

Rob%20Pratt's gravatar image

Rob Pratt
accept rate: 28%

That formula for x guarantees objective value 1, which is not likely to be optimal.

(30 Sep '14, 10:43) Paul Rubin ♦♦

The corresponding optimal objective is \(\sqrt(\sum_j a_j^2)\), not 1.

(30 Sep '14, 13:59) Rob Pratt

Sorry, you're right about the sum. Oops.

(02 Oct '14, 11:22) Paul Rubin ♦♦

This looks like a homework problem, so I'll just give a hint: there is an "obvious" optimal solution that does not require the use of Lagrange multipliers. It relies on the inequality \[|\sum_{i} z_{i}| \le \sum_{i} |z_{i}|.\]


answered 30 Sep '14, 10:50

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

Here is yet another way to look at it. Assume we have an optimal solution. If sum ai xi is negative, then we can multiply x by -1 and get another optimal solution. It shows that we can get rid of the absolute value in the objective.

In that case the objective is the inner product of vectors a and x, given a is fixed and the length of x is fixed. That inner product is maximal when the two vectors are collinear.


answered 07 Oct '14, 07:16

jfpuget's gravatar image

accept rate: 8%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 26 Sep '14, 06:30

Seen: 974 times

Last updated: 07 Oct '14, 07:16

OR-Exchange! Your site for questions, answers, and announcements about operations research.