My optimization problem is as follows:
--------------
Variable $ a = [a_0, a_1, a_2, a_3, a_4, a_5]$
Mimimize sup_{p \in \Phi} (abs(2*a_2+6*a_3*p+12*a_4*p^2 + 20*a_5*p^3))
with the set $\Phi = [-5, 5]$.
s.t. A*a = 0
where the matrix A is a 4*6 known constant matrix.
------------------------------------------
1. The function $f = sup_{p \in \Phi} (abs(2*a_2+6*a_3*p+12*a_4*p^2 + 20*a_5*p^3)) $ is convex with respect to the optimization variable $a$ (since the ‘sup’ operator preserves the convexity). Therefore, I think it is a convex optimization problem.

2. If the set $\Phi$ only contain finite points, then the problem becomes a linear programing problem. However, $\Phi$ is a closed set containing infinite points, then how to transform this problem into a standard convex problem that can be solved using software?

[img]http://sedumi.ie.lehigh.edu/images/fbfiles/images/MyProblem.jpg[/img]

Well, from an SeDuMi and SDP view, you would address this using sum-of-squares

You want to solve

minimize t
s.t
abs(f(p,a)) <= t for all p in...
A*a = 0

i.e.

minimize t
s.t
f(p,a)) <= t for all p in [-5,5]
-f(p,a)) <= t for all p in [-5,5]
A*a = 0

Now replace positivity with sum-of-squares. The interval can be dealt with either using positivstellensatz and multipliers etc, or by performing a variable change, for instance p=10z/(1+z*z) and then multiply out the denominators to get polynomial inequalities for the sum-of-squares step.

BTW, your problem is trivial. Pick a=0 and the largest value is 0, which is the smallest possible.

Hi, Johan, thanks a lot for your kindly help.

I made a mistake in the problem formulation. The equality constriant should be A*a=b where b is nonsingular.

I am a newbie to the area of optimization, so I hope I can get more help from you in the future.

I will learn some material for sos methods and then try to solve this question.

Johan,Thank you very much!

The problem is sloved using the sos method by a variable change as you suggested to cope with the interval. Yet, I have a question for using positivstellensatz and multipliers. In the YALMIP Wiki page of sos "users.isy.liu.se/johanl/yalmip/pmwiki.ph....SumOfSquares", it is said that "Define 4 parametrized polynomials. Let us hope quadratic multipliers suffice". Hence, I wonder how to choose the order of the multipliers? How to judge if a specific order multipliers is sufficient?

The order of the polynomial is the second argument, hence, this would create a parameterized quartic



You don't know which order you will need. You use as low as you can to accomplish your goal. If you are unlucky, you will need a very high order, often too high for it to work in practice.