A non-linear optimization problem includes an objective function (to be minimized or maximized) and some number of equality and/or inequality constraints where the objective or some of the constraints are non-linear. Use this tag for questions related to the theory of solving such problems or for ...

learn more… | top users | synonyms

2
votes
1answer
20 views

Showing that $x_{k+2}$ is a point which approximates a maximum?

Suppose that $x_k<x_{k+1}$ and $f'(x_k)>f'(x_{k+1})$. How can I show that the secant method will give $x_{k+2}$ as a point which approximates a maximum? $$x_{k+2}= ...
1
vote
0answers
26 views

Minimum of the difference of two logarithms

I am trying to find an analytical expression of the minimum of $$ f_n(x) = \frac{2x}{n^2+n}\log(x) - \frac{2x+2}{n^2+3n+2}\log(x+1) $$ when $x\in [1;n]$ I used to think from graphing it that this ...
0
votes
0answers
175 views

Indicator Variable, Mixed Integer Linear Programming

Assume $x$ is a real variable, and $0\leq x \leq1$. Besides, $y$ is a binary random variable. I need a linear program that: if $y$ is $1$: $x>0$, if $y$ is $0$: $x=0$ I know the following ...
0
votes
1answer
50 views

is this a convex optimization problem?

Can someone clarify is this a convex optimization problem or not. $min \| X-UV\|_{F}\quad $ s.t $ \quad U \geq ,V\geq0$ . If not , what makes the problem non-convex?
0
votes
1answer
95 views

How to perform the optimization when gradient is a matrix $\mathbf{R}^{n\times n}$

I am trying to optimize this cost function by using Gauss-Newton method. $$f = \sum_{i = 1}^n Tr{(Z^TZ)}$$ where $Z$ is a $4\times4$ matrix and it is a function of real vector ...
0
votes
0answers
51 views

relationship of eigenvalues of a matrix with conjugate gradient method

Assume that $Q$ has all its eigenvalues in the two intervals $[a,b]$, $[a+\delta,b+\delta]$, while $a,b,\delta>0$. Show that for every start point $x_0$, after two steps of conjugate gradient ...
1
vote
1answer
247 views

Proving a function of matrix is convex

I have a function of a matrix and a vector $f(A,b)=y^\top (I-A)^{-1} b$ and I want to know the conditions under which it is convex. For functions of a vector, the positive definiteness of the Hessian ...
1
vote
1answer
32 views

Solve system of non-linear differential equations

