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)

0
votes
2answers
26 views

Maximization problem with constraint: no differentiation

$$\max \ \min[\alpha x_1, \beta x_2, \gamma x_3] \ \ \text{s.t.} \ \lambda_1 x_1 + \lambda_2x_2 + \lambda_3x_3 = c, \\\ \alpha, \beta, \gamma, \lambda_i, c \ \text{are constants}$$ Well, that ...
0
votes
0answers
7 views

Sorting signals to achieve highest possible similarty

I am currently trying to develop an algorithm in Matlab that sorts signals, which I have as columns of a matrix, to achieve the highest possible similarity of the signal with its neighbors. My first ...
4
votes
2answers
200 views

Why do Lagrange Multipliers work?

I know that the Lagrange multiplier method helps us evaluate critical points of $f$ on the closed boundary of the restriction. In other words we solve:$$\nabla f=\lambda \nabla g$$ But why does ...
0
votes
0answers
10 views

Analysis of Optimizatiointechniques: Regret Analysis vs. Direct convergence? [closed]

When it comes to convergence rate analysis of optimization algorithms (like gradient descent and its family), there seems to be to be two main: Direct analysis, i.e. bound on $$ |f(x_t) - f(x^*)| ...
1
vote
1answer
25 views

Which points in the interior of a parallelogram are as far as possible from the corners?

Question 1: Given a parallelogram $P=ABCD$, how does one construct/determine the points $X \in P$ which are as far as possible from the corners? That is, the points $X$ for which $$ ...
0
votes
1answer
977 views

How to describe minimization of L1 norm error using linear programming?

Given a set of $n$ pair points $(x_1, y_1), ..., (x_n, y_n)$ in the plane, I need to find a line $ax + by = c$ that fits the points of the L1 norm error points as closely as possible. I need a linear ...
0
votes
3answers
42 views

ADMM formalization

I found lots of examples of ADMM formalization of equality constraint problems (all with single constraint). I am wondering how to generalize it for multiple constraints with mix of equality and ...
0
votes
1answer
51 views

Algorithms For Large-Scale $\ell_{\infty}$ Minimization

The general problem I want to solve is well studied: $$ \min_x \Vert Ax\Vert_\infty \;\;\; \mathrm{s.t.} \;\;\; Bx=c, $$ which is equivalent to the following linear program: $$ \min_{t,x} \, t ...
0
votes
1answer
22 views

Trace minimization-Revised

The problem is as follows: $\displaystyle\min_{V}$ trace($V^TH^T\Phi HV$)$\\$ s.t. $V^TV=I_d$ in the case when $H$ is not known. When $H$ is known, the solution is given by the eigenvectors ...
1
vote
1answer
35 views

To show that $f(y)$ has only one maximum in $y\in[0,1]$

I have function $$f(y)=\frac{1}{2} y \log \left(\frac{a^2 b \left(\frac{2}{y}-2\right)}{a b \left(\frac{2}{y}-2\right)+a+1}+1\right)$$ where $a,b>0$ and $y\in[0,1]$. I want to show that $f(y)$ ...
0
votes
0answers
30 views

Range of feasibility, feasibility interval, allowable increase and allowable decrease.

Can someone please explain how the values (allowable decrease, allowable increase, for constraints) within the blue box (under "Range of Feasibility") are determined? I understand how they determined ...
0
votes
1answer
19 views

Proving the existence of multiple maxima

Given a function of two variables, say f(x,y), what are some known techniques to prove that it has multiple maxima? I can see via simulation that this is the case, but trying to figure out a formal ...
1
vote
2answers
46 views

Is it convex function?

I have a function and I don't know it is whether convex or non-convex: $$J(c,\alpha)=\int_\Omega ( \alpha c-I(x))^2u \, dx+ \|\alpha\|^2$$ where $0 \le u \le 1$, $I(x): \Omega \to R$, $c$ is constant ...
0
votes
0answers
21 views

joint optimization problem with somewhat symmetric function

I have just brief question that the method that I use to solve optimization problem is legit. I have function $\max_{x,y}F(x,y)$, and first order condition gives me following equation. ...
0
votes
0answers
21 views

Linear Optimization - functions in constraints?

This is a real-world linear optimization problem. The model tries to minimize cost of hiring employees over a two month period, while providing a certain amount of service. Employees have a salary ...
0
votes
1answer
40 views

MATLAB: minimize function using x value from previous iteration

I'm trying to develop an algorithm for a proximal point method defined as: $$ \underset{x \in \rm I\!R^n}{\arg\min} f(x) + \lambda g(x) $$ where f(x) is a convex and coercive function and also ...
1
vote
0answers
28 views

Optimization involving convex-concave function

Let $f(x,y)$ be a function defined on $[0,1]^2$ and define \begin{align} g(a,b) = f\left(\frac{a+b}{2}, \frac{a-b}{2}\right) \end{align} where $a$ and $b$ are such that $\frac{a+b}{2} ...
0
votes
0answers
16 views

Optimization methods to find valleys in a map

