# Tag Info

26

The misunderstanding lies in what constitutes "solving" an optimization problem, e.g. $\arg\min f(x)$. For mathematicians, the problem is only considered "solved" once we have: A candidate solution: A particular choice of the decision variable $x^\star$ and its corresponding objective value $f(x^\star)$, AND A proof of optimality: A mathematical proof that ...

8

An example of a tricky low dimensional problem could be: Given you hit a local minima, how can you be sure it's anything close to as good as the global minima? How do you know if your result is a unique optimal solution, given it is globally optimal? How can you create an algorithm robust to all the hills and valleys so it doesn't get stuck somewhere? An ...

7

The problem is that of saddle points, discussed in the post which you linked. From the abstract of one of the linked articles: However, in general it is hard to guarantee that such algorithms even converge to a local minimum, due to the existence of complicated saddle point structures in high dimensions. Many functions have degenerate saddle points such ...

7

Standard terminology in nonlinear (i.e., derivative-based) optimization is that "global convergence" means "convergence to a stationary point no matter where you start from" (where the limit may in fact depend on the starting point). This is in contrast to local convergence, which requires that you start sufficiently close to a stationary point; if your ...

6

The fact that $x^*$ is a (global!) minimizer of $f$ if and only if $0\in\partial f(x^*)$ is already fully explained in the notes you linked to -- it's really that simple, but here's the argument again for the sake of completeness. Assume that $x^*$ is a global minimizer of $f$. Then, by definition, $$f(x) - f(x^*) \geq 0 = 0^T (x-x^*) \qquad\text{for any }x\... 5 The problem is a standard nonlinear nonconvex problem, so any solver for this problem class is suitable to solve the problem. As an example, the following code implements the problem in the MATLAB Toolbox YALMIP (disclaimer, developed by me) and solves the problem using the local nonlinear solver ipopt. N = 3; K = 3; h = rand(N,K); R = rand(K,1); sigma = ... 4 For generic data the optimal value (in the limit) is zero, which is achieved by any vector with arbitrarily large elements. Just pick a random vector x_0 and use x=\alpha x_0 where \alpha tends to \infty. Am I missing something? The eigenvalue discussion you have is not correct (there is no reason that you should be allowed to add the constraint y^... 4 Despite your claim that these functions have "special properties", the properties you've supplied still leave f and g extremely general. This means the answers you're going to get must be correspondingly general. If, for instance, you know that g is always positive or f is quadratic, or g is some kind of positive semi-definite matrix, and so on, then you ... 4 As @HighPerformanceMark mentioned in the comments if the set of vertices V=\{v_0,\ldots,v_{N-1}\} is the only information you have about your non-convex polygon, you did not define it uniquely. One can find a non-convex polygon defined by V, but not the one. Below, is the example (certainly non-minimal, but that is the first I drew) of two different six-... 3 You could implement the piecewise linear functions using SOS2 variables (SOS2=Special Ordered Sets of Type 2). This approach does not care about convexity (that is, convexity related to the piecewise linear functions; for most solvers it is still important that the quadratic terms are convex). MIQP (Mixed Integer Quadratic Programming) solvers with support ... 3 You are missing that, in general, integer optimization problems are much more expensive to solve than real-valued optimization problems. That's because for real-values optimization problems, you have the tools of gradients and Hessians that can guide you to a minimum, whereas the integer equivalents are at best crutches that can help you, but are not nearly ... 3 I think I found the right article myself: Lewis, A.S. & Overton, M.L. Math. Program. (2013) 141: 135. doi:10.1007/s10107-012-0514-2 3 I'm going through some of my old StackExchange posts and came across this one. As it turns out, the answer led to a section in a published paper! As detailed in that paper (and in its notation), if you wish to minimize \mathrm{KL}(B|AA^\top), the following iterations will decrease the objective---and in practice work well---$$ \begin{array}{rl} U_k&\...

3

Following the derivation in Section B.1 of Boyd and Vandenberghe, it seems plausible that you could solve the SDP dual of your primal to obtain the optimal objective function value. You could also solve the dual of the dual, which is an SDP relaxation of your primal problem. Following Boyd's notation, suppose the primal variables of your problem are denoted ...

3

If you're optimizing with respect to the $k_{i,j}$, $k_{i,j}$ isn't an argument to the Heaviside function (for each $i, j$), and the $x_{i}$ and $T$ are known parameters, your problem is continuous and (twice continuously) differentiable with respect to $k$. Your problem still looks to be nonconvex at first glance, so deterministic global optimization would ...

2

If the number of variables you have is modest, then you can just subdivide the domain into the half-lines/quadrants/octants/etc of the space. In each of them, the Heaviside function is constant. For example, for a single optimization variable, your original problem was $$\min_x k[H(x)-T] \\ \text{s.t.} \ k[x-R] \le c.$$ You can split this into two ...

2

You can look at your problem in a different way. Look at the definition of norm , and then you can define your norm as: $\| x \|_{\mathcal{B}} = \sqrt{\sum_i \| x \|_{B_i}^2} = \sqrt{\sum_i \left( x^T,B_ix \right)^2}$ where $\mathcal{B} = \{B_i\}_i$ is the set of matrices $B_i$ that you have. You can do it if your matrices $B_i$ are definite positive, ...

2

As the review article points out, there's no one best derivative-free optimizer for all problems, much like there's no one best nonlinear solver for finding roots of algebraic equations, or one best linear solver for solving linear equations, etc. Also, like linear solvers and nonlinear solvers, a certain amount of experimentation is required if you want a ...

2

I guess a problem with this approach is that it also "sparsifies" the gradient. If you look at the objective function: \begin{align} \Phi(x) = \lvert|(Ax)\odot(Ax)-b |\rvert^2+\lambda\lvert|x|\rvert_1 \end{align} If one uses a proximal gradient method, we have \begin{align} x_{k+1} = \mathcal{P}\left(x_k-\alpha A^T\left(\left((Ax_k)\odot(Ax_k)-b\...

1

If this is the only relevant part of your problem, you can write this as a semidefinite program. Since $x_1, x_2$ do not appear individually you can treat it as a square of a positive number then your problem is the feasibility of $$\begin{pmatrix} x_3 & y & \\ y & 1 & \\ && y \\ \end{pmatrix} \succeq 0$$ where $y = \sqrt{... 1 Once you have$p_x,p_y$, you can use the second and fourth of the block system you show in your question to compute the updates$p_s,p_z. They satisfy the equations \begin{align} \begin{bmatrix} \Sigma & -I \\ -I & 0 \\ \end{bmatrix} \begin{bmatrix} p_s \\ -p_z \end{bmatrix} = \begin{bmatrix} z - \mu S^{-1}e \\ c_I(x) - s - A_I(x)p_x \end{bmatrix}. ... 1 This is an indirect answer. Other answers already explain in detail why it is that non-convex optimization is challenging, but to recap: No solution method we have, other than brute force, is guaranteed to succeed or even make progress. Using brute force is prohibitively expensive. Even if we can find a solution we do not have a guarantee that it is locally ... 1 In addition to the answers already given an additional issue is that without convexity the Hessian is not guaranteed to be positive definite. This complicates any method using a quadratic model (such as Newton's method or Quasi Newton's methods) since the quadratic model will not have a minimum to determine the appropriate search direction and step length. (... 1 In terms of the subdifferential definition used in the notes, the statement is immediate by definition. For a more general notion of subdifferential, Proposition 2.3.2 on page 38 of Clarke, F. H. (1990), "Optimization and Nonsmooth Analysis" says: Iff$attains a local minimum or maximum at$x$, then$0\in \partial f (x).$1 Here is a fast implementation using sparse matrices and sparse Jacobian estimation: % define square domain [-1,1] x [-1,1] n = 51; x=linspace(-1,1,n); y=x; [X,Y]=meshgrid(x,x); % build finite differences operators dx=x(2)-x(1); e=ones(n,1); d0x=ones(n,1); grad = spdiags([-e 0*e e],-1:1,n,n)/2/dx; % use Kronecker product to build matrix of d/dx and d/dy ... 1$b$is bang-bang, ie$b$puts 1 on where$\xi$is smallest. So for any fixed$\eta$, the$b, \xi$part is known $$b^\top\xi=\min(\max(1-a_i^\top\eta,0))$$ The problem reduces to an unconstrained problem on$\eta$1 Your original problem statement is vague in that you haven't described how the convex set$D$would be encoded. The problem simplifies immediately to$\max \| p \|^{2}$subject to$p \in D\$. We'll show that this problem is NP-Hard by reduction from 0-1 Integer Linear Programming feasibility. The 0-1 Integer Linear Programming feasibility ...

Only top voted, non community-wiki answers of a minimum length are eligible