Skip to main content
4 votes

Sensitivity of Newton's method initial vlaue

The convergence of Newton's Method is sensitive to initial conditions (even if the initial point isn't obviously near a critical point) and can be difficult to predict. In many cases, applying the ...
Joshua Wang's user avatar
  • 6,113
3 votes
Accepted

Conjugate gradient descent when $A$ is non-singular but not symmetric

CG does not converge to a solution, e.g., for $$A=\begin{bmatrix}1&1\\0&1\end{bmatrix}\text{ and } b=\begin{bmatrix}1\\1\end{bmatrix}.$$ The solution is $x=[0, 1]^T$, but CG stagnates at $x_k=[...
Algebraic Pavel's user avatar
3 votes
Accepted

How can i solve this optimization problem effectively?

$ \def\a{\alpha} \def\b{\beta} \def\g{\gamma} \def\t{\theta} \def\l{\lambda} \def\s{\sigma} \def\e{\varepsilon} \def\o{{\tt1}} \def\bb{\b^{-\o}} \def\bbb{\b^{-2}} \def\BR#1{\,\Big(#1\Big)} \def\LR#1{...
greg's user avatar
  • 36.8k
3 votes
Accepted

Black-box optimization of a symmetric function

Symmetries in optimization problems are considered as a curse rather than a benefit. They multiply the number of optimal points, so that algorithm that explore trees (e.g. branch-and-bound) have ...
Jean-Armand Moroni's user avatar
3 votes
Accepted

Constrain set of a constrained optimization problem

You are right that one reason to use a set $S$ smaller than all of $\mathbb R^n$ is to allow for your objective function (or for that matter the constraints) to be undefined outside $S$. Another ...
Misha Lavrov's user avatar
3 votes
Accepted

How to transform this expression to a numerically stable form?

When computing $1-t$ for $t \to 1$ in finite-precision floating-point arithmetic, the result is exact per Sterbenz lemma. This leaves us with problems of subtractive cancellation. These can be ...
njuffa's user avatar
  • 1,828
3 votes

What's the purpose of the KKT condition when first-order optimality condition exists?

... because it is easier to check whether the KKT conditions are satisfied compared to the first-order conditions. In fact, you only need some set of multipliers, plug it into the set of equations and ...
gerw's user avatar
  • 31.6k
2 votes
Accepted

Optimization over two sets of vectors

Well, it seems that you can just differentiate the objective function and use any gradient-based method to optimize it. Let's define the dependent variable: $$z_i(y_{i1},...,y_{iM})=\sum_{j=1}^{M} y_{...
Daniel Cunha's user avatar
  • 1,745
2 votes

Large Scale Quadratic Form with Linear Box Constraints

If you can afford a single calculation of the Eigen Decomposition of $ \boldsymbol{A} $ I'd go with ADMM. Once you have the eigen decomposition you can solve the iterative problem by matrix ...
Royi's user avatar
  • 8,839
2 votes

Is there any method for gradient descent that achieves acceleration while moving always in the opposite direction of the gradient?

While the answer to this question is I believe, still unknown, the following papers give an algorithm that improves over the $O(1/\epsilon)$ rate of constant step size gradient descent while always ...
Damaru's user avatar
  • 367
2 votes

How to "speed up" a series $\displaystyle \sum_{k=0}^{\infty}a_k=\ell$

Probably too advanced but made for your curiosity. One thing that you could do is to write $(a=\frac 12)$ $$\frac{\left(-1\right)^{n}}{n+1-a}\,\log\left(n+1\right)=\sum_{k=0}^\infty 2^{-k}\, (-1)^n \,\...
Claude Leibovici's user avatar
2 votes

Why do we linearize optimization problems?

We can’t solve high degree equation exactly. And even if we could, it would be very slow. The first order (linear) approximation steps iterate the linear equations till the precision is good enough. ...
Eric's user avatar
  • 1,130
2 votes

Constrain set of a constrained optimization problem

$S$ would be the domain of your design variables. Note that you can evaluate the objective function and other constraint functions outside $\{x\in\mathbb{R}^n:g(x)=0\}$. Moreover, some properties of ...
Daniel Cunha's user avatar
  • 1,745
2 votes
Accepted

what are the generic methods to prove solution existence!?

From my point of view, the proof of existence (almost) always follows the classical steps: Define infimal value $j := \inf\{ f(x) \mid x \in P\}$ and take minimizing sequence $(x_k) \subset P$ with $...
gerw's user avatar
  • 31.6k
2 votes
Accepted

Nocedal 3.25. Calculate $\frac{\partial \phi}{\partial \alpha}$ where $\phi(\alpha) = f(x - \alpha \nabla f)$ and $f(x) = \frac{1}{2} x^T Qx - b^T x$

Both of you are right. Note that $Q$ is symmetrical, \begin{align} \alpha &= \frac{\frac{1}{2} \nabla f^T (Qx) + \frac{1}{2} x^T (Q \nabla f) - b^T \nabla f}{(\nabla f)^T (Q \nabla f)} \\ &...
Siong Thye Goh's user avatar
2 votes

Positive-semidefinite-constrained nuclear-norm-regularized optimization problem

You may use the solution in The Proximal Operator of the Nuclear Norm / Schatten Norm. It will give you a closed form solution for any $\lambda$.
Royi's user avatar
  • 8,839
1 vote

Minimum number of required function values to maximize a quadratic form

Heuristically I would expect roughly $L \approx 2rN$ values should suffice. In particular, $G$ can be written as $G=CF$ where $C$ is a $N\times r$ matrix and $F$ a $r \times N$ matrix. Consider the ...
D.W.'s user avatar
  • 5,243
1 vote

An idea for convex-concave saddle-point problem

I don't think the algorithm you proposed will converge in general, because of two reasons. First, we can rewrite you algorithm as $x_{t+1}=x_t - \alpha_t (x_t - \nabla g(y_t) )$ $y_{t+1}=y_t + \beta_t ...
durdi's user avatar
  • 763
1 vote
Accepted

Minimising inconclusive range for binary classification with two thresholds

You can linearize the problem and use a mixed integer linear programming solver, which will find a globally optimal solution without relying on an initial solution. Besides the decision variables $a$, ...
RobPratt's user avatar
  • 47.1k
1 vote
Accepted

Check the convexity of the upper bounding function of the subgradient method

You can rewrite your function as $$U(\alpha) = \frac{R^2}{2} \cdot \frac{1}{\sum_{i=1}^k \alpha_i} + \frac{M^2}{2} \cdot \frac{\|\alpha\|_2^2}{\sum_{i=1}^k \alpha_i},\: \alpha \in \mathbb{R}^k,$$ and ...
andrerg's user avatar
  • 26
1 vote

What equation would express multiple values of x for only one value of n, within a threshold of requirements?

It seems likely that a square 2D array / matrix would be the best data structure to store your computed values in. Granted, such an array has $n^2$ entries, and you only need ${n\choose 2}$, but this ...
Eli Johnson's user avatar
1 vote
Accepted

How do I minimize sum of modules?

EDIT Inside a domain where all moduli contents have constant sign, the problem is a LP (Linear Program) and hence has an optimum on a vertex of the domain boundary. This implies that the global ...
Jean-Armand Moroni's user avatar
1 vote

Equalise point-distance when optimising points on graph

Suppose that ou use the parametrization $$x=r(t-\sin(t)) \qquad \qquad y=r(1-\cos(t))$$ the length os the curve between $0$ and $2\pi$ is given by $$L=\int_0^{2\pi} \sqrt{\text{d}x^2+\text{d}y^2}\,dt=...
Claude Leibovici's user avatar
1 vote

Suppose that $f − \frac{1}{2}m||x||^2$ is convex where $f$ is differentiable.

Assume $m>0$. Some hints: For 1: Let $g(x) = f(x) - \frac12 m \vert x \vert^2$. Since $g$ is convex, for all $\alpha \in [0,1]$, we have that $$g(\alpha x + (1-\alpha) y)\leqslant \alpha g(x) +(1-\...
JackT's user avatar
  • 7,239
1 vote
Accepted

Estimate a vector given pairwise differences

Notice that adding the same constant to each entry of $x$ doesn't change the objective function, which we denote by $$ f_D(x) = \sum_{i < j} ((x_i - x_j) - D_{ij})^2. $$ Now, let $x^*$ minimise $...
Damian Pavlyshyn's user avatar
1 vote

Prove that $\|∇f(x) − ∇f(y)\| ≤ M\|x − y\|.$

Given $y$ and $x$, define the function $g:[0,1] \rightarrow \mathbb{R}$, $$g(t) = (\nabla f(x) - \nabla f(y))^{T}(\nabla f(y+t(x-y)) - \nabla f(y)),$$ for all $t \in [0,1]$. Note that $$ g'(t) = (\...
R. W. Prado's user avatar
1 vote

Primal Interior-Point Methods

You could apply a primal-dual approach or a primal approach to your problem. Both are valid. The primal approach to your problem is called the logarithmic barrier method. The primal-dual approach is ...
R. W. Prado's user avatar
1 vote

Primal Interior-Point Methods

If you go back to the original article by Fiacco & McCormick, see e.g. jstor, they do not introduce slack variables either. (Note: they work with $1/c_i(x)$ barrier instead of the logarithmic one, ...
rafexiap's user avatar
  • 668
1 vote
Accepted

Can this formula be minimized in an exact way? $r(x) = \sqrt{x^2 + (Kx + M)^2}$

An alternative to the other answer is to use calculus. Minimizing $r(x)$ is the same as minimizing: $$R(x)=[r(x)]^2=x^2+(Kx+M)^2$$ The first-order condition is $$R'(x)=2x+2K(Kx+M)=2(1+K^2)x+2KM=0$$ ...
smcc's user avatar
  • 5,724
1 vote

Can this formula be minimized in an exact way? $r(x) = \sqrt{x^2 + (Kx + M)^2}$

$r^2=x^2+(Kx+M)^2= x^2+K^2x^2+2KMx+M^2$ $r^2=x^2(1+K^2)+2KMx+M^2$ $r^2/(1+K^2)=x^2+\frac{2KM}{1+K^2} x+\frac{M^2}{1+K^2}$ $r^2/(1+K^2)=x^2+\frac{2KM}{1+K^2}x+ \frac{K^2M^2}{(1+K^2)^2}+\frac{M^2(1+K^2)...
TurlocTheRed's user avatar
  • 6,034

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