I have a map of some size say $1000\times1000$ pixels that is in a equivalent sized array. Instead of searching the map for a global minimum what I'd like to do is find a cluster of connected minimums ...
0
votes
1answer
44 views

solving Non-liner optimization with non-liner constraint using fmincon in Matlab [closed]

I'm trying to solve a non-liner optimization problem with a non-liner constraint by applying fmincon function in matlab. However, I got the following error: "Failure in initial user-supplied nonlinear ...
0
votes
1answer
26 views

How to analysis the global and local maxima of $h(x) = (1-f(x))(1-g(x))$

I want to maximize $h(x) = (1-f(x))(1-g(x))$, where $f(x)=exp(-u(x))$ and $g(x)=exp(-v(x))$ and $u,v \ge 0 $. $h'(x) = -f'(x)(1-g(x))-g'(x)(1-f(x)) = 0$ results to that the points with the ...
0
votes
0answers
19 views

Find $\alpha$ from equation $F(\alpha)=\int \left (\frac {I(x)}{\alpha^TG(x)}-1\right)^2 \, dx+\lambda\|\alpha\|^2$

I have a function such as $$F(\alpha)=\int \left (\frac {I(x)}{\alpha^TG(x)}-1\right)^2 \, dx + \lambda \|\alpha\|^2$$ where $I,\lambda,G$ are given. In which $G(x)$ is a vector; $G=[G_1(x), G_2(x), ...
1
vote
1answer
366 views

Smooth approximation of maximum using softmax?

Look at the Wiki page for Softmax function (section "Smooth approximation of maximum"): https://en.wikipedia.org/wiki/Softmax_function It is saying that the following is a smooth approximation to the ...
4
votes
1answer
2k views

Linear Programming: Three variable graphical solution

A small bank offers three type of loans: housing loans at $8.50$% interest, education loans at $13.75$% interest rates, and loans to senior citizens at $12.25$% interest. Further, it needs to ...
1
vote
0answers
14 views

Non linear programming problem using Kuhn-Tucker method

Solve using Kuhn-Tucker method $ z=x_1^2+x_2^2 $subject to i) $ x_1+x_2\le 4$ ii)$ 2x_1+x_2\le 5$ where $ x_1\ge 0 ,x_2\ge 0$
0
votes
1answer
25 views

How to solve Standard minimization problem of a function

I have a minimization problem here: minimize the cost function C= 12x + 40y +30z subject to x + 2y +2z >= 2 -x - y - 3z >= -1 -x +2y + z >= -2 x >=0 ,y >=0 ,z >=0 So i made the matrix out of ...
0
votes
1answer
91 views

Optimization of $f\left(x\right)=x^{2}\sin x^{3}$

Let $$f\left(x\right)=x^{2}\sin x^{3}$$ Set of critical points consists of isolated points. Set of critical points is compact $f(x)$ attains local extremum at any critical point ...
0
votes
0answers
10 views

If $f_{1}(x)<f_{2}(x)$, is it true that $ \min_B \max_{Bx=0} f_{1}(x)<\min_B \max_{Bx=0} f_{2}(x)$?

One "obvious" question but I hope I can get some explanations... If $f_{1}(x)<f_{2}(x)$, is it true that $ \min_B \max_{Bx=0} f_{1}(x)<\min_B \max_{Bx=0} f_{2}(x)$? $B$ is an arbitrary matrix ...
11
votes
2answers
301 views

Twilight Zelda Guardian Puzzle : Shortest Path (UPDATE: ADDED RULES)

