Skip to main content
30 votes
Accepted

What is the definition of a first order method?

Difference between 1st and 2nd order algorithm: Any algorithm that requires at least one first-derivative/gradient is a first order algorithm. In the case of a finite sum optimization problem, you may ...
rhdxor's user avatar
  • 502
10 votes

Question about KKT conditions and strong duality

If strong duality does not hold, then we have no reason to believe there must exist Lagrange multipliers such that jointly they satisfy the KKT conditions. Here is an counter-example ${\bf counter-...
Wen Ding's user avatar
  • 161
9 votes

What's the shortest distance from a point inside of an ellipsoid to its surface?

If the point is $p$ and the ellipsoid is $x^T Q x = 1$, you want to minimize $(x-p)^T(x-p)$ subject to $x^T Q x = 1$, where $Q$ is a (symmetric) positive definite matrix. Using a Lagrange multiplier, ...
Robert Israel's user avatar
8 votes

What is the definition of a first order method?

"First-order", in the term "first-order method", does not refer to the convergence rate of the method. It refers to the fact that only first-order derivatives are used by the method.
littleO's user avatar
  • 52.3k
8 votes
Accepted

Derivation of Hard Thresholding Operator (Least Squares with Pseudo $ {L}_{0} $ Norm)

The problem can be written as: $$ \arg \min_{f} \frac{1}{2} {\left\| f - x \right\|}_{2}^{2} + \lambda {\left\| f \right\|}_{0} = \arg \min_{f} \frac{1}{2} \sum_{i = 1}^{n} \left( {f}_{i} - {x}_{i} \...
Royi's user avatar
  • 8,829
8 votes
Accepted

Question on bilinear programming

A bilinear problem is an extension of a linear problem, allowing in the objective an expression of the form $x^TQy$, where $x,y$ is a partition of all the problem variables. So you allow mixed ...
Michal Adamaszek's user avatar
8 votes

Prove that the phase retrieval problem is non-convex

Consider the simple example where $n = 1$, $m = 1$, $a_1 = 1$, $y_1 = 1$, i.e. we are estimating a $1$-dimensional complex variable $z \in \mathbb{C}$ from one measurement $1 = |z|^2$. Then, $f(z) = (...
JimmyK4542's user avatar
  • 54.4k
7 votes
Accepted

How to "convexify" a non-convex function?

It seems that they are correct. The simplest form of the problem can be thought of as the following $$ \max_{\alpha, p} \; \alpha \log(1+p) \quad \text{s.t.} \quad \alpha p \le 1,\; \quad \alpha,p \...
passerby51's user avatar
  • 4,170
6 votes
Accepted

Convexity of MSE in Neural Networks?

The mean square error is convex in that the MSE is convex on its input and parameters by itself. Applied to the neural network case (e.g. with the model including parameters from the neural network), ...
Guillermo Angeris's user avatar
6 votes
Accepted

Maximization of quadratic form over unit Euclidean sphere not centered at the origin

This is (a variant of) the trust-region problem, and the solution can be computed rather easily, although not an analytical solution See, e.e., https://www8.cs.umu.se/kurser/5DA001/HT07/lectures/...
Johan Löfberg's user avatar
6 votes
Accepted

Find largest possible value of $x^2+y^2$ given that $x^2+y^2=2x-2y+2$

Hint You found $$(x-1)^2+(y+1)^2=4$$ which is the equation of a circle centered in $(1,-1)$ and with radius $2$. The function $x^2+y^2$ is the square of the distance of $(x,y)$ to the origin. Which ...
StackTD's user avatar
  • 27.9k
6 votes
Accepted

If $ {L}_{0} $ Regularization Can be Done via the Proximal Operator, Why Are People Still Using LASSO?

This following points are from optimizaiton perspective. With $\ell_0$ norm, you can obtain closed form solution for proximal mapping. But, the original problem is still non-convex and convergence ...
Mahesh Chandra Mukkamala's user avatar
6 votes
Accepted

Does every compact (not necessarily convex) set have extreme points?

I don't understand the infinite-dimensional situation so please permit me to assume that we are working in $\mathbb{R}^n$ (equivalently, since we don't need the norm except to define the topology and ...
Qiaochu Yuan's user avatar
5 votes

What is the definition of a first order method?

As far as I know, there's not an exact, precise term. Personally, I refer to first-order methods as those methods that use first derivatives and second-order methods as those that use second-...
wyer33's user avatar
  • 2,572
5 votes

Is the biconjugate of a convex function always greater than the original function?

You've got this slightly backwards. Recall that the definition of $f^*(z)$ is $$ f^*(z) = \sup_x ( \langle x,z \rangle - f(x) ), $$ hence $$ f^*(z) \geq \langle x,z \rangle - f(x), $$ which holds for ...
Chappers's user avatar
  • 67.9k
5 votes

How to solve binary nonlinear programming problems?

Is this problem is NP-Hard or not? In general, 0-1 integer linear programming is NP-hard. However, you've got a specific collection of constraints and any proof of NP-hardness for this specific ...
Brian Borchers's user avatar
5 votes
Accepted

Is there a second-order conic relaxation method for the bilinear term $z=xy$?

The 3x3 moment matrix is $\begin{pmatrix} 1 & x & y\\x & x^2 & xy\\y & xy & y^2\end{pmatrix}$ which is psd and rank-1. Introduce relaxation variables and your semidefinite ...
Johan Löfberg's user avatar
5 votes
Accepted

Maximizing $\mathbf{x}^T A \mathbf{x}$ subject to $| \mathbf{x} | \preceq \mathbf{1}$

Maximization of a convex quadratic over the hypercube is a classical intractable problem, and you will not be able to device an algorithm which, in the worst case, performs much better than simply ...
Johan Löfberg's user avatar
5 votes
Accepted

Convergence of Sequential Quadratic Programming (SQP)

There's a couple of things going, so we need to disambiguate them. First, it's important to realize that SQP isn't exactly a singular algorithm, but a general idea that can be implemented in multiple ...
wyer33's user avatar
  • 2,572
5 votes
Accepted

Convergence to a local minimum of a nonconvex function

The result does hold for such a general case, even if the function has only one global minimizer. For example, there is no way to guarantee that the function does not oscillate too much around the ...
R. W. Prado's user avatar
5 votes
Accepted

Box-constrained QCQP

This is really more of a comment than a complete answer, but in case you are not aware, a slightly simpler version of your quadratic program can be reformulated as, \begin{align} \text{minimize}\;\;&...
Set's user avatar
  • 7,640
5 votes
Accepted

Can I linearize this piecewise function so it can be used in an objective function for my LP optimization model?

Your piecewise-linear function is concave and so cannot be linearized without introducing a binary variable. If it were instead convex, you could use linear programming.
RobPratt's user avatar
  • 46.9k
4 votes
Accepted

Minimizing Quadratic Form with Norm and Positive Orthant Constraints

I would use the Projected Gradient Descend for this case. Though the problem isn't Convex it will work nicely. The algorithm is as following: Calculate the Gradient at the current point. Update the ...
Royi's user avatar
  • 8,829
4 votes
Accepted

What is the fastest mixed-integer convex programming software?

CVXGEN only addresses LPs and convex QPs. So I am guessing you are interested in convex Mixed Integer QPs (MIQPs), or perhaps MILPs. Those are addressed, by among others, GUROBI, CPLEX, and MOSEK, ...
Mark L. Stone's user avatar
4 votes
Accepted

Optimization problem where in the objective function the optimizer is divided by the square root of its L1 norm

For every $k$ between $1$ and $M$, solve the MILP with the constraint $\sum x_i = k$. With the sum (i.e. 1-norm) fixed, the denominator does not influence the optimal solution. Hence, you want to ...
Johan Löfberg's user avatar
4 votes
Accepted

Does $f(x) = \frac{1}{2}x^TAx$ have an L-Lipschitz continuous gradient

The function is $L$-Lipschitz, where $L$ is the operator norm of $A$. The operator norm is defined as $$\|A\|_{op} := \sup_{x \ne 0} \frac{\|A x\|_2}{\|x\|_2}.$$ Indeed, from your work we have $$\|\...
angryavian's user avatar
  • 90.8k
4 votes

What is the role of Tikhonov regularization in optimization?

The closest that "pure optimization" gets to regularization is probably the field of Robust Optimization, which aims to improve performance on unseen data by arming an adversary with the ability to ...
Ryan Cory-Wright's user avatar
4 votes
Accepted

Casting a function as quadratic

This cannot be done. Take the one dimensional case and let $y=1$. You cannot write $\sqrt {1-x^{2}}$ as a quadratic in $x$.
Kavi Rama Murthy's user avatar

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