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

Lee
133
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\).

link

answered 27 Sep '14, 12:36

Rob%20Pratt's gravatar image

Rob Pratt
1.2k26
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}|.\]

link

answered 30 Sep '14, 10:50

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
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.

link

answered 07 Oct '14, 07:16

jfpuget's gravatar image

jfpuget
2.5k310
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

By RSS:

Answers

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

Tags:

×231
×190

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.