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)

4
votes
1answer
1k 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
16 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
31 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 : ...
0
votes
0answers
11 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
51 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 ...
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
18 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
18 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
16 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 ...
0
votes
0answers
10 views

Mixed Integer Linear Program (MILP) question

I am trying to solve an MILP problem. I was wondering if Branch and Cut/Branch and Bound methods find optimal solution or not? Isn't the complexity exponential? Are there heuristic solvers available? ...
0
votes
2answers
31 views

Quite rare kind of proof of convexity for a quadratic function!

Excuse me all of you in advance. I got this problem as an assignment but I am not really good doing proofs! If $f(x)=\frac12x^TQx+b^Tx+a$ is quadratic in $n$ variables, where $Q$ is symmetric. Show ...
0
votes
2answers
857 views

Optimal Basic Feasible Solutions

In linear programming, is it true that you can only have at most 2 optimal basic feasible solutions? If so, why?
1
vote
1answer
23 views

Least sum of products of powers

Numbers from the set $\{2^1, 2^2, ..., 2^{10}\}$ are somehow permuted and paired with numbers from the set $\{3^1, 3^2, ..., 3^{10}\}$. Numbers in each pair are multiplied and the products are summed. ...
1
vote
0answers
16 views

Determine min and max of the following expressions

Let $a_1,\; ...\;, a_n$ and $b_1,\; ...\;, b_n\in \mathbb R$ be positive real numbers. Find $$ max \;(a_1x_1 + a_2x_2 + ... + a_nx_n) $$ and $$ min \;(a_1x_1 + a_2x_2 + ... + a_nx_n) $$ over $x_1, ...
0
votes
1answer
25 views

What is the approach to solve simple constrained optimization when first order condition $\nabla f = 0$ yields solution outside of domain

I wish to solve the problem min $ f(x_1, x_2) = x_1^2 - x_1 + x_2 + x_1x_2$ subj $x_1\ge 0, x_2 \ge 0$ We find $\nabla f = [2x_1 - 1 + x_2, 1+x_1] = 0$ yields $x_1 = -1, x_2 = 3$ which is outside ...
0
votes
2answers
30 views

Traveling salesman problem (TSP): what is the Relation with number of vertices and length of the found route?

I know that there are many algorithms (exact or approximate) which implement the traveling salesman problem. I would like to know the relation between the number of the vertices (i.e., the places to ...
0
votes
1answer
436 views

Dual cone of a L1 norm cone?

I am listening to convex optimization lectures and I hear that dual cone of a $L1$ norm cone is a $L-\infty$ norm cone. Can anybody please explain how? I understand that every point in the dual cone ...
3
votes
2answers
51 views

Finite difference method

I wanted to ask something regarding the finite difference approximation. I used the finite difference to calculate the numerical derivatives of my function. The finite difference is given by the ...
0
votes
0answers
15 views

Optimizing the trace of a matrix product

I have a problem where I have a NxT matrix P (lets just assume full rank for now, where N>>T) and a TxN inclusion matrix S. Each column of S must contain exactly one 1 and the rest 0's i.e. 1_T*S = 1, ...
1
vote
0answers
67 views

The best strategy to increase StackExchange Reputation [closed]

I do not have a lot of background in game theory, but I am curious how would one formally pose the title problem and mathematically describe possible strategies. Are the problems of this type best ...
0
votes
0answers
19 views

Devising a likelihood method for estimating disease prevalence in hunted deer populations

I am attempting to find the maximum likelihood estimate for disease prevalence in trapped mice by using data on the probability of being trapped each year and the number of mice actually trapped that ...
0
votes
0answers
8 views

Find $\min \sum_{1\le i\le n} x_i\mathbf{z}^T\mathbf{A}\mathbf{y}_i +\mathbf{b}^T\mathbf{x} +\cdots$

I have been stuck at this problem for a while :( Given $\mathbf{A}\in\mathbb{S}^{p\times p}, \mathbf{A}\ge 0,\mathbf{A} \text{ symmetric}, \mathbf{b}\in\mathbb{R}^n,\mathbf{c}_i\in\mathbb{R}^p\forall ...
2
votes
0answers
50 views

Assignment problem with multiple types, capacities and costs

I am trying to solve an optimization problem (variation of assignment problem). I'm stuck with how to represent this problem (as an LP or graph based). If it's formulated as a LP, I'm unsure of how to ...
1
vote
2answers
46 views

Max-min of a function on closed, bounded interval using EVT

I'm just having little bit of difficulty with the following question: Find the local maxima and minima of $f : [0, 1] \rightarrow \mathbb{R}$ defined by $$ f(x)=x^4(1-x)^6 $$ So we know the ...
0
votes
1answer
70 views

How to solve the coupled integer programming problem?

I have the following integer linear programming problem: $$\begin{equation*} \begin{aligned} & \underset{x}{\text{maximize}} && \sum_{k=1}^K\sum_{t=1}^Tx_{kt} \\ & \text{subject to} ...
0
votes
1answer
22 views

Is this reducible to a standard optimization problem?

There are $N$ agents who needs to be allocated $K$ discrete resources. There is a bottleneck threshold utility $R$ per agent. The $i$th agent has utility $r_{ij}$ if he is allocated $j$th resource. ...
0
votes
1answer
17 views

Motivated by Level Sets, how can I show that minimizing this functional is equivalent to this PDE?

I would like to show, that minimizing the functional $$F(g)=\alpha\int_\Omega |\nabla g(x)|^2dx+\mu \int_\Omega (g(x)-f(x))^2dx $$ is equivalent to solving the differential euqation $$-\alpha\nabla ...
1
vote
0answers
16 views

Multiple optimal solutions / LP

In the optimal primal simplex tableau, if we have a non-basic variable with a reduced cost of zero, can we say for sure the primal has multiple optimal solutions? Or can the same thing also happen ...
0
votes
2answers
26 views

optimization on two “max” function

Anyone knows how to use lagrange multiplier (or KKT conditions) to minimize an objective function such as $L(\beta,\beta_0)=\sum_{i=1}^n[a_i(1-y_if(x_i))_++b_i(1+y_if(x_i))_+$] where $a_i$, $b_i$ ...
1
vote
0answers
30 views

tangent cone to the set

I'm supposed to solve this problem: Let us consider the set $M=\{(x, \sin{x}):x\in\mathbb{R}\}\cup\{\big(\cos(x)-1,x\big):x\in\mathbb{R}\}$ The question is to find the tangent cone to the set $M$ in ...
1
vote
0answers
19 views

Derivative vector and Hessian for maximization

I'm having some troubles regarding maximization of approximated utility. I want to use the Newton method, but in order to do so I need the derivative vector and the Hessian matrix (I will be ...
0
votes
0answers
26 views

Karush-Kuhn-Tucker conditions for non-linear optimalization

I have the following problem: solve the local conditions (KKT) and find ALL optimal solutions: $$\min f(x,y)$$ subject to $$g(x,y)\le 0$$ $$x\geq0, y\in\mathbb{R}$$ I have some questions to this ...
0
votes
1answer
26 views

Rounding a distribution to minimize loss

This question deals with the problem of choosing cutoff points such that rounding a random variable down to the nearest cutoff point doesn't lose "too much" of its mean. Formally: Let $y$ be a ...
0
votes
0answers
14 views

Saturation Curve

I have a equation which is x/(x+40). I'm trying to find a point indicated in the graph. As you can see i drew 2 lines, one tangent to the region which it saturates, the other were it has max growth. ...