I'm playing a video game right now and in it is a puzzle (see here). There are solutions to solving it (see here) on the Internet, but I'd like to know if this path is the shortest path (least amount ...
0
votes
0answers
15 views

Help required in solving the lagrangian dual?

I'm trying to write the Lagrangian dual to the following problem \begin{align*} (P) \quad \min\;&\text{Trace}(CG)\\ \text{s.t.}\;&G \succcurlyeq 0\\ & G_{i,i}=I_d (i=1,..,M+1)\end{align*} ...
0
votes
2answers
30 views

Find maximum and minimum of funсtion on set

I have the task: find maximum an minimum of $$f(x) = x_1(\pi - x_1)\sin x_2 + x_2 \cos x_1$$ on X where $$X = \{x\in R^2\ |\ x_1\in [0, \pi], x_2 \ge 0\}.$$ First thing i did was system : ...
-3
votes
0answers
11 views

How to get attribute weights from a tradeoff? [closed]

Assume that we are getting oranges and apples from a fruit basket, getting apples is seen more important than oranges, and the outcome of x=(0 apple, 25 oranges) is equally preferred as x=(10 apples,0 ...
0
votes
0answers
10 views

Gradient descent derivativ of max function

I need to minimize the function: Sum over all x != t [ max( 0 , C - f(t) + f(x) ) ]; C = constant So you have a set of x-es and one of them is t. I have computed the derivative of the f ...
0
votes
2answers
49 views

How to compute primal variable based on dual variables and their multipliers

I edited this question based on information I got from comments. Assume we have an optimization problem (primal problem). we solve it's dual using some kind of primal-dual interior point solver. So, ...
6
votes
1answer
71 views

Proving the existence of $b$ such that $\prod_{k=1}^n(1-\cos(a_k-b))=\frac{1}{2^n}$

Let $n>0$ and $a_1,\ldots,a_n\in \mathbb R$. Prove there is some $b$ such that $\prod_{k=1}^n(1-\cos(a_k-b))=\frac{1}{2^n}$ This is motivated by this question Finding a point on the unit ...
-1
votes
1answer
15 views

How can I show that any local minima of a concave function is at extremal point? [closed]

I would like to know some formal proof. I think this is intuitive but I cannot prove it for the general case... Thanks in advance...
0
votes
0answers
18 views

Parallel Algorithm for Donor/Recipient Matching - Graph Matching/Optimization [closed]

This question was cross-posted and answered on Computer Science Stack Exchange. I'm not certain I can accurately describe the problem using my knowledge of discrete math, so pardon any ...
4
votes
4answers
81 views

Minima and maxima of $\left({\frac{\sin 10x}{\sin x}}\right)^2$ on $[0,\pi]$

Find the minima and maxima of $\left({\frac{\sin 10x}{\sin x}}\right)^2$in the interval $\left [ 0,\pi \right ]$. This is a question from BdMO that still haunts me a lot. I would like to find an ...
0
votes
4answers
35 views

How to find maximum value of trig function?

How to find maximum value of this: $$y = 5\sin x - 12\cos x$$ And I am more intrested in solving process, rather than answer. I know the answer. I am familiar with derivatives, not so good, but as I ...
0
votes
0answers
29 views

Convert a nonconvex function to convex function

I have a image $I: \Omega \to \Bbb R$. It is separated into 2 non-overlapping region: $D$ and $\Omega \setminus D$ Each point $x$ in the image $I$, the $\phi$ function is defined as: $$\phi(x)= ...
0
votes
0answers
42 views
0
votes
0answers
17 views

Terminal Condition in Pontryagin Maximization

I'm doing a time dependent maximization problem using Pontryagin. Now the necessary terminal condition for a solution is only sufficient if my terminal function is concave. If my terminal function is ...
5
votes
4answers
99 views

Maximum value of the integral $\int_0^1e^{|t-x|}dt$ for $0 \leq x \leq 1$

Define $$f(x)=\int_0^1e^{|t-x|}dt$$ I have to find the maximum value of $f(x)$ when $0 \leq x \leq 1$. To remove the modulus, I wrote $$f(x)=\int_0^xe^{x-t}dt + \int_x^1e^{t-x}dt$$ ...
0
votes
0answers
15 views

Justifying the “Dual feasibility”, one of the Karush-Kuhn-Tucker conditions

I am having difficulty of interpreting the KKT conditions in a general setting where we have $M$ equality and $N$ inequality constraints defined as: Minimize $f(x)$ subject to $g_i(x) \leq 0 , h_j(x) ...
0
votes
0answers
17 views

Find the signs of elements in a list such that their sum is equal to zero

I have a set $X = \{x_1, x_2, \dots x_N\} \in [0;1]^N$ containing $N$ elements, initially all positive. My goal is to find a vector of signs $S = \{s_1, s_2, \dots s_N\} \in \{-1; 1\}^N$ such that: ...
0
votes
1answer
15 views

Analysis of iterative optimization methods using lyapunov analysis

In analysis of iterative methods, is it possible that we have to use two time-lagged version of the time-varying system to analyze its convergence? (that is, we construct the evolution of x^k, ...
0
votes
2answers
66 views

Finding the minimum value of a function

Find the least value of $f(x)=3^{-x+1} + e^{-x-1}$. I tried to use the maxima/minima concept but it was of no use. Please help.
4
votes
2answers
145 views

Optimization of parameter for recursive Cauchy sequence

I have the following recursive sequence I'm analyzing: $$V_0 = 50, V_1 = (1-10k)V_0,$$ $$V_{n+1} = (1-10k)V_n - 5kV_{n-1}$$ where $k > 0$ is a parameter that I'm investigating by running ...
4
votes
1answer
1k views

Mana Maximization (Hearthstone)

I recently started playing Hearthstone and a statistic / probability question came up my mind. Here's a quick breakdown: The game is a turn-based card game which involves "points" that you can used ...
1
vote
2answers
415 views

Convex Optimization of quadratic function with inequality constraints

How would I solve the following problem? $$\min_{x\in\mathbb{R}^n} x^T A x$$ subject to the constraints $$x_i\geq 1,\,i=1,\dots,n,$$ where A is positive semidefinite and symmetric. Is it possible to ...
1
vote
1answer
39 views

Has extremum or not?

I'm learning calculus and I have to do with functions $x^2\sin(\frac{1}{x})$ where x!=0 and 0 when x=0 and $x^3\sin(\frac{1}{x})$ where x!=0 and 0 when x=0 If I computed this well, both of them have ...