# Tag Info

24

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 ...

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\... 6 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 ... 5 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 ... 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 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 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 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

The best reference I've seen on establishing relationships between constraint qualifications is Constraint Qualification for Nonlinear Programming. Since the function $g$ is nonlinear, your problem is likely nonconvex, so the Slater condition will be inapplicable to your problem, but any other constraint qualification should work, as long as you can show it ...

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 ...

3

Global optimization algorithms are almost always inefficient. This is true for all variants (simulated annealing, genetic, particle swarm, you name it). You can use them, but it's often worth finding out some properties of your objective function. For example, if you can find out where the objective function is discontinuous, then you can rephrase the ...

2

\begin{align} \text{Min}&&\frac{1}{2}\sum_{(i,j,s,t)\in I}\|x_ix_j-x_sx_t\|\\ s.t.: && Ax=b\\ &&x\geq 0 \end{align} has the same optimal solution as (and thus has the same computational complexity as, because this transformation is a polynomial reduction) \begin{align} \text{Min}&&\frac{1}{2}\sum_{(i,j,s,t)\in I}\|x_ix_j-...

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

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

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 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: If$f$attains a local minimum or maximum at$x$, then$0\in \partial f (x).$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 ... 1 Consider exploring your design space a bit more methodically. Polynomial chaos expansion is good for this; you can find it built into the very impressive DAKOTA package. Essentially you intelligently sample the design space and reconstruct it using an orthogonal polynomial expansion. It works very well in areas with discontinuities. You may be able to get ... 1 I suggest you try a Genetic Algorithm. Genetic Algorithms are robust against discontinuities in the objective function and converge to the global optimum in propability. They might be unfeasible if the evaluation of the objective is expensive. But you have a lot of parameters for tuning. Have a look at this post for implementations in python. 1 One can approximate the quadratic constraints as a set of linear constraints. Each of those constraints corresponds to the requirement that the solution$x\$ lie on an ellipsoid. You can approximate the ellipsoid by a polyhedron (a set of planes). Since you are minimizing a quadratic function, you are looking for solutions which stay outside your unit ...

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