I have a large system of non-linear differential equations of the form: $x_{i}''(y) = f_{i}(x_{1}, x_{2},\ldots,x_{n},x_{1}', x_{2}',\ldots,x_{n}', x_{1}'', ...
0
votes
0answers
77 views

Primal-dual Newton Barrier Method for Nonlinear Functions

I am writing the code for primal-dual Newton barrier method for nonlinear functions (algorithm described here in section 2). I have a few questions about the implementation details in the paper. The ...
3
votes
1answer
2k views

Intuition for gradient descent with Nesterov momentum

A clear article on Nesterov’s Accelerated Gradient Descent (S. Bubeck, April 2013) says The intuition behind the algorithm is quite difficult to grasp, and unfortunately the analysis will not be ...
1
vote
1answer
66 views

Example of maximal monotone operators in non-reflexive Banach spaces with applications in PDE

My question is about examples of maximal monotone operators that are defined in non-reflexive Banach spaces and have applications in PDEs, variational inequalities, etc (any application actually)? If ...
0
votes
0answers
58 views

L_1 norm optimization as a sequence of linear optimizations?

Does someone know of numerical methods to approximately solve ${\bf x_0} = \min_{\bf x}\{ \left\|\bf Mx - b\right\|_1\}$ by using some sequence of linear optimizations? Links or ideas are both ...
2
votes
1answer
377 views

Difference: Newton's method, Newton-Rhapson method, Gauss Newton-method.

I would appreciate some clarification w.r.t. algorithms for solving nonlinear systems of equations. 1 - I don't understand the difference between Newton's method and Newton-Rhapson method. In [1], ...
1
vote
0answers
33 views

Penalty methods in Unconstrained problems

Let me define $p : \mathbb{R}^n \to \mathbb{R}$ as a penalty function for the feasible set $\mathcal F$ of an equality and inequality constrained problem $(P)$ $$(P) : \text{min}\space f(x) \space ...
1
vote
0answers
32 views

Convexity Proof with constraints on the gradient

Consider a minimization problem $(P)$ : minimize $f(x)$ subject to $\delta_C(x) \leq 0$ Now assume that $\emptyset \neq C \subset \mathbb{R}^n$ is convex and let $f: \mathbb{R}^n \to \mathbb{R}$ be ...
1
vote
1answer
41 views

Convexity proof - can I get some pointers?

Prove that $C \subset \mathbb{R}^n$ is convex iff $\forall m \in \mathbb{N}$ and every set of $m$ points $\{x_1,...,x_m\} \subset C$ we have that $\sum_{i=1}^m \lambda_i x_i \in C$ Where ...
3
votes
1answer
201 views

Newton optimization algorithm with non-positive definite Hessian

In the newton optimization algorithm to find the local minimum $x^*$ of a non-linear function $f(x)$ with iteration sequence of $x_0 \rightarrow x_1 \rightarrow x_2 ... \rightarrow x^*$ all $\nabla ^2 ...
1
vote
1answer
219 views

Optimization of Frobenius Norm and Nuclear Norm

How to solve the following optimization problem, \begin{equation} \boldsymbol{\hat{x}} = argmin_{\boldsymbol{x}} \frac{1}{2} \| \boldsymbol{x - y} \|_F^2 + \lambda \| \boldsymbol{x} \|_{*} ...
1
vote
0answers
49 views

Difficulty in understanding a solution: Constraint minimization of sum of Non-symmetric matrices

I am trying to understand why there is significance difference in the performance of two proposed solutions. Original question (Constraint minimization of sum of Non-symmetric matrices) ...
0
votes
1answer
53 views

Find $\min x^TAy+b^Tx+c^Ty$ subject to $1^Tx=1^Ty=1,x\ge 0,y\ge 0$

The problem seems to be easy but I can't find a solution :( Problem: Given $A\in\mathbb{R}^{m\times n}, A\ge 0, b\in\mathbb{R}^{m}, c\in\mathbb{R}^{n}$. Minimize $f(x,y) = x^TAy+b^Tx+c^Ty$ subject to ...
1
vote
1answer
45 views

how to find the solution of this cost function?

I have the following cost function. $J = \sum_{i=1}^N a\, Trace(W^TX_iW) - b\, Trace(W^TY_iW)$ Where $X_i$ and $Y_i$ are symmetric matrices, $a$ and $b$ are scalars. How can I find W?
0
votes
2answers
110 views

Constraint minimization of sum of Non-symmetric matrices

I am trying to find closed form solution to following problem \begin{equation} \begin{array}{c} \text{min} \hspace{4mm} \big(\lambda_1\left( \mathbf{y}^T V^{(1)}\mathbf{x} \right)^2 + ...
1
vote
0answers
21 views

Local optimization with multiple starting values \approx global optimization?

I need to find the minimum/maximum of a nonlinear function but the constraints in the optimization problem make it tougher to solve (not a convex problem). I don't have a good global optimization ...
3
votes
0answers
154 views

Determining active constraints in KKT

Suppose there is a constrained optimization problem having inequality constraints. We can solve it using Karush-Kuhn-Tucker conditions. My question is how do we determine which constraints are active ...
1
vote
1answer
35 views

Problems with vector vector derivative in optimization

I have a loss function of the followoing form: $L(\mathbf{a}) = \|\mathbf{b} - \mathbf{a}\|_2^2$ Where, $\mathbf{a}$ and $\mathbf{b}$ are vectors of dimension $d\times 1$. I need to calculate ...
1
vote
0answers
25 views

Convexity over a line given a convex interval [duplicate]

Let $f : \mathbb{R}^n \to \mathbb{R}_∞$ be a function. I want to prove that $f$ is convex over the line $L_{v,x_0}$ iff $\psi : \mathbb{R} \to \mathbb{R}_∞$ $\psi(t) := f (x_0 + tv)$, is convex ...
1
vote
0answers
54 views

Name of method which includes Taylor linearization inside fixed point iteration

I read paper about Horn-Schunck multiscale method for computing optical flow Core part of this algorithm is minimizing some functional. One part of functional contains nonlinear term inside L2 norm. ...
1
vote
1answer
72 views

understanding a statement in Gill, Murray and Wright “Practical Optimization”

Hi: I'm reading the book "Practical Optimization" and there's a part in Chapter 3 that I can't prove to myself but I'm sure it's true. On page 64, they define the Taylor expansion of $F$ about ...
1
vote
0answers
37 views

Efficient method for refining parameters in nonlinear curve fitting

I have time-series electrical current data $i(t)$ with transient steps in it which are convoluted with the hardware filter used in data acquisition. As a result, the real steps in current, which would ...
1
vote
1answer
84 views

fastest path between two points with current

This question is an extension of the following trivial problem: on a stationary body of water, a motorized device is 100m S and 10m E of a buoy. Given the device can move 5m/s in stationary water, ...
1
vote
0answers
19 views

Optimal design for constrained Bayesian slope intercept model

Here is a problem I've been stuck on for quite a while. Consider the model \begin{equation} \mathbf{y}=\mathbf{H}\pmb{ \theta }+\pmb{\epsilon }. \end{equation} The design matrix is given by: ...
1
vote
1answer
76 views

Is there any algorithm for finding the minimum distance to the complement of a convex set?

There have been some algorithms for finding the projection from a given point onto a convex set. This problem seems to be quit easy because of the convexity of the set. However, in the case of finding ...
0
votes
0answers
38 views

solver for non-convex matrix optimization with convex constraints

So here is the problem: $\max_{D} ~~ \|A+BD\|$ subject to $\|D\|<1$ (any norm you like) where matrices A and B are given. The cost function is evidently convex as well as the constraint, but ...
0
votes
0answers
51 views

Solution of a linearly constrained quadratic programming problem

What is the solution of the following optimization problem: \begin{align} &\min{\mathbf{p}^\mathrm{T} \mathbf{B} \mathbf{p}}\\ &\text{subject to}: \mathbf{0}\leq{\mathbf{p}}\leq \mathbf{1}. ...
1
vote
0answers
45 views

Nonlinear optimization with range constraint

I am trying to solve the following problem, but so far each time trying to program either one or more of the constraints are not satisfied (using Matlab). Phrasing the problem in two different ways, ...
2
votes
0answers
65 views

Is there any way to justify this approximation of the solution of a rather simple equation?

I am considering the problem of finding the root of equation $$f(x)=-x+\sum_{i=m}^{i=n} \sqrt{x+i}=0$$ where $m,n$ can both be from very small to very large integers. Since, in a single calculation, ...
0
votes
1answer
151 views

An Interesting Resource Allocation Problem

Here is the problem: \begin{array}{ll} \text{minimize} & \sum_{i=1}^N \frac{1}{1 + \textrm{exp}(C_i + x_i)}\\ \text{subject to} & \sum_{i=1}^N x_i \le R \\ & x_i \ge 0, ~ i = 1,2,...,N ...
11
votes
1answer
386 views

Bidding Tic Tac Toe

In regular tic tac toe, both the players get alternate chances. This is a variant of that. Player $A$ has $\$x$ amount and player $B$ has $\$y$ amount as initial balance. Assume that $y>x$. Both ...
2
votes
0answers
99 views

Nonlinear non-convex semi-infinite programming with norm equality constraint

In optimization theory, semi-infinite programming (SIP) is an optimization problem with a finite number of variables and an infinite number of constraints, or an infinite number of variables and a ...
0
votes
1answer
59 views

Optimization problem with an added quadratic inequality constraint

Consider the following (non-convex) optimization problem on the real variables $\lambda_\ell^\pm$ with $\ell=1,\ldots,n$ \begin{align} \mbox{maximize}&\quad ...
2
votes
1answer
119 views

What is the motivation behind the, convex and concave closures of submodular functions?

What is the motivation behind the , convex and concave closures of submodular functions? Also, my understanding is that the submodularity condition is somewhat like concavity which makes it counter ...
1
vote
1answer
185 views

Scale ellipsoid maximally within polyhedron

Given an ellipsoid around the origin with scaling parameter $e$ in the form $x^T E x \leq e$ and a polyhedron $P$ given by $A x \leq b$, how can we define an optimization problem that maximizes e such ...
1
vote
0answers
46 views

How to interpolate a function with a reproducing kernel

I am trying to interpolate a function that is noisy, but I know with a high amount of certainty about a third of the points in the series. I am trying to estimate the smooth mean of the signal via a ...
3
votes
0answers
41 views

Solving an inverse squared sum

How would I go about solving this sum for $x$? $$\sum_i\frac{a_i}{(x+b_i)^2}=C$$ Where $\mathbf{a}$ and $\mathbf{b}$ are vectors and $C$ is a constant, and $x$ is a single number. It's for an ...
2
votes
1answer
627 views

Gauss-Newton vs Gradient descent

I would like to ask first if the second order gradient descent method is the same as the Gauss-Newton method. There is something I didn't understand. I read that with the Newton's method the step we ...
1
vote
1answer
36 views

Finding sparsest solution of a linear system

I want to find the solution $x$ with most zeros in its components, to: $Ax=b$ for $A\in \mathbb{R}^{k \times n}, b \in \mathbb{R}^k$ ($k < n$), where $x \in \mathbb{R}^n$ has no additional ...
2
votes
0answers
136 views

Strong duality for nonconvex quadratic program (with multiple constraints)

Consider the following optimization \begin{eqnarray} P_1: \quad &\underset{x\in\mathbb{C}^N}{\mathrm{minimize}}&\; f_0(x) \\ &\mathrm{subject\;to}&\; f_i(x) \leq 0, i=1,\ldots,m \\ ...
3
votes
0answers
60 views

Structural / design / meta optimization - is there mathematical theory. Optimization over categories?

There is huge branch of mathematical optimization theory, but it mostly considers the finding optimal parameter values for the predefined structures. There are variational calculus and optimal control ...
2
votes
0answers
152 views

From constrained to unconstrained maximization problem

I have the following constrained maximization problem $$ \max_{X_1,X_2,...,X_i,...,X_N} \sum_{i=1}^{N}X_i f_i(X_1,...,X_N) \hspace{0.2 cm} \text{subject to} \sum_{i=1}^{N}X_i-B\leq 0 \text{ and } ...
2
votes
0answers
96 views

short-sale constraint with nonpositive-definite matrix in portfolio optimization

This question is about portfolio optimization in R. I have a nonpositive-definite matrix. I have handled with the singularity. Unfortunately, quadprog etc. optimization packages fail to solve the ...