Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

1
vote
0answers
29 views

Complexity of Earlist Avaible Due Date for Scheduling Problem 1|ri, pi=1|Lmax

Let us consider the scheduling problem 1|ri,pi=1|Lmax (basically, this means there is one machine on which we have to schedule n jobs (all with identical procssing time 1) in such a way that the ...
1
vote
1answer
73 views

(Proximal) subgradient inclusion property proof

I'm having a bit of trouble proving what seems to be two fairly straightforward statements for a nonlinear optimisation class I'm taking. We're studying properties of the proximal subgradient, ...
0
votes
0answers
35 views

Convex optimization issues

I have to optimize a function $f(a,b,c_{ij})$ which consists of a terms like matrix $\mathrm{X = A + B + C}$ where $\mathrm{A}$ is a diagonal matrix with the diagonal elements equal to $a$. ...
0
votes
0answers
112 views

Issues in optimization with positive definite constraints

I have this function $f(\mathrm{X})$ such $\mathrm{X}$ is a positive definite matrix which is equal to $\mathrm{A+B+C}$. $\mathrm{A}$ is a diagonal matrix with variable $a$ on the diagonal elements. ...
3
votes
1answer
147 views

Dividing a set of points into two sets of roughly equal diameter

Let $S$ be a finite set whose cardinality is more than 1 and $d: S\times S\rightarrow\mathbb R$ be a positive symmetric function (that is, $d$ is a distance without the axiom of triangle inequality). ...
0
votes
1answer
61 views

Minimization problem convex set

I'm trying to minimize the function: $$f(w)=w^T\mu+k\sqrt{w^T\Sigma w}$$ where $w$ is a vector in $W=\{x \in \mathbb{R}^n|x_1+...+x_n=1 , x_i \geq 0 \forall i\}$. The vector $\mu \in \mathbb{R}^n$, ...
1
vote
1answer
17 views

Minima problem?

This is a question in my textbook which I can't solve. Any help would be appreciated, thanks. "A piece of wire 10 metres long is cut into two portions. One piece is bent to form a circle, and the ...
1
vote
1answer
146 views

Interchange of max and min

Let $f_1(x)$ and $f_2(x)$ be two functions of $x$. Is this true \begin{align} \max_{x\in \mathbb{R}}~\min_{i}~f_i(x) = \min_{x\in \mathbb{R}}~\max_{i}~-f_i(x) \end{align} (UPDATE: I am not asking if ...
5
votes
3answers
123 views

Determine the minimum of $a^2 + b^2$ if $a,b\in\mathbb{R}$ are such that $x^4 + ax^3 + bx^2 + ax + 1 = 0$ has at least one real solution

I just wanted the solution, a hint or a start to the following question. Determine the minimum of $a^2 + b^2$ if $a$ and $b$ are real numbers for which the equation $$x^4 + ax^3 + bx^2 + ax + 1 = 0$$ ...
0
votes
1answer
52 views

Checking whether a solution to MIP is optimal

Consider a binary integer program \begin{align} \min \quad &\sum _{j \in J}f_j x_j +\sum _{i \in I} c_i y_i \notag \\ \mbox{s.t.} \quad &\sum _{j \in N_i} x_j \ge 1-y_i, \quad \forall i\in I ...
0
votes
1answer
736 views

Max- Min Optimization problem

I am a noob in mathematic, so I would need your help in solving the optimization problem below \begin{array}{l} \max\limits_{\bf l} \min \left( \left| {\bf g}_1 {\bf Ml} \right|^2, \left| {\bf g}_2 ...
1
vote
0answers
99 views

Algorithm of projection

Suppose $S$ is a compact surface in $\mathbb{R}^{3}$ defined by a sufficiently smooth level set function $f$, that is, $S=\{s: f(s)=0\}.$ I am studying an algorithm that projects a point $x_{0}$on ...
3
votes
0answers
59 views

On the bounds of the objective function in a standard LP

Consider a standard linear programming (LP) such as: \begin{align} \sum_{i=1}^{N}\frac{a_{i}}{b_{i}}x_{i}\end{align} \begin{align}\text{s.t. }\left ( \sum_{i=1}^{N}x_{i}=1 \; , \; ...
1
vote
1answer
218 views

Estimate Euler angles between rotated coordinate system via Newton-method based on position vectors

I've got $N$ position vectors $\mathbf{a}_i = \begin{pmatrix} a_{i,x} \\ a_{i,y} \\ a_{i,z} \end{pmatrix}$ in one coordinate system and $N$ corresponding position vectors $\mathbf{b}_i = ...
0
votes
2answers
59 views

How is it possible to use normals in the definition of a linear programming constraint?

I'm trying to calculate the center of a feasible region in a system of linear inequalities using linear programming techniques. After a bit of research, it looked like defining the center as a ...
0
votes
1answer
125 views

Local Extrema and Global Extrema

When we have a convex function we know that a local minimum is a global minimum, and similarly for a concave function. What are some other situations where finding local extrema can yield global ...
4
votes
1answer
85 views

Maximum of a trigonometric Polynomial

Given $$x+y+z=\pi$$ $$3\sin(x)+4\sin(y)+18 \sin(z)=A$$ Question:find maximum of $A$. I spend so many time on this question. answer is $ 35\sqrt{7} /4$, but why?
2
votes
0answers
103 views

Maximizing a continuous recursive function

So I've been working at this for a while and have so far been unable to find any resources on maximizing a particularly strange function that I've been trying to deal with. The function is of the form ...
3
votes
0answers
68 views

Optimizing with Many Langrangians

I'm working on a problem where I've got to minimize the following: $\sum\limits_{i=1}^n(a+c\sqrt{(y_i^2+1)}+dy_i-v_i)^2$ with the following constraints: $0\leq c \leq 4e$ $|d| \leq c \mbox{ and } ...
0
votes
1answer
31 views

Confusion related to derivative

What is the gradient of $||x + b||_1$ with respect to $x$? Here $x$ is the variable and $b$ is the constant.
1
vote
0answers
16 views

Confusion about the implementation of thresholding operation

I was reading this paper. I didn't get the application of thresholding operator here I didn't get how the -c part came in the solution $\mu = -c + S(c-b/a, \lambda/a)$
1
vote
2answers
2k views

Derivation of soft thresholding operator

I was going through the derivation of soft threholding at http://dl.dropboxusercontent.com/u/22893361/papers/Soft%20Threshold%20Proof.pdf. It says the three unique solutions for $\operatorname{arg ...
0
votes
1answer
220 views

optimization of a non-differentiable, component-wise step function

I would like to estimate the (local) minimum of a function $c:R^N \mapsto R^+$ where: $c$ is only differentiable almost everywhere, there exists a component $j$, such that $\frac{\partial ...
0
votes
1answer
28 views

Is monotonicity of $g$ necessary and sufficient for preserving critical points of $f$ in $g(f(x))$?

Problem 1. I want to find the argminof $f(x)$. Suppose solving $f'(x)=0$ is too difficult. Instead, solve Problem 2: optimize $g(f(x))$, (presumably by solving $g'(f(x))\cdot f'(x)=0$?). For what ...
1
vote
1answer
99 views

Looking for a window containing the solution of an equation

I need to solve billions of times equations $\,f(x)=0\,$ with $$f(x) := \sum_{i=1}^N \frac {z_i}{c_i + x}$$ All $z_i$ are positive and add to $1$. Among the $N$ coefficients $c_i$, $M$ are negative ...
5
votes
1answer
206 views

Prove or disprove this argument

Let $L>0$ and let $\Omega$ be the set of all integrable functions from $[0,L]$ to $]0,+\infty[$. For all $\varphi, \psi \in \Omega$ define $\left \langle \varphi,\psi \right ...
2
votes
1answer
297 views

Optimizing trigonometric and nonlinear functions

First, Please, keep in mind that I'm a programmer not mathematician, and I have a fair mathematical background. I used optimization in Java to fit some observations to a trigonometric function, I ...
0
votes
1answer
76 views

online learning to maximize profit

I have a software which takes input as investment and gives the output as return on a particular stock. Now profit metric $x_i$ is defined as the ratio of return $g_i$ to maximum possible return ...
0
votes
0answers
86 views

A stochastic programming with a chance constraint

Let $X$ be a bounded positive variable with an unknown probability density function (PDF) and $f(X)$ be a differentiable positive function. $$\begin{align*} &\min/\max ...
1
vote
1answer
85 views

Minimize $\sum_i \arccos(v_i\cdot x)^2$ subject to the constraints $\|v_i\|=1$ and $\|x\|=1$?

Some background: (skip to the end for the actual question) Recently I have been trying to define some notion of an average of points on the surface of a sphere. My original idea was to ignore the ...
1
vote
2answers
85 views

Optimal Configuration for a Set of Points

Consider a set of $n$ points on the plane with positions $\mathbf{p}_1,\dots,\mathbf{p}_n$, such that each point $i$ has at least one neighbor $j$ at a distance of no more than $\lambda$ away from it ...
1
vote
0answers
112 views

A maximization problem in Sobolev space

For $k>0$, let $f_k$ be a sequence of positive functions in $H_N^1(0,1)$, where $H_N^1(0,1):=\{u\in H^1(0,1)|u^{'}(0)=0=u^{'}(1)\}$, $H^1(0,1)$ is the usual Sobolev space consisting of $L^2(0,1)$ ...
4
votes
2answers
57 views

What is an approach for optimizing the values of a matrix?

My apologies if I get some terminology wrong, I don't have a formal math background; half my problem is articulating what I'm trying to do and identifying the domain of math that deals with this kind ...
4
votes
1answer
393 views

Why is lasso not strictly convex

I know a nonmonotonic convex function which attains its minimum value at a unique point only is strictly convex. I didn't get how lasso is not strictly convex. For eg if I consider two dimensional ...
4
votes
2answers
73 views

Finding maximum of $ad-bc$ on $S^3$

One of my friends asked me to find the maximum of $ad-bc$ given that $a^2+b^2+c^2+d^2=1$ and $a, b, c, d \in \mathbb{R}$. I came up with the following. Can somebody please tell me if it is a ...
3
votes
2answers
146 views

Optimization for constrained problem

I'm reading about Lagrange multipliers from a Pattern recognition book appendix and on one point the following is stated: $\begin{align} ...
1
vote
1answer
145 views

Relationship between lagrange multiplier and constraint

I know there is one to one relationship between $\lambda$ and $t$ in the following two equivalent optimization formulation. But what is exact relationship? A) $$ \sum_i(y_i - \sum_k \beta_k ...
-1
votes
1answer
59 views

Minimisation of Concave Function

$f\left(\mathbf{x}\right):\mathbb{R}_+^n\rightarrow\mathbb{R}_+$ is a concave monotonically increasing function to be minimised over the feasible region $\sum_{i=1}^n x_i=1$ and $x_i\geq ...
0
votes
1answer
376 views

finding maximum perimeter of a triangle

So, here we are given task to find maximum perimeter of a triangle with a given base 'a' and given vertical angle 'x' , now how should I proceed in given problem its confusing me Now supposing ...
0
votes
3answers
109 views

Solution to a scarce resources assignment game

I would like to tell you about this game, which can looks like very simple but there's a constraint which complicates it and prevents me from finding an analytical solution. Rules of the game: ...
0
votes
2answers
3k views

Solving a set of equations with Newton-Raphson

I want to solve this set of equations with Newton-Raphson. Can anybody help me? $$ \cos(x_1)+\cos(x_2)+\cos(x_3)= \frac{3}{5} $$ $$ \cos(3x_1)+\cos(3x_2)+\cos(3x_3)=0 $$ $$ ...
9
votes
1answer
565 views

How to justify the solution of this problem?

Assume $\mathbf{x} \in \mathbb R_+^N$ with support $P=\{p_1,p_2,\cdots,p_K\}$ ($P$ is unknown). We already know that $$f_1(\mathbf{x}) = f_2(\mathbf{x}) = \cdots = f_{N-1}(\mathbf{x})$$ where ...
1
vote
1answer
97 views

Showing that the function $f(x,y)=x+y-ye^x$ is non-negative in the region $x+y≤1,x≥0,y≥0$

ok, since it's been so long when I took Calculus, I just wanna make sure I'm not doing anything wrong here. Given $f:\mathbb{R}^2\rightarrow \mathbb{R}$ defined as $f(x,y)=x+y-ye^x$. I would like to ...
2
votes
0answers
241 views

Minimize Rosenbrock Function With Conjugate Gradient Method

I want to minimize $$ f(x,y) = (1-x)^2 + 100(y-x^2)^2 $$ For the conjugate gradient method I need the quadratic form $$ f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^{\text{T}}\mathbf{A}\mathbf{x} - ...
1
vote
1answer
50 views

maximum of derivatives of lipschitz functions

Say $f$, and $g$ are nondecreasing functions on [a,b], differentiable with derivatives bounded by 1. can one infer that $$\int_a^b \min\left(\frac{d}{dx} f(x),\frac{d}{dx} g(x)\right)\,dx \leq ...
2
votes
0answers
228 views

Proof of a method to find the points of maximum slope

According to method described in a paper [1] if we want to find points of maximum slope in a signal $f(t)$, then one has to do following Convolve $f(t)$ with $g(t)$ where $g(t)=-cos(\omega ...
0
votes
1answer
105 views

The local minimum of the SQP (sequential quadratic programming) algorithm

Consider the constrained optimization problem \begin{eqnarray} goal~~&&\min f(x)\\ s.t.~~&&g_1(x)\leq0\\ &&g_2(x)\leq0\\ &&\cdots\\ &&g_n(x)\leq0 ...
0
votes
0answers
52 views

Is there an easy solution to this constrained discrete minimisation?

Given $\vec{a}$, $\vec{b}$, and $c$ I want to find a discrete combination $\vec{n}$ (i.e. a vector with non-negative integer elements) to $$\mathrm{minimise}\left(\vec{n}\cdot\vec{a}\right)$$ Under ...
0
votes
1answer
31 views

Minimizing an unknown system's output

Let we have an unknown system with two inputs and two outputs. inputs $x=[x_1 x_2]$ and outputs $y=[y_1 y_2 ]$ The system have the following properties $ y_1 = f_1(x_1,x_2)$ ; $y_2 = f_2(x_1,x_2) $ ...
0
votes
2answers
61 views

getting sign of LP solution variables

I have an LP where I'm only interested in the sign of some of the variables of an optimal solution. The value itself does not matter. Currently I'm using cplex to get an optimal solution and take the ...