Maximizing Norm over a convex set

175 views
Skip to first unread message

M.T

unread,
Jun 1, 2018, 2:06:09 PM6/1/18
to YALMIP
Given a convex function f : \mathbb{R}^n \to [0,\infty), and assume that the set {x \in \mathbb{R}^n \mid f(x) \leq 1} is non-empty compact set. 
In YALMIP, my aim is to solve the following non-convex optimization problem:

maxmize ||x||_2
subject to
f
(x) \leq 1

For such problem, using BMIBNB is advised since it can handle such optimization problems. When running the code using such solver, quickly a message pops regarding the usage of LMILAB, which was stated that it's not recommended to use such solver.
I must note that I do have MOSEK and GUROBI solvers installed on my machine, as well as CVX. How can use such solvers via BMIBNB?

Please advise.

Thanks in advance,
M.T

Johan Löfberg

unread,
Jun 1, 2018, 2:14:08 PM6/1/18
to YALMIP
You ould have to be a tad more explicit in the desciption for any reasonable advice

YALMIP has detected that you have a semidefinite programming problem, and thus selected the only SDP solver you have. Perhaps you did not intend to define a semidefinite constraints, and mistakingly defined a square matrix as symmetric instead of full, or you had a symmetric matrix which you wanted to constrain elementwise but added a psd constraint

M.T

unread,
Jun 1, 2018, 4:40:33 PM6/1/18
to YALMIP
What i have done, is that used a convex function defined as follows:
- Picked N radom points having d dimensions using rand (in MATLAB): 
P = rand(N,d);

- Defined f to be:
f = @(x)norm(P*x,1);


The problem is that it didnt use SDP, it used fmincon!

M.T

unread,
Jun 1, 2018, 4:41:42 PM6/1/18
to YALMIP
Also the constraints were 
Constraints = [f(x) <= 1];

Johan Löfberg

unread,
Jun 1, 2018, 4:58:12 PM6/1/18
to YALMIP
you talked about lmilab. YALMIP would never pick lmilab on this model, so you are not telling us everything. 

and if you have a vanilla installation, yalmip would not pick fmincon as upper bound solver in bmibnb, but quadprog by default

>> optimize(norm(x,1) <= 1, -x'*x,sdpsettings('solver','bmibnb'))
* Starting YALMIP global branch & bound.
* Branch-variables : 3
* Upper solver     : QUADPROG
* Lower solver     : LINPROG
* LP solver        : LINPROG
 Node       Upper      Gap(%)       Lower    Open
    1 :   -1.000E+00    66.67     -3.000E+00   2  Improved solution  
    2 :   -1.000E+00    66.67     -3.000E+00   3    
    3 :   -1.000E+00    66.67     -3.000E+00   4    







Johan Löfberg

unread,
Jun 1, 2018, 4:59:29 PM6/1/18
to YALMIP
...unless you actually used a sqrtm and formed the norm (bad idea, a quadartic function is much nicer)

>> optimize(norm(x,1) <= 1, -sqrtm(x'*x),sdpsettings('solver','bmibnb'))
* Starting YALMIP global branch & bound.
* Branch-variables : 4
* Upper solver     : fmincon
Reply all
Reply to author
Forward
0 new messages